Sofia Ceppi
ABSTRACT
The computation of a Nash equilibrium in a game is a challenging problem in artificial intelligence. This is because the computational time of the algorithms provided by the literature is, in the worst case, exponential in the size of the game. To deal with this problem, it is common the resort to concepts of approximate equilibrium. In this paper, we follow a different route, presenting, to the best of our knowledge, the first algorithm based on the combination of support enumeration methods and local search techniques to find an exact Nash equilibrium in two-player general-sum games and, in the case no equilibrium is found within a given deadline, to provide an approximate equilibrium. We design some dimensions for our algorithm and we experimentally evaluate them with games that are unsolvable with the algorithms known in the literature within a reasonable time. Our preliminary results are promising, showing that our techniques can allow one to solve hard games in a short time.
- S. Ceppi, N. Gatti, and N. Basilico. Computing Bayes-Nash equilibria through support enumeration methods in Bayesian two-player strategic-form games. In IAT, pages 541--548, Milan, Italy, 2009. Google Scholar
Digital Library
- C. Daskalakis, P. Goldberg, and C. Papadimitriou. The complexity of computing a Nash equilibrium. In STOC, pages 71--78, Seattle, USA, 2006. Google ScholarDigital Library
- D. Fudenberg and J. Tirole. Game Theory. The MIT Press, Cambridge, USA, 1991.Google Scholar
- C. Lemke and J. Howson. Equilibrium points of bimatrix games. SIAM J APPL MATH, 12(2):413--423, 1964.Google ScholarCross Ref
- W. Michiels, E. Aarts, and J. Korst. Theoretical Aspects of Local Search. Springer, Berlin, Germay, 2007. Google ScholarDigital Library
- E. Nudelman, J. Wortman, K. Leyton-Brown, and Y. Shoham. Run the GAMUT: A comprehensive approach to evaluating game-theoretic algorithms. In AAMAS, pages 880--887, New York, USA, 2004. Google ScholarDigital Library
- R. Porter, E. Nudelman, and Y. Shoham. Simple search methods for finding a Nash equilibrium. In AAAI, pages 664--669, 2004. Google ScholarDigital Library
- T. Sandholm, A. Gilpin, and V. Conitzer. Mixed-integer programming methods for finding Nash equilibria. In AAAI, pages 495--501, Pittsburgh, USA, 2005. Google ScholarDigital Library
- Y. Shoham and K. Leyton-Brown. Multiagent Systems: Algorithmic, Game Theoretic and Logical Foundations. Cambridge University Press, Cambridge, USA, 2008. Google ScholarDigital Library
Index Terms
- Local search techniques for computing equilibria in two-player general-sum strategic-form games
Recommendations
Computing Bayes-Nash Equilibria through Support Enumeration Methods in Bayesian Two-Player Strategic-Form Games
WI-IAT '09: Proceedings of the 2009 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology - Volume 02The computation of equilibria in games is a challenging task. The literature studies the problem of finding Nash equilibria with complete-information games in depth, but not enough attention is paid to searching for equilibria in Bayesian games. ...
Computing a self-confirming equilibrium in two-player extensive-form games
AAMAS '11: The 10th International Conference on Autonomous Agents and Multiagent Systems - Volume 3The Nash equilibrium is the most commonly adopted solution concept for non-cooperative interaction situations. However, it underlays on the assumption of common information that is hardly verified in many practical situations. When information is not ...
Comments