Computing Equilibria in Anonymous Games

Simple item page
dc.creatorDaskalakis, Constantinos
dc.creatorPapadimitriou, Christos
dc.date2007-10-30
dc.date.accessioned2026-07-07T08:39:26Z
dc.date.available2026-07-07T08:39:26Z
dc.descriptionWe 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 O(s^2 L), where s is the number of strategies and L is the Lipschitz constant of the utilities. Finally, we show that there is a PTAS for finding an epsilon
dc.identifierhttps://arxiv.org/abs/0710.5582
dc.identifierhttp://arxiv.org/abs/0710.5582
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/141069
dc.subjectComputer Science and Game Theory
dc.subjectComputational Complexity
dc.subjectDiscrete Mathematics
dc.titleComputing Equilibria in Anonymous Games
dc.typetext

Files

Collections

arXiv