Mixed Strategy Nash Equilibrium

An introduction to solving for Mixed Strategy Nash Equilibrium

Advertisements

One of my favorite sporting events to watch is the World Cup. The level of competition, intensity, and drama make it a very fun event that brings out a sense of national pride. However, it gets even more exciting when regulation ends in a tie resulting in penalty kicks. The goalie has a very difficult job of trying to anticipate where the kicker is going to kick the ball.  In addition, the kicker has to make sure the ball will be out of the goalie’s reach once the ball is kicked.

What would this look like in a game theory model? Possibly something like this:

Kicker\Goalie Left Right
Left 0,1 1,0
Right 1,0 0,1

The goalie receives a payoff of 1 when he or she correctly anticipates the direction that the soccer ball is kicked. The kicker receives a payoff of 1 when he or she is able to kick the ball in the opposite direction of the goalie’s choice. However, you can see that there is no pure strategy Nash Equilibrium.

Kicker\Goalie Left Right
Left 0,1 1,0
Right 1,0 0,1

Instead, we need to solve for the mixed strategy Nash Equilibrium. A little bit of probability and algebra is needed to solve this game. Let p represent the probability that the kicker kicks left and 1-p be the probability that the kicker kicks right. Let q represent the probability that the goalie moves to the left and 1-q be the probability the goalie moves to the right.

q 1-q
Kicker\Goalie Left Right
p Left 0,1 1,0
1-p Right 1,0 0,1

To solve for p and 1-p of the kicker we must identify the potential payoffs of the goalie should he or she choose to move left or right. They are highlighted in red and purple above.

We can solve using the following equation based on probability:

1(p) + 0(1 – p) = 0(p) + 1(1-p) =>

p = 1 – p =>

2p = 1 =>

p = 1/2 =>

Solve for 1 – p: 1 – 1/2 = 1/2

p = 1/2, 1-p = 1/2 (your probability totals must equal 1)

This means that the kicker has a mixed strategy of kicking left 1/2 of the time and kicking right 1/2 of the time. This makes sense if you think about it as the kicker does not want to be predictable on kick placement.

Now to solve for the goalie’s mixed strategy:

q 1-q
Kicker\Goalie Left Right
p Left 0,1 1,0
1-p Right 1,0 0,1

Solving for q and 1-q involves the same equation:

0(q) + 1(1 – q) = 1(q) + 0(1 – q) =>

1 – q = q =>

1 = 2q =>

q = 1/2 =>

Solve for 1-q: 1 – 1/2 = 1/2

q = 1/2, 1-q = 1/2 (your probability totals must equal 1)

Similar to the kicker, the goalie should move left 1/2 of the time and move right 1/2 if the time.  The mixed strategy Nash Equilibrium for this game would be Kicker: left(1/2), right(1/2) and Goalie: left(1/2),right(1/2). Payoff for choosing a mixed strategy is also simple to solve.

You take the original equations and plug in the values for (p, 1-p) and (q, 1-q):

Kicker: 1(p) + 0(1 – p) = 0(p) – 1(1-p)  => 1(1/2) + 0(1/2) = 0(1/2) + 1(1/2) =>

1/2 = 1/2 (both sides should equal each other)

Goalie: 0(q) + 1(1 – q) = 1(q) + 0(1 – q) => 0(1/2) + 1(1/2) = 1(1/2) + 0(1/2) =>

1/2 = 1/2

The payoffs of a mixed strategy for both Goalie and Kicker = (1/2,1/2). In the end, it is important for both players to not be predictable.

 

 

Game Theory: Nash Equilibrium III

Solving simultaneous games with three players.

In my prior blog I challenged readers to solve the game displayed in the title image. Before we move forward, let’s solve that game by finding the Nash Equilibrium.

1\2 L C R
T 2,0 1,1 4,2
M 3,4 1,2 2,3
B 1,3 0,2 3,0

First we want to look for any dominated strategies. It appears that strategy T strictly dominates strategy B. Since we assume both players are rational decision makers we can eliminate that strategy  since Player 1 will not choose strategy B. In addition, with B being eliminated, strategy R strictly dominates strategy C for Player 2 so strategy C can be removed.  We are now left with the following game:

1\2 L R
T 2,0 4,2
M 3,4 2,3

We can now solve for Nash Equilibrium. If Player 2 chooses L, Player 1 prefers M over T since 3>2. If Player 2 chooses R, Player 1 prefers T over M since 4>2. In addition, Player 2 prefers R over L when Player 1 chooses T and L over R when Player 1 chooses M. As a result, we end up with the following:

