Combining local search techniques and path following for bimatrix games

Nicola Gatti, Giorgio Patrini, Marco Rocco, Tuomas Sandholm
Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, PMLR R10:284-293, 2012.

Abstract

Computing a Nash equilibrium (NE) is a central task in computer science. An NE is a particularly appropriate solution concept for two-agent settings because coalitional deviations are not an issue. However, even in this case, finding an NE is PPAD-complete. In this paper, we combine path following algorithms with local search techniques to design new algorithms for finding exact and approximate NEs. We show that our algorithms largely outperform the state of the art and that almost all the known benchmark game classes are easily solvable or approximable (except for the GAMUT CovariantGameRand class).

Cite this Paper

BibTeX
@InProceedings{pmlr-vR10-gatti12a, title = {Combining local search techniques and path following for bimatrix games}, author = {Gatti, Nicola and Patrini, Giorgio and Rocco, Marco and Sandholm, Tuomas}, booktitle = {Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence}, pages = {284--293}, year = {2012}, editor = {de Freitas, Nando and Murphy, Kevin}, volume = {R10}, series = {Proceedings of Machine Learning Research}, month = {14--18 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r10/main/assets/gatti12a/gatti12a.pdf}, url = {https://proceedings.mlr.press/r10/gatti12a.html}, abstract = {Computing a Nash equilibrium (NE) is a central task in computer science. An NE is a particularly appropriate solution concept for two-agent settings because coalitional deviations are not an issue. However, even in this case, finding an NE is PPAD-complete. In this paper, we combine path following algorithms with local search techniques to design new algorithms for finding exact and approximate NEs. We show that our algorithms largely outperform the state of the art and that almost all the known benchmark game classes are easily solvable or approximable (except for the GAMUT CovariantGameRand class).}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Combining local search techniques and path following for bimatrix games %A Nicola Gatti %A Giorgio Patrini %A Marco Rocco %A Tuomas Sandholm %B Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2012 %E Nando de Freitas %E Kevin Murphy %F pmlr-vR10-gatti12a %I PMLR %P 284--293 %U https://proceedings.mlr.press/r10/gatti12a.html %V R10 %X Computing a Nash equilibrium (NE) is a central task in computer science. An NE is a particularly appropriate solution concept for two-agent settings because coalitional deviations are not an issue. However, even in this case, finding an NE is PPAD-complete. In this paper, we combine path following algorithms with local search techniques to design new algorithms for finding exact and approximate NEs. We show that our algorithms largely outperform the state of the art and that almost all the known benchmark game classes are easily solvable or approximable (except for the GAMUT CovariantGameRand class). %Z Reissued by PMLR on 04 October 2026.
APA
Gatti, N., Patrini, G., Rocco, M. & Sandholm, T.. (2012). Combining local search techniques and path following for bimatrix games. Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R10:284-293 Available from https://proceedings.mlr.press/r10/gatti12a.html. Reissued by PMLR on 04 October 2026.

Related Material