# Perturbing Best Responses in Zero-Sum Games

arXiv: https://arxiv.org/abs/2511.12523 · HTML: https://mlsanity.com/paper/2511.12523/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 18 references that are in the map.
- First posted on arXiv 16 Nov 2025.

## Builds on (most cited first, 4 of 4)

- [Fast Policy Extragradient Methods for Competitive Games with Entropy Regularization](https://mlsanity.com/paper/2105.15186/) (2021)
- [The Computational Power of Optimization in Online Learning](https://mlsanity.com/paper/1504.02089/) (2015)
- [A Counter-Example to Karlin's Strong Conjecture for Fictitious Play](https://mlsanity.com/paper/1412.4840/) (2014)
- [Policy Space Response Oracles: A Survey](https://mlsanity.com/paper/2403.02227/) (2024)

## Abstract (arXiv)

This paper investigates the impact of perturbations on the best-response-based algorithms approximating Nash equilibria in zero-sum games, namely Double Oracle and Fictitious Play. More precisely, we assume that the oracle computing the best responses perturbs the utilities before selecting the best response. We show that using such an oracle reduces the number of iterations for both algorithms. For some cases, suitable perturbations ensure the expected number of iterations is logarithmic. Although the utility perturbation is computationally demanding as it requires iterating through all pure strategies, we demonstrate that one can efficiently perturb the utilities in games where pure strategies have further inner structure.