Teamwork Makes The Von Neumann Work: Two Team Zero Sum Games
summary
Claim: computing an approximate Nash equilibrium in two-team zero-sum games is CLS-hard, standard first-order discretizations like gradient descent, extragradient and optimistic updates empirically cycle around mixed equilibria, and adding realistic noise breaks many convergence fixes. The proposed remedy is a new feedback-control wash-out discretization (inspired by aviation Dutch-roll filters) that the authors discretize and prove sufficient convergence conditions for on some instances; experiments and complexity reductions show the method succeeds where classical schemes fail.
AI-written summary · about
chapters (11)
- 0:00Start
- 2:58Smoothed Complexity Analysis
- 3:27Continuous Optimization without gradients
- 3:52Real World Optimization Challenges
- 4:44Min-Max Optimization in Machine Learning
- 5:34Multi-Agent Online Equilibrium Learning
- 7:30Teamwork makes von Neumann work: Min-Max optimization in Two-Team Zero-Sum Games
- 8:03Team Games
- 9:02Team of Agents & Reinforcement Learning
- 9:24The Proposed Method - High Level View
- 11:40Hardness of Two-Team Zero-Sum Games
related talks
06mDecoding the Maze: New Frontiers in Achieving Nash Equilibrium in AI Architectures
31mLearning in Games with Best-Response Oracles
25mReal Algebraic Geometry in Computational Game Theory
33mKarp Plays a Game
22mOpponent Indifference in Rating Systems: A Theoretical Case for Sonas
48mInformation Collection Through Strategic Agents
19mTime To Resolve
11mGames People Play