OpenAlex ·
Hardness Amplification for Approximate Nash Equilibrium with Constantly Many Players
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2610.25608
- Original
- Read it at the publisher
- Topics
Abstract
For every fixed integer $k\ge2$ and fixed parameters $δ,\varepsilon\in(0,1)$ and $η\in[0,1)$, we give a deterministic polynomial-time reduction from finding a $δ$-approximate Nash equilibrium ($δ$-ANE) in a $k$-player game $G$ with payoffs in $[0,1]$ to finding an $(\varepsilon,η)$-weak approximate Nash equilibrium (weak ANE) in a game $H$ with $C$ players, where $C$ depends only on $k,δ,\varepsilon,η$, independently of the action-set sizes. The constructed game is symmetric with binary payoffs. The games and strategies are represented by complete payoff tables and probabilities, with rational entries encoded in binary. Consequently, the existence of deterministic polynomial-time weak-ANE algorithms at one fixed pair of parameters $\varepsilon\in(0,1),η\in[0,1)$ for every fixed number of players would give deterministic polynomial-time $δ$-ANE algorithms at every fixed approximation parameter $δ\in(0,1)$ and number of players. Under deterministic PPAD-ETH, combining our reduction with Rubinstein's hardness result (FOCS 2016) for bimatrix games at some fixed approximation parameter $γ_0\in(0,1)$ rules out a deterministic algorithm for $(\varepsilon,η)$-weak ANE with running time $N^{O((\log N)^{1-ξ})}$ for any fixed $ξ\in(0,1)$. This holds for every fixed $\varepsilon\in(0,1)$ and $η\in[0,1)$ at a suitable constant number $C$ of players, where $N$ is the binary encoding length of the constructed game's complete payoff table.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Complexity
When Better Opportunities Backfire: Service Worker Responses to Parallel AI Deployment in Customer Acquisition
Speculative Imbalance Positions by Non-Physical Traders: Impacts on Electricity System Balancing in Great Britain
Stronger artificial intelligence breakthroughs hasten their own exhaustion
Occupational Uniqueness and Wage Growth
Choose your own adventure: How data source selection shapes urban accessibility analyses
Get the few papers worth your time in Computational Complexity every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.