1\2 L R
T 2,0 4,2
M 3,4 2,3

Wait, we have more than one Nash Equilibrium? The answer is yes! In fact, many games can have multiple Nash Equilibrium (ex. Battle of the Sexes). The next game we will analyze could have one or more Nash Equilibrium. This game will also involve three players instead of two. Don’t worry, we will work through this together.

Capture

In this game we have three college students who have finished school for the day and are debating whether they should go to the local bar or not (…should be studying). The problem is that the bar can be overcrowded (or empty)  so the overall utility of going to the bar drops when too many people go (or not enough people go). The third value represents the utility (payoff) for Student 3.

Let’s look at this step by step:

Capture2

 

Both Students 2 & 3 choose Go: Student 1 prefers to stay (1>-2)

Capture3.PNG

 

Student 2 chooses Stay, Student 3 chooses Go: Student 1 prefers to go (2>1)

Capture4.PNG

 

Student 2 chooses Go, Student 3 chooses Stay: Student 1 prefers to go (2>1)

Capture5

 

Both Students 2 & 3 choose Stay: Student 1 prefers to stay (1>0)

Capture6

Students 1 & 3 choose Go: Student 2 prefers to stay (1>-2)

Capture7

Student 1 chooses Stay, Student 3 chooses Go: Student 2 prefers to go (2>1)

Capture8

Student 1 chooses Go, Student 3 chooses Stay: Student 2 prefers to go (2>1)

Capture9

Both Students 1 & 3 choose Stay: Student 2 prefers to stay (1>0)

Capture10

Both Students 1 & 2 choose Go: Student 3 prefers to stay (1>-2)

Capture11

 

Student 1 chooses Go, Student 2 chooses Stay: Student 3 prefers to go (2>1)

Capture12

Student 1 chooses Stay, Student 2 chooses Go: Student 3 prefers to go (2>1)

Capture13

Both Students 1 & 2 choose Stay: Student 3 prefers to stay (1>0)

Capture14

In this game we end up with a total of four Nash Equilibrium. So it appears that each student prefers that only 2/3 students go to the bar otherwise they would rather stay home. Throughout these examples we have solved simultaneous games that involved pure strategy Nash Equilibrium. We have discovered that games could have one or many. But what happens if we come across a game where there is no pure strategy Nash Equilibrium? I will cover this occurrence in the next blog.

I appreciate your feedback in the comments below.

 

Game Theory: Nash Equilibrium II

Additional practice for solving pure strategy Nash Equilibrium

Last time we introduced the important concept of Nash Equilibrium in Game Theory. In this blog we will continue to practice solving for pure strategy Nash Equilibrium. All the examples provided will be games of complete information. In addition, I will introduce the concept of iterated elimination of strictly dominated strategies. Let’s begin with the following game:

1\2 C D
A 1,5 2,1
B 3,3 2,2

Player 1 has two pure strategies of A and B while Player 2 has two pure strategies of C and D. We will assume that both players make rational choices (look to optimize). Player 1 would rather choose strategy B if Player 2 chooses strategy C since 3 > 1. If Player 2 chooses D, Player 1 will be indifferent between A and B since 2 = 2.

On the other hand, Player 2 will prefer strategy C to D if Player 1 chooses A since 5 > 1. In addition Player 2 will choose strategy C if Player 1 chooses B since 3 > 2. What can be observed from this game so far? Regardless of what Player 1 chooses, Player 2 will always choose strategy C over D due to the higher payoff. Strategy D is an example of a strictly dominated strategy. Rational players do not play strictly dominated strategies. As a result:

1\2 C D
A 1,5 2,1
B 3,3 2,2

becomes

1\2 C
A 1,5
B 3,3

This makes the game a lot easier to solve. Since Player 1 prefers strategy B over A due to the higher payoff and Player 2 will always choose strategy C, the pure strategy Nash Equilibrium for this game is (B,C) for payoff (3,3).

1\2 C
A 1,5
B 3,3

Let’s look at another example with more strategies:

1\2 D E F
A 1,0 3,2 5,3
B 2,3 2,4 1,5
C 3,1 1,3 3,2

First thing to look for is removing any dominated strategies. Do you see any? Let’s break this down to determine if Player 1 has any dominated strategies.

If Player 2 chooses D: C > B > A

If Player 2 chooses E: A > B > C

If Player 2 chooses F: A > B > C

