loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07)
Computing Equilibria in Anonymous Games
Providence, Rhode Island
October 21-October 23
ISBN: 0-7695-3010-9
We present efficient approximation algorithms for finding Nash equilibria in anonymous games, that is, games in which the players utilities, though different, do not differentiate between other players. Our results pertain to such games with many players but few strategies. We show that any such game has an approximate pure Nash equilibrium, computable in polynomial time, with approximation {\rm O}(s^2 \lambda ), where s is the number of strategies and \lambda is the Lipschitz constant of the utilities. Finally, we show that there is a PTAS for finding an \in - approximate Nash equilibrium when the number of strategies is two.
Citation:
Constantinos Daskalakis, Christos Papadimitriou, "Computing Equilibria in Anonymous Games," focs, pp.83-93, 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), 2007
Usage of this product signifies your acceptance of the Terms of Use.