Conference item icon

Conference item

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

Actions


Access Document


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

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
Publisher:
Springer, Berlin, Heidelberg Publisher's website
Volume:
9928
Pages:
3-14
Series:
Lecture Notes in Computer Science
Host title:
International Symposium on Algorithmic Game Theory: SAGT 2016: Algorithmic Game Theory
Publication date:
2016-01-01
Acceptance date:
2016-07-01
DOI:
ISSN:
0302-9743
Source identifiers:
634636
ISBN:
9783662533536
Pubs id:
pubs:634636
UUID:
uuid:0a1744a2-6139-4c87-a408-5452f764dcc8
Local pid:
pubs:634636
Deposit date:
2016-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