Game Theory: Algorithms and Applications

This document discusses various game theory problems and their solutions. It covers topics such as payoff matrix, mixed Nash equilibrium, coordination game, hot-potato game, and rock-paper-scissors game. The document also explores the algorithms and applications of game theory.

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.