Article Preview
Top1. Introduction
Game Theory (Von Neumann and7 Morgenstern, 1944) is a branch of applied mathematics and economics that studies situations (games) where self-interested interacting players act for maximizing their returns; therefore, the return of each player depends on his behaviour and on the behaviours of the other players. Game Theory, which plays an important role in the social and political sciences, has recently drawn attention in new academic 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 of a game in which any cooperation among the players must be self-enforcing (non-cooperative game) is represented by the Nash equilibrium. In particular, a Nash equilibrium is a set of strategies, one for each player of the game, such that no player can benefit by changing his strategy unilaterally, i.e. while the other players keep their strategies unchanged (Nash, 1951). The problem of computing Nash equilibria in non-cooperative games is considered one of the most important open problem in Complexity Theory (Papadimitriou, 2001). Daskalakis, Goldbergy, and Papadimitriou (2005), showed that the problem of computing a Nash equilibrium in a game with four or more players is complete for the complexity class PPAD-Polynomial Parity Argument Directed version (Papadimitriou, 1991), moreover, Chen and Deng extended this result for 2-player games (Chen & Deng, 2005). However, even in the two players case, the best algorithm known has an exponential worst-case running time (Savani & von Stengel, 2004); furthermore, if the computation of equilibria with simple additional properties is required, the problem immediately becomes NP-hard (Bonifaci, Di Iorio, & Laura, 2005; Conitzer & Sandholm, 2003; Gilboa & Zemel, 1989; Gottlob, Greco, & Scarcello, 2003).
Motivated by these results, recent studies have dealt with the problem of efficiently computing Nash equilibria by exploiting approaches based on the concepts of learning and evolution (Fudenberg & Levine, 1998; Maynard Smith, 1982). In these approaches the Nash equilibria of a game are not statically computed but are the result of the evolution of a system composed by agents playing the game. In particular, each agent after different rounds will learn to play a strategy that, under the hypothesis of agent’s rationality, will be one of the Nash equilibria of the game (Benaim & Hirsch, 1999; Carmel & Markovitch, 1996).
This article presents SALENE, a Multi-Agent System (MAS) for computing Nash equilibria in non-cooperative games, which is based on the above mentioned concepts. In particular, given a static non cooperative game described in its normal form, the agents of the system will play the static game k times; after each match each agent will decide which strategy to play in the next match on the basis of his beliefs about the strategies that the other agents are adopting. More specifically, two possible approaches are introduced and experimented: (i) Myopic best response; (ii) Myopic smoothed best response. In both approaches each agent assumes that his beliefs about the other players’ strategies are correct and he plays a strategy that is the best or a smoothed best response to his beliefs depending on which of the two approaches the agent is adopting. By increasing k the agents should converge in playing one of the Nash equilibria of the game. The papers represents an extension of Garro (2008) in which only the Myopic best response approach was introduced and experimented. The Myopic smoothed best response approach introduced in this paper allows to improve the convergence properties of the proposed agent-based solution for efficiently computing Nash equilibria in non-cooperative games.