算法代写 | 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