Journal article
Query complexity of approximate equilibria in anonymous games
- Abstract:
- We study the computation of Nash equilibria of anonymous games, via algorithms that use adaptive queries to a game’s payoff function. We show that exact equilibria cannot be found via query-efficient algorithms, and exhibit a two-strategy, 3-player anonymous game whose exact equilibria require irrational numbers. We obtain positive results for known sub-classes of anonymous games. Our main result is a new randomized query-efficient algorithm for approximate equilibria of two-strategy anonymous games that improves on the running time of previous algorithms. It is the first to obtain an inverse polynomial approximation in poly-time, and yields an efficient polynomial-time approximation scheme.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 405.6KB, Terms of use)
-
- Publisher copy:
- 10.1016/j.jcss.2017.07.002
Authors
+ Engineering and Physical Sciences Research Council
More from this funder
- Funding agency for:
- Goldberg, P
- Grant:
- EP/K01000X/1
- Publisher:
- Elsevier
- Journal:
- Journal of Computer and System Sciences More from this journal
- Volume:
- 90
- Pages:
- 80-98
- Publication date:
- 2017-07-29
- Acceptance date:
- 2017-07-19
- DOI:
- ISSN:
-
0022-0000
- Keywords:
- Pubs id:
-
pubs:708505
- UUID:
-
uuid:65b60d93-542d-43c0-ae7c-b00e6ac83076
- Local pid:
-
pubs:708505
- Source identifiers:
-
708505
- Deposit date:
-
2017-07-19
- ARK identifier:
Terms of use
- Copyright holder:
- Elsevier Inc
- Copyright date:
- 2017
- Notes:
- Copyright © 2017 Elsevier Inc. This is the accepted manuscript version of the article. The final version is available online from Elsevier at: https://doi.org/10.1016/j.jcss.2017.07.002
If you are the owner of this record, you can report an update to it here: Report update to this record