Perturbing Best Responses in Zero-Sum Games
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915621116051456 |
|---|---|
| author | Dziwoki, Adam Horcik, Rostislav |
| author_facet | Dziwoki, Adam Horcik, Rostislav |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_12523 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Perturbing Best Responses in Zero-Sum Games Dziwoki, Adam Horcik, Rostislav Computer Science and Game Theory Artificial Intelligence 91A10 (Primary) 91A05 (Secondary) 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. |
| title | Perturbing Best Responses in Zero-Sum Games |
| topic | Computer Science and Game Theory Artificial Intelligence 91A10 (Primary) 91A05 (Secondary) |
| url | https://arxiv.org/abs/2511.12523 |