Published June 2014
| public
Book Section - Chapter
Query Complexity of Approximate Nash Equilibria
- Creators
- Babichenko, Yakov
Abstract
We study the query complexity of approximate notions of Nash equilibrium in games with a large number of players n and a constant number of actions m. Our main result states that even for constant ε, the query complexity of an ε-well-supported Nash equilibrium is exponential in n.
Additional Information
© 2014 ACM. A full version of this paper is available at arxiv.org/abs/1306.6686 The author wishes to thank Noam Nisan, Sergiu Hart, Paul Goldberg, and Yishay Mansour for useful discussions and comments. The author gratefully acknowledges support from a Walter S. Baer and Jeri Weiss fellowship, from NSF grant CCF-1101470, and from the Powell Foundation.Additional details
- Eprint ID
- 66449
- Resolver ID
- CaltechAUTHORS:20160425-105719545
- Walter S. Baer and Jeri Weiss fellowship
- CCF-1101470
- NSF
- Charles Lee Powell Foundation
- Created
-
2020-03-09Created from EPrint's datestamp field
- Updated
-
2021-11-10Created from EPrint's last_modified field