Game Theory and Linear Programming
Fall 2014
MP Johnson

Problem Set 1
Due: In class, 10/08/14

You're free to work with a partner, but the solutions you submit must be written "in your own words."
  1. In proving Sperner's Lemma, we verified the (trivial) base case of the single-vertex simplex $\Delta_0$. Now verify the case of $\Delta_1$: let $k$ points be placed into the 0-1 interval, decomposing it into $k+1$ subintervals, and let each point be labeled 0 or 1. Prove that on any such labeling, the number of (the $k+1$) subintervals getting both labels is odd. (Hint: you could use induction, though you don't have to.)

  2. Consider the following game: 2 players, each has to name a number (integer, say), and the one who names the bigger number wins. Does this game have an NE, pure or mixed? Explain.

  3. Consider the following game: 2 players, Bashful and Friendly, each pick a point (call them $a_B$ and $a_F$) on the unit circle. The payoffs are $u_B(a_B, a_F) = d(a_B, a_F)$ and $u_F(a_B, a_F) = -d(a_B, a_F)$, where $d(\cdot,\cdot)$ is the "as the wolf runs" arc length distance on the circle, varying between 0 and 180 degrees. (Friendly wants to be close together; Bashful doesn't.)

    1. Show that there is no pure NE.
    2. Find a mixed NE and verify that it's in equilibrium.
    3. Find and verify another mixed NE.

  4. Another "tennis" game. Let the payoff matrix be:

    L R
    U 80,30 20,50
    D 40,70 60,10

    There's no pure NE, or NE with either of the players playing pure strategies (why?), so let $(1-p,p)$ indicate player 1 (Row)'s probabilities of playing (U,D), and $(1-q,q)$ indicate player 2 (Column)'s probabilities of playing (L,R).

    1. Write down expressions, involving $q$, for Row's payoffs 1) when playing U and 2) when playing D, equate them, and solve for $q$.
    2. Similarly, write down expressions for Column's pure payoffs and solve for $p$.
    3. Plot Row's payoffs under each pure strategy, as a function of $q$ (that is, two straight lines, where the x axis is $q$, ranging from 0 to 1, and the y axis is $u_1$). Also, plot Row's BR as a function of $q$ (x axis is $q$, y axis is the value $p$ of Row's BR).
    4. Similarly, plot Column's payoffs under its pure strategies, and plot its BR.
    5. Jointly plot the BRs, indicating their intersection (x axis $q$, y axis $p$).