Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
Combining local search techniques and path following for bimatrix games
Nicola Gatti, Giorgio Patrini, Marco Rocco, Tuomas Sandholm
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).
Keywords:
Pages: 286-295
PS Link:
PDF Link: /papers/12/p286-gatti.pdf
BibTex:
@INPROCEEDINGS{Gatti12,
AUTHOR = "Nicola Gatti and Giorgio Patrini and Marco Rocco and Tuomas Sandholm",
TITLE = "Combining local search techniques and path following for bimatrix games",
BOOKTITLE = "Proceedings of the Twenty-Eighth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-12)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2012",
PAGES = "286--295"
}


hosted by DSL   •   site info   •   help