O(1/T) Time-Average Convergence in a Generalization of Multiagent Zero-Sum Games

2021/10/06 by James P. Bailey, Bailey, James P. · 1 citation
Decision Sciences · #Advanced Bandit Algorithms Research #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Game Theory and Applications #Multiagent Systems (cs.MA)

paper · pdf · doi:10.48550/arxiv.2110.02482

openalex publication_date 2021/10/06 · openalex created_date 2021/10/11 · openalex updated_date 2026/07/28

Abstract

We introduce a generalization of zero-sum network multiagent matrix games and prove that alternating gradient descent converges to the set of Nash equilibria at rate O(1/T) for this set of games. Alternating gradient descent obtains this convergence guarantee while using fixed learning rates that are four times larger than the optimistic variant of gradient descent. Experimentally, we show with 97.5% confidence that, on average, these larger learning rates result in time-averaged strategies that are 2.585 times closer to the set of Nash equilibria than optimistic gradient descent.

Cited by

• Characterizing Nash Equilibria in Zero-Sum Games: A Physics-Inspired, Parallelizable Approach with a Linear Number of Gradient Queries

Related

• Fast Convergence of Optimistic Gradient Ascent in Network Zero-Sum Extensive Form Games
• Exponential Convergence of Gradient Methods in Concave Network Zero-sum Games
• Towards convergence to Nash equilibria in two-team zero-sum games
• On the O(1/T) Convergence of Alternating Gradient Descent-Ascent in Bilinear Games
• Convergence of Time-Averaged Mean Field Gradient Descent Dynamics for Continuous Multi-Player Zero-Sum Games