[SOLVED] Cs3333 game theory with computer science applications homework 1

Problem 1. Show that the two-player game illustrated in the following has a unique equilibrium. (Hint: Show that it has a unique pure-strategy equilibrium; then show that player 1,
say, cannot put positive weight on both U and M; then show that player 1, say, cannot put
positive weight on both U and D, but not on M, for instance.)





L M R
U 1,−2, −2,1 0,0
M −2,1 1,−2 0,0
D 0,0 0,0 1,1




Problem 2. Let X and Y be subsets of some vector space. Let f (x, y) be a function from X ×Y
to R. Show that
supx∈X
infy∈Y f (x, y) ≤ infy∈Y supx∈X
f (x, y).Problem 3. Find a saddle point and the value of the following zero-sum game:


4 3 1 4
2 5 6 3
1 0 7 0

Please show all the steps you used in obtaining the saddle point, such as the relevant LPs. If
you used a computer program, please attach a copy of the program.Problem 4. Repeat Problem 3 for the following matrix:


0 5 −2
−3 0 4
6 −4 0

Problem 5. Find all the NE of the following two-person nonzero-sum game
b1 b2 b3 b4
a1 (−2,2) (0,−4) (11,−5) (5,−6)
a2 (−4,0) (−1,−1) (11,−2) (4,−3)
a3 (−5,3) (−5,2) (10,0) (3,1)
a4 (−6,2) (−7,1) (1,0) (2,3)Problem 6. Consider the following nonzero game. Let (x
∗
, y
∗
) and (xˆ, yˆ) be two mixed strategy Nash equilibria of this game. Show that (x
∗
, yˆ) and (xˆ, y
∗
) are also Nash equilibria. (Hint:
Consider the sum of the payoffs of the two players.)
L R
U (4,−2) (−3,5)
D (10,−8) (0,2)Problem 7. Prove Farka’s Lemma. Let A ∈ R
m×n
and b ∈ R
m×1
. Then exactly one of the following two conditions holds:
(1) ∃x ∈ R
n×1
such that AX = b, x ≥ 0;
(2) ∃y ∈ R
1×m such that A
T
y ≥ 0, y
T b < 0;Problem 8. Prove Brouwer fixed-point theorem for one-dimensional case. Let C ∈ R be a
convex, closed and bounded set. Let f : C → C be a continuous function. Then f has a fixed
point, i.e., ∃x ∈C such that x = f (x).