-This paper describes SALENE, a Multi Agent System (MAS) for learning Nash Equilibria in non-cooperative games. SALENE is based on the following assumptions: if agents representing the players act as rational players, i.e. they act to maximise their expected utility in each match of a game, and if such agents play k matches of the game they will converge in playing one of the Nash Equilibria of the game. SALENE can be conceived as a heuristic and efficient method to compute at least one Nash Equilibria in a non-cooperative game represented in its normal form.
Tcomputing Nash equilibria in non-cooperative games, is
he complexity of NASH [
Motivated by these results, recent studies have dealt with
the problem of computing Nash Equilibria by exploiting
approaches based on the concepts of learning and evolution
[
In this paper we present SALENE, a MAS for learning Nash Equilibria in non-cooperative games. 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, each agent assumes that his beliefs about the other players strategies are correct and he plays a strategy that is a best response to his beliefs. By increasing k the agents will converge in playing one of the Nash equilibria of the game.
This paper is structured as follows. In Section 2, a formal definition of the problem will be given and the system requirements detailed. In Section 3 and in Section 4 the design and the implementation of SALENE will be described respectively, then, in Section 5, some experimental results will be shown. Finally, in Section 6, conclusions and future efforts will be addressed.
II. PROBLEM DEFINITION AND SYSTEM REQUIREMENTS An n-person strategic game G can be defined as a tuple G = (N; (Ai)iN; (ri)iN), where N = {1, 2, , n} is the set of players, Ai is a finite set of actions for player iN, and ri : A1 × × An o is the payoff function of player i. The set Ai is called also the set of pure strategies of player i. The Cartesian product ×iNAi = A1 × × An can be denoted by A and r : A o 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)iN; (ri) iN).
For any finite set Ai the set of all probability distributions on Ai can be denoted by (Ai). An element i (Ai) is a mixed strategy for player i.
A (Nash) equilibrium of a strategic game G = (N, A, r) is an N-tuple of (mixed) strategies = ( i) iN, i (Ai), such that for every i N and any other strategy of player i, i (Ai), ri( i, -i) ri( i, -i), where ri denotes also the expected payoff to player i in the mixed extension of the game and -i represents the mixed strategies in of all the other players. Basically, supposing that all the other players do not change their strategies it is not possible for any player i to play a different strategy i able to gain a better payoff of that gained by playing i. i is called a Nash equilibrium strategy for player i.
In 1951 J. F. Nash proved that a strategic (non-cooperative)
game G = (N, A, r) has a (Nash) equilibrium [
In order to exemplify the definitions given above let us
consider a game with two players (n=2) and |A1|=|A2|=m, i.e.,
the sets of pure strategies have both cardinality equals to m
[
A mixed strategy, a probability distribution over pure strategies, is a vector M such that ¦sM F s 1 and for every s M, s 0.
When the row player plays mixed strategy and the column player plays mixed strategy , their expected payoffs will be, respectively, F t BJ and F tWJ ( t is the transpose of vector ).
A Nash Equilibrium of the game described by the matrices B and W is a pair of mixed strategies ( , ) such that for all mixed strategies F and J , of the row and the column player respectively, F t BJ t F t BJ and F tWJ t F tWJ .
Starting from the problem definition discussed above, SALENE was conceived as a system for learning at least one Nash Equilibrium of a non-cooperative game given in the form G = (N; (Ai)iN; (ri)iN). In particular, the system asks the user for: - the number n of the players which defines the set of players N = {1, 2, , n}; - for each player iN, the related finite set of pure strategies Ai and his payoff function ri : A1 × × An o ; - the number k of times the players will play the game.
Then, the system creates n agents, one associated to each
player, and a referee. The players and the referee both know
that G is the actual game to be played, i.e. there is complete
information [
This kind of agents will play the game G k times, after each
match, each agent will decide the strategy to play in the next
match to maximise his expected utility on the basis of his
beliefs about the strategies that the other agents are adopting.
By increasing k the agents will converge in playing one of the
Nash Equilibria of the game. This conclusion relays on the
hypothesis that the agents will act as rational players and
derives straightly from the assumptions on which the Nashs
theorem is based [
2 Payoffs are numeric representations of the utility obtainable by a player in the different outcomes of a game.
On the basis of the requirements highlighted in the previous section the SALENE (Software Agent for LEarning Nash Equilibria) MAS was designed. The class diagram of SALENE is shown in Figure 1.
FIPAAgent 1
1 ManagerAgent
GameDefinition
The Manager Agent interacts with the user and it is responsible for the global behaviour of the system. In particular, after having obtained from the user the input parameters G and k (see section II), the Manager Agent creates both n Player Agents, one associated to each player, and a Referee Agent that coordinates and monitors the behaviours of the players. The Manager Agent sends to all the agents the definition G of the game then he asks the Referee Agent to orchestrate k matches of the game G. In each match, the Referee Agent asks each Player Agent which pure strategy he has decided to play, then, after having acquired the strategies from all players, the Referee Agent communicates to each Player Agent both the strategies played and the payoffs gained by all players. After playing k matches of the game G the Referee Agent communicates all the matches data to the Manager Agent which analyses it and properly presents the obtained results to the user.
A Player Agent is a rational player that, given the game
definition G, acts to maximise his expected utility in each
single match of G. In particular the behaviour of the Player
Agent i can be described by the following main steps:
1. In the first match the Player Agent i chooses to play a
pure strategy randomly generated considering all the pure
strategies playable with the same probability: if |Ai|=m the
probability of choosing a pure strategy sAi is 1/m.
2. The Player Agent i waits for the Referee Agent to ask him
which strategy he wants to play, then he communicates to
the Referee Agent the chosen pure strategy as computed
in step 1 if he is playing his first match or in step 4
otherwise;
3. The Player Agent waits for the Referee Agent to
communicate him both the pure strategies played and the
payoffs gained by all players;
4. The Player Agent decides the mixed strategy to play in
the next match. In particular, the Player Agent updates the
beliefs about the mixed strategies currently adopted by
the other players and consequently recalculate the
strategy able to maximise his expected utility. Basically,
the Player Agent i tries to find the strategy i (Ai),
such that for any other strategy i (Ai), ri( i, -i)
ri( i, -i) where ri denotes his expected payoff and -i
represents his beliefs about the mixed strategies currently
adopted by all the other players, i.e. -i=( j)jN,ji, j
(Aj). In order to evaluate j for each other player ji the
Player Agent i considers the pure strategies played by the
player j in all the previous matches and computes the
frequency of each pure strategy, this frequency
distribution will be the estimate for j. If there is at least
an element in the actually computed set -i=( j)jN,ji that
differs from the set -i as computed in the previous match,
the Player Agent i solves the inequality ri( i, -i) ri( i, -i)
that is equivalent to solve the optimization problem
P={max(ri( i, -i)), i (Ai)}. It is worth noting that P is
a linear optimization problem, actually, given the set -i,
ri( i, -i) is a linear objective function in i (see the two
players example reported in Section II), and with |Ai|=m
i (Ai) is a vector M such that ¦sM F s 1 and for
every sM s0, so the constraint i (Ai) is a set of
m+1 linear inequalities. P is solved by the Player Agent
by using an efficient method for solving problems in
linear programming [
The Manager Agent, receives from the Referee Agent all the data about the k matches of the game G and computes an estimate of a Nash Equilibrium of G, i.e. an N-tuple =( i)iN, i (Ai). In particular, in order to estimate i (the Nash equilibrium strategy of the player i), the Manager Agent computes, on the basis of the pure strategies played by the player i in each of the k match, the frequency of each pure strategy: this frequency distribution will be the estimate for i. The so computed set =( i)iN, i (Ai) will be then properly proposed to the user together with the data exploited for its estimation.
Agent class of JADE [
extend FSMBehaviour class of JADE which models a complex task whose sub-tasks correspond to the activities performed in the states of a finite state machine. In particular, the behaviours of both the Referee and the Player Agent are also cyclic.
The interactions among SALENE Agents are appositely defined through sequences of ACL messages instances of the ACLMessage class of JADE.
SALENE was tested on different games that differ from each other both in the number and in the kind of Nash Equilibria. This section presents the results obtained for three popular games: (1) The Prisoners Dilemma which has one pure Nash Equilibrium (that is an equilibrium in which all the players play a pure strategy); (2) Matching Pennies which has one mixed Nash Equilibrium (that is an equilibrium in which at least one player plays a mixed strategy); (2) Battle of the Sexes which has three Nash Equilibria (two Pure Equilibria and one Mixed Equilibrium).
An informal description of the Prisoners Dilemma can be
found in [
By looking at Table Ib, it is possible to note that for Player
1 d is the best response to c (10>6) and d is also the best
response to d (3>0). The same is true for Player 2, so both
players rationally will play their pure strategy d that is their
dominant strategy. Formally, the Prisoners Dilemma has one
Nash Equilibrium ={ 1, 2}={ , }, 1 (A1), 2 (A2),
2, 2, where =[
In order to compare the analytical result with the result obtainable in SALENE we ran 30 experiments each consisting of 100 matches (k=100) of the Prisoners Dilemma. In the case of the Prisoners Dilemma the expected result was that as soon as a Player Agent played his dominant strategy d, he would never change his choice, so after few matches the Player Agents played both their dominant strategy d so converging in playing the Nash Equilibrium of the game. The experiments confirm the expected result, as an example Figure 2a-b reports one of the experiments carried out. In particular, Figure 2a(2b) shows the strategy played by Player 1(Player 2) in each of the k match of an experiment. As showed in Figure 2a-b, after few matches both the Player Agents play their pure strategy d as required by the Nash Equilibrium of the game. c d 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
match (b) Strategy played by Player 2
Fig. 2. The Prisoners Dilemma: experimental results
An informal description of the Matching Pennies game follows: the game is played between two players, each player has a penny and must secretly turn it to heads or tails, the players then reveal their choices simultaneously; if the pennies match (both heads or both tails), Player 1 receives S dollars from Player 2. If the pennies do not match (one heads and one tails), Player 2 receives S dollars from Player 1. This is an example of a zero-sum game, where one player's gain is exactly equal to the other player's loss. Formally, in a game G of Matching Pennies (MP), two players (n=2) simultaneously choose a move, either heads (h) or tails (t), so A1=A2={h,t} and |A1|=|A2|=m=2. Each player receives a payoff after each encounter as reported in Table IIa-b. (a) Strategy played by Player 1 (b) Strategy played by Player 2
Fig. 3. Matching Pennies: experimental results
Matching Pennies has no pure strategy Nash equilibrium since there is no pure strategy (heads or tails) that is a best response to a best response, i.e. a dominant strategy. Alternatively, there is not a pure strategy that a player would ever change when told the pure strategy played by the other player. Instead, the unique Nash equilibrium of Matching Pennies is in mixed strategies: each player chooses heads or tails with equal probability. In this way, each player makes the other indifferent in choosing heads or tails, so neither player has an incentive to try another strategy. Formally, Matching Pennies has one mixed Nash Equilibrium ={ 1, 2}={ , }, 1 (A1), 2 (A2), 2, 2, where =[0.5, 0.5] and =[0.5, 0.5].
In order to compare the analytical result with the result obtainable in SALENE we ran 30 experiments each consisting of 100 matches (k=100) of Matching Pennies. The expected result was that, analyzing the pure strategies played by each player in each of the k match, their frequency distribution would asymptotically converge to the mixed Nash Equilibrium of the game. The experiments confirm the expected result: by increasing k the computed frequency distributions asymptotically converge to the mixed Nash Equilibria of the game. As an example Figure 3a-b reports one of the experiments carried out. In this case the computed frequency distributions were: 1= =[0.49, 0.51] and 2= =[0.49, 0.51].
An informal description of the Battle of Sexes game follows: a man and a woman plan to meet after work to attend an event: an opera or a football match, but they can not communicate so they have to choose separately where to go. The woman prefers the opera to the football match, whereas the man prefers the football match to the opera, but both prefer to be together at either event than alone at either one. More formally in a game G of Battle of Sexes (BS), two players (n=2) simultaneously choose a move, either opera (o) or football (f), so A1=A2={o,f} and |A1|=|A2|=m=2. Each player receives a payoff after each encounter as reported in Table IIIa-b. Regarding the payoffs reported in Table IIIa the following order must hold: T>R>L. Table IIIb shows a valid assignment for the payoffs.
III={V I1II ,V I2II }={ III, III}, V I1II (A1), V I2II (A2), III , III 2, where III =[2/3, 1/3] and III=[1/3, 2/3]; 2
In order to compare the analytical result with the result obtainable in SALENE, we ran 30 experiments each consisting of 100 matches (k=100) of the Battle of Sexes. Battle of Sexes presents an interesting case for games theory since each of the Nash Equilibria is deficient in some way. The two pure strategy Nash Equilibria are unfair, one player consistently does better than the other. In the mixed strategy Nash Equilibrium the players will be together at the same event with probability 4/9 and will be alone with probability 5/9, leaving each player with an expected payoff of 10/9 that is very low if compared with the expected payoff of the two pure Nash Equilibria.
The expected result was that as soon as both the Player Agents played the same pure strategy (o or f), i.e. one of the Pure Nash Equilibria of the game, the Agents would never change their choices: the Player who plays his favorite strategy will not have incentive to change it, the player who does not play his favorite strategy will not change it because in this case his expected payoff will get worse in the next match. In particular, after 1 or h*(T+R) matches, kh1, there is a probability of 50% that from this match on the Player Agents will converge in playing one of the Pure Nash Equilibria of the game. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
match (b) Strategy played by Player 2
Fig. 4. Battle of Sexes: experimental results
The experiments confirm the expected result: in all the experiments after 1 or h*(T+R) matches the Player Agents play one of the two pure Nash Equilibria of the game. As an example Figure 4a-b reports one of the experiments carried out, in this case the played Nash Equilibrium was I.
The complexity of NASH, the problem consisting in computing Nash equilibria in non-cooperative games, is still debated, but even in the two players case, the best algorithm known has an exponential worst-case running time. Starting from these considerations SALENE, a MAS for learning Nash Equilibria in non cooperative games, was developed. SALENE is based on the assumptions that if agents representing the players act as rational players, i.e. if each player acts to maximise his expected utility in each match of a game G, and if such agents play k matches of G they will converge in playing one of the Nash Equilibria of the game. In particular, after each match each agent decides the strategy to play in the next match on the basis of his beliefs about the strategies that the other agents are adopting. More specifically, each agent assumes that his beliefs about the other players strategies are correct and plays a strategy that is a best response to his beliefs. Analyzing the behaviour of each agent in all the k matches of G, SALENE presents to the user an estimate of a Nash Equilibrium of the game.
A set of experiments was carried out on different games that differ from each other both in the number and in the kind of Nash Equilibria. The experiments demonstrated that: - if the game has one Pure Nash Equilibrium the agents converge in playing this equilibrium; - if the game has one Mixed Nash Equilibrium, the frequency distributions of the pure strategies played by each player asymptotically converge to the mixed Nash Equilibrium of the game; - if the game has p>1 Pure Nash Equilibria and s>1 Mixed Nash Equilibria the agents converge in playing one of the p Pure Nash Equilibria.
SALENE can be conceived as a heuristic and efficient
method for computing at least one Nash Equilibria in a
noncooperative game represented in its normal form; actually, the
learning algorithm adopted by the Player Agents has a
polynomial running time [
Efforts are currently underway to: (i) evaluate different learning algorithms and extensively testing them on complex games; (ii) let the user ask for the computation of equilibria with simple additional properties.