# 算法代写 | Algorithmic Game Theory and Applications

这次作业是完成一个博弈论算法

Algorithmic Game Theory and Applications:

Homework 1

This homework is due at 3:00pm, on Thursday, February 27th.

This is a firm deadline. Please hand in your printed or hand-written solutions

to the ITO by that time. Do not collaborate with other students on

the coursework. Your solutions must be your own.

Each question counts for 25 points, for a total of 100 points.

1. Consider the following 2-player strategic game, G:

(13, 9) (5, 9) (7, 13) (11, 12) (17, 12)

(3, 5) (14, 5) (8, 11) (13, 4) (4, 10)

(15, 5) (10, 11) (9, 5) (6, 13) (7, 14)

(4, 11) (8, 12) (7, 4) (12, 10) (2, 9)

This is a “bimatrix”, to be read as follows: 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.

Describe all Nash equilibria of this game G.

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

NE of G.

Argue why there are no other (pure or mixed) NEs of G, other than

the profile(s) you claim are NE(s) of G.

2. Consider the 2-player zero-sum game given by the following payoff

matrix for player 1 (the row player):

0 4 3 0 5

5 7 9 4 3

3 9 0 9 4

8 9 11 3 3

7 1 4 0 9

Set up a linear program associated with this game, and use some linear

program solver to compute both the minimax value for this game,

as well as a minimax profile, i.e., ”optimal” (i.e., minmaximizer and

maxminimizer) strategies for players 1 and 2, respectively. Specify the

linear program(s) that you used to solve the game. Also, specify the

1

dual of the linear program, and explain how to interpret the variables

of the dual program.

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

linprog in MATLAB,available on DICE machines. 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.)

3. Consider the following simple 2-player zero-sum game called Matching

pennies, where the payoff table for Player 1 (the row player) is given

by:

”

1 −1

−1 1 #

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

“tails” (T), and if their choices match, then player 1 wins, but if their

choices don’t match, then player 2 wins.

(a) (3 points) First, a very easy question: what is the unique Nash

equilibrium, or equivalently the unique minimax profile of mixed

strategies for the two players, in this game?

(b) (22 points) Now, suppose that the two players play this game

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 (mixed) strategy after each round of the game.

i. At the beginning, in the first round, each player chooses either

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

that.

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

its opponents 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 numbers

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 opponent

will next play a mixed strategy σ, which plays Heads

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

M/(N + M).

2

Under the assumption that its opponent is playing the “statistical

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

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

If the statistical mixed strategy σ of the opponent is (1/2, 1/2),

then you are allowed to use any tie breaking rule you

wish in order to determine the pure strategy played in the

next round by player i.

iii. They repeat playing like this forever.

Do one of the following two things (preferably the first):

i. Prove that, regardless how the two players start playing the

game in the first round, the “statistical mixed strategies” of

both players in this method of repeatedly playing the matching

pennies game will, in the long run, as the number of

rounds goes to infinity, converge to their mixed strategies in

the unique Nash equilibrium of the game.

You are allowed to show that this holds using any specific

tie breaking rule that you want. Please specify the precise

tie breaking rule you have used. (It turns out that it hold

true for any tie breaking rule. So it would be better, but

not required, if you actually prove that any tie breaking rule

works.)

ii. Alternatively, instead of proving that it works, you can “show”

this experimentally by writing a simple program that plays

this strategy update method for both players in repeated

matching pennies, and show experimentally that, for all possible

start strategies of both players, the “statistical mixed

strategies” of the two players looks like it is converging to

their NE strategies. (You will need to provide your program

code, as well as the experimental output which shows that

convergence “looks like” it is happening.)

Note that experimentally you can only “show” that the “statistical

mixed strategies” look like they are converging to the

NE, by repeating the game some finite number of times, but

you can not be sure that they do actually converge to the

NE, without proving this. This is why a mathematical proof

is preferable.

(c) (0 points. This is a really hard question that I want you to think

about; but you do not need to submit a solution for it, unless you

want to impress us, since you get zero marks for it.)

3

Does this same method of updating strategies always converge to

statistical mixed strategies that yield a Nash Equilibrium for any

finite 2-player normal form game? If so, explain why it does. If

not, give an example of a 2-player finite game where it doesn’t

work, and argue why it doesn’t work.

4. (a) (22 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

y

T A = 0 (i.e., 0 in every coordinate) and such that y

T

b < 0.

Prove this Farkas Lemma with the aid of Fourier-Motzkin elimination.

(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) (3 points) Recall that in the Strong Duality Theorem one possible

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).

4