On the Approximation of Nash Equilibria in Sparse Win-Lose Games

AAAI 2018 pp. 1154-1160

doi:10.1609/AAAI.V32I1.11439 /aaai/2018/liu2018aaai-approximation/

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.

PDF AAAI Semantic Scholar

Cite

Text

Liu and Sheng. "On the Approximation of Nash Equilibria in Sparse Win-Lose Games." AAAI Conference on Artificial Intelligence, 2018. doi:10.1609/AAAI.V32I1.11439

Markdown

[Liu and Sheng. "On the Approximation of Nash Equilibria in Sparse Win-Lose Games." AAAI Conference on Artificial Intelligence, 2018.](https://mlanthology.org/aaai/2018/liu2018aaai-approximation/) doi:10.1609/AAAI.V32I1.11439

BibTeX

@inproceedings{liu2018aaai-approximation,
  title     = {{On the Approximation of Nash Equilibria in Sparse Win-Lose Games}},
  author    = {Liu, Zhengyang and Sheng, Ying},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2018},
  pages     = {1154-1160},
  doi       = {10.1609/AAAI.V32I1.11439},
  url       = {https://mlanthology.org/aaai/2018/liu2018aaai-approximation/}
}