Local Search Methods for Finding a Nash Equilibrium in Two-Player Games

Sofia Ceppi, Nicola Gatti, G. Patrini, Marco Rocco

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The computation of a Nash equilibrium of 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. In this paper, we present, to the best of our knowledge, the first anytime algorithm based on the combination of support enumeration methods and local search techniques to find a Nash equilibrium in two-player general-sum games. The algorithm searches for a Nash equilibrium and, if it is stopped before it has found an equilibrium, it returns the best approximate equilibrium found so far. We design some dimensions for our algorithm and we experimentally evaluate them. Our algorithm solves with high probability games that are unsolvable with the algorithms known in the literature within a reasonable time and provides good anytime performance.
Original languageEnglish
Title of host publicationWeb Intelligence and Intelligent Agent Technology (WI-IAT), 2010 IEEE/WIC/ACM International Conference on
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages335-342
Number of pages8
Volume2
ISBN (Electronic)978-1-4244-8482-9
ISBN (Print)978-0-7695-4191-4
DOIs
Publication statusPublished - 1 Aug 2010

Keywords

  • artificial intelligence
  • game theory
  • search problems
  • Nash equilibrium
  • local search methods
  • support enumeration methods
  • two-player general-sum games
  • Approximation algorithms
  • Games
  • Joints
  • Optimization
  • Search problems
  • Silicon
  • Algorithmic game theory
  • local search techniques

Fingerprint Dive into the research topics of 'Local Search Methods for Finding a Nash Equilibrium in Two-Player Games'. Together they form a unique fingerprint.

Cite this