\documentclass[11pt]{article} \usepackage{amssymb,amsmath,amsthm,mathrsfs} \usepackage{tikz} \usepackage[pdftex]{hyperref} \usetikzlibrary{fit} \newcommand{\R}{{\mathbb R}} \newcommand{\Q}{{\mathbb Q}} \newcommand{\Z}{{\mathbb Z}} \newcommand{\N}{{\mathbb N}} \newcommand{\F}{{\mathcal F}} \newcommand{\G}{{\mathcal G}} \newcommand{\A}{{\mathcal A}} \newcommand{\C}{{\mathcal C}} \newcommand{\B}{{\mathcal B}} \newcommand{\val}{\ensuremath{\operatorname{val}}} \renewcommand{\P}{{\mathcal P}} \newcommand{\1}{{\mathbf 1}} \newcommand{\defined}{:=} \newcommand{\Aut}{\operatorname{Aut}} \newcommand{\im}{\operatorname{im}} \newcommand{\degree}{\operatorname{degree}} \newcommand{\divides}{\mbox{ \Large{$\vert$} }} \newcommand{\gameBox}[6]{\ensuremath{\begin{array}{|c|c|c|c|c|c|} \hline 0 & 1 & 2 & 3 & 4 & 5 \\ #1 & #2 & #3 & #4 & #5 & #6 \hline \end{array}}} \newenvironment{question}[1]{\noindent{\large{\bf{Problem #1}}}\hspace{1em} \begin{em}}{\end{em}\bigskip} \newenvironment{solution}{\noindent\ignorespaces\par\noindent \large{\bf{Solution}} }{\bigskip} \parindent=0cm \oddsidemargin=-.3in \evensidemargin=0in \textwidth=6.9in \topmargin=-.4in \textheight=9.2in \title{Math 167\\Homework 8} \author{} \begin{document} \maketitle \section*{Game Theory\\Thomas Ferguson} \subsection*{Section II.3.7} \begin{question}{15.} \textbf{Battleship.} The game of Battleship, sometimes called Salvo, is played on two square boards, usually $10$ by $10$. Each player hides a fleet of ships on his own board and tries to sink the opponent's ships before the opponent sinks his. (For one set of rules, see \href{http://www.kielack.de/games/destroya.htm}{http://www.kielack.de/games/destroya.htm}, and while you are there, have a game.)\\ For simplicity, consider a $3$ by $3$ board and suppose that Player I hides a destroyer (length 2 squares) horizontally or vertically on this board. Then Player II shoots by calling out squares on the board, one at a time. After each shot, Player I says whether the shot was a hit or a miss. Player II continues until both squares of the destroyer have been hit. The payoff to Player I is the number of shots that Player II has made. Let us label the squares from $1$ to $9$ as follows \[ \begin{array}{|c|c|c|} \hline 1 & 2 & 3 \\ \hline 4 & 5 & 6 \\ \hline 7 & 8 & 9 \\ \hline \end{array} \] The problem is invariant under rotations and reflections of the board. In fact, of the $12$ possible positions for the destroyer, there are only two distinct invariant choices available to Player I: the strategy, $[1,2]^*$, that chooses one of $[1,2],[2,3],[3,6],[6,9],[8,9],[7,8],[4,7]$ and $[1,4]$, at random with probability $1/8$ each, and the strategy, $[2,5]^*$, that chooses one of $[2,5],[5,6],[5,8]$ and $[4,5]$, at random with probability $1/4$ each. This means that invariance reduces the game to a $2$ by $n$ game where $n$ is the number of invariant strategies of Player II. Domination may reduce it somewhat further. Solve the game. Consider the mis\`ere version of the take-away game of Section 1.1, where the last player to move loses. The object is to force your opponent to take the last chip. Analyze this game. What are the target positions (P-positions)? \end{question} \begin{solution} % The invariance group is just the set of transformations of the square, this is called the Dihedral group of order $8$, and is denoted $D_4$ or $D_8$. I prefer to call it % $D_4$, so I will. $D_4$ is generated by two elements a rotation by $90\degree$, $g$, and reflection across the vertical line through the center, $r$. There is a choice of where to reflect, and the vertical line is arbitrary. It could easily % be the horizontal, or one of the diagonals. Thus we have the relations $g^4 = r^2 = e$, and $gr = rg^3$. It's not hard to check that the sets $\{ [1,2],[2,3],[3,6],[6,9],[8,9],[7,8],[4,7],[1,4] \}$ is the orbit of $[1,2]$ under this group action. % Similarly $\{[2,5],[5,6],[5,8],[4,5]\}$ is the orbit of $[2,5]$. % % To find Player II's invariant strategies, we first notice that II's pure strategies are just $\{1,\ldots,9\}$ where $i$ denotes choosing square $i$. \end{solution} \subsection*{Ferguson II.5.9} \begin{question}{1.} \textbf{The Silver Dollar.} Player II chooses one of two rooms in which to hide a silver dollar. Then, Player I, not knowing which room contains the dollar, selects one of the rooms to search. However, the search is not always successful. In fact, if the dollar is in room \#1 and I searches there, then (by a chance move) he has only probability $1/2$ of finding it, and if the dollar is in room \#2 and I searches there, then he has only probability $1/3$ of finding it. Of course, if he searches the wrong room, he certainly won't find it. If he does find the coin, he keeps it; otherwise the dollar is returned to Player II. Draw the game tree. \end{question} \begin{solution} \[ \begin{tikzpicture} [level 1/.style={sibling distance=32mm},level 2/.style={sibling distance=16mm},level 3/.style={sibling distance=16mm},every node/.style={circle}] \tikzstyle{vertex}=[circle,fill=black,inner sep=1mm] \tikzstyle{terminal}=[circle,fill=white,draw=black,inner sep=1mm] \node (root) [vertex] {} child {node (room1) [vertex] {} child {node (r1g1) [vertex] {} child {node [terminal] {1}} child {node [terminal] {0}} edge from parent node [left] {1} } child {node (r1g2) [terminal] {0} edge from parent node [right] {2} } edge from parent node [left] {1} } child {node (room2) [vertex] {} child { node (r2g1) [terminal] {0} edge from parent node [left] {1} } child { node (r2g2) [vertex] {} child {node [terminal] {1}} child {node [terminal] {0}} edge from parent node [right] {2} } edge from parent node [right] {2} }; %\draw (room1.north) -- (room2.north); %\draw (room1.south) -- (room2.south); \node [draw=black,circle,fit=(root)] {}; \node [draw=black,rectangle,rounded corners,fit=(room1) (room2)] {}; \end{tikzpicture} \] \end{solution} \begin{question}{2.} \textbf{Two Guesses for the Silver Dollar.} Draw the game tree for problem 1, if when I is unsuccessful in his first attempt to find the dollar, he is given a second chance to choose a room and search for it with the same probabilities of success, independent of his previous search. (Player II does not get to hide the dollar again.) \end{question} \begin{solution} \[ \begin{tikzpicture} [level 1/.style={sibling distance=96mm},level 2/.style={sibling distance=48mm},level 3/.style={sibling distance=24mm},level 4/.style={sibling distance=12mm},every node/.style={circle}] \tikzstyle{vertex}=[circle,fill=black,inner sep=1mm] \tikzstyle{terminal}=[circle,fill=white,draw=black,inner sep=1mm] \node (root) [vertex] {} child {node (room1) [vertex] {} child {node (r1g1) [vertex] {} child {node [terminal] {1}} child {node (r1g1m) [vertex] {} child {node (r1g11) [vertex] {} child {node [terminal] {1}} child {node [terminal] {0}} edge from parent node [left] {1} } child {node (r1g12) [terminal] {0} edge from parent node [right] {2} } } edge from parent node [left] {1} } child {node (r1g2) [vertex] {} child {node (r1g21) [vertex] {} child {node [terminal] {1}} child {node [terminal] {0}} edge from parent node [left] {1} } child {node (r1g22) [terminal] {0} edge from parent node [right] {2} } edge from parent node [right] {2} } edge from parent node [left] {1} } child {node (room2) [vertex] {} child { node (r2g1) [vertex] {} child {node (r2g11) [terminal] {0} edge from parent node [left] {1} } child {node (r2g12) [vertex] {} child {node [terminal] {1}} child {node [terminal] {0}} edge from parent node [right] {2} } edge from parent node [left] {1} } child { node (r2g2) [vertex] {} child {node [terminal] {1}} child {node (r2g2m) [vertex] {} child {node (r2g21) [terminal] {0} edge from parent node [left] {1} } child {node (r2g22) [vertex] {} child {node [terminal] {1}} child {node [terminal] {0}} edge from parent node [right] {2} } } edge from parent node [right] {2} } edge from parent node [right] {2} }; \node [draw=black,circle,fit=(root)] {}; %\node [draw=black,rectangle,rounded corners,fit=(room1) (room2)] {}; \draw (room1.north) -- (room2.north); \draw (room1.south) -- (room2.south); \draw (r1g1m.north) -- (r2g1.north); \draw (r1g1m.south) -- (r2g1.south); \draw (r2g2m.north) -- (r1g2.north); \draw (r2g2m.south) -- (r1g2.south); \end{tikzpicture} \] \end{solution} \begin{question}{10} Find the equivalent strategic form and solve the game of \begin{itemize} \item [(a)] Exercise 1. \item [(b)] Exercise 2. \end{itemize} \end{question} \begin{solution} \begin{itemize} \item [(a)] \[ \left( \begin{array}{cc} \frac{1}{2} & 0 \\ 0 & \frac{1}{3} \end{array} \right) \] Since this is a diagonal matrix, we know the value of the game is $\frac{1}{2+3} = \frac{1}{5}$ and the optimal strategies are \[ p = q = \left[ \begin{array}{cc} \frac{2}{5} & \frac{3}{5} \end{array} \right]. \] \item [(b)] \[ \begin{array}{c} (1,1) \\ (1,2) \\ (2,1)\\ (2,2) \end{array} \left( \begin{array}{cc} \frac{3}{4} & 0 \\ \frac{1}{2} & \frac{1}{3} \\ \frac{1}{2} & \frac{1}{3} \\ 0 & \frac{5}{9} \end{array} \right). \] Since this is a $4 \times 2$ matrix this can be solved via the graph method. \[ \begin{tikzpicture} \pgftransformxscale{6} \pgftransformyscale{.6} \draw[very thin,color=gray] (0,-1) grid (1,14); \draw[very thick](0,0) -- (1,0); \draw[very thick](0,-1) -- (0,14); \draw[very thick](1,-1) -- (1,14); \draw plot[very thick,domain=0:1] (\x,27/2*\x) node[right] {Row 1}; \draw plot[very thick,domain=0:1] (\x,3*\x+6) node[right] {Row 2}; \draw plot[very thick,domain=0:1] (\x,-10*\x+10) node[right] {Row 4}; \node at (-.05,1) {$\frac{1}{18}$}; \draw (4/13,0) -- (4/13,18*5/13); \node at (4/13,-.5) {$\frac{4}{13}$}; \end{tikzpicture} \] So the optimal strategy for Player II is $(4/13,9/13)$ and the value of the game is $5/13$. To find the optimal strategy for Player I, we solve the matrix \[ \left( \begin{array}{cc} \frac{1}{2} & \frac{1}{3} \\ 0 & \frac{5}{9} \end{array} \right). \] Which gives the optimal strategy for Player I is $(0,10/13,0,3/13)$. In fact, since rows 2 and 3 are the same, the $10/13$ can be split in any way among them. \end{itemize} \end{solution} \subsection*{Ferguson III.2.5} \begin{question}{1.} \textbf{Strategic Equilibria Are Individually Rational.} A payoff vector is said to be \emph{individually rational} if each player receives at least his safety level. Show that if $(p,q)$ is a strategic equilibrium for the game with matrices $A$ and $B$, then $p^TAq \ge v_I$ and $p^TBq \ge v_{II}$. Thus, the payoff vector for strategic equilibrium is individually rational. \end{question} \begin{solution} Since $(p,q)$ is a strategic equilibrium, we have \begin{align*} \forall p^\prime \quad g_1(p,q) \ge g_1(p^\prime,q),\\ \forall q^\prime \quad g_2(p,q) \ge g_2(p,q^\prime). \end{align*} Rewriting this in terms of matrices we have \begin{align*} \forall p^\prime \quad p^TAq \ge (p^\prime)^TAq, \\ \forall q^\prime \quad p^TBq \ge p^TBq. \end{align*} so \begin{align*} \max_{p^\prime} (p^\prime)^TAq = p^TAq, \\ \max_{q^\prime} p^TBq^\prime = p^TBq. \end{align*} Now, \[ v_I = \max_p \min j \sum_{i=1}^m p_i a_{ij} = \max_p \min_q p^TAq, \] and \[ v_{II} = \max_q \min i \sum_{j=1}^n b{ij}q_j = \max_q \min_p p^TBq, \] But now, the inequalities are clear \[ \min_{q^\prime} (p^\prime)^T Aq^\prime \le p^\prime Aq \quad \mbox{ for all $p^\prime$}, \] taking the max over $p^\prime$ of both sides gives \[ v_I = \max_{p^\prime} \min_{q^\prime} (p^\prime)^TAq^\prime \le \max_{p^\prime} (p^\prime)^TAq = p^TAq. \] Similarly \[ \min_{p^\prime} (p^\prime)^T Bq^\prime \le pBq^\prime \quad \mbox{ for all $q^\prime$}, \] taking the max over $q^\prime$ of both sides gives \[ v_I = \max_{q^\prime} \min_{p^\prime} (p^\prime)^TBq^\prime \le \max_{q^\prime} p^TBq^\prime = p^TBq. \] \end{solution} \begin{question}{4.} \textbf{An extensive form non-zero-sum game.} A coin with probability $2/3$ of heads and $1/3$ of tails is tossed and the outcome is shown to player I but not to player II. Player I then makes a claim which may be true or false that the coin turned up heads or that the coin turned up tails. Then, player II, hearing the claim, must guess whether the coin came up heads or tails. Player II wins \$3 if his guess is correct, and nothing otherwise. Player I wins \$3 if I has told the truth in his claim. In addition, player I wins an additional \$6 if player II guesses heads. \begin{itemize} \item [(a)] Draw the Kuhn tree. \item [(b)] Put into strategic (bimatrix) form. \item [(c)] Find all PSE's. \end{itemize} \end{question} \begin{solution} \begin{itemize} \item [(a)] \[ \begin{tikzpicture} [level distance=32mm,level 1/.style={sibling distance=96mm},level 2/.style={sibling distance=48mm},level 3/.style={sibling distance=24mm},level 4/.style={sibling distance=12mm},every node/.style={circle}] \tikzstyle{vertex}=[circle,fill=black,inner sep=1mm] \tikzstyle{terminal}=[circle,fill=white,draw=black,inner sep=1mm] \node (root) [vertex] {} child {node (H) [vertex] {} child {node (HcH) [vertex] {} child {node (HcHgH) [terminal] {(9,3)} edge from parent node [left] {gH} } child {node (HcHgT) [terminal] {(3,0)} edge from parent node [right] {gT} } edge from parent node [left] {cH} } child {node (HcT) [vertex] {} child {node (HcTgH) [terminal] {(6,3)} edge from parent node [left] {gH} } child {node (HcTgT) [terminal] {(0,0)} edge from parent node [right] {gT} } edge from parent node [right] {cT} } edge from parent node [left] {H} } child {node (T) [vertex] {} child {node (TcH) [vertex] {} child {node (TcHgH) [terminal] {(6,0)} edge from parent node [left] {gH} } child {node (TcHgT) [terminal] {(0,3)} edge from parent node [right] {gT} } edge from parent node [left] {cH} } child {node (TcT) [vertex] {} child {node (TcTgH) [terminal] {(9,0)} edge from parent node [left] {gH} } child {node (TcTgT) [terminal] {(3,3)} edge from parent node [right] {gT} } edge from parent node [right] {cT} } edge from parent node [right] {T} }; \node [draw=black,circle,fit=(H)] {}; \node [draw=black,circle,fit=(T)] {}; \draw [-] (HcH.north) to [bend right=10] (TcH.north); \draw [-] (HcH.south) to [bend right=10] (TcH.south); \draw [-] (HcT.north) to [bend left=10] (TcT.north); \draw [-] (HcT.south) to [bend left=10] (TcT.south); %\draw (HcT.north) -- (TcT.north); %\draw (HcT.south) -- (TcT.south); \end{tikzpicture} \] \item [(b)] Player I has four strategies \begin{align*} HH &\mbox{:Call heads if the coin is heads, and call heads if the coin is tails} \\ HT &\mbox{:Call heads if the coin is heads, and call tails if the coin is tails} \\ TH &\mbox{:Call tails if the coin is heads, and call heads if the coin is tails} \\ TT &\mbox{:Call tails if the coin is heads, and call tails if the coin is tails} \\ \end{align*} Similarly, Player II has four strategies \begin{align*} HH &\mbox{:Guess heads if Player I calls heads, and call heads if Player I calls tails} \\ HT &\mbox{:Guess heads if Player I calls heads, and call tails if Player I calls tails} \\ TH &\mbox{:Guess tails if Player I calls heads, and call heads if Player I calls tails} \\ TT &\mbox{:Guess tails if Player I calls heads, and call tails if Player I calls tails} \\ \end{align*} Thus the game matrix becomes \[ \begin{array}{c|c|c|c|c|} & HH & HT & TH & TT \\ \hline HH & (8,2) & (8,2) & (1,2) & (1,2) \\ \hline HT & (9,2) & (7,3) & (5,0) & (3,1) \\ \hline TH & (6,2) & (2,0) & (4,3) & (0,1) \\ \hline TT & (7,2) & (1,1) & (7,2) & (1,1) \\ \hline \end{array} \] \item [(c)] \[ \begin{array}{c|c|c|c|c|} & HH & HT & TH & TT \\ \hline HH & (8,2^*) & (8^*,2^*) & (1,2^*) & (1,2^*) \\ \hline HT & (9^*,2) & (7,3^*) & (5,0) & (3^*,1) \\ \hline TH & (6,2) & (2,0) & (4,3^*) & (0,1) \\ \hline TT & (7,2^*) & (1,1) & (7^*,2^*) & (1,1) \\ \hline \end{array} \] Thus the PSEs are I chooses HH and II chooses HT, and I chooses TT and II Chooses TH. \end{itemize} \end{solution} \begin{question}{6.} Consider the bimatrix game \[ \left( \begin{array}{ccc} (0,0) & (1,2) & (2,0) \\ (0,1) & (2,0) & (0,1) \end{array} \right) \] \begin{itemize} \item [(a)] Find the safety levels for the two players. \item [(b)] Find all PSE's. \item [(c)] Find all SE's given by mixed equalizing strategies. \end{itemize} \end{question} \begin{solution} \begin{itemize} \item [(a)] Splitting the bimatrix into two matrices $A$ and $B$, we have \[ A = \left( \begin{array}{ccc} 0 & 1 & 2 \\ 0 & 2 & 0 \end{array} \right) \quad B^T = \left( \begin{array}{cc} 1 & 0 \\ 0 & 2 \\ 1 & 0 \end{array} \right) \] Now, $v_I = \val(A)$, and $v_{II} = \val{B^T}$. These are easy to calculate. $\val(A) = 0$, since $0$ is a saddle point. For, $B^T$, the last row is dominated, so we remove it, and the matrix becomes diagonal, thus the value is $1/(1/2+1) = 2/3$. \item [(b)] \[ \left( \begin{array}{ccc} (0^*,0) & (1,2^*) & (2^*,0) \\ (0^*,1^*) & (2^*,0) & (0,1^*) \end{array} \right) \] Thus the only PSE is Player I plays $(0,1)$ and Player II plays $(1,0,0)$. \item [(c)] To find the equalizing strategy, remember that we are equalizing \emph{the opponent's} winnings. For Player I if he chooses row 1 with probability $p$, then equalizing, we have \[ 1-p = 2p = 1-p \Rightarrow p = \frac{1}{3}. \] Thus Player I's equalizing strategy is $(1/3,2/3)$. For Player II, if he chooses column $j$ with probability $q_j$, equalizing gives \[ 2q_2 = q_2+2q_3. \] Using the equation $q_1+q_2+q_3 = 1$, and $0 \le q_j \le 1$, we have the equalizing strategy $(1-3q,2q,q)$ for any $q$ satisfies $0 \le q \le 1/3$. As $q$ increases, so do I's average payoffs, however, for any fixed value of $q$, Player I is indifferent between row 1 and row 2. \end{itemize} \end{solution} \subsection*{Additional Problems} \begin{question}{1.} For the matrix \[ \left( \begin{array}{cccc} 3 & 2 & 4 & 0 \\ -2 & 1 & -4 & 5 \end{array} \right) \] do the following: \begin{itemize} \item [(a)] Write down the linear program that defines an optimal strategy of Player I. \item [(b)] Each inequality in the program says that the value V has to be in a certain half-plane (on one side of a certain line). Draw those lines on the plane and mark the regions which are defined by the inequalities. \item [(c)] Find the solution V for your linear program. \item [(d)] Explain why the procedure above is precisely what you would have done in order to solve this $2\times 4$ game. \end{itemize} \end{question} \begin{solution} \begin{itemize} \item [(a)] Suppose Player I chooses row 1 with probability $p$, then the linear program becomes maximize $v$ such that: \begin{align*} v &\le 3p -2(1-p) = 5p-2 \\ v &\le 2p+(1-p) = p+1\\ v &\le 4p-4(1-p) = 8p - 4 \\ v &\le 5(1-p) = -5p+5\\ p &\ge 0\\ p &\le 1. \end{align*} While the book suggests using $p_1,p_2,\ldots,p_m$ for the probabilities of the rows, when there are only two rows it seems more natural to call the probabilities $p$ and $1-p$ instead of $p_1$ and $p_2$.\\ \item [(b)] \[ %This is my first attempt to draw a bunch of half-planes. It's not the cleanest thing, but it seems to work. %Note the 'use as bounding box' command. This doesn't do any cropping, it just says: pretend this is the border of the picture when determining its position (e.g. when centering) \begin{tikzpicture}[xscale=7] \draw [use as bounding box,draw=black!60] (0,-4) grid (1,5); %Draw the half-planes \pgfmathatan{5} %Note pgfmathatan{x} sets the variable \pgfmathresult to arctan(x) \draw [draw=black!70,fill=black!40,rotate around={\pgfmathresult:(0,-2)},opacity=.5] (-2,-2) rectangle (6,-4); \pgfmathatan{1} \draw [draw=black!70,fill=black!40,rotate around={\pgfmathresult:(0,1)},opacity=.5] (-4,1) rectangle (3,-4); \pgfmathatan{8} \draw [draw=black!70,fill=black!40,rotate around={\pgfmathresult:(0,-4)},opacity=.5] (-2,-4) rectangle (9,-5); \pgfmathatan{-5} \draw [draw=black!70,fill=black!40,rotate around={\pgfmathresult:(0,5)},opacity=.5] (-1,5) rectangle (10,3); %Crop business \draw [fill=white,draw=white] (1,-5) rectangle (4,6); \draw [fill=white,draw=white] (-3,5) rectangle (2,5.5); \draw [fill=white,draw=white] (-3,-5) rectangle (0,6); \draw [fill=white,draw=white] (-3,-7) rectangle (2,-4); %Draw the axes \draw [->,very thick] (0,0) -- (1.1,0); \draw [->,very thick] (0,0) -- (0,5.7); \end{tikzpicture} \] \item [(c)] The maximum point in the intersection of all the half-planes is at the intersection of $5p-2$ and $-5p+5$, which occurs at $(7/10,3/2)$. Thus $p = 7/10$, $v = 3/2$. \item [(d)] To solve the $2 \times 4$ game by using the method outlined in the book, we would have drawn these lines and found the maximal point on the lower envelope. But this is exactly what we have just done. \end{itemize} \end{solution} \begin{question}{2.} For the same matrix \[ \left( \begin{array}{cccc} 3 & 2 & 4 & 0 \\ -2 & 1 & -4 & 5 \end{array} \right) \] do the following: \begin{itemize} \item [(a)] Write down the linear program that defines an optimal strategy of Player II. \item [(b)] What kind of a region does each inequality define? \item [(c)] Explain why I am not asking you to draw the graphs and mark the regions defined by the inequalities. \item [(d)] Does the solution V you've found in the previous problem equal the solution W for this linear program? Why? \end{itemize} \end{question} \begin{solution} \begin{itemize} \item [(a)] Maximize $w$ such that \begin{align*} w &\le 3q_1 + 2q_2 + 4q_3 \\ w &\le -2q_1 +q_2 -4q_3 + 5q_4\\ q_1&+q_2+q_3+q_4 = 1\\ q_i &\ge 0. \end{align*} \item [(b)] Each of the inequalities on $w$ define a half-space in four dimensional space. \item [(c)] Because, even with the amazing graphics program \href{http://sourceforge.net/projects/pgf}{pgf} at our disposal, it is very difficult to render 4-dimensional space on a 2-dimensional page. \item [(d)] Yes, this is exactly the minimax theorem. In the provious problem we calculated the lower value, and solving this linear program would calculate the upper value. \end{itemize} \end{solution} \begin{question}{3.} Give an example of a matrix with more than 2 rows which is invariant under a permutation that switches the first two rows and fixes the rest. What does this say about the optimal strategies? \end{question} \begin{solution} Any matrix with more than two rows that satisfies $R_1 = R_2$ is a trivial solution. Here's a slightly more interesting example. \[ \left( \begin{array}{cccc} 1 & 2 & 3 & 4 \\ 3 & 4 & 1 & 2 \\ 1 & 2 & 1 & 2 \end{array} \right) \] This tells us that there exists an optimal strategy for Player I where the first and second rows have equal weight. Note this \emph{does not} say that all optimal strategies give the first and second row equal weight. \end{solution} \begin{question}{4.} Give an example of a matrix with 4 rows which is invariant under the permutation that switches the first two rows as well as the last two rows. What does this say about the optimal strategies? \end{question} \begin{solution} Again, any matrix that satisfies $R_1 = R_2$ and $R_3 = R_4$ is a trivial solution. Here is a slightly more interesting example \[ \left( \begin{array}{cccc} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \end{array} \right) \] You can easily make a game like this. Suppose each player picks a number in $\{1,2,3,4\}$ if the sum of their numbers is odd Player I gets $1$, otherwise he gets nothing. Clearly, this is invariant under changing the names of $1,3$ and $2,4$. We were asked for a matrix in which we could interchange $1,2$ and $3,4$, so we jus reorganize the matrix from the parity-game just described and end up with the matrix above.\\ Since the game is invariant under swapping the first two rows and the last two rows, this tells us that \emph{there exists} an optimal strategy for Player I giving equal weight to the first two rows and the last two rows. \end{solution} \begin{question}{5.} True or false: if a matrix is invariant under a permutation that does not fix any rows, then there is an optimal strategy in which all the rows get equal probabilities? \end{question} \begin{solution} \textbf{False.}\\ Just because no rows are fixed does not imply that the action is transitive, i.e. that there is only one orbit. For a counterexample we can modify the previous example. \[ \left( \begin{array}{cccc} 2 & 3 & 2 & 3 \\ 3 & 2 & 3 & 2 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \end{array} \right) \] This matrix is still invariant under a permutation that swaps the first two rows, and a permutation that swaps the last two rows, hence it is invariant under the composition permutation that swaps the first two and the last two. This permutation leaves no rows fixed, but clearly any strategy that gives positive weight to row 3 or row 4 cannot be optimal. \end{solution} \begin{question}{6.} True or false: if a matrix A is invariant under a ``cyclic shift" of the rows (see below), then there is an optimal strategy in which all the rows get equal probabilities? A cyclic shift puts the first row in place of the second one, the second in place of the third, etc, and the last one in place of the first. \end{question} \begin{solution} \textbf{True.} If a ``cyclic shift'' of the rows is in the invariant group, then by composing it with itself $k$ times, we have an invariant permutation that takes row $i$ to row $i + k \mod m$. Since we can map row $i$ to any row $j$ in this manner, the action is transitive, i.e. there is exactly one orbit, so there is a strategy for Player I giving equal weight to all of the rows. \end{solution} \begin{question}{7.} Show that if a bimatrix $AB$ represents a 0-sum game (what does this mean?), then an entry $(a,b)$ is a PSE if and only if it is a saddle point of the appropriate $A^\prime$ matrix representing the same game (how do you get $A^\prime$ from $AB$?). \end{question} \begin{solution} If a bimatrix $AB$ represents a zero-sum game, than every entry $(a,b)$ has $b = -a$. Thus if $AB = ((a_{ij},b_{ij}))$, then $A^\prime = (a_{ij})$. Now, the $i^*$th row and $j^*$th column represents a PSE in the game $AB$. if and only if \[ a_{i^*j^*} \ge a_{ij^*} \quad \forall j, \] and \[ b_{i^*j^*} \ge b_{i^*j} \quad \forall i, \] since $b_{ij} = -a_{ij}$, multiplying the previous equation by $-1$ gives \[ a_{i^*j^*} \le a_{i^*j} \quad \forall j. \] But these are exactly the criteria for a saddle point. \end{solution} \begin{question}{8.} True or false: in every bimatrix $1\times n$ there is a PSE. \end{question} \begin{solution} \textbf{True.}\\ Since Player I has no choice, the PSE is just where Player II chooses the column where his payoff is maximized. \end{solution} \begin{question}{9.} True or false: in every bimatrix $m\times 1$ there is a PSE. \end{question} \begin{solution} \textbf{True.}\\ Since Player II has no choice, the PSE is just where Player I chooses the row where his payoff is maximized. \end{solution} \begin{question}{10.} True or false: in every bimatrix $2\times 2$ there is a PSE. \end{question} \begin{solution} \textbf{False.}\\ Consider \[ \left( \begin{array}{cc} (0,1) & (1,0) \\ (1,0) & (0,1) \end{array} \right) \] \end{solution} \begin{question}{11.} Prove (assuming Nash's Equilibrium Theorem) the Minimax Theorem. Recall that the precise statement of the Minimax Theorem appears at the end of II.4.2, and Nash's Theorem appears at the end of III.2.1. \end{question} \begin{solution} % To prove this, it suffices to notice that in a zero-sum game, the safety level for Player I is simply the lower value of the game $\underbar{V}$. Now, after multiplying by $-1$ we see that the safety level for % Player II corresponds exactly to the upper value of the game $\bar{V}$. Now, Nash's Theorem tells us that there exists a strategic equilibrium, and by III.2.5 exercise 1, we know that following this strategic equilibrium % both players achieve their safety levels. Thus the payoff is Suppose $A$ is a matrix for a zero-sum game. Nash's Theorem tells us that there is a strategic equilibrium given by strategies $p^*,q^*$. Strategic equilibria satisfy \[ (p^*)^TAq^* = \max_p p^TAq^*, \] and \[ (p^*)^TAq^* = \min_q (p^*)^TAq. \] This gives us \[ (p^*)^TAq^* = \min_q (p^*)^TAq \le \max_p \min_q p^TAq = \underbar{V} \le \overline{V} = \min_q \max_p p^TAq \le \max_p p^TAq^* = (p^*)^TAq^*. \] Thus $\underbar{V} = \overline{V}$ which is the minimax theorem. \end{solution} \end{document}