Name
Abstract | ||
|---|---|---|
The Nash equilibrium is an important benchmark for behaviour in systems of strategic autonomous agents. Polymatrix games are a succinct and expressive representation of multiplayer games that model pairwise interactions between players. The empirical performance of algorithms to solve these games has received little attention, despite their wide-ranging applications. In this paper we carry out a comprehensive empirical study of two prominent algorithms for computing a sample equilibrium in these games, Lemke's algorithm that computes an exact equilibrium, and a gradient descent method that computes an approximate equilibrium. Our study covers games arising from a number of interesting applications. We find that Lemke's algorithm can compute exact equilibria in relatively large games in a reasonable amount of time. If we are willing to accept (high-quality) approximate equilibria, then we can deal with much larger games using the descent method. We also report on which games are most challenging for each of the algorithms. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.5555/2936924.2936955 | AAMAS |
Keywords | DocType | Volume |
Game Theory,Nash Equilibrium,Approximate Equilibria,Polymatrix Games,Auctions,Bayesian Two-Player Games,Lemke's Algorithm,Gradient Descent | Conference | abs/1602.06865 |
ISBN | Citations | PageRank |
978-1-4503-4239-1 | 2 | 0.37 |
References | Authors | |
19 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Argyrios Deligkas | 1 | 19 | 7.43 |
| John Fearnley | 2 | 134 | 17.49 |
| Tobenna Peter Igwe | 3 | 6 | 0.83 |
| Rahul Savani | 4 | 243 | 30.09 |