\documentclass[12pt]{article}
\usepackage{amsmath,amsthm, amssymb}
\usepackage{graphicx}
\parindent=0in
\setlength{\oddsidemargin}{0in}
\setlength{\topmargin}{0in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{8.5in}
\begin{document}
\thispagestyle{empty}
\centerline{\bf \Large Math 315 Homework 8}
\smallskip
\centerline{\bf Due Friday, April 14}
\bigskip
Solutions must be written in \LaTeX. You are encouraged to work with others on the assignment,
but you should write up your own solutions independently.
You should reference all of your sources, including your
collaborators.
\smallskip
\begin{enumerate}
\item Consider the following linear programming problem:
\smallskip
\begin{center}
Maximize $-30x_1 - 3x_2 - 11x_3 - 8x_4-6x_5-12x_6$ subject to
\bigskip
$\begin{array}{r @{\hspace{.1cm}} r @{\hspace{.1cm}} r @{\hspace{.1cm}} r @{\hspace{.1cm}} r @{\hspace{.1cm}} r @{\hspace{.1cm}} r
@{\hspace{.1cm}} r @{\hspace{.1cm}} r @{\hspace{.1cm}} r @{\hspace{.1cm}} r @{\hspace{.1cm}} r @{\hspace{.1cm}} r}
-2x_1 & + & x_2 & - & 2x_3 & - & x_4 & - & 2x_5 & + & x_6 & \le & 6 \\[5pt]
-3x_1 & + & x_2 & - & x_3 & - & x_4 & + & x_5 & - & 2 x_6 & \le & -5 \\ \end{array}$ \\[5pt]
$x_1 \ge 0, \,\, x_2 \ge 0,\,\, x_3 \ge 0,\,\, x_4 \ge 0,\,\, x_5 \ge 0,\,\, x_6 \ge 0$
\end{center}
\begin{enumerate}
\item Determine the dual problem.
\smallskip
\item For the dual problem, graph the region corresponding to the inequalities. The minimum value will occur at one of the vertices
of the region --- what is the minimum value, and which vertex does it occur at?
\smallskip
\item What is the maximum value of the original linear programming problem?
\end{enumerate}
\bigskip
\item Let $G$ and $\hat{G}$ be two strategically equivalent two-player strategic-form games. Suppose that
in both games Player 1 has two strategies $S_1 = \{A, B\}$ and Player 2 has two strategies $S_2 = \{C, D\}$.
Suppose that the payoff functions in $G$ are $u_1$ and $u_2$ and the payoff function in $\hat{G}$ are $v_1$ and $v_2$.
Since $G$ and $\hat{G}$ are strategically equivalent, there exists $\alpha_1, \alpha_2, \beta_1, \beta_2$ with $\alpha_1, \alpha_2 > 0$
such that $v_1 = \alpha_1 u_1 + \beta$ and $v_2 = \alpha_2 u_2 + \beta_2$.
Call the mixed strategy payoff functions $U_1, U_2, V_1$, and $V_2$, respectively.
\begin{enumerate}
\item Suppose that $\sigma_1 = x_1A + x_2B$ is a mixed strategy for Player 1 and $\sigma_2 = y_1C + y_2D$ is a mixed strategy for Player 2. Prove the following:
\begin{align*}
V_1 (\sigma_1, \sigma_2) &= \alpha_1 U_1 (\sigma_1, \sigma_2) + \beta_1 \\
V_2 (\sigma_1, \sigma_2) &= \alpha_2 U_2 (\sigma_1, \sigma_2) + \beta_2
\end{align*}
\item Prove Theorem 5.35 for 2-player $2 \times 2$ games: Prove that every mixed strategy Nash equilibrium $(\sigma_1^*, \sigma_2^*)$ of
$G$ is also a mixed strategy Nash equilibrium of $\hat{G}$.
\end{enumerate}
\bigskip
\item In a penalty kick in a game of soccer, one player (the kicker) attempts to kick the soccer ball into a net, while another player (the goalie) tries to stop the ball from going in the net.
There is not enough time for the goalie to see where the ball is going before attempting to move towards it, so the goalie must guess which direction the ball will be going.
For simplicity, we will assume that the kicker chooses to kick left or right (so we'll disregard kicking to the middle), and the goalie decides whether to block left or right.
Also, for simplicity, we'll use ``left" and ``right" to mean the kicker's left and right, and we'll also assume that all players (both kickers and goalies) are right-handed.
A study of professional soccer players observed the following:
\begin{itemize}
\item If both kicker and goalie chose left, the kicker had a 58\% chance of getting the ball in the net.
\item If both kicker and goalie chose right, the kicker had a 70\% chance of getting the ball in the net.
\item If the kicker chose left and the goalie chose right, the kicker had a 93\% chance of getting the ball in the net.
\item If the kicker chose right and the goalie chose left, the kicker had a 95\% chance of getting the ball in the net.
\end{itemize}
\begin{enumerate}
\item Set this up as a strategic-form game. Use the probabilities as the payoffs.
\item Is this game strategically equivalent to a zero-sum game? Explain why or why not.
\item Find all Nash equilibria (both pure strategy and mixed strategy) for the game.
\end{enumerate}
\bigskip
\item Consider the following 2-player strategic game:
\centerline{\hspace{2cm}Player 2} \vspace{-.5cm}
\begin{center}
$\begin{array}{c}
\\ \mbox{Player 1} \\ \end{array}\begin{array}{| c || c | c |}
\hline
& C & D \\ \hline
\hline
A & 4, 3 & 1, 0 \\ \hline
B & 0, 2 & 2, 4 \\ \hline
\end{array}$
\end{center}
\begin{enumerate}
\item Find the mixed strategy maximin $\underline{v}_1$ and minimax $\overline{v}_1$ for Player 1. What mixed strategy will guarantee Player 1 at least
an expected value of $\underline{v}_1$?
\item Find the mixed strategy maximin $\underline{v}_2$ and minimax $\overline{v}_2$ for Player 2. What mixed strategy will guarantee Player 2 at least
an expected value of $\underline{v}_2$?
\end{enumerate}
\end{enumerate}
\end{document}