Game Theory and Linear Programming
Fall 2014
MP Johnson

Problem Set 2
Due: In class, 11/03/14

You're free to work with a partner, but the solutions you submit must be written "in your own words."
  1. Consider the following two-player game. Each player chooses a real number between zero and one: $s_1,s_2 \in [0,1]$. If $s_1 < s_2$ then $u_1 = (s_1+s_2)/2$ and $u_2 = 1- (s_1+s_2)/2$; if $s_1>s_2$ the payoffs are reversed. If $s_1=s_2$ then $u_1 = u_2 = 1/2$.

    Compute all the Nash equilibria (pure? mixed?) of this game.

  2. Recall the 2-politician problem: each politician must choose a position (a real number in the [0,1] interval, let's say), voters are equally distributed across [0,1], each person votes for the politician closest to her position (dividing the vote equally if it's a tie), and each politician's payoff is the number of votes she gets (or here, the length of the subinterval of [0,1]). (So if the two politicians choose positions $(p_1,p_2)=(0,1)$ or $(.5,.5)$, for example, they split the votes equally, whereas if they choose positions $(0.1,0.2)$ then the first gets 0.15 of the votes and the second gets 0.85.)

    Now let there be 3 politicians choosing positions $(p_1,p_2,p_3$. Prove that there is no longer a pure NE. (Hint: do a case analysis: e.g., why can't a strategy profile of the form $p_1 < p_2 < p_3$ be Nash? why can't $p_1 = p_2 < p_3$ be Nash? why can't $p_1=p_2=p_3$ be Nash?)

  3. The Shoham & Leighton-Brown text proves one direction of the Minimax Theorem (Theorem 3.4.4, p74-75), calling the two players $i$ and $-i$. Prove the other direction.

  4. Add a single inequality constraint to $x_1 \ge 0, x_2 \ge 0$ so that the feasible region contains only one point.

  5. Consider the following problem:

    $\max x_1 - x_2$
    s.t.
    $-2x_1 - 3x_2 \le -4$
    $-x_1 + x_2 \le -1$
    $x_1,x_2 \ge 0$

    1. Plot the feasible region of the LP.
    2. Show that the LP is unbounded by showing that for any value $B\ge 0$ you can find a solution $(x_1,x_2)$ of value at least $B$.
    3. Construct the dual of this problem and plot its feasible region.
    4. Is the dual problem feasible? (Why/why not?)

  6. Consider the problem:

    $\min 2x_1 + x_2$
    s.t.
    $x_1+x_2 \le 6$
    $x_1+3x_2 \ge 3$
    $x_1,x_2 \ge 0$

    1. Plot the feasible region and solve the problem by inspecting your plot. Rearrange into symmetric form (i.e., all $\ge$s) and find the dual.
    2. Plot the dual and solve it by inspection.
    3. Verify that primal and dual optimal solutions satisfy the Strong Duality Theorem.