cft

Game Theory concepts with application in Python using Nashpy (Part 1)

Today, I will try to explain some concepts of game theory in simple terms using 2 player games. You will also learn how to solve these games using Nashpy in python.


user

Mythili Krishnan

3 years ago | 10 min read

“Rock, paper, scissors” — everyone of us might have played this game in our childhood. Have you ever wondered the strategies we chose could in fact be modeled in a game theoretic concept?

You might think that people randomly choose a strategy here, but in reality we are trying to predict what my opponent’s strategy will be and accordingly choose a move in order to win the game.

“Game Theory” is an analysis of strategic interaction. It consists of analyzing or modelling strategies and outcomes based on certain rules, in a game of 2 or more players.It has widespread applications and is useful in political scenarios, logical parlour games, business as well as to observe economic behaviour.

Today, I will try to explain some concepts of game theory in simple terms using 2 player games. You will also learn how to solve these games using Nashpy in python. Here is the agenda:

  1. Payoff matrix of a game
  2. What is a dominant strategy
  3. Nash equilibrium
  4. Pure and mixed strategies
  5. Application in Python
  6. Some limitations of Nash equilibrium
  7. Pareto efficiency
  8. Prisoner’s dilemma game and some practical applications
Fig 1: 2 player game (Table by Author)
Fig 1: 2 player game (Table by Author)

Consider the 2-player game given in Fig 1, which will be played by 2 players- Player A and Player B. Each player has 2 strategies each- Player A can play Top or Bottom and Player B can play Left or right.

The matrix above is called the “payoff matrix”. Player A is also called row player and Player B column player.The numbers in red denote the payoff of Player A and the numbers in cyan denote the payoffs of Player B.

For eg: If Player A plays Bottom and player B plays left then what do you think will be the payoffs ?

Fig 2: Game 1 (Image by Author)
Fig 2: Game 1 (Image by Author)

The payoff to Player A will be 4 and player B will be 2 as you can see in Fig 2.This particular game has a very simple solution. For Player A , it is always better to play “Bottom” because his payoffs (4 or 2) from this strategy is always greater than Top (2 or 0).

Similarly, for Player B, it is always better to play “Left” because his payoffs (4 or 2) is always greater than (2 or 0). Hence, the equilibrium strategy is for Player A to play “Bottom” and Player B to play “Left”. This brings us to the concept of dominant strategy.

Dominant strategy: There is one optimal strategy for each player irrespective of what strategy the other player adopts. Whatever choice B makes, A should always choose Bottom and whatever choice A makes B should always choose Left.

In this game, this is the equilibrium outcome of the game.

Can we now solve this game in Python?

Before that, let us first discuss the concept of Nash equilibrium.

Nash Equilibrium

Let us consider Game 2 below:

Fig 3: Game 2 (Image by Author)
Fig 3: Game 2 (Image by Author)

N.B.: Payoffs of Player A is given in green and Player B in brown.

In this game, if player B chooses left , then player A’s pay-offs are either 4 or 0. While, when player B chooses right, player A’s pay-offs are 0 or 2. Hence, if B chooses left A should choose Top and if B chooses Right then A should choose Bottom. This, optimal choice of A is dependent on what choice B makes.

A pair of strategies is said to be Nash equilibrium (NE), if optimal choice of Player A given Player B’s choice coincides with optimal choice of Player B given Player A’s choice. In simple terms, initially neither player knows what the other player will do when deciding or making a choice.

Hence NE is a pair of choices/strategies/expectations where neither player wants to change their behaviour even after the strategy/choice of the other player is revealed.

In this game, strategy (Top, Left) is a Nash equilibrium because if A chooses Top, then the best thing for B is to choose Left because his pay-off for choosing left is 2 as opposed to 0 if he chooses bottom. Similarly if B chooses left then best choice for A is to choose Top, because he will get a higher pay-off of 4 if he chooses Top versus he will get 0 if he chooses Bottom.

So, can there be multiple Nash equilibrium? The answer is Yes. In this game we just discussed, in fact we have 2 Nash equilibria- the strategy (Bottom, Right) is also a NE because if A chooses Bottom, B should choose Right and vice versa.

Let us now try to find out the Nash equilibrium for this game (Game 2) and the previous one i.e. Game 1 using Nashpy in Python.

Game 1 using Python:

# Create the game with the payoff matrixA = np.array([[2,0],[4,2]]) # A is the row player
B = np.array([[4,2],[2,0]]) # B is the column player
game1 = nash.Game(A,B)
game1

We will get an output like this:

Bi matrix game with payoff matrices:

