On the Approximation of Nash Equilibria in Sparse Win-Lose Games
Authors: Zhengyang Liu, Ying Sheng
AAAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. |
| Researcher Affiliation | Academia | Zhengyang Liu Shanghai Jiao Tong University lzy5118@sjtu.edu.cn Ying Sheng Columbia University ys2982@columbia.edu |
| Pseudocode | Yes | Figure 1: Construction of Gadget game (M[T], N[T]) , where T = (G, v1, v2, v3, v, c, w) |
| Open Source Code | No | The paper does not mention any open-source code release, specific repository links, or statements about code availability. |
| Open Datasets | No | This paper is theoretical and does not describe experiments using any datasets, therefore no dataset availability information is provided. |
| Dataset Splits | No | This paper focuses on theoretical proofs and does not describe any experiments that would require training, validation, or test dataset splits. |
| Hardware Specification | No | This paper is purely theoretical and does not include details on hardware used for experiments as no experiments were conducted. |
| Software Dependencies | No | This paper focuses on theoretical contributions and does not mention any specific software dependencies or their version numbers for experimental setup. |
| Experiment Setup | No | This is a theoretical paper providing mathematical proofs and reductions; it does not describe any experimental setup or hyperparameters. |