\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}