Each question counts for 50 points, for a total of 100 points for AN-

SWERING *** TWO *** QUESTIONS ONLY. (DO NOT SUBMIT AN-

SWERS FOR MORE THAN TWO QUESTIONS. ONLY TWO WILL BE

MARKED.)

1. (a) (25 points) Consider 2-player strategic form game, G, specied

by the following \bimatrix”:

2664

(7; 4) (9; 5) (2; 3) (2; 6)

(4; 1) (9; 2) (2; 1) (3; 6)

(8; 7) (6; 7) (5; 8) (2; 7)

(3; 3) (7; 4) (4; 6) (2; 4)

3775

As usual, player 1 is the row player, and player 2 is the column

player. If the content of the bimatrix at row i and column j is

the pair (a; b), then u1(i; j) = a and u2(i; j) = b.

Compute all of the Nash equilibria (NEs) of this game G, together

with the expected payo to each player in each NE. Explain why

any prole x that you claim is an NE of G, is indeed an NE of G,

and furthermore, explain why there are no other (pure or mixed)

NEs of G, other than the prole(s) you claim are NE(s) of G.

(b) (25 points) Consider a nite game, G, with pure strategy sets

S1; : : : ; Sn for the n players, and with a payo function ui(s)

for each player i 2 f1; : : : ; ng that assigns a payo to each pure

strategy prole s = (s1; : : : ; sn) 2 S = S1 S2 : : : Sn.

Now consider a dierent n-player game, G0, which has exactly the

same strategy sets S1; : : : ; Sn, as G, but where the payo function

u0i(s) for each player i diers from ui(s) as follows:

u0i(s) = ui(s) + gi(si)

where, for each player i, gi : Si ! R is a function (any function)

that depends only on the other players’ pure strategies and not

on player i’s own pure strategy.

Prove that G and G0 have exactly the same set of Nash equi-

libria. In other words, prove that a mixed strategy prole x =

(x1; : : : ; xn) is a NE for G if and only if x is a NE for G0.

(Note, however, that the same NE may yield entirely dierent

payos to the dierent players in G and in G0.)

2. (a) (20 points) Consider the 2-player zero-sum game given by the

following payo matrix for player 1 (the row player):

266664

5 6 4 7 3

6 4 5 3 8

7 2 5 4 6

4 7 3 5 7

3 5 8 6 3

377775

Compute both the minimax value for this game, as well as a min-

imax prole (NE), i.e. a pair of minmaximizer and maxminimizer

strategies for players 1 and 2, respectively.

(You can, for example, use the linear programming solver package

linprog in MATLAB, available on DICE machines, to do this.

To run MATLAB, type \matlab” at the shell command prompt.

For guidance on using the linprog package, see:

http://uk.mathworks.com/help/optim/ug/linprog.html.)

(b) (30 points) Recall from Lecture 7 on LP duality, the symmetric 2-

player zero-sum game, G, for which the (skew-symmetric) payo

matrix (in block form) for player 1 is:

B =24

0 A b

AT 0 c

bT cT 0

35

Suppose that there exist vectors x0 2 Rn and y0 2 Rm, such

that Ax0 < b, x0 0, AT y0 > c and y0 0. (Note the two

strict inequalities.) Prove that for the game G, every minmaxi-

mizer strategy w = (y; x; z) for player 1 (and hence also every

maxminimizer strategy for player 2, since the game is symmetric)

has the property that z > 0, i.e., the last pure strategy is played

with positive probability. (Recall that this was one of the missing

steps in our sketch proof in the lecture that the minimax theorem

implies the LP duality theorem.)

(Hint: Let w = (y; x; z) be a maxminimizer strategy for player

2 in the game G. Note that the value of any symmetric 2-player

zero-sum game must be equal to zero. This implies, by the min-

imax theorem, that Bw 0. Suppose, for contradiction, that

z = 0. What does this imply about Ax , AT y, and bT ycT x?

Then if y 6= 0, show that this implies (y)T (Ax0 b) < 0. In

turn, show that it also implies (x)T (AT y0 c) > 0. Use these

and related facts to conclude a contradiction.)

3. Consider the following simple 2-player zero-sum games, where the pay-

o table for Player 1 (the row player) is given by:

A = 1 1

1 1

We can view this as a game where each player chooses \heads” (H) or

\tails” (T), where the rst strategy for each player is denoted H and

the second strategy is denoted T.

(a) (10 points) First, what is the unique Nash equilibrium, or equiva-

lently the unique minimax prole of mixed strategies for the two

players, in this game? And what is the minimax value of that

game?

(b) (40 points) Now, suppose that the two players play the same game

you have chosen in part (a), against each other, over and over

again, for ever, and suppose that both of them use the following

method in order to update their own strategy after each round of

the game.

i. At the beginning, in the rst round, each player chooses ei-

ther of the pure strategies, H or T, arbitrarily, and plays

that.

ii. After each round, each player i accumulates statistics on how

its opponent has played until now, meaning how many Heads

and how many Tails have been played by the opponent, over

all rounds of the game played thusfar. Suppose these num-

bers are N Heads and M Tails.

Then player i uses these statistics to \guess” its opponents

\statistical mixed strategy” as follows. It assumes that its op-

ponent will next play a mixed strategy , which plays Heads

with probability N=(N+M) and plays Tails with probability

M=(N +M).

Under the assumption that its opponent is playing the \sta-

tistical mixed strategy” , in the next round player i plays a

pure strategy (H or T) that is a pure best response to .

If both H and T are a best response at any round, then

player i can use any tie breaking rule it wish in order to

determine the pure strategy it plays in the next round.

iii. They repeat playing like this forever.

Prove that, regardless how the two players start playing the game

in the rst round, the \statistical mixed strategies” of both play-

ers in this method of repeatedly playing the game will, in the long

run, as the number of rounds goes to innity, converge to their

mixed strategies in the unique Nash equilibrium of the game.

You are allowed to show that this holds using any specic tie

breaking rule that you want. Please specify the precise tie break-

ing rule you have used. (It turns out that it holds true for any

tie breaking rule. But some tie breaking rules make the proof a

lot easier than others.)

4. (a) (40 points) One variant of the Farkas Lemma says the following:

Farkas Lemma A linear system of inequalities Ax b has a

solution x if and only if there is no vector y satisfying y 0 and

yTA = 0 (i.e., 0 in every coordinate) and such that yT b < 0.

Prove this Farkas Lemma with the aid of Fourier-Motzkin elim-

ination. (Hint: One direction of the \if and only if” is easy.

For the other direction, use induction on the number of columns

of A, using the fact that Fourier-Motzkin elimination \works”.

Note basically that each round of Fourier-Motzkin elimination

can \eliminate one variable” by pre-multiplying a given system

of linear inequalities by a non-negative matrix.)

(b) (10 points) Recall that in the Strong Duality Theorem one possi-

ble case (case 4, in the theorem as stated on our lecture slides)

is that both the primal LP and its dual LP are infeasible. Give

an example of a primal LP and its dual LP, for which both are

infeasible (and argue why they are both infeasible).