In this video, I'll talk about Rock, Paper, Scissors, which is a two-person zero-sum game
with no saddle point.
Then I'll show you how to formulate it as a linear programing problem using mixed strategies.
In a previous video titled "Two-Person Zero-Sum Game and Pure Strategy", I showed that not
all two-person constant-sum games have saddle points using pure strategies.
A pure strategy means a player always chooses the same strategy every time he or she plays
the game.
To solve such problems, we need to consider mixed strategies.
A mixed strategy means a player chooses each strategy with a certainty probability
For a player with n possible strategies, a mixed strategy is (x1, x2, … , xn), and
x1 + x2 + … + xn = 1.
If any of the probability is equal to 1, then the mixed strategy becomes a pure strategy.
Let's see an example.
Two players are playing the rock, paper, scissors game.
They must simultaneously utter one of the three words rock, paper, or scissors and show
corresponding hand signs.
If both players utter the same word, then the game is a tie.
Otherwise one player wins $1 from the other player according to the following rules.
Scissors defeats paper, paper defeats rock, and rock defeats scissors.
Find the optimal strategies for this two-person zero-sum game.
This is the payoff matrix.
If player 1 plays rock and player 2 plays rock, it's a tie and player 1 wins $0.
If player 1 plays rock and player 2 plays paper, player 1 loses $1.
If player 1 plays rock and player 2 plays scissors, player 1 wins $1.
And so on.
For each row, the minimum value is -1.
So, the maxmin is just -1.
For each column, the maximum value is +1.
So, the minmax is just +1.
There is no saddle point because -1 is not equal to +1.
That means the pure strategy does not work for this example.
Let's try the mixed strategy.
Let x1, x2, x3 be the probabilities that player 1 chooses rock, paper, and scissors, respectively.
Let y1, y2, y3 be the probabilities that player 2 chooses rock, paper, and scissors, respectively.
Now, player 1 should decide the values of x1, x2, and x3.
If player 2 plays rock, then the expected payoff for player 1 is x1 times 0, plus x2
times +1, plus x3 times -1.
If player 2 plays paper, then the expected payoff for player 1 is x1 times -1, plus x2
times 0, plus x3 times +1.
If player 2 plays scissors, then the expected payoff for player 1 is x1 times +1, plus x2
times -1, plus x3 times 0.
Player 1 knows that Player 2 will choose a strategy that makes player 1’s expected
payoff equal to the smallest one of these three, that means the minimum value of these
three.
So, Player 1 should choose x1, x2, x3 to make the minimum value as large as possible.
Let's give the minimum value of these three to v.
Because Player 1 should make v as large as possible, it is a maximization problem.
Because v is the smallest value of these three, so v should be less than or equal to each
of them.
The sum of the probabilities is 1.
The decision variables x1, x2, x3 are probabilities, so they are all between 0 and 1.
v is unrestricted in sign.
Now, player 2 should decide the values of y1, y2, and y3.
If player 1 plays rock, then his expected payoff is y1 times 0, plus y2 times -1, plus
y3 times +1.
If player 1 plays paper, then his expected payoff is y1 times +1, plus y2 times 0, plus
y3 times -1.
If player 1 plays scissors, then his expected payoff is y1 times -1, plus y2 times +1, plus
y3 times 0.
Player 2 knows that Player 1 will choose a strategy to ensure that he obtains an expected
payoff equal to the largest one of these three, that means the maximum value of these three.
So, Player 2 should choose y1, y2, y3 to make the maximum value as small as possible.
Let's give the maximum value of these three to w.
Because Player 2 should make w as small as possible, it is a minimization problem.
Because w is the largest value of these three, so w should be greater than or equal to each
of them.
The sum of the probabilities is 1.
The decision variables y1, y2, y3 are probabilities, so they are all between 0 and 1.
w is unrestricted in sign.
Here, we have Player 1's LP formulation and Player 2's LP formulation.
It turns out that player 2's LP formulation is the dual of player 1’s LP formulation.
Therefore, the optimal solutions v* is equal to w*, which is the value of the game to player
1.
This is the relation between player 1's LP formulation and player 2's LP formulation.
We can solve the problems using the simplex algorithm.
The optimal solution is v*=w*=0.
The optimal strategy for player 1 is 1/3 of the time he should play rock, 1/3 of the time
he should play paper, and 1/3 of the time he should play scissors.
The optimal strategy for player 2 is the same.
The optimal solution of a mixed strategy is called a mixed strategy Nash equilibrium.
Okay, that is Rock, Paper, Scissors game and mixed strategies.
Thanks for watching.