Row player:
[[2 0]
[4 2]]

Column player:
[[4 2]
[2 0]]

Now the Nash equilibrium is given by:

# Find the Nash Equilibrium with Support Enumerationequilibria = game1.support_enumeration()
for eq in equilibria:
print(eq)

The output is:

(array([0., 1.]), array([1., 0.]))

Since there are 2 strategies per player- Player A has strategies (Top, Bottom) and Player B has strategies (Left, Right).

The output can be interpreted as: Player A chooses strategy 2 i.e. ‘Bottom’ as given by ‘1’ in the second position of the array and Player B chooses strategy 1 i.e. ‘Left’ as given by ‘1’ in the first position of the array. Hence, as we saw earlier (Bottom, Left) is the NE or outcome of this game.

Game 2 using Python:

Using the same logic as above let us compute the Nash equilibria for Game 2.

# Create the payoff matrixA = np.array([[4,0],[0,2]]) # A is the row player
B = np.array([[2,0],[0,4]]) # B is the column player
game2 = nash.Game(A,B)
game2# Find the Nash Equilibrium with Support Enumerationequilibria = game2.support_enumeration()
for eq in equilibria:
print(eq)

The output that we will get is this:

(array([1., 0.]), array([1., 0.]))
(array([0., 1.]), array([0., 1.]))
(array([0.66666667, 0.33333333]), array([0.33333333, 0.66666667]))

Here we see 3 output lines, let us take each line and try to interpret it:

Player A has strategies (Top, Bottom) and Player B has strategies (Left, Right)

Line 1: “(array([1., 0.]), array([1., 0.])) “

Interpretation: This is the first Nash equilibrium (Top, Left).Player A chooses strategy 1 i.e. ‘Top’ as given by ‘1’ in the first position of the first array and Player B chooses strategy 1 i.e. ‘Left’ as given by ‘1’ in the first position of the second array.

Line 2: “(array([0., 1.]), array([0., 1.])) “

Interpretation: This is the second Nash equilibrium (Bottom, Right).Player A chooses strategy 2 i.e. ‘Bottom’ as given by ‘1’ in the second position of the first array and Player B chooses strategy 2 i.e. ‘Right’ as given by ‘1’ in the second position of the second array.

But we have a 3rd line as well, so why did we get another output?To understand this, let me introduce mixed strategies.

The strategies that we discussed above in Game 1 and Game 2 are called “Pure strategies”. But, we as humans, often might not make a choice and stick to that through eternity. Sounds reasonable? So, instead what the players can do is randomize their strategies. Probabilities can be assigned to each pure strategy and the players can choose the strategies as per the probability assigned to it. Hence, line 3 of the output of game 2 can be interpreted as:

Line 3: “(array([0.66666667, 0.33333333]), array([0.33333333, 0.66666667])) “

Interpretation: Player A plays strategy 1 i.e. “Top” 66.67% of the times and strategy 2 i.e. “Bottom” 33.33% of the times while Player B plays strategy 1 i.e. “Left” 33.33% of the times and strategy 2 i.e. “Right” 66.67% of the times.

Logically also, Player A should assign higher probability to “Top” and player B to “Right” because these give them higher pay-offs.

This equilibrium is a mixed strategy Nash equilibrium and defined as

“Each player chooses the optimal “frequency” with which to play his strategies given the frequency choices of the other player”

How do we calculate the utility /pay-offs of Player A and Player B in the mixed strategy Nash equilibrium?

The general mathematical formulation is given as:

Consider the game

with σr and σc are the mixed strategies for the row and column players here A and B respectively.

Then the utility/pay-off for the row player (A) is:

and utility/pay-off for the column player (B) is:

The probability of being in a given cell of (A or B) is

The value of the cell is

In our case, utility to A will be then :

0.67*0.33*4 +0.33*0.67*0+0.33*0.67*0+0.33*0.67*2 =1.3266

and for B it will be :

0.33*0.67*2 + 0.67*0.33*0 + 0.33*0.67*0+0.67*0.33*4 = 1.3266

Let us compute this in Python now:

# Calculate Utilitiessigma_r = np.array([.67,.33])
sigma_c = np.array([.33,.67])
pd = nash.Game(A, B)
pd[sigma_r, sigma_c]

Output is given as :

array([1.3266, 1.3266])

This matches with our calculation above.

There are few problems or limitations of Nash equilibrium:

  1. Multiple Nash equilibria: As illustrated in Game 2, there can be multiple Nash equilibria, so in that case there is no unique solution that exists.
  2. No Nash equilibrium: There are games where there is no Nash equilibrium. Consider Game 3 below:
