Metraipolis › archive › dc_fdf949ba614e

Algorithmic Asymmetry in Zero-Sum Games: Unilateral Recovery of Fast Convergence Against a Slow Opponent — arXiv:2608.09780

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.09780
License (as archived)
CC0-1.0
Archived
2026-10-19T08:55:49.715Z
SHA-256 of the archived text
bb03e773dc0e085cc28c12da3b928f78808d7f6aab19be6d99bc36f4c06858a5
Stable URL of this page
https://metraipolis.com/documento/dc_fdf949ba614e

How to cite

Algorithmic Asymmetry in Zero-Sum Games: Unilateral Recovery of Fast Convergence Against a Slow Opponent — arXiv:2608.09780 — arXiv (en), https://arxiv.org/abs/2608.09780 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_fdf949ba614e (Metraipolis archive dc_fdf949ba614e, sha256 bb03e773dc0e085cc28c12da3b928f78808d7f6aab19be6d99bc36f4c06858a5)
BibTeX
@misc{dcfdf949ba614e,
  title = {Algorithmic Asymmetry in Zero-Sum Games: Unilateral Recovery of Fast Convergence Against a Slow Opponent — arXiv:2608.09780},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.09780},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_fdf949ba614e; sha256 bb03e773dc0e085cc28c12da3b928f78808d7f6aab19be6d99bc36f4c06858a5},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.09780. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Learning dynamics in zero-sum games are typically analyzed under algorithmic symmetry: both agents use the same update rule, or methods from a common algorithmic family. This is at odds with the nature of zero-sum games; competing agents need not coordinate on algorithm selection. This paper studies algorithmic asymmetry in learning dynamics in zero-sum games. In particular, we ask whether fast convergence can be recovered when one agent is fixed to vanilla gradient descent, whose standard regret-based analysis certifies, at best, $O(1/\sqrt{T})$ ergodic convergence. We show that the slow rate is not intrinsic. When one agent uses gradient descent, the opposing agent can use a modified optimistic update, which we call Alternating Optimistic Gradient Descent (AOGD), to make the joint dynamics simulate Alternating Gradient Descent on the even iterates. As a result, the time-average of the asymmetric GD vs.\ AOGD dynamics converges to Nash equilibria at rate $O(1/T)$. Our results show that fast convergence need not require coordinated algorithm selection: one agent can compensate for a slower opponent. More broadly, the paper highlights algorithmic asymmetry as a useful lens for understanding cross-class interactions in multiagent optimization.

Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-08-11 in cs.GT).
Categorie arXiv: Computer Science and Game Theory (cs.GT) ; Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2608.09780 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-19T08:52:22.701Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-08-11?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).