ML Anthology

Equilibrium Finding in Normal-Form Games via Greedy Regret Minimization

Hugh Zhang, Adam Lerer, Noam Brown
AAAI 2022 pp. 9484-9492
doi:10.1609/AAAI.V36I9.21181 /aaai/2022/zhang2022aaai-equilibrium/

Abstract

We extend the classic regret minimization framework for approximating equilibria in normal-form games by greedily weighing iterates based on regrets observed at runtime. Theoretically, our method retains all previous convergence rate guarantees. Empirically, experiments on large randomly generated games and normal-form subgames of the AI benchmark Diplomacy show that greedy weights outperforms previous methods whenever sampling is used, sometimes by several orders of magnitude.

PDF AAAI Semantic Scholar

Cite

Text

Zhang et al. "Equilibrium Finding in Normal-Form Games via Greedy Regret Minimization." AAAI Conference on Artificial Intelligence, 2022. doi:10.1609/AAAI.V36I9.21181

Markdown

[Zhang et al. "Equilibrium Finding in Normal-Form Games via Greedy Regret Minimization." AAAI Conference on Artificial Intelligence, 2022.](https://mlanthology.org/aaai/2022/zhang2022aaai-equilibrium/) doi:10.1609/AAAI.V36I9.21181

BibTeX

@inproceedings{zhang2022aaai-equilibrium,
  title     = {{Equilibrium Finding in Normal-Form Games via Greedy Regret Minimization}},
  author    = {Zhang, Hugh and Lerer, Adam and Brown, Noam},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2022},
  pages     = {9484-9492},
  doi       = {10.1609/AAAI.V36I9.21181},
  url       = {https://mlanthology.org/aaai/2022/zhang2022aaai-equilibrium/}
}