摘要
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.
| 源语言 | 英语 |
|---|---|
| 主期刊名 | 32nd AAAI Conference on Artificial Intelligence, AAAI 2018 |
| 出版商 | AAAI press |
| 页 | 1154-1160 |
| 页数 | 7 |
| ISBN（电子版） | 9781577358008 |
| 出版状态 | 已出版 - 2018 |
| 已对外发布 | 是 |
| 活动 | 32nd AAAI Conference on Artificial Intelligence, AAAI 2018 - New Orleans, 美国 期限: 2 2月 2018 → 7 2月 2018 |
出版系列
| 姓名 | 32nd AAAI Conference on Artificial Intelligence, AAAI 2018 |
|---|
会议
| 会议 | 32nd AAAI Conference on Artificial Intelligence, AAAI 2018 |
|---|---|
| 国家/地区 | 美国 |
| 市 | New Orleans |
| 时期 | 2/02/18 → 7/02/18 |
指纹
探究 'On the approximation of nash equilibria in sparse win-lose games' 的科研主题。它们共同构成独一无二的指纹。引用此
Liu, Z., & Sheng, Y. (2018). On the approximation of nash equilibria in sparse win-lose games. 在 32nd AAAI Conference on Artificial Intelligence, AAAI 2018 (页码 1154-1160). (32nd AAAI Conference on Artificial Intelligence, AAAI 2018). AAAI press.