It appears that there are 0 dominated strategies for Player 1. Now let’s take a look to see if there are any dominated strategies for Player 2.

If Player 1 chooses A: F > E  > D

If Player 1 chooses B: F > E > D

If Player 1 chooses C: E > F > D

Based on these observations, strategy D is strictly dominated by both strategy E and F. Player 2 will never choose this strategy so it can be eliminated from the game.

1\2 D E F
A 1,0 3,2 5,3
B 2,3 2,4 1,5
C 3,1 1,3 3,2

becomes

1\2 E F
A 3,2 5,3
B 2,4 1,5
C 1,3 3,2

We can now analyze this game further. Remember earlier when we analyzed whether Player 1 had any dominated strategies? With strategy D eliminated:

If Player 2 chooses E: A > B > C

If Player 2 chooses F: A > C > B

Strategy A dominates both B and C so they both can be eliminated!

1\2 E F
A 3,2 5,3
B 2,4 1,5
C 1,3 3,2

becomes

1\2 E F
A 3,2 5,3

So the Nash Equilibrium for this game is (A,F).

1\2 E F
A 3,2 5,3

Try to solve for the Nash Equilibrium in the title image above. In my next blog I will go over the solution. I look forward to hearing your feedback.

Game Theory: Nash Equilibrium

An introduction to solving for Nash Equilibrium in non-cooperative games

Welcome back! Last time we looked at games involving Prisoner Dilemma and how to solve them. I introduced both sequential and simultaneous games with my examples focusing on the later. We also discussed games of complete information and perfect rationality. Now we will look at the Nash Equilibrium solution for solving games.

Nash equilibrium was developed by the late John Nash (pictured). A mathematician who in 1994 won the Nobel Memorial Prize in Economic Sciences for his contribution to non-cooperative games (the games we are currently analyzing). Nash Equilibrium has been widely used in the fields included but not limited to economics, political science, and evolutionary biology. In 2001, the film A Beautiful Mind was released which won the Academy Award for Best Picture (one of my favorite films).

Nash

A Nash Equilibrium is defined as a profile of strategies such that each player’s strategy is an optimal response to the other players’ strategies (What?). Let’s look back at the example of Prisoner’s Dilemma:

1\2 Silent Betray
Silent -1,-1 -6,0
Betray 0,-6 -4,-4

Remember, a major premise of game theory is each player will look to optimize (or maximize) their utility (or payoff). With this in mind, we know that both players 1 and 2 will choose to betray each other. This results in a payoff of -4 for both players. You may be wondering why the players would end up with payoff of -4 when better payoffs exist. If player 1 chose the strategy of silent, player 2 could choose the strategy of betray resulting in payoff of -6 which is not optimal. So player 1’s best interest is to choose the strategy of betray.

1\2 Silent Betray
Silent -1,-1 -6,0
Betray 0,-6 -4,-4

Now let’s look at player 2. Following the premise of optimization and perfect rationality, player 2 would also choose the strategy of betray. By definition the strategy choices of (Betray, Betray) with payoff (-4,-4) is a Nash Equilibrium! It would not be optimal for Player 1 to choose silent since Player 2 would optimize by choosing betray and vice versa.

1\2 Silent Betray
Silent -1,-1 -6,0
Betray 0,-6 -4,-4

Let’s now take a look at an example from a previous blog and solve for Nash Equilibrium.

1\2 Talk Avoid
Talk 4,4 -2,6
Avoid 6,-2 1,1

In this scenario you frequent the night scene with your friends and are at a club (been there done that). You see someone from across the way and take in interest in that person. You have the strategy of either talking to that person of interest or avoiding them (so does the individual). If you both choose to talk to each other you both get a payoff of 4 (barring an awkward conversation). If you both choose to not talk to each other then you get a payoff of 1 (avoid embarrassment). But you can face the ultimate humiliation if you choose to talk and the person chooses to avoid or vice versa (people can be ruthless). The Nash Equilibrium is (Avoid, Avoid) with a payoff of (1,1).

1\2 Talk Avoid
Talk 4,4 -2,6
Avoid 6,-2 1,1

Going forward we will be solving games using Nash Equilibrium. Feel free to follow my blog and leave comments below as your feedback is appreciated.

Analyzing Prisoner’s Dilemma

Building a foundation for solving simultaneous games.

At the end of my previous blog you were given an example of prisoner’s dilemma. This game is a classic in game theory modeling. Let’s begin by understanding what type of game this is. In game theory you will more than likely come across two types of games: simultaneous and sequential.  A sequential game involves one player choosing their action before the others choose theirs (like a game of chess). In a simultaneous game, each player takes an action without the knowledge of the other player’s action. Prisoner’s Dilemma is an example of a simultaneous game.

