Perturbing Best Responses in Zero-Sum Games
This addresses computational efficiency for game theory practitioners, though it is incremental as it builds on existing algorithms with modifications.
The paper tackles the problem of accelerating convergence to Nash equilibria in zero-sum games by perturbing utilities in best-response algorithms like Double Oracle and Fictitious Play, showing that this reduces iteration counts and can achieve logarithmic expected iterations in some cases.
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.