Journal article icon

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

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
  • (Accepted manuscript, pdf, 405.6KB)
Publisher copy:
10.1016/j.jcss.2017.07.002

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
More from this funder
Funding agency for:
Goldberg, P
Grant:
EP/K01000X/1
Publisher:
Elsevier Publisher's website
Journal:
Journal of Computer and System Sciences Journal website
Volume:
90
Pages:
80-98
Publication date:
2017-07-29
Acceptance date:
2017-07-19
DOI:
ISSN:
0022-0000
Source identifiers:
708505
Keywords:
Pubs id:
pubs:708505
UUID:
uuid:65b60d93-542d-43c0-ae7c-b00e6ac83076
Local pid:
pubs:708505
Deposit date:
2017-07-19

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP