Posts

Showing posts from May 24, 2009

Computing Nash Equilibria: journal papers

Daskalakis , Paul Goldberg , and Papadimitriou have been instrumental in settling the complexity of computing the Nash equilibria of the normal form game. Similarly Chen , Deng and Teng have also been coming up with results to settle the complexity. Recently both groups of researchers published journal papers which describe in detail their results in the last few years: JACM paper and SIAM Journal of Computing .

Secretary Problems

The classical secretary problem involves n secretary job applicants who can be ranked by a total order. The applicants are interviewed one by one in some random order. After each interview, the applicant is accepted or rejected. The decision is based only on the relative ranks of the applicants interviewed so far. The game has payoff 1 if the best applicant is selected and 0 otherwise. The solution is to interview the first n/e candidates and then hire the first that is better than the first n/e candidates. For large enough n, the probability of success is 1/ e. Today, Nicholas Georgiou gave an interesting talk where a general partial order on candidates is considered instead of a linear order. He presented a strategy where the probability of success is 1/4. Check out the paper .

Games zoo

Classes and examples of well known games: link .

Secret of Googlenomics

Wired Magazine covers the economic theory begind Google's success. Here is the link . (Hat tip to Noam Nisan ) For more on the same topic, check out Hal Varian's (Google's chief economist) talks: 1 , 2.

Computing Nash Equilibria

A talk by Constantinos Daskalakis on computing approximate Nash equilibria. The talk also presents a PTAS for Nash equilibria for anonymous games (where a player is oblivious to the identities of the other players. )

Approximate Mechanism Design Without Money

At AAMAS 2009, Ariel Procaccia gave a talk on "Approximate Mechanism Design Without Money" where he discussed mechanisms in the the standard facility location setting with the condition that there are no side payments and optimality of social welfare is traded (via approximation) for strategy proof (group or individual) mechanisms. The talk is based on an EC paper with the same title. It will be interesting to find other well-motivated settings where similar tools can get such results. Check out the paper from here .

Mechanism Design and Game Theory Talks

Talks by Anna Karlin Noam Nisan Rahul Jain Stefano Leonardi Amin Saberi (on Ad Auctions) Nicole Immorlica Mirrokni http://www.researchchannel.org http://videolectures.net