Abstract
Game Theory (Von Neumann & 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 selfenforcing (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 learning Nash Equilibria in noncooperative games, which is based on the above mentioned concepts.
TopBackground
An n-person strategic game G can be defined as a tuple G = (N; (Ai)i∈N; (ri)i∈N), where N = {1, 2, …, n} is the set of players, Ai is a finite set of actions for player i∈N, and ri: A1 × … × An → ℜ is the payoff function of player i. The set Ai is called also the set of pure strategies of player i. The Cartesian product ×iÎN Ai = A1 × … × An can be denoted by A and r: A → ℜN can denote the vector valued function whose ith component is ri, i.e., r(a) = (r1(a), …, rn(a)), so it is possible to write (N, A, r) for short for (N; (Ai)i∈N; (ri) i∈N).
Key Terms in this Chapter
Game Theory: A branch of applied mathematics and economics that studies situations (games) where self-interested interacting players act for maximizing their returns.
Non-Cooperative Games: A game in which any cooperation among the players must be self-enforcing.
Computational Complexity Theory: A branch of the theory of computation in computer science which studies how the running time and the memory requirements of an algorithm increase as the size of the input to the algorithm increases.
Nash Equilibrium: A solution concept of a game where no player can benefit by changing his strategy unilaterally, i.e. while the other players keep theirs unchanged; this set of strategies and the corresponding payoffs constitute a Nash Equilibrium of the game.
Heuristic: In computer science, a technique designed to solve a problem which allows for gaining computational performance or conceptual simplicity potentially at the cost of accuracy and/or precision of the provided solutions to the problem itself.
NP-Hard Problems: Problems that are intrinsically harder than those that can be solved by a nondeterministic Turing machine in polynomial time.
Payoffs: Numeric representations of the utility obtainable by a player in the different outcomes of a game.