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

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


\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 1\\Due Friday, April 14\textsuperscript{th} at
11:59pm \\ Resubmission due Friday, April 28\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 20 points.} What are the subgame perfect equilibria of the centipede game?

\item Explain why the second player cannot force a
  victory in
  \begin{myenumerate}
  \item {\em 20 points}. Tic-tac-toe. Hint: assume the second player
    has a strategy that forces a victory. Explain how the first player
    can use this strategy to build a strategy that would force victory
    too, leading to a contradition. This can be done in a way that is
    independent of most of the details of the definition of the game.
  \item {\em 20 poinst}. The sweet fifteen game, as described in section 2.2
    of the lecture notes. Hint:
      \url{https://en.wikipedia.org/wiki/Magic_square}.
  \end{myenumerate}

\item {\em Intransitive dice.} A die has six sides, each labeled with
  a number. Consider three dice that are labeled as follows
  \begin{enumerate}
  \item 2, 2, 4, 4, 9, 9.
  \item 1, 1, 6, 6, 8, 8.
  \item 3, 3, 5, 5, 7, 7.
  \end{enumerate}
  Players 1 and 2 play the following extensive form game with perfect
  information. First, player 1 picks one of these three dice. Then
  player 2 picks one of the two that are left over. The utility of a
  player is the probability, when the two picked dice are rolled, that
  their die shows the higher number.

  \begin{myenumerate}
    \item {\em 10 points.} Find a subgame perfect equilibrium of this
      game.
    \item {\em 9 points.} Who has the higher utility? Is there a
      subgame perfect equilibrium in which the other player has higher utility?
    \item {\em 1 point.} Read this: \url{https://en.wikipedia.org/wiki/Intransitive_dice#Warren_Buffett}.
  \end{myenumerate}

  \item {\em 20 points.} Find a subgame perfect equilibrium of
    the dollar auction extensive form game, as described in section 2.9
    of the lecture notes.
  
\item {\em Bonus question: countability via games}. Recall that a set
  $S$ is {\em countable} if there exists a bijection (one-to-one
  correspondence) $f \colon S \to \N$ from $S$ to the natural
  numbers. Equivalently, $S$ is countable if it can be written
  as $S = \{s_1,s_2,\ldots\}$. Recall also that the interval $[0,1]$
  is not countable (Cantor, 1874). We will prove this using a
  game. This proof is due to Grossman and Turett (1998).

  Consider the following game. Fix a subset $S \subseteq [0,1]$, and
  let $a_0 = 0$ and $b_0 = 1$.  The players Al and Betty take
  alternating turns, starting with Al. In Al's $n$\textsuperscript{th}
  turn he has to choose some $a_n$ which is strictly larger than
  $a_{n-1}$, but strictly smaller than $b_{n-1}$. At Betty's
  $n$\textsuperscript{th} turn she has to choose a $b_n$ that is
  strictly smaller than $b_{n-1}$ but strictly larger than $a_n$. Thus
  the sequence $\{a_n\}$ is strictly increasing and the sequence
  $\{b_n\}$ is strictly decreasing, and furthermore $a_n < b_m$ for
  every $n,m \in \N$.

  Since $a_n$ is a bounded increasing sequence, it has a limit
  $a = \lim_n a_n$. Al wins the game if $a \in S$, and Betty wins the
  game otherwise.

  \begin{myenumerate}
    \setlength{\itemsep}{10pt}
  \item {\em 1 point}. Let $S = \{s_1,s_2,\ldots\}$ be
    countable. Prove that the following is a winning strategy for
    Betty: in her $n$\textsuperscript{th} turn she chooses $b_n = s_n$
    if she can (i.e., if $a_n < s_n < b_{n-1}$). Otherwise she chooses
    any other allowed number.
  \item {\em 1 point}. Explain why this implies that $[0,1]$ is
    uncountable.
  \end{myenumerate}
  
\end{myenumerate}


\end{document}