Name
Abstract | ||
|---|---|---|
In an $$\\epsilon $$∈-Nash equilibrium, a player can gain at most $$\\epsilon $$∈ by unilaterally changing his behavior. For two-player (bimatrix) games with payoffs in [0, 1], the best-known $$\\epsilon $$∈ achievable in polynomial time is 0.3393 (Tsaknakis and Spirakis in Internet Math 5(4):365---382, 2008). In general, for n-player games an $$\\epsilon $$∈-Nash equilibrium can be computed in polynomial time for an $$\\epsilon $$∈ that is an increasing function of n but does not depend on the number of strategies of the players. For three-player and four-player games the corresponding values of $$\\epsilon $$∈ are 0.6022 and 0.7153, respectively. Polymatrix games are a restriction of general n-player games where a player's payoff is the sum of payoffs from a number of bimatrix games. There exists a very small but constant $$\\epsilon $$∈ such that computing an $$\\epsilon $$∈-Nash equilibrium of a polymatrix game is $$\\mathtt {PPAD}$$PPAD-hard. Our main result is that a $$(0.5+\\delta )$$(0.5+ź)-Nash equilibrium of an n-player polymatrix game can be computed in time polynomial in the input size and $$\\frac{1}{\\delta }$$1ź. Inspired by the algorithm of Tsaknakis and Spirakis [28], our algorithm uses gradient descent style approach on the maximum regret of the players. We also show that this algorithm can be applied to efficiently find a $$(0.5+\\delta )$$(0.5+ź)-Nash equilibrium in a two-player Bayesian game. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/s00453-015-0078-7 | Algorithmica |
Keywords | DocType | Volume |
Approximate Nash equilibria,Gradient descent,Polymatrix games,Bayesian games | Journal | 77 |
Issue | ISSN | Citations |
2 | 0178-4617 | 2 |
PageRank | References | Authors |
0.38 | 21 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Argyrios Deligkas | 1 | 19 | 7.43 |
| John Fearnley | 2 | 8 | 1.15 |
| Rahul Savani | 3 | 243 | 30.09 |
| Paul G. Spirakis | 4 | 2 | 0.72 |