Computing Nash Equilibria in Non-Cooperative Games: an agent-based approach

Game Theory has recently drawn attention in new fields which go from algorithmic mechanism design to cybernetics. However, a fundamental problem to solve for effectively applying Game Theory in real word applications is the definition of well-founded solution concepts of a game and the design of efficient algorithms for their computation. A widely accepted solution concept for games in which any cooperation among the players must be self-enforcing (non-cooperative games) is represented by the Nash equilibrium. However, even in the two players case, the best algorithm known for computing Nash equilibria has an exponential worst-case running time; furthermore, if the computation of equilibria with simple additional properties is required, theproblem becomes NP-hard. The paper aims to provide a solution for efficiently computing the Nash equilibriaof a game as the result of the evolution of a system composed by interacting agents playing the game.