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
Version:
Accepted Manuscript

Actions


Access Document


Files:
Publisher copy:
10.1016/j.jcss.2017.07.002

Authors


More by this author
Department:
Oxford, MPLS, Computer Science
Turchetta, S More by this author
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
Pubs id:
pubs:708505
URN:
uri:65b60d93-542d-43c0-ae7c-b00e6ac83076
UUID:
uuid:65b60d93-542d-43c0-ae7c-b00e6ac83076
Local pid:
pubs:708505

Terms of use


Metrics



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

TO TOP