\documentclass{amsart}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage[T1]{fontenc} % Output font encoding for international characters
\usepackage{fouriernc} % Use the New Century Schoolbook font
\usepackage{hyperref}
\hypersetup{
colorlinks=true,
linkcolor=blue,
citecolor=blue
}
\usepackage{sgame}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{bb}[theorem]{Blackboard}
\newcommand{\vecl}[1]{\overrightarrow{#1}}
\newcommand{\dls}[1]{\overrightarrow{#1}}
\def\vproj{\mbox{proj}}
\def\half{{\textstyle \frac12}}
\def\third{{\textstyle \frac13}}
\def\C{\mathbb{C}}
\def\R{\mathbb{R}}
\def\N{\mathbb{N}}
\def\pleq{\preceq}
\def\pgt{\succ}
\def\Z{\mathbb{Z}}
\newenvironment{myenumerate}
{\begin{enumerate}
\setlength{\itemsep}{10pt}}
% \setlength{\parskip}{0pt}
{\end{enumerate}}
\newcommand\blfootnote[1]{%
\begingroup
\renewcommand\thefootnote{}\footnote{#1}%
\addtocounter{footnote}{-1}%
\endgroup
}
\newcommand{\solution}[1]{}
%\newcommand{\solution}[1]{\vspace{0.15in}{\bf Solution: {#1}}\vspace{0.15in}}
\begin{document}
%\newcommand{\itemt}[2]{\item {\bf {#1}} \newline{#2}}
\blfootnote{Omer Tamuz. Email: tamuz@caltech.edu.}
\section*{PS/Ec 172, Set 3\\Due Friday, April 28\textsuperscript{th} at
11:59pm \\ Resubmission due Friday, May 12\textsuperscript{th} at
11:59pm}
Collaboration on homework is encouraged, but individually written
solutions are required. Also, please name all collaborators and
sources of information on each assignment; any such named source may
be used.
\mbox{}
\begin{myenumerate}
\item {\em The surprise quiz.} A teacher and a student play the
following game. The teacher gives a surprise quiz on one of the five
days of the work week. The student, who does not know the material,
will fail if she does not review the material right before the quiz,
but only has time to study on one day. Thus each player's set of
strategies is the set of five days of the work week. The student's
utility is one if she and the teacher chose the same day, and zero
otherwise. The teacher's utility is one minus the student's.
\begin{myenumerate}
\item {\em 25 points}. Show that this game does not have a pure Nash
equilibrium.
\item {\em 25 points}. Find a mixed Nash equilibrium for this game.
\item {\em Bonus question (1 point).} Show that if there are
infinitely many days then there does not exist a mixed Nash
equilibrium. Why does this not violate Nash's Theorem?
\end{myenumerate}
\item Let $G = (N,S_i,u_i)$ be a finite normal form game. Suppose
that the set of players is $N = \{1,\ldots,n\}$, that $S_i=\{a,b\}$
for all $i \in N$, and that there is a function $f \colon \{a,b\}^2
\to \R$ such that for each player $i \in \{1,\ldots,n-1\}$ it holds
that $u_i(s_1,\ldots,s_n) = f(s_i,s_{i+1})$, and
$u_n(s_1,\ldots,s_n) = f(s_n,s_1)$. That is, the players are
positioned in a circle, and the utility of each player is a function
(in fact, the same function) of his strategy and the strategy of his
neighbor on the right.
\begin{myenumerate}
\item {\em 50 points}. Using only the Intermediate Value Theorem
(i.e., without using Nash's Theorem or Brouwer's Theorem), prove
that this game has a mixed (or pure) Nash equilibrium.
\end{myenumerate}
\item {\em Bonus question}. A prisoner escapes to $\Z^2$ on
Sunday. Every day he must move either one up (i.e., add $(0, 1)$ to
his location) or one to the right (add $(1,0)$), except on
Saturdays, when he must rest. The detective can, once a day, check
one element of $\Z^2$ and see if the prisoner is there. If she finds
him then she wins. He wins if she never finds him.
Formally, the prisoner's strategy is an element
\begin{align*}
(z,f) \in \Z^2 \times \{(1, 0),(0, 1),(0, 0)\}^\N
\end{align*}
such that $f(n) =(0, 0)$ whenever $n \equiv 0 \mod 7$, and
$f(n) \in \{(1, 0),(0, 1)\}$ otherwise. The detective's
strategy is a sequence $\{z_n\}_{n \in \N}$ with $z_n \in \Z^2$.
The prisoner's current location when using strategy $(z,f)$ is
\begin{align*}
\ell_n = z + \sum_{k=1}^{n-1} f(k).
\end{align*}
The detective wins if $\ell_n = z_n$ for some $n$. The prisoner wins
otherwise.
\begin{myenumerate}
\item {\em 1 point.} Show that the detective has a winning strategy.
\item {\em 1 point.} Show that if we remove the requirement that
the prisoner rests on Saturdays then the detective does not have a
winning strategy.
\end{myenumerate}
\end{myenumerate}
\end{document}