2021/10/26 by Aadesh Salecha, Salecha, Aadesh
Computer Science · Decision Sciences · Social Sciences · #Artificial Intelligence in Games #Computational Complexity (cs.CC) #Computer Science and Game Theory (cs.GT) #Evolutionary Game Theory and Cooperation #Experimental Behavioral Economics Studies #FOS: Computer and information sciences #Game Theory and Applications
paper · pdf · doi:10.48550/arxiv.2110.13563
openalex publication_date 2021/10/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The framework outlined in [arXiv:2010.13024] provides an approximation\nalgorithm for computing Nash equilibria of normal form games. Since NASH is a\nwell-known PPAD-complete problem, this framework has potential applications to\nother PPAD problems. The correctness of this framework has been empirically\nvalidated on 4 well-studied 2x2 games: Prisoner's Dilemma, Stag Hunt, Battle,\nand Chicken. In this paper, we provide the asymptotic time-complexities for\nthese methods and in particular, verify that for 2x2 games the worst-case\ncomplexity is linear in the number of actions an agent can choose from.\n