Abstract
We show that the problem of finding an approximate Nash equilibrium with a polynomial precision is PPAD-hard even for two-player sparse win-lose games (i.e., games with {0, 1}-entries such that each row and column of the two n×n payoff matrices have at most O(log n) many ones). The proof is mainly based on a new class of prototype games called Chasing Games, which we think is of independent interest in understanding the complexity of Nash equilibrium.
| Original language | English |
|---|---|
| Title of host publication | 32nd AAAI Conference on Artificial Intelligence, AAAI 2018 |
| Publisher | AAAI press |
| Pages | 1154-1160 |
| Number of pages | 7 |
| ISBN (Electronic) | 9781577358008 |
| Publication status | Published - 2018 |
| Externally published | Yes |
| Event | 32nd AAAI Conference on Artificial Intelligence, AAAI 2018 - New Orleans, United States Duration: 2 Feb 2018 → 7 Feb 2018 |
Publication series
| Name | 32nd AAAI Conference on Artificial Intelligence, AAAI 2018 |
|---|
Conference
| Conference | 32nd AAAI Conference on Artificial Intelligence, AAAI 2018 |
|---|---|
| Country/Territory | United States |
| City | New Orleans |
| Period | 2/02/18 → 7/02/18 |
Fingerprint
Dive into the research topics of 'On the approximation of nash equilibria in sparse win-lose games'. Together they form a unique fingerprint.Cite this
Liu, Z., & Sheng, Y. (2018). On the approximation of nash equilibria in sparse win-lose games. In 32nd AAAI Conference on Artificial Intelligence, AAAI 2018 (pp. 1154-1160). (32nd AAAI Conference on Artificial Intelligence, AAAI 2018). AAAI press.