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