Simple strategies for large zero-sum games with applications to complexity theory

DOI10.1145/195058.195447zbMath1345.68175arXivcs/0205035OpenAlexW3102712431MaRDI QIDQ2817668

Richard J. Lipton, Neal E. Young

Publication date: 1 September 2016

Published in: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/cs/0205035

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05) Applications of game theory (91A80) Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

On incremental approximate saddle-point computation in zero-sum matrix games ⋮ New Limits to Classical and Quantum Instance Compression ⋮ The query complexity of correlated equilibria ⋮ Computing sparse approximations deterministically ⋮ A sublinear-time randomized approximation algorithm for matrix games ⋮ Resolving Braess's paradox in random networks ⋮ On the Number of Iterations for Dantzig--Wolfe Optimization and Packing-Covering Approximation Algorithms ⋮ On the hardness of network design for bottleneck routing games ⋮ Complexity limitations on one-turn quantum refereed games ⋮ A remark on pseudo proof systems and hard instances of the satisfiability problem ⋮ Efficient methods for selfish network design ⋮ Patience of matrix games ⋮ Arthur and Merlin as oracles ⋮ Unnamed Item ⋮ Randomized sampling for large zero-sum games ⋮ Feasibly constructive proofs of succinct weak circuit lower bounds ⋮ Arthur and Merlin as Oracles ⋮ A note on approximate Nash equilibria ⋮ Hardness magnification near state-of-the-art lower bounds