Local search techniques for computing equilibria in two-player general-sum strategic-form games

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.

• Publication year

  2010

• Venue

  Adaptive Agents and Multi-Agent Systems

• Publication date

  2010-05-10

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/1838206.1838436
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The complexity of computing a Nash equilibrium

  2009cited by this paper
• Computing Bayes-Nash Equilibria through Support Enumeration Methods in Bayesian Two-Player Strategic-Form Games

  2009cited by this paper
• Multiagent Systems: Introduction to Noncooperative Game Theory: Games in Normal Form

  2008cited by this paper
• Theoretical Aspects of Local Search (Monographs in Theoretical Computer Science. An EATCS Series)

  2007cited by this paper
• Theoretical aspects of local search

  2006cited by this paper
• Mixed-Integer Programming Methods for Finding Nash Equilibria

  2005influential reference
• Simple search methods for finding a Nash equilibrium

  2004cited by this paper
• Run the GAMUT: a comprehensive approach to evaluating game-theoretic algorithms

  2004cited by this paper
• Game theory (3. pr.)

  1991cited by this paper
• Equilibrium Points of Bimatrix Games

  1964cited by this paper

• Personality-Based Representations of Imperfect-Recall Games

  2019cites this paper
• Computing Optimal Ex Ante Correlated Equilibria in Two-Player Sequential Games

  2019cites this paper
• Adaptation of ant supercolony behavior to solve route assignment problem in integers

  2018cites this paper
• On the Verification and Computation of Strong Nash Equilibrium

  2017cites this paper
• Using representative strategies for finding nash equilibria

  2013cites this paper
• On the verification and computation of strong nash equilibrium

  2013cites this paper
• Game theoretical solution concepts for learning agents with extensive-form games (Extended Abstract)

  2012cites this paper
• New results on the verification of Nash refinements for extensive-form games

  2012cites this paper
• Smoothed analysis in Nash equilibria and the Price of Anarchy

  2012cites this paper
• Finding a Nash Equilibrium by Asynchronous Backtracking

  2012cites this paper
• Combining local search techniques and path following for bimatrix games

  2012cites this paper
• An efficient algorithm for nonlinear integer programming

  2011cites this paper
• Local Search Techniques for Nash Equilibrium Computation with Bimatrix Games

  2011cites this paper
• Computing an Extensive-Form Perfect Equilibrium in Two-Player Games

  2011cites this paper