University Game Theory: Algorithms and Applications Homework 2

This document presents a student's solution to a Game Theory homework assignment from the course CS 539. The assignment covers several key game theory concepts, including the determination of mixed strategy Nash Equilibria in various game scenarios. The solution begins by analyzing a game where two players choose integers, and then proceeds to solve for mixed strategy Nash Equilibria in a coordination game, a hot-potato routing game, and the classic Rock-Paper-Scissors game. The solution provides detailed calculations, including the setup of payoff matrices and the derivation of probabilities for mixed strategies. The analysis explores how changes in game parameters, such as the cost of effort, impact the equilibrium strategies. The assignment demonstrates a solid understanding of game theory principles and the ability to apply them to solve complex strategic problems.

Running head: GAME THEORY: ALGORITHMS AND APPLICATIONS
GAME THEORY: ALGORITHMS AND APPLICATIONS
Name of the Student
Name of the University
Author Note

2GAME THEORY: ALGORITHMS AND APPLICATIONS
Question 1:
The payoff matrix of the two players rolling two integers x1 and x2 by player 1 and player 2
respectively.
x2 <= x1 x1<=x2
x1<=3x2 (1,-1) (-1,1)
x2<= 3x1 (-1,1) (1,-1)
Now, in this particular strategy there is no pure Nash equilibrium as by choosing any strategy
one player win or other player loses. Hence, the best strategy in this case will be to mix or
randomize the between the strategies such that no player gets exploited.
Now, let player 1 chooses x1 in x2 <= x1 <= 3x2 with probability p and hence, (1-p) is the
probability of choosing outside the range. Now, E(player 1) = p*1 + (1-p)*(-1). Now, the
Nash equilibrium condition is when player 1 neither gain nor loses.
Hence, p*1 + (1-p)*(-1) = 0 => 2p = 1 => p = 0.5
This is same for player 2 also.
Thus in the mixed Nash equilibrium condition player 1 chooses x1 with 50% and player 2
chooses x2 with 50% probability.
2.
The pay-off matrix for the Co-ordination game is given below.
Payoff Slack-off Effort
Slack-off (0,0) (0,-c)
Effort (-c,0) (1-c,1-c)

3GAME THEORY: ALGORITHMS AND APPLICATIONS
For calculating the mixed Nash equilibria let assume the probability of Slack-off is p and
probability of Effort is (1-p).
Hence, the payoff of player 1 if slack-off chosen by player 2 = p*0 + (1-p)*0 = 0
Now, payoff of player 1 if Effort is chosen by player 2 = p*(-c) + (1-c)*(1-p)
Hence, in equilibria
0 = p*(-c) + (1-c)*(1-p) => -pc + 1 – p – c + pc = 0 => p = c-1
Hence, if player 2 plays slack-off with probability (c-1) and Effort with probability (2-c) then
the game is in Nash equilibria.
Similarly, let player 1 plays slack-off with probability q and Effort with probability 1-q.
Hence, payoff of player 2 if slack-off by player 1= q*0 + (1-q)*(-c)
Payoff of player 2 if Effort is chosen by player 1 = q*0 + (1-c)*(1-q)
Hence, in equilibria
q*0 + (1-q)*(-c) = q*0 + (1-c)*(1-q)
 -c + qc = 1 –q –c + qc
 q = 1
Hence, mixed strategy for Nash equilibria:
Player 2: (c-1)*Slack-off + (2-c)*Effort
Player 1: Slack-off
As the value of c increases the slack-off probability for equilibria increases and the Effort
probability decreases for player 2 and player 1 will always choose slack-off. Also, c must be
in [0,1].

4GAME THEORY: ALGORITHMS AND APPLICATIONS
3.
The pay-off matrix for hot-potato or routing game is given below.
Payoff Hot-Potato Planned
Hot-Potato -4,-4 -1,-5
Planned -5,-1 -2,-2
Now, for mixed equilibrium let network provider 2 chooses Hot-potato with probability p and
Planned with probability (1-p).
Hence, Payoff(Provider 1)|hot-potato Provider 2 = -4*p + -1*(1-p) = -3p - 1
Payoff(Provider 2)|planned provider 2 = -5*p + -2*(1-p) = -3p - 2
Hence,
-4*p + -1*(1-p) = -5*p + -2*(1-p)
=> -4p -1 + p = -5p -2 + 2p
In this equation p gets cancelled and hence there exists no mixed equilibrium or all the
strategies are pure equilibria.
4.
The payoff matrix for Rock-paper-Scissor game is given below.
Payoff Rock Paper Scissor
Rock 0,0 -10,10 10,-10
Paper 10,-10 0,0 -10,10
Scissor -10,10 10,-10 0,0

5GAME THEORY: ALGORITHMS AND APPLICATIONS
Now, in mixed strategy let Player 2 plays rock with r, paper with p and scissor with (1-p-r)
Player 1 payoff for choosing rock = 0*r + -10*p + 10*(1-p-r) = -10p + 10 -10p – 10r = -20p -
10r + 10
Player 1 payoff for choosing paper = 10*r + 0*p + (1-p-r)*-10 = 10r + 10 -10p + 10r = -10p +
20r + 10
Player 1 payoff for choosing scissor = -10*r + 10*p
Now, for equilibria condition -20p -10r + 10 = -10*r + 10*p
 p = 1/3
And, -20p -10r + 10 = -10p + 20r + 10
 r = 1/3(by putting value of p)
Hence, the unique mixed strategy for rock-paper-scissor game is rock=paper=scissor= 1/3 or
with playing the game by players with same probability. This is true for player 1 also.