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