Computing Equilibria in Anonymous Games

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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 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

Keywords

Computer Science and Game Theory, Computational Complexity, Discrete Mathematics

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/141069

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0710.5582
 http://arxiv.org/abs/0710.5582

Collections

arXiv