Conference icon

Conference

Logarithmic query complexity for approximate Nash computation in large games

Abstract:

We investigate the problem of equilibrium computation for “large” n-player games where each player has two pure strategies. Large games have a Lipschitz-type property that no single player’s utility is greatly affected by any other individual player’s actions. In this paper, we assume that a player can change another player’s payoff by at most 1 n by changing her strategy. We study algorithms having query access to the game’s payoff function, aiming to find ε-Nash equilibria. We seek algorith...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Accepted Manuscript

Actions


Access Document


Files:
Publisher copy:
10.1007/978-3-662-53354-3_1

Authors


More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Computer Science
More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Computer Science
Publisher:
Springer, Berlin, Heidelberg Publisher's website
Volume:
9928
Pages:
3-14
Series:
Lecture Notes in Computer Science
Publication date:
2016
DOI:
ISSN:
0302-9743
URN:
uuid:0a1744a2-6139-4c87-a408-5452f764dcc8
Source identifiers:
634636
Local pid:
pubs:634636
ISBN:
978-3-662-53353-6

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