Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
On the Approximation of Nash Equilibria in Sparse Win-Lose Games
Authors: Zhengyang Liu, Ying Sheng
AAAI 2018 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We show that the problem of ο¬nding 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 EMAIL Ying Sheng Columbia University EMAIL |
| 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. |