Game 3 (Image by Author)
Game 3 (Image by Author)

N.B.: Payoffs of Player A is given in green and Player B in brown.

Here, if Player A plays Top, then Player B should play Left (payoff 0 is > payoff -2). If player B plays Left, then player A should play Bottom (payoff 2 is > payoff 0). If Player A plays Bottom, then Player B should play Right (payoff 6 > payoff 0) and if Player B plays Right then player A should play Top (payoff 0 >payoff -2). Hence, there is “No Nash equilibrium in this game in pure strategy”.

3. Nash equilibrium does not ensure Pareto efficient outcomes :

Let us illustrate this by considering one of the most famous games called “Prisoner’s dilemma”

Before that, let us quickly define Pareto efficiency in this context

Pareto efficiency is a situation where no individual can be better off without making at least one individual worse-off

Now back to our Prisoner’s dilemma game.Two prisoners have partnered in a crime and they are being questioned in separate rooms. Each of them has 2 strategies -

a) Confess to the crime — Confess

b) Denial of being involved — Deny

Game 4: Prisoner’s Dilemma (Image by Author)
Game 4: Prisoner’s Dilemma (Image by Author)

If only one prisoner confesses, then he would go free and the other prisoner would be booked and made to serve 6 months in prison. However, if both deny to the crime then they would need to serve 1 month each in prison and if they both confess then they would each need to serve 3 months in prison. The pay-off matrix is illustrated above in Game 4.

Let’s now look at the utilities and the strategies that each prisoner should choose.

If Prisoner A confesses then it is better for Prisoner B to confess because his payoff of -3 > payoff of -6 . If Prisoner A denies then it is better for Prisoner B to confess because his payoff of 0 > payoff of -1 and he can get off scot free. Hence, in both the cases, irrespective of what prisoner B does it is better for prisoner A to confess always.

The same logic applies for prisoner B as well. Thus (Confess, Confess) is the Nash equilibrium in this game. This is also the dominant strategy equilibrium because each prisoner has an optimal strategy independent of the other player.

However, there is a catch here. This strategy is pareto-inefficient as we will illustrate below:

If both prisoners could trust each other (they cannot talk to each other and co-ordinate because they are in separate rooms and not allowed to talk) and deny, then both of them would be better off. Their payoffs would be (-1, -1) in this case. Hence, the strategy (Deny, Deny) is pareto-efficient because there is no other strategy that makes both prisoners better off.

Python application of the Prisoner’s dilemma game:

Here is the code that you can use to solve the game:

# Create the payoff matrixA = np.array([[-3,0],[-6,-1]]) # A is the row player
B = np.array([[-3,-6],[0,-1]]) # B is the column player
game4 = nash.Game(A,B)
game4# Find the Nash Equilibrium with Support Enumerationequilibria = game4.support_enumeration()
for eq in equilibria:
print(eq)

The output will be :

Bi matrix game with payoff matrices:

Row player:
[[-3 0]
[-6 -1]]

Column player:
[[-3 -6]
[ 0 -1]](array([1., 0.]), array([1., 0.]))

As you can see strategy 1 i.e. (Confess, Confess) for both prisoners is the Nash equilibrium.

Applications of prisoner’s dilemma game:

The prisoner’s dilemma game has a lot of applications in economics, politics , industry and other business decisions as well. To give one eg: There are 2 firms -firm A and firm B who are the leaders in the market of say the airlines industry. Take strategy 1 (confess) to be ‘keep price of flight ticket unchanged’ and strategy 2 (deny) as ‘lower price of flight ticket’.

The lowering of the price can be an attempt to fill up empty seats and capture the market.If say firm A keeps flight ticket price unchanged then it would pay firm B to lower the price and capture the market. Firm B can do the same i.e lower the price and in a sequential game this could result in a price war, However, if both firms form a cartel and decide to keep prices unchanged, then both will be better off.

Summary:

We discussed the concepts of game theory with some well-known games.

In my future posts, I will talk about sequential games and how the outcomes of the game can change.

Here is another famous game “Hawk-Dove” game. True to its name “hawk” refers to an aggressive strategy and “dove” to a passive one.

Game 5: Hawk-Dove Game (Image by Author)
Game 5: Hawk-Dove Game (Image by Author)

Let me know in the comments what would be the outcome of this game and do reach out to me in case you have any questions.

The full code can be accessed here on Github.

Upvote


user
Created by

Mythili Krishnan


people
Post

Upvote

Downvote

Comment

Bookmark

Share


Related Articles