\documentclass[11pt]{article}
\usepackage{amssymb,amsmath,amsthm,mathrsfs}
\usepackage[all]{xy}
\usepackage{tikz}
\usetikzlibrary{matrix}

\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}{\rule[-1.2ex]{0pt}{0pt}} %Struts
\newcommand{\T}{\rule{0pt}{2.6ex}}	%Struts
\renewcommand{\P}{{\mathcal P}}
\renewcommand{\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 7}
\author{}

\begin{document}
	\maketitle
	\section*{Game Theory\\Thomas Ferguson}
	\subsection*{Section II.3.7}
	\begin{question}{1.}
		Consider the game with matrix
		\[
			\begin{tikzpicture}
				\matrix [matrix of math nodes,left delimiter=(,right delimiter=)]
				{
					-2 & 2 & -1 \\
					1  & 1 & 1 \\
					3 & 0 & 1 \\
				};
			\end{tikzpicture}
		\]

	\begin{itemize}
		\item [(a)]
			Note that this game has a saddle point.
		\item [(b)]
			Show that the inverse of the matrix exists.
		\item [(c)]
			Show that II has an optimal strategy giving positive weight to each of his columns.
		\item [(d)]
			Why then, don't equations (16) give an optimal strategy for II?
	\end{itemize}

	\end{question}

	\begin{solution}
		\begin{itemize}
			\item [(a)]
				This is a saddle point.
				\[
					\begin{tikzpicture}
						\matrix [matrix of math nodes,left delimiter=(,right delimiter=)]
						{
							-2 & 2 & -1 \\
							1  & 1 & \node [circle,draw=black,fill=white] {1}; \\
							3 & 0 & 1 \\
						};
					\end{tikzpicture}
				\]
			\item [(b)]
				This matrix is invertible because its determinant is $5$.  In fact, its inverse is	
				\[
					\begin{tikzpicture}
						\matrix [matrix of math nodes,left delimiter=(,right delimiter=)]
						{
							\frac{1}{5} & \frac{-2}{5} & \frac{3}{5} \\
							\frac{2}{5} & \frac{1}{5} & \frac{1}{5} \\
							\frac{-3}{5} & \frac{6}{5} & \frac{4}{5} \\
						};
					\end{tikzpicture}
				\]
			\item [(c)]
				One optimal strategy for II is to play $q = \left[ \begin{array}{ccc} \frac{1}{4} & \frac{1}{2} & \frac{1}{4} \end{array} \right]$.  Then 
				$Aq = \left[ \begin{array}{ccc} \frac{1}{4} & 1 & 1 \end{array} \right]$.  Since the value of the game is 1, this strategy is optimal.
			\item [(d)]
				If we set $q = A^{-1}\1/\1^TA^{-1}\1 = \left[ \begin{array}{ccc} \frac{2}{5} & \frac{4}{5} & \frac{-1}{5} \end{array} \right]$.

				This is not a valid strategy for II because the assumption for equation (16) to hold is that \emph{Player I} has an optimal strategy with all rows active.  This is not the case.

				Since Player II has an all-active strategy we can perform this analysis from II's perspective, but in that case we use the matrix $-A^T$, doing that, yields the optimal strategy 
				$p = \left[ \begin{array}{ccc} 0 & 1 & 0 \end{array} \right]$.
		\end{itemize}
	\end{solution}

	\begin{question}{2.}
		Consider the diagonal matrix game with matrix 
		\[
			A = \left( \begin{array}{cccc} d_1 & 0 & \cdots & 0 \\ 0 & d_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & d_m \end{array} \right).
		\]

		\begin{itemize}
			\item [(a)]
				Suppose one of the diagonal terms is zero.  What is the value of the game?
			\item [(b)]
				Suppose one of the diagonal terms is positive and another is negative.  What is the value of the game?
			\item [(c)]
				Suppose all diagonal terms are negative.  What is the value of the game?
		\end{itemize}

	\end{question}

	\begin{solution}
		\begin{itemize}
			\item [(a)]
				If all the other diagonal terms remain positive, then that column dominates all the others, so the value of the game is 0, and the optimal strategy is for II to choose that column.
			\item [(b)]
				If $d_i > 0$ and $d_j < 0$, then $a_{ij} = 0$ is a saddle point because $a_{ij} < d_i = a_{ii}$ so it's the minimum of its row, but $a_{ij} > d_j = a_{jj}$ so it's the maximum of its column.
				So the value of the game is $0$, and both players have optimal pure strategies.
			\item [(c)]
				We can simply multiply the matrix by negative 1, and analyze it the same was as before to get the value is $v = \frac{-1}{\sum_i \frac{1}{d_i}}$.  If you prefer, you can view this as viewing the game from Player II's perspective since $-A^T = -A$.
		\end{itemize}
	\end{solution}

	\begin{question}{3.}
		Player II chooses a number $j \in \{1,2,3,4\}$, and Player I tries to guess what number II has chosen.  If he guesses correctly and the number was $j$, he wins $2^j$ dollars from 
		II.  Otherwise there is no payoff.  Set up the matrix for this game and solve.
	\end{question}

	\begin{solution}
				\[
					\begin{tikzpicture}
						\matrix [matrix of math nodes,left delimiter=(,right delimiter=)]
						{
							2 & 0 & 0 & 0\\ 
							0 & 4 & 0 & 0 \\ 
							0 & 0 & 8 & 0 \\ 
							0 & 0 & 0 & 16 \\
						};
					\end{tikzpicture}
				\]
				
				Following the analysis for diagonal matrices in the book, we have
				\[
					V = \frac{1}{\frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \frac{1}{16}} = \frac{16}{15},
				\]
				\[
					p = q = \left[ \begin{array}{cccc} \frac{8}{15} & \frac{4}{15} & \frac{2}{15} & \frac{1}{15} \end{array} \right].
				\]
	\end{solution}

	\begin{question}{4.}
		Player II chooses a number $j \in \{1,2,3,4\}$ and I tries to guess what it is.  If he guesses correctly, he wins 1.  If he overestimates he wins $1/2$ from II.  If he underestimates, 
		there is no payoff.  Set up the matrix of this game and solve.
	\end{question}

	\begin{solution}
		The matrix looks like
			\[
				\begin{tikzpicture}
					\matrix [matrix of math nodes,left delimiter=(,right delimiter=)]
					{
						1 & \frac{1}{2} & \frac{1}{2} 	& \frac{1}{2} \\
						0 & 1			& \frac{1}{2} 	& \frac{1}{2} \\
						0 & 0			& 1				& \frac{1}{2} \\
						0 & 0			& 0				& 1	\\
					};
				\end{tikzpicture}
			\]
			Solving for Player I's optimal strategy, $p$, we have
			\begin{align*}
				p_1	&= V \\
				\frac{1}{2}p_1 + p_2 &= V \\
				\frac{1}{2}p_1 + \frac{1}{2}p_2 + p_3 &= V \\
				\frac{1}{2}p_1 + \frac{1}{2}p_2 + \frac{1}{2}p_3 + p_4 &= V
			\end{align*}
			
			Thus
			\[
				p_1 = V \quad p_2 = \frac{1}{2}V \quad p_3 = \frac{1}{4}V \quad p_4 = \frac{1}{8}V.
			\]

			Since
			\[	
				p_1 + p_2 + p_3 + p_4 = 1,
			\]
			we have $V = \frac{8}{15}$.
			Thus 
			\[
				p = \left[ \begin{array}{cccc} \frac{8}{15} & \frac{4}{15} & \frac{2}{15} & \frac{1}{15} \end{array} \right].
			\]

			For Player II's optimal strategy, we solve
			\begin{align*}
				q_4	&= V \\
				\frac{1}{2}q_4 + p_3 &= V \\
				\frac{1}{2}q_4 + \frac{1}{2}q_3 + q_2 &= V \\
				\frac{1}{2}q_4 + \frac{1}{2}q_3 + \frac{1}{2}q_2 + q_1 &= V
			\end{align*}
			
			Thus 
			\[
				q = \left[ \begin{array}{cccc} \frac{1}{15} & \frac{2}{15} & \frac{4}{15} & \frac{8}{15} \end{array} \right].
			\]
			
	\end{solution}

	\begin{question}{5.}
		Player II chooses a number $j \in \{1,2,\ldots,n\}$ and I tries to guess what it is.  If he guesses correctly, he wins 1.  If he guesses too high, he loses 1.  If he guesses too 
		low, there is no payoff.  Set up the matrix and solve.
	\end{question}

	\begin{solution}
		So the matrix looks like
		\[
			\begin{tikzpicture}
				\matrix [matrix of math nodes,left delimiter=(,right delimiter=)]
				{
					1 & 0 & \cdots & 0 \\
					-1 & 1  & \ddots & \vdots \\
					\vdots & \ddots & \ddots & 0 \\
					-1 & \cdots & -1 & 1 \\
				};
			\end{tikzpicture}
		\]
		Solving for $p$, this yields equations
		\begin{align*}
			q_1	& = V \\
			-q_1 + q_2 &= V \\
			-q_1 -q_2 +q_3 &= V \\
			-q_1 -p_2 -q_3 + q_4 &= V \\
			&\vdots \\
			-q_1 -q_2 \cdots -q_{n-1} + q_n &= V.
		\end{align*}

		This gives $q_i = 2^{i-1}V$.  Since $\sum_i q_i = 1$, we have
		\[
			1 = \sum_{i=1}^n q_i = \sum_{i=1}^n 2^{i-1}V = V \sum_{i=1}^n 2^{i-1} = (2^n-1)V.
		\]

		Thus $V = \frac{1}{2^n-1}$, and 
		\[
			q = \left[ \begin{array}{cccc} \frac{1}{2^n-1} & \frac{2}{2^n-1} & \cdots & \frac{2^{n-1}}{2^n-1} \end{array} \right]. 
		\]
		Similarly, 
		\[
			p = \left[ \begin{array}{cccc} \frac{2^{n-1}}{2^n-1} & \frac{2^{n-2}}{2^n-1} & \cdots & \frac{1}{2^n-1} \end{array} \right]. 
		\]
	\end{solution}

	\begin{question}{8.}
		Solve the games with the following matrices.
		\begin{itemize}
			\item [(a)]
				\[
					\begin{tikzpicture}
						\matrix [matrix of math nodes,left delimiter=(,right delimiter=)]
						{
							1 & -1 & -1 \\
							0 & 2 & 1 \\
							0 & 0 & 3 \\
						};
					\end{tikzpicture}
				\]
			\item [(b)]
				\[
					\begin{tikzpicture}
						\matrix [matrix of math nodes,left delimiter=(,right delimiter=)]
						{
							2 & 1 & 1 & 1 \\
							1 & \frac{3}{2} & 1 & 1 \\
							1 & 1& \frac{4}{3} & 1 \\
							1 & 1 & 1 & \frac{5}{4} \\
						};
					\end{tikzpicture}
				\]
			\item [(c)]
				\[
					\begin{tikzpicture}
						\matrix [matrix of math nodes,left delimiter=(,right delimiter=)]
						{
							2 & 0 & 0 & 2 \\
							0 & 3 & 0 & 0 \\
							0 & 0 & 4 & 3 \\
							1 & 1 & 0 & 1 \\
						};
					\end{tikzpicture}
				\]
		\end{itemize}
	\end{question}

	\begin{solution}
		\begin{itemize}
			\item [(a)]
				Solving for player I's optimal strategy, we have
				\begin{align*}
					p_1 &= V \\
					-p_1 + 2p_2 &=V \\
					-p_1 + p_2 +3p_3 &= V.
				\end{align*}

				Thus
				\[
					p_1 = V \quad p_2 = V \quad p_3 = \frac{V}{3}.
				\]
				Since $\sum_i p_i = 1$, we have $V = \frac{3}{7}$.

				Player II's optimal strategy, $q$, satisfies
				\begin{align*}
					3q_3 &= V \\
					q_3 + 2q_2 &=V \\
					-q_3 -q_2 + q_1 &= V.
				\end{align*}

				Thus 
				\[
					q_1 = \frac{V}{3} \quad q_2 = \frac{V}{3} \quad q_3 = \frac{5}{3} V.
				\]
				
				Plugging in the value for $V$ gives
				\[
					p = \left[ \begin{array}{ccc} \frac{3}{7} & \frac{3}{7} & \frac{1}{7} \end{array} \right] \qquad q = \left[ \begin{array}{ccc} \frac{1}{7} & \frac{1}{7} & \frac{5}{7} \end{array} \right].
				\]
			\item [(b)]
				By subtracting one from  every component of the matrix, we can turn it into a diagonal matrix
				\[
					\begin{tikzpicture}
						\matrix [matrix of math nodes,left delimiter=(,right delimiter=)]
						{
							1 & 0 & 0 & 0 \\
							0 & \frac{1}{2} & 0 & 0 \\
							0 & 0 & \frac{1}{3} & 0 \\
							0 & 0 & 0 & \frac{1}{4} \\
						};
					\end{tikzpicture}
				\]
				
				This game has value
				\[
					V = \frac{1}{1 + 2 + 3  +4} = \frac{1}{10},
				\]

				and the optimal strategies are
				\[
					p = q = \left[ \begin{array}{cccc} \frac{1}{10} & \frac{2}{10} & \frac{3}{10} & \frac{4}{10} \end{array} \right]
				\]

				Now we need to relate this to the original game.  The value is $\frac{11}{10}$, and the optimal strategies remain the same.
			\item [(c)]
				Notice that $\frac{1}{2}R_1 + \frac{1}{2}R_2$ dominates $R_4$, so
				\[
					\begin{tikzpicture}
						\matrix [matrix of math nodes,left delimiter=(,right delimiter=)] (A)
						{
							2 & 0 & 0 & 2 \\
							0 & 3 & 0 & 0 \\
							0 & 0 & 4 & 3 \\
							1 & 1 & 0 & 1 \\
						};
						\draw (A-4-1.west) -- (A-4-4.east);
					\end{tikzpicture}
				\]
				Now the first column dominates the last column.
				\[
					\begin{tikzpicture}
						\matrix [matrix of math nodes,left delimiter=(,right delimiter=)] (A)
						{
							2 & 0 & 0 & 2 \\
							0 & 3 & 0 & 0 \\
							0 & 0 & 4 & 3 \\
							1 & 1 & 0 & 1 \\
						};
						\draw (A-4-1.west) -- (A-4-4.east);
						\draw (A-1-4.north) -- (A-3-4.south);
					\end{tikzpicture}
				\]

				Now the matrix is diagonal, so the value is
				\[
					V = \frac{1}{\frac{1}{2}+\frac{1}{3}+\frac{1}{4}} = \frac{12}{13},
				\]
				and
				\[
				 	p = q = \left[ \begin{array}{ccc} \frac{1}{2} & \frac{1}{3} & \frac{1}{4} \end{array} \right].
				\]
				
				Putting this back into the original game, we have 
				\[
				 	p = q = \left[ \begin{array}{cccc} \frac{1}{2} & \frac{1}{3} & \frac{1}{4} & 0 \end{array} \right].
				\]
				
		\end{itemize}
	\end{solution}
	
	\subsection*{Section II.4.6}
	\begin{question}{1.}
		Consider the game with matrix $A$.  Past experience in playing the game with Player II enables Player I to arrive at a set of probabilities reflecting 
		his belief of the column that II will choose.  I thinks that with probabilities $1/5,1/5,1/5$, and $2/5$, II will choose columns $1,2,3$, and $4$ respectively.
		\[
			\begin{tikzpicture}
				\matrix [matrix of math nodes,left delimiter=(,right delimiter=)] (A)
				{
					0 & 7 & 2 & 4 \\
					1 & 4 & 8 & 2 \\
					9 & 3 & -1 & 6 \\
				};
			\end{tikzpicture}
		\]
		
		\begin{itemize}
			\item [(a)]
				Find for I a Bayes strategy (best response) against $(1/5,1/5,1/5,2/5)$.
			\item [(b)]
				Suppose II guesses correctly that I is going to use a Bayes strategy against $(1/5,1/5,1/5,2/5)$.  Instruct II on the strategy she should use - that is, find 
				II's Bayes strategy against I's Bayes strategy against $(1/5,1/5,1/5,2/5)$.
		\end{itemize}
	\end{question}

	\begin{solution}
		\begin{itemize}
			\item [(a)]
				\[
					Aq = \left[ \begin{array}{ccc} \frac{17}{5} & \frac{17}{5} & \frac{23}{5} \end{array} \right].
				\]
				So Player I's pure Bayes strategy is to choose with probabilities $\left[ \begin{array}{ccc} 0 & 0 & 1 \end{array} \right]$.  This 
				will give him an expected winnings of $23/5$.
			\item [(b)]
				Assuming Player I is playing the strategy $p = (0,0,1)$, then 
				\[
					pA = \left[ \begin{array}{cccc} 9 & 3 & -1 & 6 \end{array} \right].
				\]
				Thus II's best response is to play $(0,0,1,0)$.  This gives player II an expected winnings of $1$.
		\end{itemize}
	\end{solution}
	
	\begin{question}{2.}
		The game with matrix $A$ has value zero, and $(6/11,3/11,2/11)$ is optimal for I.
		\[
			A = \left( \begin{array}{ccc} 0 & -1 & 1 \\ 2 & 0 & -2 \\ -3 & 3 & 0 \end{array}\right) \qquad B = \left( \begin{array}{ccc} 5 & 3 & 7 \\ 9 & 5 & 1 \\ -1 & 11 & 5 \end{array} \right).
		\]
		\begin{itemize}
			\item [(a)]
				Find the value of the game with matrix $B$ and an optimal strategy for I.
			\item [(b)]
				Find an optimal strategy for II in both games.
		\end{itemize}
	\end{question}

	\begin{solution}
		\begin{itemize}
			\item [(a)]
				Since $B = 2A+5$, the value of the game with matrix $B$ is $5$, and an optimal strategy for I equal to $(6/11,3/11,2/11)$.
			\item [(b)]
				It is enough to solve it for one of the games since the strategies are the same in both games.  Now, $A$ is singular, but $B$ is non-singular, 
				so we solve for $B$.
				\[
					B^{-1} = \frac{1}{330} \left( \begin{array}{ccc} 7 & 31 & -16 \\ -23 & 16 & 29 \\ 52 & -29 & -1 \end{array} \right).
				\]
				Then equation (16) tells us
				\[
					q = B^{-1}\1/\1^TB^{-1}\1 = \left[ \begin{array}{ccc} \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \end{array} \right],
				\]
				and
				\[
					p^T = \1^TB^{-1}/\1^TB^{-1}\1 = \left[ \begin{array}{ccc} \frac{6}{11} & \frac{3}{11} & \frac{2}{11} \end{array} \right].
				\]
		\end{itemize}
	\end{solution}
	
	\begin{question}{5.}
		\textbf{An Example In Which the Lower Value is Greater than the Upper Value?}

		Consider the infinite game with strategy spaces $X = Y = \{0,1,2,\ldots\}$, and payoff function,
		\[
			A(i,j) = \left\{ \begin{array}{ll} 0 & \mbox{if $i=j$, } \\ 4^j & \mbox{ if $i > j$, } \\ -4^i & \mbox{ if $i<j$.} \end{array} \right.
		\]
		Note that the game is symmetric.  Let $p = (p_0,p_1,p_2,\ldots) = (1/2,1/4,1/8,\ldots)$ be a mixed strategy for Player I, $p_i = 2^{-(i+1)}$.

		\begin{itemize}
			\item [(a)]
				Show that if Player I uses this strategy, his average return, $\sum_{i=0}^\infty p_iA(i,j)$, is equal to $1/2$ for all pure strategies $j$ for Player II.
			\item [(b)]
				So $p$ is an equalizer strategy that guarantees Player I at least $1/2$.  So teh lower value is at least $1/2$.  Perhaps he can do better.  In fact he can, but ... Wait 
				a minute!  The game is symmetric.  Shouldn't the value be zero?  Worse, suppose Player II uses the same strategy.  By symmetry, she can keep Player I's winnings down to $-1/2$ 
				no matter what pure strategy he chooses.  So the upper value is at most $-1/2$.  What is wrong?  What if both players use the mixed strategy $p$?  We haven't talked much about infinite 
				games, but what restrictions would you place on infinite games to avoid such absurd examples?  Should the restriction be placed on the payoff function, $A$, or on the notion of a mixed strategy?
		\end{itemize}
	\end{question}

	\begin{solution}
		\begin{itemize}
			\item [(a)]
				If Player II chooses $j$, then Player I's winnings are
				\begin{align*}
					\sum_{i=0}^\infty p_i A(i,j) 	&= \sum_{i=0}^{j-1} 2^{-(i+1)} -4^{i} + \sum_{i=j+1}^\infty 2^{-(i+1)} 4^j \\ 
													&= -\sum_{i=0}^{j-1} 2^{i-1} + 4^j \sum_{i=j+1}^\infty  2^{-(i+1)} \\
													&= -\frac{1}{2}(2^j-1) + 4^j 2^{-(j+1)} \\
													&= -2^{j-1}+\frac{1}{2} + 2^{j-1} \\
													&= \frac{1}{2}.
				\end{align*}
			\item [(b)]
				First, let us examine what is going wrong.\\

				Suppose that Player II plays strategy $q$, and Player I counters by playing strategy $p$.  Then according to equation (3), the average payoff is
				\[
					\sum_{i} \sum_{j} p_i A(i,j) q_j,
				\]
				If, however, Player I plays strategy $p$ `first', and Player II counters by playing strategy $q$, we have the average payoff is
				\[
					\sum_{j} \sum_{i} p_i A(i,j) q_j,
				\]
				For finite sums, the two sums are equal, but for infinite sums we need some restrictions to make the sums equal.  Since the strategies are chosen simultaneously, there 
				is not a natural ordering to the sum, so if we are to have any hope of defining the average payoff in a game, the two orderings must give the same sum.  From 
				analysis, Fubini's Theorem tells us a sufficient criterion, in particular
				\[
					\sum_{i} \sum_{j} |f_{ij}| < \infty \Rightarrow \sum_i \sum_j f_{ij} = \sum_j \sum_i f_{ij}.
				\]
				If we restrict ourselves to games where one player never wins a positive amount, we can use Tonelli's Theorem, which says if $f_{ij} \ge 0$ then 
				\[
					\sum_i \sum_j f_{ij} = \sum_j \sum_i f_{ij}
				\]
				where we view both sides as equal if they are both infinite.  This seems more restrictive for this type of games.
				
				Since $0 \le p_i,q_j \le 1$,
				\[
					\sum_i \sum_j |A(i,j)| < \infty \Rightarrow \sum_i \sum_j |p_iA(i,j)q_j| < \infty,
				\]
				and $A(i,j) \ge 0$ implies $p_iA(i,j)q_j \ge 0$.  So it is sufficient to place these restrictions on the payoff function.

				Another potential problem remains, the mixed strategy spaces $X^*,Y^*$ are no longer compact, so we are not guaranteed that continuous functions (e.g. the value function) 
				have an attainable maximum and minimum.  For example, consider the matrix $a_{ij} = 2^{-(i+j)}$.  Then $\sum_i \sum_j a_{ij} < \infty$, and $(1,0,0,\ldots)$ is a dominant strategy 
				for Player I, but Player II has no optimal strategy, he is always better off choosing a larger number.

				This type of problem remains even if you restrict both players to choosing finite strategies, i.e. strategies with only a finite number of nonzero entries.
		\end{itemize}			
	\end{solution}

	\subsection*{Additional Problems}

	\begin{question}{1.}
		Prove that for any $0$-sum game, the lower value is always less than the upper value.
	\end{question}
	
	\begin{solution}
		As the book notes, this follows immediately from an application of the general statement for any real-valued $f$
		\[
			\sup_x \inf_y f(x,y) \le \inf_y \sup_x f(x,y).
		\]
		This is straightforward to show.  To see this, fix $x^\prime,y^\prime$.  Then
		\[
			\inf_y f(x^\prime,y) \le f(x^\prime,y^\prime) \le \sup_x f(x,y^\prime)
		\]
		by the definition of $\inf$ and $\sup$.  But this holds for all $x^\prime$ and $y^\prime$, so we can 
		take the $\sup$ on the left and the $\inf$ on the right to obtain
		\[
			\sup_{x^\prime} \inf_y f(x^\prime,y) \le \inf_{y^\prime} \sup_x f(x,y^\prime).
		\]
		relabelling variables gives
		\[
			\sup_x \inf_y f(x,y) \le \inf_y \sup_x f(x,y).
		\]
		When $f$ is continuous, and $x,y$ are coming from compact sets, we can say
		\[
			\max_x \min_y f(x,y) \le \min_y \max_x f(x,y).
		\]
		Finally, plugging in $f(x,y) = x^TAy$ gives the result.
	\end{solution}

	\begin{question}{2.}
		Prove equation (4) in section 4.1.
	\end{question}

	\begin{solution}
		This proof is described in the book.\\

		We prove the two inequalities separately.
		\begin{align*}
			\max_{1 \le i \le m} \sum_{j=1}^m a_{ij}q_j	&= \max_{p \in X} p^TAq \\ 
														&\le \max{p \in X^*} p^TAq.
		\end{align*}
		This is because $X \subset X^*$.

		Letting $e_k$ be the $k$th pure strategy, suppose $p=p^*$ maximizes $p^TAq$, i.e.
		\[
			(p^*)^TAq = \max_{p \in X^*} p^TAq,
		\]
		then $p^* = \sum_i p_i^* e_i$ where $\sum_i p_i^* = 1$.  Now
		\[
			\max_{1\le i\le m} \sum_{j=1}^m a_{ij}q_j = \max_{1 \le i \le m} e_i^T Aq,
		\]
		and suppose this sum is maximized by $i^*$.  Then
		\begin{align*}
			\max_{p \in X^*} p^T Aq	&= (p^*)^TAq \\
									&= \left(\sum_i p_i^* e_i\right)^T Aq \\
									&= \sum_i p_i^* \left(e_i^TAq\right) \\
									&\le \sum_i p_i^* \left(e_{i^*}^TAq\right) \\
									&= e_{i^*}^TAq \\
									&= \max_{1 \le i \le m} e_i^TAq \\
									&= \max_{1 \le i \le m} \sum_{j=1}^n a_{ij}q_j.
		\end{align*}
	\end{solution}

	\begin{question}{3.}
		Prove (using the minimax theorem) that even if Player II had to announce their strategy in advance, this would not change the average payoff 
		that Player I can guarantee for themselves.
	\end{question}

	\begin{solution}
		The Minimax Theorem guarantees that Player II has a minimax strategy $q^*$.  Thus 
		\[
			\bar{V} = \max_{p \in X^*} p^TAq^*
		\]
		The minimax theorem then tells us that $\bar{V} = V$, so 
		\[
			V = \max_{p \in X^*} p^TAq^*.
		\]
		Thus $V \ge p^TAq^*$ for all $p \in X^*$, so knowing $q^*$ in advance cannot increase the payoff for Player I (and obviously it cannot lower it, since Player I could just ignore this knowledge).
		
	\end{solution}
	
	\begin{question}{4.}
		For the matrix
		\[
			A = \left( \begin{array}{ccc} 0 & 1 & 2 \\ 2 & -1 & -2 \\ 3 & -3 & 0 \end{array} \right).
		\]
		do the following:

		\begin{itemize}
			\item [(a)]
				Write down the equations (6) and (7) defining the lower and upper value of the game.
			\item [(b)]
				Write down the linear programs for finding both the lower and upper values of the game.
		\end{itemize}
	\end{question}
	
	\begin{solution}
		\begin{itemize}
			\item [(a)]
				Equation (6) is
				\[
					\bar{V} = \min_{q \in Y^*} \max_{1 \le i \le m} \sum_{q=1}^n a_{ij}q_j.
				\]
				In our case, 
				\[
					\bar{V} = \min_{q \in Y^*} \max \{ q_2+2q_3, 2q_1-q_2-q_3, 3q_1-3q_3 \}
				\]

				Equation (7) is

				\[
					\underbar{V} = \max_{p \in X^*} \min_{1 \le j \le n} \sum_{i=1}^m p_i a_{ij}.
				\]
				In our case,
				\[
					\underbar{V} = \max_{p \in X^*} \min \{ 2p_2+3p_3, p_1 -p_2-3p_3, 2p_1-2p_2 \}.
				\]
			\item [(b)]
				To calculate the lower bound, we want to choose $w,q_1,q_2,q_3$ to minimize $w$ subject to
				\begin{align*}
					w &\ge q_2+2q_3 \\
					w &\ge 2q_1-q_2-q_3 \\
					w &\ge 3q_1-3q_3 \\
					q_1 &+ q_2 + q_3 = 1 \\
					q_i &\ge 0.
				\end{align*}

				To calculate the upper bound, we want to choose $v,p_1,p_2,p_3$ to maximize $v$ subject to
				\begin{align*}
					v &\le 2p_2+3p_3 \\
					v &\le p_1-p_2-3p_3 \\
					v &\le 2p_1-2p_2 \\
					p_1 &+ p_2 +p_3 = 1 \\
					p_i &\ge 0.
				\end{align*}

		\end{itemize}

	\end{solution}
\end{document}