\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 5\\Due Friday, May 12\textsuperscript{th} at
11:59pm \\ Resubmission due Friday, May 26\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 envelope paradox}. A coin is tossed until it comes out
heads. Let $k$ denotes the (random) number of tosses. There are two
pieces of paper; on one is written the number $10^k$, and on the
other $10^{k+1}$. One of the two notes is chosen at random and given
to Rachel. The other is given to Max. They each look at their own
note. If both want to trade then they are allowed to. After trading
(or not) each is given an amount of money equal to the number
written on his or her paper.
Formally, the states of the world are
$\Omega = \{1,2,3,\ldots\} \times \{0,1\}$, where the first
coordinate is the number of tosses and the second corresponds to the
random allocation of notes. There is a common prior, which, for
$(k,b) \in \Omega$ is
\begin{align*}
\mu(k,b) = \left(\frac{1}{2}\right)^k \cdot \frac{1}{2} = 2^{-(k+1)}.
\end{align*}
Rachel's signal is $t_R(k,b) = 10^{k+b}$ and Max's signal is
$t_M(k,b) = 10^{k+1-b}$. Rachel's utility for not trading is
$t_R$. Her utility for trading is $t_M$. Max's utility for not
trading is $t_M$, and his utility for trading is $t_R$.
\begin{myenumerate}
\item {\em 40 points.} What is the common knowledge algebra $\Sigma_C$?
\item {\em 40 points.} For each possible value of Rachel's signal,
calculate her conditional expected gain from trading. Do the same for Max.
\item {\em 20 points.} What is Rachel's expected gain from trading
before she sees her signal (i.e., before she looks at her note)?
\item {\em Bonus question (1 point).} Would Rachel want to trade
before she looked at her note?
\end{myenumerate}
\item {\em Bonus question: Mind reading (with high probability).}
Nachiket and Kimia play a game, in which Kimia tries to read
Nachiket's mind. There is an infinite set of mailboxes $\N =
\{1,2,3,\ldots\}$. Nachiket choose a finite subset $F \subset \N$,
and places a letter in each mailbox in $F$. Kimia then gets to
open any subset $S \subset \N$ of the letter boxes; note that $S$
need not be finite, but it cannot be all of $\N$. She observes
which ones have letters, and then has to decide to open one more
box $n$ that is not in $S$. Kimia wins if there is not a letter in
box $n$, and otherwise Nachiket wins.
Formally, a pure strategy for Nachiket is a choice of a finite
$F\subset \N$. A pure strategy for Kimia is a choice of $S$, plus a
function $n \colon P_f(S) \to \N \setminus S$ from finite subsets of
$S$ to $\N \setminus S$. Nachiket wins if $n(S \cap F) \in F$.
\begin{myenumerate}
\item {\em 1 point.} Show that for every pure strategy of Kimia
there is a pure strategy of Nachiket that ensures that he wins, and
that for every pure strategy of Nachiket there is a pure strategy of
Kimia that ensures that she wins.
\item {\em 1 point.} Show that Kimia has a {\em mixed} strategy
(i.e., a randomly picked strategy) such that for {\em every $F$},
her probability of losing is at most $\gamma = 10^{-100}$.
\item {\em 1 point.} Show that Kimia has a mixed strategy such that
for {\em every $F$}, her probability of losing is at most
$\gamma\mathrm{e}^{-|F|/\gamma}$.
\end{myenumerate}
\end{myenumerate}
\end{document}