An example Prisoner’s Dilemma:

1\2 Silent Betray
Silent -1,-1 -6,0
Betray 0,-6 -4,-4

Scenario: You and your partner have been arrested for burglary (shame on you two). The police have placed both of you in separate interrogation rooms. The officers tell you that your partner is about to tell them everything and that you better come clean or else you will face major jail time. However, you do not know if the officers are being truthful or not. So what do you do?

Let’s examine the payoffs in this game. Both of you are looking at a total of 1 year each if you both choose to stay silent. However, if your partner betrays you by confessing and you stay silent, your partner will be let go and you will get 6 years in prison. This is reversed if you choose to betray and your partner stays silent. If you both choose to betray each other(no honor among thieves) then you will both get 4 years in prison.

In this game you are aware of both you and your partner’s strategies and payoffs (everything is common knowledge). This is an example of a game with complete information (versus incomplete information). Remember that you do not know what choice your partner will make.

An important concept of game theory is the assumption that players behave with perfect rationality. Perfect rationality means that you ALWAYS act in a way that maximizes your utility (payoff). With this in mind, let’s determine which actions you should take in this game.

First, if your partner chooses to stay silent you have the option of either staying silent or betraying him. Since 0 (betraying) > -1 (silent) the rational choice would be to betray your partner. If your partner chooses to betray you, you would rather betray than stay silent as -4 > -6. However, it is assumed that your partner will make rational choices as well. So he or she will betray you if you stay silent or if you betray as well.

1\2 Silent Betray
Silent -2,-2 -6,0
Betray 0,-6 -4,-4

Notice that it is in your best interest to always betray your partner regardless of the choice your partner makes. This is an example of a dominant strategy where regardless of what any other players do, the strategy earns a player a larger payoff than any other. The game has been solved as you will both choose betray\betray. Congratulations! Try solving the game from the previous blog and leave feedback in the comments below.

Game Theory Intro

Scratching the surface of understanding basic game theory.

Let’s talk game theory! Game theory can be explained as “the study of mathematical models of conflict and cooperation between intelligent rational decision-makers” (thanks Wikipedia). So when we discuss game theory, we are not talking about video-games. We are talking about decisions that “players” (people, businesses, governments, animals) have to make while taking into consideration the decisions of opposing (or cooperating) “players.” For those who do not have a mathematical background, you can relax. The fundamental concepts of basic game theory can be understood with a minimal math background. Before diving into the subject, a brief overview on the structure of game theory must be explained.

When analyzing basic game theory models, you will usually see the “normal-form representation of games.” The normal form representation of games specifies:

  1.  The players in the game.
  2. The strategies available to each player
  3. The payoff received by each player for each combination of strategies that could be chosen by the player.

The term “payoff” can be interchangeable with the term “utility” which is widely used in the field of economics. When we talk about utility we mean the “measurement of usefulness.” For example, let’s say I have the option of going to the movies or an antique store. I value the movies at 6 utils (another way to say utility) and the antique store at 2 utils (sorry fans of antique stores). Since 6 > 2 I would rather go to the movies than the antique store. But with game theory, I could be involved in a game where there is an opposing player who would prefer to go to the antique store than the movies.

Let’s draw this game out using a matrix:

Me\Mom Movies Antique
Movies 6,2 0,0
Antique  0,0 2,6

We can summarize this matrix with the normal form representation.

  1. The number of players in the game is 2 (myself and my mom)
  2. The strategies are listed for both players. I have two strategies (represented in bold) to choose either movies or antique. My mom also has two strategies (shown in red) of movies or antique.
  3. Within each cell is a payoff for the players. (My payoffs are bold and my mom’s are red).

So the way to read this is if both my mom and I choose simultaneously to go to the movies then my payoff will be 6 and hers will be 2. If we both choose to go to an antique store, my payoff will be 2 and hers will be 6. If we make the opposite choice from each other then we will both get a payoff of 0 since we would not be together (I would rather go to the antique store than be alone). The above game is an example of Battle of the Sexes which will be analyzed later. This is a simultaneous game since there is no order of which the players must choose.

Let’s look at this other matrix:

If you are player one, which strategy would you choose and why?

1\2 Talk Avoid
Talk 4,4 -2,6
Avoid 6,-2 1,1

We will discuss this game in the next blog.