%------------------------------------------------------------------------------
% Beginning of journal.tex
%------------------------------------------------------------------------------
%
% AMS-LaTeX version 2 sample file for journals, based on amsart.cls.
%
%        ***     DO NOT USE THIS FILE AS A STARTER.      ***
%        ***  USE THE JOURNAL-SPECIFIC *.TEMPLATE FILE.  ***
%
% Replace amsart by the documentclass for the target journal, e.g., tran-l.
%

\documentclass[12pt]{article}

%% Basic
\usepackage{amsmath, amsfonts, amssymb, amsthm, microtype, enumerate,
  enumitem, fullpage}
\usepackage{hyperref}
\hypersetup{
  colorlinks=true,
  linkcolor=blue,
  citecolor=red
}
\usepackage{fancyhdr}
\usepackage{bbm}
%\usepackage[all]{xy}
\usepackage{sgame}
%\usepackage{refcheck}
\usepackage{etoolbox}
%\usepackage{titletoc,tocloft}
%\setlength{\cftsubsecindent}{2cm}
%\setlength{\cftsubsubsecindent}{4cm}
%\dottedcontents{section}[1.5em]{}{1.3em}{.6em}

\newcommand{\plogo}{\fbox{$\mathcal{OT}$}} % Generic dummy publisher logo

\usepackage[utf8]{inputenc} % Required for inputting international characters
\usepackage[T1]{fontenc} % Output font encoding for international characters
\usepackage{fouriernc} % Use the New Century Schoolbook font


\newcommand{\omer}[1]{{\color{red} Omer: #1}}

\newtheorem{theorem}{Theorem}
\newtheorem*{theorem*}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{example}[theorem]{Example}
\newtheorem{question}[theorem]{Question}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{maintheorem}{Theorem}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem*{definition*}{Definition}
\newtheorem*{lemma*}{Lemma}
\usepackage{graphicx}
\usepackage{pstricks, enumerate, pst-node, pst-text, pst-plot}

\numberwithin{equation}{section}
\numberwithin{theorem}{section}


\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\PP}{\mathbb{P}}
\newcommand{\eps}{\varepsilon}

\newcommand{\half}{{\textstyle \frac12}}
\newcommand{\third}{{\textstyle \frac13}}
\newcommand{\fourth}{{\textstyle \frac14}}
\newcommand{\fifth}{{\textstyle \frac15}}

\renewcommand{\P}[1]{{\mathbb{P}}\left[{#1}\right]}
\newcommand{\E}[1]{{\mathbb{E}}\left[{#1}\right]}
\newcommand{\Esub}[2]{{\mathbb{E}_{{#1}}}\left[{#2}\right]}
\newcommand{\Psub}[2]{{\mathbb{P}_{{#1}}}\left[{#2}\right]}
\newcommand{\CondEsub}[3]{{\mathbb{E}_{{#1}}}\left[{#2}\middle\vert{#3}\right]}
\newcommand{\CondPsub}[3]{{\mathbb{P}_{{#1}}}\left[{#2}\middle\vert{#3}\right]}
\newcommand{\CondP}[2]{{\mathbb{P}}\left[{#1}\middle\vert{#2}\right]}
\newcommand{\CondE}[2]{{\mathbb{E}}\left[{#1}\middle\vert{#2}\right]}
\newcommand{\ind}[1]{{\mathbbm{1}_{\left\{{#1}\right\}}}}
 
\DeclareMathOperator{\supp}{supp}
\newcommand{\argmax}{\operatornamewithlimits{argmax}}
\newcommand{\argmin}{\operatornamewithlimits{argmin}}
\def\cc{\curvearrowright}
\def\dd{\mathrm{d}}
\def\sigalg{\Sigma}
\def\sigalgp{\Pi}
\def\pleq{\preceq}
\def\pgeq{\succeq}
\def\pgt{\succ}
\def\nd{\mathrm{nd}}
\DeclareMathOperator{\ulim}{\lim_{\mathcal{U}}}
\def\cI{\mathcal{I}}

\newcommand{\noshow}[1]{}
\let\oldsection\section
\renewcommand\section{\clearpage\oldsection}

\begin{document}


\begin{titlepage} % Suppresses headers and footers on the title page

     \begin{center} % Centre everything on the title page
	
	\scshape % Use small caps for all text on the title page
	
	\vspace*{\baselineskip} % White space at the top of the page
	
	%------------------------------------------------
	%	Title
	%------------------------------------------------
	
	\rule{\textwidth}{1.6pt}\vspace*{-\baselineskip}\vspace*{2pt} % Thick horizontal rule
	\rule{\textwidth}{0.4pt} % Thin horizontal rule
	
	\vspace{0.75\baselineskip} % Whitespace above the title
	
	{\LARGE Graduate Game Theory\\ \medskip Lecture Notes} % Title
	
	\vspace{0.75\baselineskip} % Whitespace below the title
	
	\rule{\textwidth}{0.4pt}\vspace*{-\baselineskip}\vspace{3.2pt} % Thin horizontal rule
	\rule{\textwidth}{1.6pt} % Thick horizontal rule
	
	\vspace{2\baselineskip} % Whitespace after the title block
	
	%------------------------------------------------
	%	Subtitle
	%------------------------------------------------
	
	%A Number of Fascinating and Life-changing Templates Presented in a Clear and Concise Way % Subtitle or further description
	
	\vspace*{3\baselineskip} % Whitespace under the subtitle
	
	%------------------------------------------------
	%	Editor(s)
	%------------------------------------------------
	
	 By
	
	\vspace{0.5\baselineskip} % Whitespace before the editors
	
	{\scshape\Large Omer Tamuz \\} % Editor list
	
	\vspace{0.5\baselineskip} % Whitespace below the editor list
	
	\textit{California Institute of Technology} % Editor affiliation
	
	\vfill % Whitespace between editor names and publisher logo
	
	%------------------------------------------------
	%	Publisher
	%------------------------------------------------
	
	%\plogo % Publisher logo
	
	\vspace{0.3\baselineskip} % Whitespace under the publisher logo
	
	2018 % Publication year
	

     \end{center} % Centre everything on the title page
\end{titlepage}


%\author{Omer Tamuz\footnote{Partially adapted from Osborne and
%  Rubinstein~\cite{osborne1994course}, Maschler, Solan and
%  Zamir~\cite{maschler2013game}, lecture notes by Federico Echenique,
%  and slides by Daron Acemoglu and Asu Ozdaglar. We are indebted to
%  Seo Young (Silvia) Kim for her help in finding and correcting many
%  errors. Any comments or suggestions are welcome.}}
% Address of record for the research reported here
 

% Information for third author

% \thanks{}

%\date{\today}

\setcounter{page}{2}


\section*{Acknowledgments}
These lecture notes are partially adapted from Osborne and
Rubinstein~\cite{osborne1994course}, Maschler, Solan and
Zamir~\cite{maschler2013game}, lecture notes by Federico Echenique,
and slides by Daron Acemoglu and Asu Ozdaglar. I am indebted to Seo
Young (Silvia) Kim and Zhuofang Li for their help in finding and
correcting many errors. Any comments or suggestions are welcome.

\newpage
\tableofcontents

\section*{Disclaimer}
This a not a textbook. These are lecture notes.

\section{Extensive form games with perfect information}


\subsection{Tic-Tac-Toe}
Two people play the following game. There are cards on the table
numbered one through nine, facing up, and arranged in a square. The
first player marks a card with an ``x'', then the second player marks
a card from those left with an ``o'', etc. The winner is the first
player to have cards that form either a row, a column or a diagonal.

Does the first player have a strategy that assures that she wins? What
about the second player?

\subsection{The Sweet Fifteen Game}
Two people play the following game. There are cards on the table
numbered one through nine, facing up, and arranged in a square. The
first player marks a card with an ``x'', then the second player marks
a card from those left with an ``o'', etc. The winner is the first
player to have three cards that sum to exactly fifteen.

Does the first player have a strategy that assures that she wins? What
about the second player?

\subsection{Chess}
We assume the students are familiar with chess, but the details of the
game will, in fact, not be important. We will choose the following
(non-standard) rules for the ending of chess: the game ends either by
the capturing of a king, in which case the capturing side wins and the
other loses, or else in a draw, which happens when there a player has
no legal moves, or more than 100 turns have elapsed.

As such, this games has the following features:
\begin{itemize}
\item There are two players, white and black.
\item There are (at most) 100 times periods.
\item In each time period one of the players chooses an action. This
  action is observed by the other player.
\item The sequence of actions taken by the players so far determines
  what actions the active player is allowed to take.
\item Every sequence of alternating actions eventually ends with
  either a draw, or one of the players winning.
\end{itemize}

We say that white can {\em force a victory} if, for any moves that
black chooses, white can choose moves that will end in its victory.
Zermelo showed in 1913~\cite{zermelo1913anwendung} that in the game of
chess, as described above, one of the following three holds:
\begin{itemize}
\item White can force a victory.
\item Black can force a victory.
\item Both white and black can force a draw.
\end{itemize}
We will prove this later.

We can represent the game of chess mathematically as follows.
\begin{itemize}
\item Let $N = \{W,B\}$ be the set of players.
\item Let $A$ be the set of actions (or moves) that any of the players
  can potentially take at any stage of the game. E.g., rook from A1 to
  B3.
\item A history $h = (a_1,\ldots,a_n)$ is a finite sequence of
  elements of $A$; we denote the empty sequence by $\emptyset$. We say
  that $h$ is legal if each move $a_i$ in $h$ is allowed in the game
  of chess, given the previous moves $(a_1,\ldots,a_{i-1})$, and if
  the length of $h$ is at most 100. We denote by $H$ the set of legal
  histories, including $\emptyset$.
\item Let $Z \subset H$ be the set of {\em terminal} histories; these
  are histories of game plays that have ended (as described above, by
  capturing or a draw). Formally, $Z$ is the set of histories in $H$
  that are not prefixes of other histories in $H$.
\item Let $O = \{W,B,D\}$ be the set of outcomes of the game
  (corresponding to $W$ wins, $B$ wins, and draw). Let
  $o \colon Z \to O$ be a function that assigns to each terminal
  history the appropriate outcome.
\item Let $P \colon H \setminus Z \to N$ be the player function. $P$
  assigns to each non-terminal history the player whose turn it is to
  play. Specifically, $P(h)$ will be $W$ if the length of $h$ is even,
  and $B$ otherwise.
\item Let $\pleq_{W}$ and $\pleq_{B}$ be the white player's and the
  black player's (obvious) preferences over $O$.
\end{itemize}

A {\em strategy} of a player is a complete description of what that
player would do in her turns, given every possible history. Formally,
a strategy $s$ of $W$ is a mapping $s \colon P^{-1}(W) \to A$ that
assigns to each history $h$ with $P(h) = W$ an $a \in A$ such
that $(h,a) \in H$.  Here we denote by $(h,a)$ the strategy
$(a_1,\ldots,a_n,a)$, where $h = (a_1,\ldots,a_n)$.

Let $(s_W,s_B)$ be a pair of strategies, one for each player. Then we
can define the history $h(s_W,s_B) \in H$ to be the terminal history
that is reached when the two players chooses these strategies.  We can
also define $o(s_W,s_B) = o(h(s_W,s_B))$ to be the resulting outcome
of the game.

Given these definitions, we can formally state Zermelo's Theorem.
\begin{theorem}[Zermelo, 1913]
  \label{thm:zermelo}
  In the game of chess, as described above, exactly one of the
  following three holds:
  \begin{itemize}
  \item There exists a strategy $s_W^*$ for $W$ such that, for any
    strategy $s_B$ of $B$, $o(s_W^*,s_B) = W$.
  \item There exists a strategy $s_B^*$ for $B$ such that, for any
    strategy $s_W$ of $W$, $o(s_W,s_B^*) = B$.
  \item There exist strategies $s_W^*$ for $W$ and $s_B^*$ for $B$
    such that, for any strategies $s_W$ and $s_B$,
    $o(s_W^*,s_B) \neq B$ and $o(s_W,s_B^*) \neq W$. (It follows that
    $o(s_W^*,s_B^*) = D$).
  \end{itemize}
\end{theorem}
Note that it is not known which of the three is true.



\newpage
\subsection{Definition of extensive form games with perfect
  information}

\label{sec:extensive-perfect-definition}

In general, an extensive form game (with perfect information) $G$ is a
tuple $G = (N,A,H,O,o,P,\{\pleq_i\}_{i \in N})$ where
\begin{enumerate}
\item $N$ is the set of players.
\item $A$ is the set of actions.
\item $H$ is the set of allowed histories. This is a set of sequences
  of elements of $A$ such that if $h \in H$ then every prefix of $h$
  is also in $H$.

  $Z$ is the set of sequences in $H$ that are not subsequences of
  others in $H$. Note that we can specify $H$ by specifying $Z$; $H$
  is the set of subsequences of sequences in $Z$.
  
  In general, the sequences in $H$ needn't be finite. In this case we
  need an additional requirement, namely that if $H$ contains every
  subsequence of some infinite sequence then it also contains that
  infinite sequence. The set $Z$ of terminal histories - those that
  are not prefixes of others - includes all the infinite ones.

  
\item $O$ is the set of outcomes.
\item $o$ is a function from $Z$ to $O$.
\item $P$ is a function from $H \setminus Z$ to $N$.
\item For each player $i \in N$, $\pleq_i$ is a preference relation
  over $O$. (I.e., a complete, transitive and reflexive binary
  relation).
\end{enumerate}
We denote by $A(h)$ the actions available to player $P(h)$ after
history $h$:
\begin{align*}
  A(h) = \{a \in A\,:\, ha \in H\}.
\end{align*}

A game is called a {\em finite horizon game} if there is a bound on
the length of histories in $H$. A game is called {\em finite} if $H$
is finite.

Strategies are defined as for chess. A {\em strategy profile}
$s = \{s_i\}_{i \in N}$ constitutes a strategy for each player. We
can, as for chess, define $h(s)$ and $o(s)$ as the history and outcome
associated with a strategy profile.

\subsection{The ultimatum game}
In the ultimatum game player 1 makes an offer $a \in \{0,1,2,3,4\}$ to
player 2. Player 2 either accepts or rejects. If player 2 accepts then
she receives $a$ dollars and player 1 receives $4-a$ dollars. If 2
rejects then both get nothing. This is how this game can be written in
extensive form:
\begin{enumerate}
\item $N = \{1,2\}$.
\item $A = \{0,1,2,3,4,a,r\}$.
\item $Z = \{0a,1a,2a,3a,4a,0r,1r,2r,3r,4r\}$.
\item $O = \{(0,0),(0,4),(1,3),(2,2),(3,1),(4,0)\}$.  Each pair
  corresponds to what players 1 receives and what player 2 receives.
\item For $b \in \{0,1,2,3,4\}$, $o(b a) = (4-b,b)$ and
  $o(b r) = (0,0)$.
\item $P(\emptyset) = 1$, $P(0) = P(1) = P(2) = P(3) = P(4) = 2$.
\item For $a_1,b_1,a_2,b_2 \in \{0,1,2,3,4\}$,
  $(a_1,a_2) \pleq_1 (b_1,b_2)$ iff $a_1 \leq b_1$, and
  $(a_1,a_2) \pleq_2 (b_1,b_2)$ iff $a_2 \leq b_2$.
\end{enumerate}

A strategy for player 1 is just a choice among $\{0,1,2,3,4\}$. A
strategy for player 2 is a map from $\{0,1,2,3,4\}$ to $\{a,r\}$:
player 2's strategy describes whether or not she accepts or rejects
any given offer.

\subsection{Equilibria}
Given a strategy profile $s = \{s_i\}_{i \in N}$, we denote by
$(s_{-i},s_i')$ the strategy profile in which $i$'s strategy is
changed from $s_i$ to $s_i'$ and the rest remain the same.

A strategy profile $s^*$ is a {\em Nash equilibrium} if for all
$i \in N$ and strategy $s_i$ of player $i$ it holds that
\begin{align*}
  o(s_{-i}^*,s_i) \pleq_i o(s^*).
\end{align*}
When $s$ is the equilibrium $h(s)$ is also known as the {\em
  equilibrium} path associated with $s$.

Example: in the ultimatum game, consider the strategy profile in which
player 1 offers $3$, and player 2 accepts $3$ or $4$ and rejects $0$,
$1$ or $2$. It is easy to check that this is an equilibrium profile.


\subsection{The centipede game}
In the centipede game there are $n$ time periods and 2 players. The
players alternate in turns, and at each turn each player can either
stop (S) or continue (C), except at the last turn, where they must
stop. Now, there is a piggy bank which initially has in it 2
dollars. If a player decides to stop, she is awarded half of what's in
the bank, plus one dollar, and the other player is awarded the
remainder. If a player decides to continue, 2 dollars are added to the
bank. Hence, in period $m$, a player is awarded $m+1$ if she decided
to stop, and the other player is given $m-1$.

\begin{exercise}
  Define the centipede game formally, for $n=6$. How many strategies
  does each player have?
\end{exercise}

\begin{exercise}
  Show that the strategy profile in which both players play $S$ in
  every time period is an equilibrium.
\end{exercise}


\begin{theorem}
  In every Nash equilibrium, player 1 plays $S$ in the first period.
\end{theorem}
\begin{proof}
  Assume by contradiction that player 1 plays $C$ in the first period
  under some equilibrium $s$. Then there is some period $m > 1$ in
  which $S$ is played for the first time on the equilibrium path. It
  follows that the player who played $C$ in the previous period is
  awarded $m-1$. But she could have been awarded $m$ by playing $S$ in
  the previous period, and therefore $s$ is not an equilibrium.
\end{proof}

\newpage

\subsection{Subgames and subgame perfect equilibria}
A {\em subgame} of a game $G = (N,A,H,O,o,P,\{\pleq_i\}_{i \in N})$ is
a game that starts after a given finite history $h \in H$.  Formally,
the subgame $G(h)$ associated with $h = (h_1,\ldots,h_n) \in H$ is
$G(h) = (N,A,H_h,O,o_h,P_h,\{\pleq_i\}_{i \in N})$, where
\begin{align*}
  H_h = \{(a_1,a_2,\ldots) \,:\, (h_1,\ldots,h_n,a_1,a_2,\ldots)
  \in H\}
\end{align*}
and
\begin{align*}
  o_h(h') = o(h h')\quad\quad P_h(h') = P(h h').
\end{align*}
A strategy $s$ of $G$ can likewise used to define a strategy $s_h$ of
$G(h)$. We will  drop the $h$ subscripts whenever this does
not create (too much) confusion.

A {\em subgame perfect equilibrium} of $G$ is a strategy profile $s^*$
such that for every subgame $G(h)$ it holds that $s^*$ (more
precisely, its restriction to $H_h$) is a Nash equilibrium of
$G(h)$. We will prove Kuhn's Theorem, which states that every finite
extensive form game with perfect information has a subgame perfect
equilibrium. We will then show that Zermelo's Theorem follows from
Kuhn's.


As an example, consider the following Cold War game played between the
USA and the USSR. First, the USSR decides whether or not to station
missiles in Cuba. If it does not, the game ends with utility 0 for
all. If it does, the USA has to decide if to do nothing, in which case
the utility is 1 for the USSR and -1 for the USA, or to start a
nuclear war, in which case the utility is -1,000,000 for all.

\begin{exercise}
  Find two equilibria for this game, one of which is subgame perfect,
  and one which is not.
\end{exercise}

\begin{exercise}
  Find two equilibria of the ultimatum game, one of which is subgame
  perfect, and one which is not.
\end{exercise}

An important property of finite horizon games is the {\em one
  deviation property}. Before introducing it we make the following
definition.

Let $s$ be a strategy profile.  We say that $s_i'$ is a {\em
  profitable deviation} from $s$ for player $i$ at history $h$ if
$s_i'$ is a strategy for $G$ such that
\begin{align*}
  o_h(s_{-i},s_i') \pgt_i o_h(s).
\end{align*}
Note that a strategy profile has no profitable deviations if and only
if it is a subgame perfect equilibrium.

\begin{theorem}[The one deviation principle]
  \label{thm:one-deviation}
  Let $G = (N,A,H,O,o,P,\{\pleq_i\}_{i \in N})$ be a finite horizon,
  extensive form game with perfect information. Let $s$ be a strategy
  profile that is {\em not} a subgame perfect equilibrium. There there
  exists some history $h$ and a profitable deviation $\bar s_i$ for player
  $i = P(h)$ in $G(h)$ such that $\bar s_i(k) = s_i(k)$ for all
  $k \neq h$.
\end{theorem}
\begin{proof}
  Let $s$ be a strategy profile that is {\em not} a subgame perfect
  equilibrium. Then there is a subgame $G(h)$ and a strategy $s_i'$
  for player $i = P(h)$ such that $s_i'$ is a profitable deviation for
  $i$ in $G(h)$. Denote $s'=(s_{-i},s'_i)$, and note that
  $o_h(s') \pgt_i o_h(s)$.

  Let $h$ be a maximal (in length) history such that
  $o_h(s_i') \pgt_i o_h(s_i)$. Let $\bar s_i$ be given by
  $\bar s_i(k)=s_i(k)$ for all $k \neq h$, and
  $\bar s_i(h)=s'_i(h)$.

  Assume that under $\bar s_i$ player $i$ chooses the action $a$ at
  history $h$, i.e., $\bar s_i(h)=a$. Then
  \begin{align*}
    o_h(\bar s_i) = o_{h a}(\bar s_i) = o_{h a}(s_i) \pgeq_i o_{h a}(s_i') = o_h(s_i') \pgt_i o_h(s_i),
  \end{align*}
  where each (in)equality is, respectively, a consequence of 
  \begin{enumerate}
  \item $\bar s_i(h)=a$,
  \item $\bar s_i$ and $s_i$ coincide on $G(h a)$,
  \item the maximality of $h$, which means that $s_i'$ is not a
    profitable deviation for the history $h a$,
  \item $s_i'(h)=a$,
  \item $s_i'$ is a profitable deviation for the history $h$.
  \end{enumerate}
  We thus have that $\bar s_i$ is a profitable deviation for
  $G(h)$ that differs from $s_i$ in just one history.
\end{proof}

\subsection{The dollar auction}
Two players participate in an auction for a dollar bill. Player 1 acts
in the odd periods, and player 2 in the even periods. Both players
start with a zero bid. In each period the playing player can either
stay or quit. If she quits the other player gets the bill, both pay
the highest they have bid so far, and the game ends. If she stays her
bid goes up by 10 cents (except in the first period, when it goes up
by 5 cents) and the game continues.

\begin{exercise}
  Does this game have equilibria? Subgame perfect equilibria? Under
  the additional stipulation that it ends once one of the bids exceeds
  100 dollars (in which case the person who made the highest bid gets
  the dollar, and both pay the highest they have bid so far)?
\end{exercise}
\newpage
\subsection{Backward induction, Kuhn's Theorem and a proof of
  Zermelo's Theorem}

Let $G = (N,A,H,O,o,P,\{\pleq_i\}_{i \in N})$ be an extensive form
game with perfect information.  Recall that $A(\emptyset)$ is the set
of allowed initial actions for player $i = P(\emptyset)$. For each
$b \in A(\emptyset)$, let $s^{G(b)}$ be some strategy profile for
the subgame $G(b)$. Given some $a \in A(\emptyset)$, we denote by
$s^a$ the strategy profile for $G$ in which player
$i = P(\emptyset)$ chooses the initial action $a$, and for each action
$b \in A(\emptyset)$ the subgame $G(b)$ is played according to
$s^{G(b)}$. That is, $s^a_i(\emptyset) = a$ and for every
player $j$, $b \in A(\emptyset)$ and $b h \in H \setminus Z$,
$s^a_j(b h) = s^{G(b)}_j(h)$.

\begin{lemma}[Backward Induction]
  \label{lem:backward}
  Let $G = (N,A,H,O,o,P,\{\pleq_i\}_{i \in N})$ be a finite extensive
  form game with perfect information.  Assume that for each
  $b \in A(\emptyset)$ the subgame $G(b)$ has a subgame perfect
  equilibrium $s^{G(b)}$.  Let $i = P(\emptyset)$ and let $a$ be the
  $\pgt_i$-maximizer over $A(\emptyset)$ of $o_a(s^{G(a)})$. Then
  $s^a$ is a subgame perfect equilibrium of $G$.
\end{lemma}
\begin{proof}
  By the one deviation principle, we only need to check that $s^a$
  does not have deviations that differ at a single history. So let $s$
  differ from $s^a$ at a single history $h$.

  If $h$ is the empty history then $s = s^{G(b)}$ for
  $b = s_i(\emptyset)$. In this case $o(s^a) \pgt_i o(s) = o_b(s^{G(b)})$,
  by the definition of $a$ as the maximizer of $o_a(s^{G(a)})$.

  Otherwise, $h$ is equal to $b h'$ for some $b \in A(\emptyset)$ and
  $h' \in H_b$, and $o(s) = o_b(s)$. But since $s^a$ is a subgame
  perfect equilibrium when restricted to $G(b)$ there are no
  profitable deviations, and the proof is complete.
\end{proof}

Kuhn~\cite{kuhn1953extensive} proved the following theorem.
\begin{theorem}[Kuhn, 1953]
  \label{thm:kuhn}
  Every finite extensive form game with perfect information has a
  subgame perfect equilibrium.
\end{theorem}
Given a game $G$ with allowed histories $H$, denote by $\ell(G)$ the
maximal length of any history in $H$.
\begin{proof}[Proof of Theorem~\ref{thm:kuhn}]
  We prove the claim by induction on $\ell(G)$.  For $\ell(G) = 0$ the
  claim is immediate, since the trivial strategy profile is an
  equilibrium, and there are no proper subgames. Assume we have proved
  the claim for all games $G$ with $\ell(G) < n$.

  Let $\ell(G) = n$, and denote $i = P(\emptyset)$. For each
  $b \in A(\emptyset)$, let $s^{G(b)}$ be some subgame perfect
  equilibrium of $G(b)$. These exist by our inductive assumption, as
  $\ell(G(b)) < n$.

  Let $a^* \in A(\emptyset)$ be a $\pleq_i$-maximizer of
  $o(s^{a^*})$. Then by the Backward Induction Lemma $s^{a^*}$ is a
  subgame perfect equilibrium of $G$, and our proof is concluded.
\end{proof}

Given Kuhn's Theorem, Zermelo's Theorem admits a simple proof.
\begin{proof}[Proof of Theorem~\ref{thm:zermelo}]
  Let $s^*=(s_W^*,s_B^*)$ be a subgame perfect equilibrium of any
  finite extensive form game with two players ($W$ and $B$) and
  outcomes $\{W,B,D\}$ with preferences as in chess. Hence the outcome
  $o(s^*)$ is either $W$, $B$ or $D$. Consider these three cases. If
  $o(s^*) = W$ then for any $s_B$
  \begin{align*}
    o(s_W^*,s_B) \pleq_B o(s^*) = W. 
  \end{align*}
  But $W$ is the unique $\pleq_B$ minimizer, and so
  $o(s_W^*,s_B) = W$. That is, white can force victory by playing
  $s_W^*$. The same argument shows that if $o(s^*) = B$ then black can
  force victory. Finally, if $o(s^*) = D$ then for any $s_B$
  \begin{align*}
    o(s_W^*,s_B) \pleq_B o(s^*) = D, 
  \end{align*}
  so $o(s_W^*,s_B)$ is either $D$ or $W$. By the same argument
  $o(s_W,s_B^*)$ is either $D$ or $B$ for any $s_W$, and so we have
  proved the claim.
\end{proof}



\section{Strategic form games}

\subsection{Definition}

A game in strategic form (or normal form) is a tuple
$G = (N,\{S_i\}_{i \in N},O,o,\{\pleq_i\}_{i \in \N})$ where
\begin{itemize}
\item $N$ is the set of players.
\item $S_i$ is the set of actions or strategies available to player
  $i$. We denote by $S = \prod_i S_i$ the set of strategy profiles.
\item $O$ is the set of outcomes.
\item $o \colon S \to O$ is a function that assigns an outcome to each
  strategy profile.
\item For each player $i \in N$, $\pleq_i$ is a preference relation
  over $O$.
\end{itemize}

Sometimes it is more convenient to define a game by
$G = (N,\{S_i\}_{i \in N},\{u_i\}_{i \in \N})$, where for each
$i \in N$, the function $u_i \colon S \to \R$ is player $i$'s utility
(or payoff) for each strategy profile.

We say that $G$ is finite if $N$ is finite and $S$ is finite.

\subsection{Nash equilibria}
Given a strategy profile $s$, a {\em profitable deviation} for player
$i$ is a strategy $s_i$ such that
\begin{align*}
  o(s_{-i},s_i) \pgt_i o(s).
\end{align*}
A strategy profile $s$ is a {\em Nash equilibrium} if no player has a
profitable deviation. These are also called {\em pure} Nash
equilibria, for reasons that we will see later. They are often just
called equilibria.

\subsection{Classical examples}
\label{sec:normal-form-examples}
\begin{itemize}
\item {\bf Extensive form game with perfect information.} Let
  $G = (N,A,H,O,o,P,\{\pleq_i\}_{i \in N})$ be an extensive form game
  with perfect information. Let $G'$ be the strategic form game given
  by $G' = (N',\{S_i\}_{i \in N},O',o',\{\pleq_i'\}_{i \in \N})$,
  where
  \begin{itemize}
  \item $N' = N$.
  \item $S_i$ is the set of $G$-strategies of player $i$.
  \item $O' = O$.
  \item For every $s \in S$, $o'(s) = o(s)$.
  \item $\pleq'_i = \pleq_i$.
  \end{itemize}
  We have thus done nothing more than having written the same game in
  a different form. Note, however, that not every game in strategic
  form can be written as an extensive form game with perfect
  information.

    \begin{exercise}
      Show that $s \in S$ is a Nash equilibrium of $G$ iff it is a
      Nash equilibrium of $G'$.
    \end{exercise}
    Note that a disadvantage of the strategic form is that there is no
    natural way to define subgames or subgame perfect equilibria.
    
  \item {\bf Matching pennies.} In this game, and in the next few,
    there will be two players: a row player (R) and a column player
    (C). We will represent the game as a payoff matrix, showing for
    each strategy profile $s=(s_R,s_C)$ the payoffs $u_R(s),u_C(s)$ of
    the row player and the column player.
    
    \begin{center}
      \begin{game}{2}{2}
        & $H$     & $T$\\
        $H$   & $1,0$  & $0,1$\\
        $T$ & $0,1$ & $1,0$
      \end{game}
    \end{center}
    
    In this game each player has to choose either heads (H) or tails
    (T). The row player wants the choices to match, while the row
    player wants them to mismatch.

    \begin{exercise}
      Show that matching pennies has no pure Nash equilibria.
    \end{exercise}
    

  \item {\bf Prisoner's dilemma.}

    Two prisoners are faced with a dilemma. A crime was committed in
    the prison, and they are the only two who could have done it. Each
    prisoner has to make a choice between testifying against the other
    (and thus betraying the other) and keeping her mouth shut. In the
    former case we say that the prisoner defected (i.e., betrayed the
    other), and in the latter she cooperated (with the other prisoner,
    not with the police).

    If both cooperate (i.e., keep their mouths shut), they will have
    to serve the remainder of their sentences, which are 2 years
    each. If both defect (i.e., agree to testify against each other),
    each will serve 3 years. If one defects and the other cooperates,
    the defector will be released immediately, and the cooperator will
    serve 10 years for the crime.
    
    Assuming that a player's utility is minus the number of years
    served, the payoff matrix is the following.
    
    \begin{center}
      \begin{game}{2}{2}
        & $D$     & $C$\\
        $D$   & $-3,-3$  & $0,-10$\\
        $C$ & $-10,0$ & $-2,-2$
      \end{game}
    \end{center}

    \begin{exercise}
      Show that the unique pure Nash equilibrium is $(D,D)$.
    \end{exercise}

  \item {\bf Split or steal.}

    Split or steal is a game played in a British game show called
    {\em golden balls}:
    \url{https://www.youtube.com/watch?v=y6GhbT-zEfc}, and this one:
    \url{https://www.youtube.com/watch?v=S0qjK3TWZE8}.
    
    \begin{center}
      \begin{game}{2}{2}
        & $St$     & $Sp$\\
        $St$   & $0,0$  & $1,0$\\
        $Sp$ & $0,1$ & $1/2,1/2$
      \end{game}
    \end{center}

    \begin{exercise}
      What are the equilibria of this game?
    \end{exercise}


  \item {\bf Stag hunt.}

    Two friends go together on a hunt. Each has to decide whether to
    try and catch a hare---which she can do by herself---or to
    cooperate on trying to catch a stag.  The payoff matrix is the
    following.
    
    \begin{center}
      \begin{game}{2}{2}
        & $S$     & $H$\\
        $S$   & $2,2$  & $0,1$\\
        $H$ & $1,0$ & $1,1$
      \end{game}
    \end{center}

    \begin{exercise}
      What are the Nash equilibria?
    \end{exercise}

    
    

  \item {\bf Battle of the sexes\footnote{The name of this game seems
        archaic in this day and age, but we will keep it, as it is
        standard in the literature.}.} Adam and Steve are a married
    couple. They have to decide whether to spend the night at the
    monster truck show (M) or at the opera (O). Adam (the row player)
    prefers the truck show, while Steve prefers the opera. Both would
    rather go out then do nothing, which is what would happen if they
    could not agree. Their payoff matrix is the following.

    \begin{center}
      \begin{game}{2}{2}
        & $M$     & $O$\\
        $M$   & $2,1$  & $0,0$\\
        $O$ & $0,0$ & $1,2$
      \end{game}
    \end{center}

    \begin{exercise}
      Find all the equilibria of this game.
    \end{exercise}
    

  \item {\bf Bertrand.} There are $n$ companies that are selling the
    same product. There are 1,000 customers who want to buy one
    product each, but will not buy if the price is more than \$1,000.
    Each company has to set a price, which we will assume has to be an
    integral amount of dollars.

    All customers buy from the company that set the lowest price
    (unless all prices are more than \$1,000, in which case they buy
    nothing). If more than one has set the lowest price then the
    revenue is split evenly between these companies. Therefore, if $m$
    companies chose the lowest price $p$, then the payoff to each of
    these companies is $1000 \cdot p / m$, and the payoff to the rest
    is zero.

    \begin{exercise}
      Find all the equilibria of this game.
    \end{exercise}

    Thought experiment: what can the members of the cartel do (in real
    life) to ensure that all set the price to \$1,000?
    
  \item {\bf The regulated cartel.} As in the previous game, there are
    $n$ companies and 1,000 customers who will buy at \$1,000 or
    less. There is a production cost $p_{\mathrm{prod}}$ to this
    product (which is the same for all companies) and the payoff for
    the company from selling a product is its price minus the
    production cost. As before, customers are split between the lowest
    priced companies.

    Regulation dictates that companies must sell at production cost
    plus \$1. However, the regulator does not know the production cost
    $p_{\mathrm{prod}}$, which the companies do know.

    Hoping to solve this problem, the regulator has dictated that any
    company that sets a price $p$ that is higher than the lowest set
    price $p_{\mathrm{min}}$ has to pay a fine of
    $p - p_{\mathrm{min}}$.

    \begin{exercise}
      Find the equilibria of this game.
    \end{exercise}


  \item {\bf Cournot.} Consider a finite set of companies $N$ that are
    selling the same product. Each has to decide on a quantity $q_i$
    to manufacture. The function $D(p)$ describes the demand as a
    function of price, and we set denote its inverse by $P = D^{-1}$.
    Let $c(q)$ be the cost of manufacturing, as a function of
    quantity. Assuming prices are set so that all the manufactured
    goods are sold, company $i$'s payoff is
    \begin{align*}
      u_i(q_1,\ldots,q_n) = q_i \cdot P\left(\sum_i q_i\right) - c(q_i).
    \end{align*}

    \begin{exercise}
      Let $P(q) = A - B \cdot q$, and let $c(q) = C \cdot q$ (so that
      the cost per unit is independent of the amount manufactured),
      and assume $A > C$.  Show that there is a Nash equilibrium in
      which all companies set the same quantity $q$, and calculate this
      $q$.
    \end{exercise}

  \item {\bf Public goods.} Each of four players has to choose an
    amount in $q_i \in [0,1]$ to contribute to a public
    goods project. The total amount contributed $q=\sum_i q_i$ is
    multiplied by 2 to yield the total return $r = 2q$. This return is
    distributed evenly among the players. Hence
    player $i$'s utility is $r/4-q_i$.

    \begin{exercise}
      Find all equilibria of this game.
    \end{exercise}

    \begin{exercise}
      Now arrange the players in some order and have each one choose
      after seeing the choices of her predecessors. What are the
      possible utilities in equilibria of this game? In subgame
      perfect equilibria?
    \end{exercise}

  \item {\bf Voter turnout.} There is a finite set of voters
    $N = N^a \cup N^b$ with $N^a \cap N^b = \emptyset$ and
    $|N^a| \geq |N^b|$. Each voter chooses one of the three actions
    $\{a,b,0\}$: either vote for candidate $a$, for candidate $b$, or
    abstain. After the vote the winner is decided according to the
    majority, or is chosen randomly if the vote was tied.

    Each voter in $N^a$ gets utility $1$ if $a$ wins, utility $0$ if
    $b$ wins, and utility $1/2$ if the winner is chosen at random. The
    same hold for voters in $N^b$, with the roles of $a$ and $b$
    revered. Additionally, each voter pays a cost $c \in (0,1/2)$ if
    they do not abstain.

    \begin{exercise}
      Find all equilibria of this game. In the following cases: (1) $N^a$
      and $N^b$ are of equal size and (2) $N^a$ is larger than $N^b$.
    \end{exercise}

    
  \end{itemize}
\newpage
  \subsection{Dominated strategies}
  
  A strategy $s_i$ of player $i$ in
  $G = (N,\{S_i\}_{i \in N},O,o,\{\pleq_i\}_{i \in \N})$ is {\em
    strictly dominated} (or just dominated) if there exists another
  strategy $t_i$ such that, for all choices of strategy $s_{-i}$ of
  the other players it holds that
  \begin{align*}
    o(s_{-i},t_i) \pgt_i o(s_{-i},s_i).
  \end{align*}
  That is, regardless of what the other players do, $s_i$ is a better
  choice for $i$ than $t_i$.

  We say that $s_i$ is {\em weakly dominated} if there exists another
  strategy $t_i$ such that for all $s_{-i}$
  \begin{align*}
    o(s_{-i},t_i) \pgeq_i o(s_{-i},s_i),
  \end{align*}
  and furthermore for some $s_{-i}$
  \begin{align*}
    o(s_{-i},t_i) \pgt_i o(s_{-i},s_i).
  \end{align*}

  \begin{exercise}
    Does matching pennies have strictly dominated strategies?  Weakly
    dominated strategies? How about the prisoner's dilemma? The
    regulated cartel? Voter turnout?
  \end{exercise}
  

  \subsection{Repeated elimination of dominated strategies}
  It seems unreasonable that a reasonable person would choose a
  strictly dominated strategy, because she has an obviously better
  choice. Surprisingly, taking this reasoning to its logical
  conclusion leads to predictions that sharply contradict observed
  human behavior.

  Consider the regulated cartel game $G$, and assume that
  $p_{\mathrm{prod}} = \$0$ and that the set of possible strategies is
  $\{\$1,\ldots,\$1000\}$. It is easy to see that \$1,000 is a
  dominated strategy; if all other companies choose \$1,000 then \$999
  is a better strategy. If the lowest price $p_{\mathrm{min}}$ is
  lower than \$1,000, then still \$999 is a better strategy, since
  then the fine is smaller. It is likewise easy to check that \$1,000
  is the only dominated strategy.
  
  Since no reasonable player would choose \$1,000, it is natural to
  define a new game $G'$ which is identical to $G$, except that the
  strategy space of every player no longer includes \$1,000. Indeed,
  assuming that we are interested in equilibria, the following theorem
  guarantees that analyzing $G'$ is equivalent to analyzing $G$.

  \begin{theorem}
    Let $G = (N,\{S_i\}_{i \in N},O,o,\{\pleq_i\}_{i \in \N})$, let
    $d_j \in S_j$ be a dominated strategy of player $j$, and let
    $G' = (N,\{S_i'\}_{i \in N},O,o',\{\pleq_i\}_{i \in \N})$, where
    \begin{align*}
      S_i' =
      \begin{cases}
        S_i&\mbox{for } i \neq j\\
        S_j \setminus \{d_j\}&\mbox{for }i=j
      \end{cases},
    \end{align*}
    and $o'$ is the restriction of $o$ to $S'$.
    
    Then every Nash equilibrium $s \in S$ of $G$ is in
    $S'$. Furthermore $s \in S'$ is a Nash equilibrium of $G$ if and
    only if it is a Nash equilibrium of $G'$.
  \end{theorem}
  The proof of this Theorem is straightforward and is left as an
  exercise.

  Now, as before, it is easy to see that \$999 is a dominated strategy
  for $G'$, and to therefore remove it from the set of strategies and
  arrive at a new game, $G''$. Indeed, if we repeat this process, we
  will arrive at a game in which the single strategy is \$1. However,
  in experiments this is very rarely the chosen
  strategy\footnote{Except in populations of game theory students.}.

  The following theorem of Gilboa, Kalai and
  Zemel~\cite{gilboa1990order} shows that the order of elimination of
  dominated strategies does not matter, as long as one continues
  eliminating until there are no more dominated strategies. Note that
  this is not true for weakly dominated
  strategies~\cite{gilboa1990order}.


  \begin{theorem}[Gilboa, Kalai and Zemel, 1990]
    Fix a finite game $G$, and let $G_1$ be a game that
    \begin{itemize}
    \item is the result of repeated elimination of dominated
      strategies from $G$, and
    \item has no dominated strategies.
    \end{itemize}
    Let $G_2$ be a game with the same properties. Then $G_1=G_2$.
  \end{theorem}

  \subsection{Dominant strategies}
  A strategy $s_i$ of player $i$ in
  $G = (N,\{S_i\}_{i \in N},O,o,\{\pleq_i\}_{i \in \N})$ is {\em
    strictly dominant} if for every other strategy $t_i$ it holds that
  \begin{align*}
    o(s_{-i},s_i) \pgt_i o(s_{-i},t_i).
  \end{align*}
  That is, regardless of what the other players do, $t_i$ is a better
  choice for $i$ than $s_i$.

  \begin{exercise}
    Which of the games above have a strictly dominant strategy?
  \end{exercise}

  The proof of the following theorem is straightforward.
  \begin{theorem}
    If player $i$ has a strictly dominant strategy $d_i$ then, for
    every pure Nash equilibrium $s^*$ it holds that $s_i^* = d_i$.
  \end{theorem}


  \newpage
  \subsection{Mixed equilibria and Nash's Theorem}

  Given a finite set $X$, denote by $\Delta X$ set of probability
  distributions over $X$.
  
  Let $G = (N,\{S_i\},\{u_i\})$ be a finite game.  A {\em mixed
    strategy} $\sigma_i$ is an element of $\Delta S_i$. Given a {\em
    mixed strategy profile} $\sigma = (\sigma_1,\ldots,\sigma_n)$, we
  overload notation and let $\sigma$ be the element of $\Delta S$
  given by the product $\prod_i \sigma_i$. That is, $\sigma$ is the
  distribution over $\prod_i S_i$ in which we pick independently from
  each $S_i$, with distribution $\sigma_i$.

  Define a game $\hat G(N,\{\hat S_i\},\{\hat u_i\})$ as follows:
  \begin{itemize}
  \item $\hat S_i = \Delta S_i$.
  \item $\hat u_i(\sigma) = \Esub{s \sim \sigma}{u_i(s)}$.
  \end{itemize}
  That is, $\hat G$ is a game whose strategies are the mixed
  strategies of $G$, and whose utilities are the expected utilities of
  $G$, taken with respect to the given mixed strategies. A pure Nash
  equilibrium of $\hat G$ is called a {\em mixed Nash equilibrium} of
  $G$. That is, a mixed strategy profile
  $\sigma \in \prod_i \Delta S_i$ is a mixed Nash equilibrium if no
  player can improve her expected utility by deviating to another
  mixed strategy. We will often just say ``Nash equilibrium'' when
  referring to mixed equilibria. We will use $u_i$ to also mean
  $\hat u_i$; that is, we will extend $u_i$ from a function $S \to \R$
  to a function $\Delta S \to \R$.

  Fix any $\sigma_{-i}$, and note that as a function
  $\Delta S_i \to \R$, $u_i(\sigma_{-i},\cdot)$ is linear. That is,
  \begin{align*}
    u_i(\sigma_{-i},\alpha \sigma_i+(1-\alpha)\tau_i) = \alpha u_i(\sigma_{-i},\sigma_i) +
    (1-\alpha) u_i(\sigma_{-i},\tau_i).
  \end{align*}
 
  
  Nash's celebrated theorem~\cite{nash1950equilibrium} states that
  every finite game has a mixed equilibrium.
  \begin{theorem}[Nash, 1950]
    \label{thm:nash}
    Every finite game has a mixed Nash equilibrium.
  \end{theorem}

  To prove Nash's Theorem we will need Brouwer's Fixed Point Theorem.
  \begin{theorem}[Brouwer's Fixed Point Theorem]
    Let $X$ be a compact convex subset of $\R^d$. Let
    $T \colon X \to X$ be continuous. Then $T$ has a fixed
    point. I.e., there exists an $x \in X$ such that $T(x) = x$.
  \end{theorem}
  Corollary: if you are in a room and hold a map of the room
  horizontally, then there is a point in the map that is exactly above
  the point it represents.

  \begin{exercise}
    Prove Brouwer's Theorem for the case that $X$ is a convex compact
    subset of $\R$.
  \end{exercise}
  \begin{exercise}
    Show that both the compactness and the convexity assumptions are
    necessary.
  \end{exercise}


  Brouwer's Theorem has a simple proof for the case that $T$ is
  affine, i.e., in the case that
  \begin{align*}
   T(\alpha x + (1-\alpha)y) = \alpha T(x) + (1-\alpha)T(y) 
  \end{align*}
  for all $0 \leq \alpha \leq 1$.

  To give some intuition for this proof consider first the case that
  $T$ has a {\em periodic point}. That is, if we denote by $T^n$ the
  $n$-fold composition of $T$ with itself\footnote{E.g., $T^3(x) = 
  T(T(T(x)))$.} then there is some $x$ and $n \geq 1$ such that
  $T^n(x)=x$. In this case
  \begin{align*}
    z = \frac{1}{n}\left(x + T(x) + T^2(x) + \cdots + T^{n-1}(x)\right)
  \end{align*}
  is a fixed point of $n$, by the affinity property of $T$.

  For the more general case that $T$ has no periodic points, pick any $x \in X$. Let
  \begin{align*}
  x_n = \frac{1}{n}\left(x + T(x) + T^2(x) + \cdots + T^{n-1}(x)\right).
  \end{align*}
  Because $T$ is affine,
  \begin{align*}
    T(x_n)
    &= \frac{1}{n}\left(T(x) + T^2(x) + T^3(x) + \cdots + T^n(x)\right).
  \end{align*}
  Adding and subtracting $\frac{1}{n}x$ yields
  \begin{align*}
    T(x_n)
    &= \frac{1}{n}\left(x + T(x) + T^2(x) + \cdots +
    T^{n-1}(x)\right) + \frac{1}{n}T^n(x)-\frac{1}{n}x\\
    &= x_n + \frac{1}{n}T^n(x)-\frac{1}{n}x.
  \end{align*}
  Hence
  \begin{align*}
    \lim_n T(x_n)-x_n = \lim_n \frac{1}{n}T^n(x)-\frac{1}{n}x = 0.
  \end{align*}
  Since $X$ is compact the sequence $(x_n)_n$ has a subsequence $(x_{n_k})_k$
  that converges to some $z \in X$. Along this subsequence we also
  have that $\lim_k T(x_{n_k})-x_{n_k} = 0$, and so, since $T$ is
  continuous, $T(z)-z=0$.
  
  
  \subsection{Proof of Nash's Theorem}

  
  Consider a ``lazy player'' who, given that all players are currently
  playing a mixed strategy profile $\sigma$, has utility for playing
  some mixed strategy $\sigma_i'$ which is given by
  \begin{align*}
    g_i^\sigma(\sigma_i') = u_i(\sigma_{-i},\sigma_i') - \lambda\|\sigma_i'-\sigma_i\|^2_2
  \end{align*}
  for some $\lambda > 0$.  That is, her utility has an extra addend
  which is lower the further away the new strategy is from her current
  strategy. Analyzing what happens when all players are lazy is the
  key to the following proof of Nash's Theorem.
  
  \begin{proof}[Proof of Theorem~\ref{thm:nash}]
    Let $G = (N,\{S_i\},\{u_i\})$ be a finite game. Let
    $f \colon \Delta S \to \Delta S$ be given by
    \begin{align*}
      [f(\sigma)]_i = \argmax_{\sigma_i' \in \Delta S_i}g_i^\sigma(\sigma_i'). 
    \end{align*}
    It is straightforward to show that $f$ is continuous. This maximum
    is unique, since $g$ is strictly concave and $\Delta S_i$ is a
    convex set.


    Since we can think of $\Delta S$ as a convex subset of $\R^{|S|}$,
    $f$ has a fixed point $\sigma^*$, by Brouwer's Theorem. We will
    show that $\sigma^*$ is a mixed Nash equilibrium.

    Assume by contradiction that there exists a player $i$ and a
    $\sigma_i \in \Delta S_i$ such that
    \begin{align*}
      \delta := u_i(\sigma^*_{-i},\sigma_i) - u_i(\sigma^*) > 0.
    \end{align*}

    Given any $\eps > 0$, let
    $\tau_i^\eps = (1-\eps) \cdot \sigma_i^* + \eps \cdot
    \sigma_i$. Then
    \begin{align}
      \label{eq:g-i}
      g_i^{\sigma^*}(\tau_i^\eps)
      = u_i(\sigma_{-i}^*,\tau_i^\eps) - \lambda\|\tau_i^\eps-\sigma_i^*\|^2_2.
    \end{align}
    Now, by the linearity $u_i$,
    \begin{align*}
      u_i(\sigma_{-i}^*,\tau_i^\eps)
      &= u_i(\sigma_{-i}^*,(1-\eps) \cdot \sigma_i^* + \eps \cdot
        \sigma_i)\\
      &= (1-\eps) \cdot u_i(\sigma^*) + \eps \cdot u_i(\sigma_{-i}^*,\sigma_i)\\
      &= u_i(\sigma^*) + \eps \cdot \delta.
    \end{align*}
    By the definition of $\tau_i^\eps$
    \begin{align*}
      \|\tau_i^\eps-\sigma_i^*\|^2_2 = \|\eps
      \cdot(\sigma_i-\sigma_i^*)\|_2^2 = \eps^2 \|\sigma_i-\sigma_i^*\|_2^2.
    \end{align*}
    Plugging these expressions back into~\eqref{eq:g-i} we get
    \begin{align*}
      g_i^{\sigma^*}(\tau_i^\eps) =  u_i(\sigma^*) + \eps \cdot \delta
      - \eps^2 \lambda \|\sigma_i-\sigma_i^*\|_2^2,
    \end{align*}
    which, for $\eps$ small enough, is greater than
    $u_i(\sigma^*)$. Hence
    \begin{align*}
      \sigma_i^* \neq \argmax_{\sigma_i' \in \Delta S_i}g_i^{\sigma^*}(\sigma_i'),
    \end{align*}
    and $\sigma^*$ is not a fixed point of $f$ - contradiction.
  \end{proof}


  \subsection{Best responses}

  Let $G = (N,\{S_i\},\{u_i\})$ be a finite game, and let $\sigma$ be
  a mixed strategy profile in $G$. We say that $s_i \in S_i$ is a {\em
    best response} to $\sigma_{-i}$ if, for all $t_i \in S_i$,
  \begin{align*}
    u_i(\sigma_{-i},s_i) \geq u_i(\sigma_{-i},t_i).
  \end{align*}
  This notion can be naturally extended to mixed strategies.
  
  The following proposition is helpful for understanding mixed
  equilibria.
  \begin{proposition}
    \label{prop:indifference}
    Let $G = (N,\{S_i\},\{u_i\})$ be a finite game, and let $\sigma^*$
    be a mixed Nash equilibrium of $G$. Then any $s_i$ in the support
    of $\sigma_i^*$ (i.e., any $s_i$ to which $\sigma_i^*$ assigns
    positive probability) is a best response to $\sigma_{-i}^*$.
  \end{proposition}
  \begin{proof}
    Suppose $s_i \in S_i$ is in the support of $\sigma_i^*$, but is
    not a best response to $\sigma^*_{-i}$, and let $t_i \in S_i$ be
    some best response to $\sigma^*_{-i}$. We will prove the claim by
    showing that $t_i$ is a profitable deviation for $i$.

    Let $C = u_i(\sigma^*_{-i},t_i)$. Then $u_i(\sigma^*_{-i},r_i) \leq C$
    for any $r_i \in S_i$, and $u_i(\sigma^*_{-i},s_i) < C$. It follows
    that
    \begin{align*}
      u_i(\sigma^*) &= \sum_{r_i \in
                      S_i}\sigma^*_i(r_i)u_i(\sigma^*_{-i},r_i)\\
                      &< C,
    \end{align*}
    and so $t_i$ is indeed a profitable deviation, since it yields
    utility $C$ for $i$.
  \end{proof}

  It follows that if $\sigma^*$ is an equilibrium then
  $u_i(\sigma^*_{-i},s_i)$ is the same for every $s_i$ in the support
  of $\sigma^*_i$. That is, $i$ is indifferent between all the pure
  strategies in the support of her mixed strategy.


  The following claim is also useful for calculating mixed
  equilibria. In its proof we use the fact that if the expectation of
  a random variable $X$ is lower than $x$ then with positive
  probability $X < x$.
  \begin{proposition}
    Let $G = (N,\{S_i\},\{u_i\})$ be a finite game, and let $\sigma$
    be a mixed strategy profile of $G$. Then $\sigma$ is a mixed
    equilibrium if and only if, for every player $i$, every $s_i$ in
    the support of $\sigma_i$ is a best response to $\sigma_{-i}$.
  \end{proposition}
  \begin{proof}
    Assume that $\sigma$ is a mixed equilibrium. Then the claim
    follows by Proposition~\ref{prop:indifference}.

    Assume now that $\sigma$ is not a mixed equilibrium. Then there
    exists a player $i$ and a strategy $\sigma_i'$ such that
    $u_i(\sigma_{-i},\sigma'_i) > u_i(\sigma)$. Hence there exists a
    strategy $s'_i$ such that $u_i(\sigma_{-i},s'_i) >
    u_i(\sigma)$.
    Hence there is some $t_i$ in the support of $\sigma_i$ such that
    $u_i(\sigma_{-i},s'_i) > u_i(\sigma_{-i},t_i)$, and we have proved
    the claim.
  \end{proof}

\newpage
  
  \subsection{Correlated equilibria}

  \subsubsection{Motivating example}
  
  Aumann~\cite{aumann1987correlated} introduced the notion of a {\em
    correlated equilibrium}. Consider the following game, which is
  usually called ``Chicken''. There are two drivers who arrive at the
  same time to an intersection. Each one would like to drive on
  (strategy D) rather than yield (strategy Y), but if both drive then
  they run the risk of damaging the cars. If both yield time is
  wasted, but no egos are hurt. The payoff matrix is the following.
  \begin{center}
    \begin{game}{2}{2}
      & $Y$     & $D$\\
      $Y$   & $3,3$   & $0,5$\\
      $D$ & $5,0$ & $-4,-4$
    \end{game}
  \end{center}
  This game has three Nash equilibria: two pure ($(Y,D)$ and $(D,Y)$)
  and one mixed, in which each player drives with probability $1/3$.

  \begin{exercise}
    Show that this is indeed a mixed equilibrium.
  \end{exercise}

  The players' expected utilities in these equilibria are $(0,5)$,
  $(5,0)$ and $(2,2)$.
  
  A natural way to resolve this conflict is by the installation of a
  traffic light which would instruct each player whether to yield or
  drive. For example, the light could choose uniformly at random from
  $(Y,D)$ and $(D,Y)$. It is easy to convince oneself that a player
  has no incentive to disobey the traffic light, assuming that the
  other player is obeying it. The players' utilities in this case
  become $(2.5,2.5)$.

  One could imagine a traffic light that chooses from
  $\{(Y,Y), (Y,D), (D,Y)\}$, where the first option is chosen with
  probability $p$ and the second and third are each chosen with
  probability $(1-p)/2$. Now, given that a player is instructed to
  drive, she knows that the other player has been instructed to yield,
  and so, if we again assume that the other player is obedient, she
  has no reason to yield.

  Given that a player has been instructed to yield, she knows that the
  other player has been told to yield with conditional probability
  $p_Y = p/(p+(1-p)/2)$ and to drive with conditional probability
  $p_D = ((1-p)/2)/(p+(1-p)/2)$. Therefore, her utility for yielding
  is $3p_Y$, while her utility for driving is $5p_Y - 4p_D$. It thus
  follows that she is not better off disobeying, as long as
  $3p_Y \geq 5p_Y-4p_D$. A simple calculation shows that this is
  satisfied as long as $p \leq 1/2$.

  Now, each player's expected utility is $3p + 5(1-p)/2$. Therefore,
  if we choose $p=1/2$, the players' expected utilities are
  $(2.75, 2.75)$. In this equilibrium the sum of the players' expected
  utilities is larger than in any Nash equilibrium.

  \subsubsection{Definition}
  We now generalize and formalize this idea. Let
  $G = (N,\{S_i\}_{i \in N},\{u_i\}_{i \in N})$ be a finite game. A
  distribution $\mu \in \Delta S$ is a {\em correlated equilibrium} if
  for every player $i$ and every $s_i,t_i \in S_i$ it holds that
  \begin{align}
    \label{eq:corr-def}
    \sum_{s_{-i}}\mu(s_{-i},s_i)u_i(s_{-i},s_i) \geq \sum_{s_{-i}}\mu(s_{-i},s_i)u_i(s_{-i},t_i).
  \end{align}
  Player $i$'s expected utility under a correlated equilibrium $\mu$ is
  simply $\Esub{s \sim \mu}{u_i(s)}$.

  Note that for given $i$ and $s_i$, the condition
  in~\eqref{eq:corr-def} is closed (i.e., if each of a converging
  sequence $\{\mu_n\}$ of distributions satisfies it then so does
  $\lim_n \mu_n$). Note also that if $\mu_1$ and $\mu_2$
  satisfy~\eqref{eq:corr-def} then so does any convex combination of
  $\mu_1$ and $\mu_2$. These observations immediately imply the
  following claim.
  \begin{claim}
    The set of correlated equilibria is a compact, convex subset of
    $\Delta S$.
  \end{claim}

  An advantage of correlated equilibria is that they are easier to
  calculate than Nash equilibria, since they are simply the set of
  solutions to a linear program. It is even easy to find a correlated
  equilibrium that maximizes (for example) the sum of the players'
  expected utilities, or indeed any linear combination of their
  utilities. Finding Nash equilibria can, on the other hand, be a
  difficult problem~\cite{goldberg2006reducibility}.

\newpage
  \subsection{Trembling hand perfect equilibria}

  \subsubsection{Motivating example}
  Recall the Cuban missile crisis game, but this time in strategic
  form. There are two players: the US and the USSR. The USSR has to
  decide whether to station missiles in Cuba ($S$) or not ($N$). If
  the USSR chooses $N$, the US does nothing. If the USSR chooses $S$,
  US has to decide if to start a nuclear war ($W$) or forfeit
  ($F$). The payoff matrix in normal form is the following:
  \begin{center}
    \begin{game}{2}{2}
          & $W$     & $F$\\
      $S$ & $-1000,-1000$   & $1,-1$\\
      $N$ & $0,0$ & $0,0$
    \end{game}
  \end{center}

  There are two equilibria to this game: $(S,F)$ and $(N,W)$. One way
  to eliminate the $(N,W)$ equilibrium is to consider the extensive
  form of this game, and to note that it is not subgame
  perfect. Another approach would be to consider that each player
  might make a mistake with some very small probability. Assume that
  the players play $(N,W)$, but that the USSR makes a mistake with
  some very small probability $\eps > 0$ and plays $S$. Then the
  utility for the US for playing $F$ is $-\eps$, whereas the utility
  for playing $W$ is $-1000\eps$. Hence for any $\eps > 0$, $W$ is
  not a best response for $N$.


  Consider now the equilibrium $(S,F)$, and assume again that USSR
  errs with some probability $\eps > 0$ and plays $N$. Then the
  utility for the US for playing $W$ is $-1000\cdot(1-\eps)$, while
  the utility for playing $F$ is $-(1-\eps)$, and so under any such
  perturbation $F$ is a still a best response. From the point of view
  of the USSR, if the US errs and plays $W$ with probability $\eps$,
  the utility for playing $S$ is $-1000\eps+(1-\eps)=1-1001\eps$,
  while the utility for playing $N$ is $0$. Thus, for $\eps$ small
  enough, $S$ is still a best response.
  
  In a {\em trembling hand perfect equilibrium} we require each
  strategy to be a best response if it still is a best response for
  some arbitrarily small error. The formal definition follows.

  

  \subsubsection{Definition and results}
  
  Let $G = (N,\{S_i\},\{u_i\})$ be a finite game, and let $\sigma$ be
  a mixed strategy profile in $G$. We say that $\sigma_i$ is
  completely mixed if it assigns positive probability to each
  $s_i \in S_i$.

  A mixed strategy profile $\sigma$ is called a {\em trembling hand
    perfect equilibrium}~\cite{selten1975reexamination} if there
  exists a sequence of completely mixed strategy profiles
  $\{\sigma^k\}_{k \in \N}$ that converge to $\sigma$ and such that,
  for each $i \in N$ and $k \in \N$, $\sigma_i$ is a best response to
  $\sigma^k_{-i}$.

  An equivalent definition is that $\sigma$ is {\em not} a trembling
  hand perfect equilibrium if there is some $\eps>0$ such that for
  every completely mixed strategy $\tau$ with $|\tau-\sigma|<\eps$
  there is a player $i$ such that $\sigma_i$ is not a best response to
  $\tau$.

  \begin{exercise}
    Prove that these definitions are equivalent.
  \end{exercise}
  
  
  We state without proof that every finite game has a trembling hand
  perfect equilibrium.
  
  \begin{exercise}
    Show that every trembling hand perfect equilibrium is a Nash
    equilibrium.
  \end{exercise}
  
  
  \begin{claim}
    Let $s_i$ be a weakly dominated strategy of player $i$. Then
    $\sigma_i(s_i) = 0$ in any trembling hand perfect equilibrium
    $\sigma$.
  \end{claim}
  \begin{proof}
    Let $\{\sigma^k\}_{k \in \N}$ be a sequence of completely mixed
    strategy profiles that converge to $\sigma$, and such that
    $\sigma_i$ is a best response to $\sigma^k_{-i}$ for all $i$ and
    $k$.

    Since $s_i$ is weakly dominated then there exists an $s_{-i}$ and
    a $t_i$ such that
    \begin{align*}
      u_i(s_{-i},s_i) < u_i(s_{-i},t_i).
    \end{align*}
    Since $\sigma^k(s_{-i},s_i) > 0$, and since
    $u_i(s_{-i}',s_i) \leq u_i(s_{-i}',t_i)$ for all $s_{-i}'$, it
    follows that $s_i$ is not a best response to $\sigma^k_{-i}$, and
    thus $\sigma_i(s_i)=0$.
  \end{proof}

  In fact, for finite two player games, if $\sigma$ is a mixed Nash
  equilibrium in which every strategy is not weakly dominated (as a
  mixed strategy), then $\sigma$ is trembling hand perfect. In
  general, this is not true for games with more than two players.


  \newpage
  \subsection{Zero-sum games}


  \subsubsection{Motivating example}

  Consider the following game~\cite{o1987nonmetric}. We write here
  only the utilities of the row player. The utilities of the column
  player are always minus those of the row player.
  \begin{center}
    \begin{game}{4}{4}
          & $J$      & $1$     & $2$    & $3$   \\
      $J$ & $+1$   & $-1$  & $-1$ & $-1$ \\
      $1$ & $-1$   & $-1$  & $+1$ & $+1$ \\
      $2$ & $-1$   & $+1$  & $-1$ & $+1$ \\
      $3$ & $-1$   & $+1$  & $+1$ & $-1$ 
    \end{game}
  \end{center}

  
  Consider the point of view of the row player, and assume that she
  uses the mixed strategy $\sigma_R$ in which $J$ is played with some
  probability $q$ and each of $1$, $2$ and $3$ is played with
  probability $(1-q)/3$. Then
  \begin{align*}
    u_R(\sigma_R,J) = 2q-1\quad\mbox{ and }\quad u_R(\sigma_R,1) =
    u_R(\sigma_R,2) = u_R(\sigma_R,3) = 1/3-4q/3.
  \end{align*}
  If we assume that the column player knows what $q$ is and would do
  what is best for her (which here happens to be what is worst for the
  row player), then the row player would like to choose $q$ that
  maximizes the minimum of $\{2q-1,1/3-4q/3\}$. This happens when
  $q=2/5$, in which case the row player's utility is $-2/5$, regardless
  of which (mixed!) strategy the column player chooses.

  The same reasoning can be used to show that the column player will
  also choose $q=2/5$.  Her expected utility will be be $+1/5$. Note
  that this strategy profile (with both using $q=2/5$) is a mixed Nash
  equilibrium, since both players are indifferent between all
  strategies.
  
  \subsubsection{Definition and results}
  
  A two player game $G = (\{1,2\},\{S_i\},\{u_i\})$ is called {\em
    zero-sum} if $u_1 + u_2 = 0$. For such games we drop the subscript
  on the utility functions and use $u := u_1$.

  A general normal form game may have {\em cooperative} components
  (see, e.g., the battle of the sexes game), in the sense that moving
  from one strategy profile to another can benefit both
  players. However, zero-sum games are {\em competitive}: whatever one
  player gains the other loses. Hence a player may want to prepare
  herself for the worst possible outcome, namely one in which, given
  her own strategy, her opponent will choose the strategy yielding her
  the minimal utility. Hence an interesting quantity for a strategy
  $\sigma_1$ for player 1 is the guaranteed utility $u_g$ when playing
  $\sigma_1$:
  \begin{align*}
    u_g(\sigma_1) = \min_{\sigma_2 \in \Delta S_2}u(\sigma_1,\sigma_2).
  \end{align*}
  Continuing with this line of reasoning, player 1 will choose a
  strategy that maximizes her guaranteed utility. She would thus
  choose an action in\footnote{The argmax of an expression is in
    general a set, rather than a single value.}
  \begin{align*}
    \argmax_{\sigma_1 \in \Delta S_1}u_g(\sigma_1)= \argmax_{\sigma_1 \in \Delta S_1}\min_{\sigma_2 \in \Delta S_2}
    u(\sigma_1,\sigma_2).
  \end{align*}
  Any such strategy is called a {\em maxmin} strategy for player 1. It
  gives her the best possible guaranteed utility, which is
  \begin{align*}
    \max_{\sigma_1 \in \Delta S_1}u_g(\sigma_1) = \max_{\sigma_1 \in \Delta S_1}\min_{\sigma_2 \in \Delta S_2}
    u(\sigma_1,\sigma_2).
  \end{align*}

  The next theorem shows that maxmin strategies and mixed Nash
  equilibria are closely related in zero-sum games.
  \begin{theorem}[Borel, 1921, von Neumann, 1928]
    \label{thm:zero-sum}
    Let $G$ be a finite zero-sum game.
    \begin{enumerate}
    \item In every mixed Nash equilibrium $\sigma^*$ each strategy is
      a maxmin strategy for that player.
    \item There is a number $v \in \R$ such that
      \begin{align*}
        \max_{\sigma_1 \in \Delta S_1}\min_{\sigma_2 \in \Delta S_2}
        u(\sigma_1,\sigma_2) = v.
      \end{align*}
      and
      \begin{align*}
        \max_{\sigma_2 \in \Delta S_2}\min_{\sigma_1 \in \Delta S_1}
        -u(\sigma_1,\sigma_2) = -v.
      \end{align*}
    \end{enumerate}
  \end{theorem}
  The quantity $v$ is called the {\em value} of $G$. It follows that
  $u(\sigma^*) = v$ for any equilibrium $\sigma^*$.



  % \begin{proof}[Proof of Theorem~\ref{thm:zero-sum}]
  %   In this proof we will disencumber notation by shortening
  %   $\max_{\sigma_1 \in \Delta S_1}$ to simply $\max_{\sigma_1}$,
  %   etc. 
  %   \begin{enumerate}
  %   \item Let $\sigma^*$ be a mixed Nash equilibrium of $G$.  Without
  %     loss of generality, it suffices to show that $\sigma_1^*$ is a
  %     maxmin strategy for player 1.

  %     Since $\sigma_1^*$ is a best response of player 1,
  %     \begin{align*}
  %       \max_{\sigma_1}u(\sigma_1,\sigma_2^*) =  u(\sigma_1^*,\sigma_2^*).
  %     \end{align*}
  %     Since
  %     $\min_{\sigma_2}u(\sigma_1,\sigma_2) \leq
  %     u(\sigma_1,\sigma_2^*)$, it follows from maximizing both sides that
  %     \begin{align}
  %       \label{eq:maxmin-nash}
  %       \max_{\sigma_1}\min_{\sigma_2}u(\sigma_1,\sigma_2) \leq
  %       \max_{\sigma_1}u(\sigma_1,\sigma_2^*) = u(\sigma_1^*,\sigma_2^*),
  %     \end{align}
  %     where the equality is the previous display.

  %     To show the other direction, note that since $\sigma_2^*$ is a
  %     best response of player 2, it maximizes her utility, which,
  %     since this is a zero-sum game, minimizes player 1's
  %     utility. Hence we have that
  %     $\min_{\sigma_2}u(\sigma_1^*,\sigma_2) =
  %     u(\sigma_1^*,\sigma_2^*)$. Hence
  %     \begin{align*}
  %       \max_{\sigma_1}\min_{\sigma_2}u(\sigma_1,\sigma_2) \geq u(\sigma_1^*,\sigma_2^*).       
  %     \end{align*}

  %   \item Let $\sigma^*$ be an arbitrary mixed equilibrium of $G$; at
  %     least one exists by Nash's Theorem. Since, as we have just
  %     established, $\sigma^*$ is a maxmin strategy for player 1, it
  %     follows that 
  %     \begin{align*}
  %       \max_{\sigma_1}\min_{\sigma_2}u(\sigma_1,\sigma_2) = u(\sigma^*).
  %     \end{align*}
  %     The same argument applied with the roles of the players reversed
  %     shows that
  %     \begin{align*}
  %       \max_{\sigma_1}\min_{\sigma_2}-u(\sigma_1^*,\sigma_2) = -u(\sigma^*),
  %     \end{align*}
  %     and thus our proof is complete, with $v = u(\sigma^*)$.
  %   \end{enumerate}
  % \end{proof}
  % In this proof we used Nash's Theorem to generate a mixed Nash
  % equilibrium of this game. In fact, the existence of Nash equilibria
  % in zero-sum games can be proved using convex analysis methods, and
  % this was done by Borel~\cite{borel1921theorie} and von
  % Neumann~\cite{neumann1928theorie} long before Nash's
  % Theorem. Moreover, in zero-sum games equilibria can be found by
  % solving a linear program, which, as observed in the previous
  % section, is easier than the general problem of finding mixed Nash
  % equilibria.


  \section{Knowledge and belief}

  \subsection{Knowledge}
  \subsubsection{The hats riddle}
  The hats riddle is a motivating example for studying knowledge.
  Consider $n$ players, each of which is wearing a hat that is either
  red (r) or blue (b). The players each observe the others' hats, but
  do not observe their own.

  An outside observer announces in the presence of all the players
  that ``At least one of you has a red hat.'' They now play the
  following (non-strategic) game: a clock is set to ring every
  minute. At each ring, anyone who knows the color of their hat
  announces it, in which case the game ends. Otherwise the game
  continues.

  \begin{exercise}
    What happens?
  \end{exercise}
  We will formally analyze what transpires, after introducing some
  concepts and notation.

  \subsubsection{Knowledge spaces}
  Consider a situation in which there is uncertainty regarding one or
  more variables of interest. The set of all possible combinations of
  values of these variables is called the set of {\em states of the
    world}, so that knowing the state of the world is equivalent to
  knowing all there is to know and thus having no uncertainty.

  We refer to a player's {\em type} as the information (or the type of
  information) this player has regarding the state of the world. Thus,
  for example, one player may know one variable of interest, another
  player may know another variable, and a third could know the sum of
  the first two variables. A fourth could just know whether the first
  variable is non-zero.
  
  Formally, a {\em knowledge space}\footnote{This terminology is
    non-standard.}  is a tuple
  $(N,\Omega, \{T_i\}_{i \in N},\{t_i\}_{i \in N})$ where
  \begin{itemize}
  \item $N$ is a set of players.
  \item $\Omega$ is the space of the {\em states of the world}. We
    will assume here that $\Omega$ is finite.\footnote{And treat
      infinite cases informally, without delving into measurability
      issues.}
  \item $T_i$ the space of possible types of player $i$. 
  \item $t_i \colon \Omega \to T_i$ is player $i$'s {\em private
      signal} or {\em type}.
  \end{itemize}
  We define the information partition function
  $P_i \colon \Omega \to 2^\Omega$ by
  \begin{align*}
    P_i(\omega) = t_i^{-1}(t_i(\omega)). 
  \end{align*}
  That is, $P_i(\omega)$ is the set of states of the world for which
  player $i$ has the same type as she does in $\omega$. It is easy to
  show that $\omega \in P_i(\omega)$. The set
  $\{P_i(\omega)\}_{\omega \in \Omega}$ is easily seen to be a
  partition of $\Omega$, and is usually called $i$'s {\em information
    partition}. A knowledge space can thus be given as
  $(N,\Omega, \{P_i\}_{i \in N})$.

  
  As an example, let $\Omega$ be the set of all possible outcomes of
  tossing a pair of dice:
  $$\Omega = \{(k,\ell),:\,k,\ell =1,\ldots,6\}.$$

  Let $N = \{1,2\}$, let $T_1 = \{1,2,\ldots,6\}$ with
  \begin{align*}
    t_1(\omega) = t_1(k,\ell) = k
  \end{align*}
  and let $T_2 = \{2,\ldots,12\}$ with
  \begin{align*}
    t_2(\omega) = t_2(k,\ell) = k + \ell.
  \end{align*}
  So player $1$ sees the first die, and player 2 knows their sum.

  As another example, consider the knowledge space associated to the
  hats riddle, before it is declared that at least one player has a
  red hat. Here, $\Omega = \{r,b\}^n$, $T_i = \{r,b\}^{n-1}$ and
  $t_i(\omega) = \omega_{-i}$.


  

  \subsubsection{Knowledge}

  Let $(N,\Omega, \{T_i\}_{i \in N},\{t_i\}_{i \in N})$ be a
  knowledge space. Let $A \in 2^\Omega$ be an event. We say that player
  $i$ {\em knows} $A$ at $\omega$ if $P_i(\omega) \subseteq A$, or,
  equivalently, if $t_i(\omega') = t_i(\omega)$ implies that
  $\omega' \in A$. Intuitively, when $\omega$ occurs, $i$ does not
  know that - she only knows that $P_i(\omega)$ occurred. She thus
  knows that $A$ occurred only if $P_i(\omega)$ is contained in $A$.


  Given an event $A \in 2^\Omega$, let $K_i A$ be the set of states of
  the world in which $i$ knows $A$:
  \begin{align*}
    K_i A = \{\omega\,:\, P_i(\omega) \subseteq A\}.
  \end{align*}
  Equivalently,
  \begin{align*}
    K_i A = \bigcup \{P_i(\omega) \,:\, P_i(\omega) \subseteq A\}.
  \end{align*}

  \begin{theorem}[Kripke's S5 system]
    \label{thm:kripke}
    \begin{enumerate}
    \item $K_i \Omega = \Omega$. A player knows that some state of the
      world has occurred.
    \item $K_i A \cap K_i B = K_i(A \cap B)$. A player knows $A$ and a
      player knows $B$ if and only if she knows $A$ and $B$.
    \item {\em Axiom of knowledge.} $K_i A \subseteq A$. If a player
      knows $A$ then $A$ has indeed occurred.
    \item {\em Axiom of positive introspection.} $K_i K_i A = K_i
      A$. If a player knows $A$ then she knows that she knows $A$.
    \item {\em Axiom of negative introspection.}
      $(K_i A)^c = K_i((K_i A)^c)$. If a player does not know $A$ then
      she knows that she does not know $A$.
    \end{enumerate}
  \end{theorem}
  \begin{proof}
    \begin{enumerate}
    \item This follows immediately from the definition.
    \item
      \begin{align*}
        K_i A \cap K_i B
        &= \{\omega\,:\, P_i(\omega) \subseteq A\} \cap \{\omega\,:\,
          P_i(\omega) \subseteq B\}\\
        &= \{\omega\,:\, P_i(\omega) \subseteq A, P_i(\omega) \subseteq B\}\\
        &= \{\omega\,:\, P_i(\omega) \subseteq A \cap B\}\\
        &= K_i(A \cap B).
      \end{align*}
    \item By definition, if $\omega \in K_i A$ then
      $P_i(\omega) \subseteq A$.  Since $\omega \in P_i(\omega)$, it
      follows that $\omega \in A$. Hence $K_i A \subseteq A$.
    \item By the previous part we have that
      $K_i K_i A \subseteq K_i A$.

      To see the other direction, let $\omega \in K_i A$, so that
      $P_i(\omega) \subseteq A$. Choose any $\omega' \in P_i(\omega)$.
      Hence $P_i(\omega') = P_i(\omega)$, and it follows that
      $\omega' \in K_i A$. Since $\omega'$ was an arbitrary element of
      $P_i(\omega)$, we have shown that $P_i(\omega) \subseteq K_i
      A$. Hence, by definition, $\omega \in K_i K_i A$.

    \item The proof is similar to that of the previous part.
    \end{enumerate}
  \end{proof}

  Interestingly, if a map $L \colon 2^\Omega \to 2^\Omega$ satisfies the
  Kripke S5 system axioms, then it is the knowledge operator for some
  type: there exists a type space $T$ and a function
  $t \colon \Omega \to 2^\Omega$ such that $L$ is equal to the
  associated knowledge operator given by
  \begin{align*}
    K A = \{\omega\,:\,P(\omega) \subseteq A\},
  \end{align*}
  where $P(\omega) = t^{-1}(t(\omega))$.

  \subsubsection{Knowledge in terms of self-evident event algebras}

  An event $A \subset 2^\Omega$ is said to be {\em self-evident} to
  player $i$ if $K_i A = A$. Let $\sigalg_i$ be the collection of self
  evident events.
  \begin{claim}
    \begin{enumerate}
    \item $A$ is self-evident if and only if it is the union of
      partitions elements $P_i(\omega)$.
    \item $\sigalg_i$ is an {\em algebra}:
      \begin{enumerate}
      \item $\Omega \in \sigalg_i$.
      \item If $S \in \sigalg_i$ then $S^c \in \sigalg_i$.
      \item If $A,B \in \sigalg_i$ then $A \cup B \in \sigalg_i$.
      \end{enumerate}
    \end{enumerate}
  \end{claim}

  As an alternative to specifying the partition elements
  $P_i(\omega)$, one can specify the (self-evident) event algebras
  $\sigalg_i$. We can recover $P_i(\omega)$ from $\sigalg_i$ by
  \begin{align*}
    P_i(\omega) = \cap \{S \in \sigalg_i\,:\,\omega \in S\}.
  \end{align*}
  Accordingly, we will occasionally define knowledge spaces using these
  event algebras only. That is, a knowledge space will be given by a
  tuple $(N,\Omega,\{\sigalg_i\}_{i \in N})$.


  
  \begin{proposition}
    \label{prop:knowlege-alg}
    Let $A \in 2^\Omega$. Then $K_i A \in \sigalg_i$, and in
    particular
    \begin{align*}
      K_i A = \cup \{S \in \sigalg_i\,:\,S \subseteq A\}.
    \end{align*}
  \end{proposition}
  Since any event algebra is closed to unions, it follows that
  $K_i A$ is the largest element of $\sigalg_i$ that is contained in
  $A$:
  \begin{align*}
    K_iA = \max\{S \in \sigalg_i\,:\,S \subseteq A\}.
  \end{align*}
  Hence $K_i A$ is always self-evident. This makes the proof of the
  axioms of introspection and negative introspection immediate.
  
  It is important to note that we can take this to be a definition of
  $K_i$. The advantage of this definition is that it is entirely in
  terms of our newly defined algebras $\{\sigalg_i\}$.





  \begin{exercise}
    Given a knowledge space
    $B = (N,\Omega,\{\sigalg_i\}_{i \in N})$ find a knowledge space
    $B' = (N,\Omega, \{T_i\}_{i \in N},\{t_i\}_{i \in N})$ such that
    each $\sigalg_i$ is the algebra generated by player $i$'s
    information partition in $B'$.
  \end{exercise}
  \newpage
  

  \subsubsection{Common knowledge}
  Let $(N,\Omega, \{T_i\}_{i \in N},\{t_i\}_{i \in N})$ be a finite
  knowledge space. An event $A$ is said to be {\em common knowledge} at
  $\omega \in \Omega$ if for any sequence $i_1,i_2,\ldots,i_k \in N$
  it holds that
  \begin{align*}
    \omega \in K_{i_1} K_{i_2} \cdots K_{i_k} A.
  \end{align*}

  We will give two alternative ways of thinking about common knowledge
  events. In order to introduce these we will need a few definitions.
  
  Let $\sigalg, \sigalgp$ be two sub-algebras of some
  algebra. We say that $\sigalg$ is a {\em refinement} of
  $\sigalgp$ if $\sigalgp \subseteq \sigalg$. In this case we also say
  that $\sigalgp$ is a {\em coarsening} of $\sigalg$. In terms of the
  partitions that generate these algebras, this is the same as saying
  that each of the information sets that generates $\sigalgp$ is a
  union of the corresponding sets associated with $\sigalg$.

  The {\em meet} of two algebras is
  $\sigalg_1, \sigalg_2 \subseteq \sigalg$ is the finest
  sub-algebra of $\sigalg$ that is a coarsening of each
  $\sigalg_i$. Their {\em join} is the coarsest sub-algebra of
  $\sigalg$ that is a refinement of each $\sigalg_i$.

  \begin{exercise}
    Show that the meet of $\sigalg_1$ and $\sigalg_2$ is their
    intersection $\sigalg_1 \cap \sigalg_2$. Show that their join is
    the algebra generated by their union.
  \end{exercise}

  
  Let $\sigalg_C = \cap_i\sigalg_i$ be the meet of the player's
  algebras.


  \begin{claim}
    \label{clm:sigalg-c}
    The following are equivalent:
    \begin{enumerate}
    \item $C \in \sigalg_C$.
    \item $K_i C = C$ for all $i \in N$.
    \end{enumerate}
  \end{claim}
  \begin{proof}

    We note first that $K_i A = A$ iff $A \in \sigalg_i$. This follows
    from Proposition~\ref{prop:knowlege-alg}.
    
    Hence $K_i C = C$ iff $C \in \sigalg_i$ for all $i$ iff
    $C \in \sigalg_C$, as $\sigalg_c = \cap_i\sigalg_i$.
  \end{proof}

  Recall that, by Proposition~\ref{prop:knowlege-alg},  
  \begin{align*}
    K_i A = \cup \{S \in \sigalg_i\,:\,S \subseteq A\} = \max \{S \in \sigalg_i\,:\,S \subseteq A\}.
  \end{align*}
  Analogously we define
  \begin{align*}
    K_C A = \cup \{S \in \sigalg_C\,:\,S \subseteq A\} = \max \{S \in \sigalg_C\,:\,S \subseteq A\}.
  \end{align*}
  As we show in Theorem~\ref{thm:common-knowledge} below, $K_C A$ is
  the set of states of the world in which $A$ is common knowledge.

  Another way of thinking about common knowledge is through the
  undirected graph $G_C$, whose vertices are the elements of $\Omega$,
  and where there is an edge between $\omega,\omega' \in \Omega$ if
  there exists a player $i$ such that $P_i(\omega) =
  P_i(\omega')$.
  Let $C(\omega)$ be the {\em connected component} of $\omega$; that
  is the maximal set of vertices in the graph for which there exists a
  path from $\omega$. Here, a path from $\omega$ to $\omega'$ is a
  sequence of edges
  $(\omega_1,\omega_2),(\omega_2,\omega_3),(\omega_3,\omega_4),\ldots,(\omega_{k-1},\omega_k)$
  such that $\omega_1 = \omega$ and $\omega_k = \omega'$.
  

  \begin{theorem}
    \label{thm:common-knowledge}
    Given a finite knowledge space
    $(N,\Omega, \{\sigalg_i\}_{i \in N})$, a
    state of the world $\omega \in \Omega$ and an event
    $A$, the following are equivalent.
    \begin{enumerate}
    \item $A$ is common knowledge at $\omega$.
    \item $C(\omega) \subseteq A$.
    \item $\omega \in K_C A$.
    \end{enumerate}
  \end{theorem}
  \begin{proof}
    We first show that (1) implies (2). Choose an arbitrary
    $\omega' \in C(\omega)$; we will show that $\omega' \in A$.  Since
    $\omega' \in C(\omega)$, there exists a path
    $(\omega_1,\omega_2),(\omega_2,\omega_3),\ldots,(\omega_{k-1},\omega_k)$
    such that $\omega_1 = \omega$ and $\omega_k = \omega'$. There
    exists therefore a sequence of players $i_1,\ldots,i_{k-1}$ such
    that $P_{i_j}(\omega_j) = P_{i_j}(\omega_{j+1})$.

    Now, by the common knowledge assumption
    \begin{align*}
      \omega = \omega_1 \in K_{i_1}K_{i_2}\cdots K_{i_{k-1}} A.
    \end{align*}
    Hence
    \begin{align*}
      P_{i_1}(\omega_1) \in K_{i_2}\cdots K_{i_{k-1}} A 
    \end{align*}
    and in particular
    \begin{align*}
      \omega_2 \in K_{i_2}\cdots K_{i_{k-1}} A,
    \end{align*}
    since $\omega_2 \in P_{i_1}(\omega_1)$. Applying this argument
    inductively yields $\omega' = \omega_k \in A$, and thus we have
    shown that $C(\omega) \subseteq A$.
    
    
    To show that (2) implies (3) we first prove that $C(\omega) \in
    \sigalg_C$. To this end it suffices to
    show that $C(\omega) \in \sigalg_i$ for all $i \in N$. Let
    $\omega' \in C(\omega)$. Then, by the definition of the graph $G$,
    $P_i(\omega') \subseteq C(\omega)$. Hence $C(\omega)$ is a union
    of sets of the form $P_i(\omega')$, and thus it is an element of
    $\sigalg_i$.

    Now, assuming (2), $\omega \in C(\omega) \subseteq A$. Therefore,
    by the definition of $K_C$, $\omega \in K_C A$.


    Finally, we show that (3) implies (1). Because $\omega \in K_C$
    then there is some $C \in \sigalg_C$ such that $\omega \in C$ and
    $C \subseteq A$. Let $i_1,i_2,\ldots,i_k$ be an arbitrary sequence
    of players. We first prove that
    \begin{align*}
      \omega \in K_{i_1} K_{i_2} \cdots K_{i_k} C.
    \end{align*}
    Indeed, by Claim~\ref{clm:sigalg-c},
    \begin{align*}
      K_{i_1} K_{i_2} \cdots K_{i_k} C = C,
    \end{align*}
    and since $\omega \in C$, we have shown that
    \begin{align*}
      \omega \in K_{i_1} K_{i_2} \cdots K_{i_k} C.
    \end{align*}
    Since $C \subseteq A$, 
    \begin{align*}
      K_{i_1} K_{i_2} \cdots K_{i_k} C \subseteq K_{i_1} K_{i_2} \cdots K_{i_k} A
    \end{align*}
    and thus we also have that
    \begin{align*}
      \omega \in K_{i_1} K_{i_2} \cdots K_{i_k} A.
    \end{align*}
  \end{proof}

  \subsubsection{Back to the hats riddle}
  
  Recall the knowledge space associated to the hats riddle (before the
  declaration that there is at least one red hat):
  $\Omega = \{r,b\}^n$, $T_i = \{r,b\}^{n-1}$ and
  $t_i(\omega) = \omega_{-i}$.

  The information partition functions are
  \begin{align*}
    P_i(\omega) = \{(\omega_{-i},r), (\omega_{-i},b)\}.
  \end{align*}

  Thus the set of edges of the graph $G_C$ is exactly given by
  \begin{align*}
    E = \{P_i(\omega)\}_{i,\omega} = \big\{\{(\omega_{-i},r),
    (\omega_{-i},b)\}\,:\, \omega_{-i} \in \{r,b\}^{n-1}\big\}.
  \end{align*}

  \begin{claim}
    $\sigalg_C = \{\emptyset,\Omega\}$.
  \end{claim}
  \begin{proof}
    It is easy to see that for every $\omega,\omega' \in \Omega$ there
    is a sequence of edges (corresponding to the coordinates in which
    they differ) that forms a path from $\omega$ to $\omega'$ in
    $G_C$. Thus $C(\omega) = \Omega$, and the events that can be
    common knowledge are $\Omega$ and $\emptyset$.
  \end{proof}

  In particular in no state is it common knowledge that there is at least one
  red hat, even when everyone has one. 
  
  \newpage
  % Let $R^{\geq k}$ be the event that there are at least $k$ red
  % hats. Let $R^k$ be the event that there are exactly $k$ red hats
  % After the declaration that at least one person has a red hat
  % $R^{\geq 1}$ becomes common knowledge.
  
  % \begin{theorem}
  %   \label{thm:hats}
  %   Assume that $\omega \in R^k$, so that there are $k$ red hats.
  %   Then
  %   \begin{enumerate}
  %   \item At round $k$ all players with red hats declare their color,
  %   \item At the beginning of each round $\ell < k$ it holds that
  %     \begin{enumerate}
  %     \item $R^{\geq \ell}$ is common knowledge.
  %     \item No player knows the color of their own hat, i.e., none
  %       declare.
  %     \end{enumerate}
  %   \end{enumerate}
  % \end{theorem}
  % \begin{proof}
  %   For $k=1$ the claim is trivial, since players know that there is
  %   at least one red hat, and since the players with the red hats see
  %   no other red hats and thus learn their own color. We prove that
  %   the claim holds for $k > 1$, assuming by induction that it holds
  %   up to $k - 1$.
    
  %   We will start with (2), which we prove by induction on $\ell$. For
  %   $\ell=1$ it indeed holds that $R^{\geq 1}$ is common knowledge,
  %   since this was just declared. Since $k > 1$, each player can
  %   observe at least $k-1>0$ red hats, and therefore does not know her
  %   own color.

  %   Assume that (2) holds for $\ell-1$. By our first inductive
  %   assumption, players with red hats declare at round $k$. Hence,
  %   after no player declares, it becomes common knowledge that
  %   $R^{\ell}$ did not occur. Since $R^{\geq \ell-1}$ is already
  %   common knowledge, $R^{\ell}$ becomes common knowledge. Since $\ell
  %   < k$ 

    
  %   player knows how many red hat there are, since knowing that is the
  %   same as knowing the color of one's hat. , and since no one
  %   declares, it also becomes common knowledge that $k > \ell-1$, or
  %   that $R^{\geq \ell}$.
  % \end{proof}
  

  % We will prove this theorem using the following lemma:
  % \begin{lemma}
  %   Assume that at some round it holds that $R^{\geq k}$ is common
  %   knowledge at some $\omega$. If $\omega \in R^k$ then all the
  %   players with red hats will declare their color. Otherwise
  %   $R^{\geq k+1}$ becomes common knowledge.
  % \end{lemma}
  % \begin{proof}
  %   Assume that $R^{\geq k}$ is common knowledge at $\omega$ on some
  %   round. If $\omega \in R^k$ then every player with a red hat
  %   observes exactly $k-1$ other red hats, and so knows that
  %   $\omega \in R^k$, and hence will declare her color. Thus if no-one
  %   declares then $\omega \not \in R^k$, and furthermore this becomes
  %   common knowledge. Hence it becomes common knowledge that
  %   $\omega \in R^{\geq k+1}$.
  % \end{proof}
  
  % \begin{proof}[Proof of Theorem~\ref{thm:hats}]
  %   We first prove by induction that $R^{\geq \ell}$ is common
  %   knowledge the beginning of round $\ell \leq k$. At the beginning
  %   of round 1 $R^{\geq 1}$ is common knowledge, as it was declared.
  %   Assume that we have shown the claim for $\ell-1$. Then if player 1
  %   did not declare her color at round $\ell-1$ then, by the inductive
  %   assumption $R^{\geq \ell-1}$ was common knowledge at the beginning
  %   of that round, and thus by the lemma $R^{\geq \ell}$ becomes
  %   common knowledge.

  %   Applying this to $\ell = k$ we get that $R^k$ is common
  %   knowledge at the beginning of round $k$. Hence, by another
  %   application of the lemma, all the players with the red hats will
  %   declare their colors.
  % \end{proof}
  
  \subsection{Beliefs}
  A {\em belief} of a player over a finite space $\Omega$ is a probability
  measure on $\Omega$.

  \subsubsection{A motivating example}
  \label{sec:beliefs-example}
  Beliefs are useful for modeling uncertainty.  For example, consider
  a monopoly seller who would like to sell a single object to a single
  buyer. The value of the product to the buyer is $v$.  The sellers
  sets a price $p$; hence her strategy space is $\R$. The buyer learns
  $p$ and then decides to either buy or not to buy. Thus her
  strategies can each be characterized by a set $B \subset \R$ of the
  prices in which she decides to buy.

  If the buyer buys then her utility is $v-p$, and the seller's
  utility is $p$. Otherwise both have zero utility.  Note that this is
  an (infinite) extensive form game with perfect information.

  \begin{exercise}
    Prove that if the seller knows $v$ then a subgame perfect
    equilibrium is for the seller to choose $p=v$ and for the buyer to
    buy if and only if $p \leq v$.
  \end{exercise}

  We would like to model the case in which the seller does not know
  $v$ exactly. One way to do this is to assume that the seller has
  some {\em belief} $\mu$ over $v$. That is, she believes that $v$ is
  chosen at random from $\mu$. Given this belief, she now has to
  choose a price $p$. The seller first learns $v$. She then learns $p$
  and has to decide whether or not to buy. In a subgame perfect
  equilibrium, she will buy whenever $v\geq p$, or whenever $v > p$.
  The buyer's utility is now the expected price that the seller paid,
  given that she bought, and where expectations are taken with respect
  to $\mu$. The buyer's utility is, as before, $v-p$ if she buys and
  zero otherwise.

  Assume that the seller's belief can be represented by a probability
  distribution function $f \colon [0,\infty) \to \R$, so that the
  probability that $v \in [a,b)$ is $\int_a^b f(v)\dd v$.  In this
  case it will not matter whether the buyer's strategy is to buy
  whenever $p \leq v$ or whenever $p < v$; the following calculation
  will be the same in both cases, since player 1's belief is
  non-atomic. Then the seller's utility is
  \begin{align*}
    u_S(p) = p \cdot \int_p^\infty f(v)\dd v,
  \end{align*}
  which we can write as $p \cdot (1-F(p))$, where
  $F(x) = \int_0^x f(x)\dd x$ is the cumulative distribution function
  associated with $f$. To find the seller's best response we need to
  find a maximum of $u_S$. Its derivative with respect to $p$ is
  \begin{align*}
    \frac{\dd u_S}{\dd p} = 1-F(p) -p \cdot f(p).
  \end{align*}
  Hence in any maximum it will be the case that
  \begin{align*}
    p = \frac{1-F(p)}{f(p)}.
  \end{align*}
  It is easy to show that if this equation has a single solution then
  this solution is a maximum. In this case $p$ is called the {\em
    monopoly price}.

  
  \begin{exercise}
    Let
    \begin{align*}
      f(v) =
      \begin{cases}
        0& \mbox{if } v < v_0\\
        \frac{v_0}{v^2}&\mbox{if } v \geq v_0
      \end{cases}
    \end{align*}
    for some $v_0$. Calculate $u_S(p)$.  Under the seller's belief,
    what is the buyer's expected utility as a function of $p$?
  \end{exercise}
  
  \begin{exercise}
    Let $f(v) = \frac{1}{v_0} \cdot e^{-v / v_0}$ for some $v_0 > 0$.
    Calculate the monopoly price. Under the seller's belief, what is
    the buyer's expected utility as a function of $p$?
  \end{exercise}

  
  \subsubsection{Belief spaces}

  A {\em belief space} is a tuple
  $(N,\Omega, \{\mu_i\}_{i \in N},\{T_i\}_{i \in
    N},\{t_i\}_{i \in N})$ where
  \begin{itemize}
  \item
    $(N,\Omega ,\{T_i\}_{i \in
      N},\{t_i\}_{i \in N})$ is a knowledge space.
  \item $\mu_i$ is player $i$'s belief over $\Omega$.
  \end{itemize}

  We denote by $\CondPsub{i}{A}{t_i}$ the probability, under $\mu_i$,
  of the event $A$, conditioned on $t_i$. When the underlying
  knowledge space is given in terms of algebras, we write this as
  $\CondPsub{i}{A}{\sigalg_i}$
  
  When $\Omega$ is finite, this is given by
  \begin{align}
    \label{eq:belief-cond-prob-finite}
    \CondPsub{i}{A}{\sigalg_i}(\omega) = \frac{\mu_i(E \cap P_i(\omega))}{\mu_i(P_i(\omega))}.
  \end{align}

  Note that $\CondPsub{i}{A}{\sigalg_i}$ is a {\em function} from
  $\Omega$ to $\R$.

  If the different $\mu_i$'s are equal then we say that the players
  have a {\em common prior}. This will be our standing assumption.

  Consider again the example of the two weather forecasters.  The
  forecasters believe that half the days have rain and a half do
  not, that their programs predict the future with some probability
  $p > 1/2$, and that the programs fail or succeed independently from
  each other. This is reflected in the common prior $\mu$, as detailed
  in Table~\ref{table:common-prior-example}.  \def\arraystretch{1.5}
  \begin{table}[h]
    \bgroup
    \label{table:common-prior-example}
    \centering
    \begin{tabular}{c|c|c|c|c}
      $\omega$&$\mu(\omega)$&$t_1(\omega)$&$t_2(\omega)$&$t_3(\omega)$\\
      \hline
      $R R R$&$\half p^2$   &R&R&A\\
      $R R S$&$\half (1-p)^2$&R&R&A\\
      $R S R$&$\half p(1-p)$&R&S&D\\
      $R S S$&$\half p(1-p)$&R&S&D\\
      $S R R$&$\half p(1-p)$&S&R&D\\
      $S R S$&$\half p(1-p)$&S&R&D\\
      $S S R$&$\half (1-p)^2$&S&S&A\\
      $S S S$&$\half p^2$&S&S&A\\
    \end{tabular}
    \egroup
    \caption{The forecasters' common prior.}
  \end{table}

  \begin{exercise}
    What is the probability that player 1 assigns to the event
    $t_2=R$, conditioned on $t_1=R$? Conditioned on $t_1=S$? What
    probability does she assign to $\omega_3 = R$ in each of these
    cases?
  \end{exercise}

  \subsection{Rationalizability}
  
  
  Rationalizability tries to formalize the idea of {\em common
    knowledge of rationality}. Let
  $G = (N,\{S_i\}_{i \in N},\{u_i\}_{i \in N})$ be a normal form game,
  with $S=\prod_i S_i$, as usual. Let $\Omega = S$, let
  $T_i = S_i$ and let $t_i(s) =  s_i$. Consider belief spaces of the form
  $(N,\Omega, \{\mu_i\}_{i \in N},\{T_i\}_{i \in N},\{t_i\}_{i \in
    N})$. What this captures is a situation in which each player has a
  belief regrading the strategies used by the others, and knows her
  own strategy.

  We assume that all measures $\mu_i$ are product measures. That is,
  if $s=(s_1,\ldots,s_n)$ is chosen from $\mu_i$, then
  $(s_1,\ldots,s_n)$ are independent.

  We say that $\mu_i$ is best responding if conditioned on $t_i$,
  $t_i(s)$ maximizes expected utility, where expectations are taken
  according to $\mu_i$, conditioned on $t_i(s)$. Note that if
  $\mu_i=\mu$ for all $i$, then $\mu$ is a Nash equilibrium if
  and only if all agents are best responding. In this case, however,
  we do not require that all agents have the same prior belief.

  We say that $\mu_i$ is $k$-rationalizable if it is best responding, and if
  for every $j \neq i$ there is a $\mu_j'$ that is $k-1$-rationalizable, and
  such that the distribution of $s_j$ under $\mu_j'$ is identical to
  the distribution of $s_j$ under $\mu_i$. We define the set of
  $0$-rationalizable $\mu_i$ to be all possible $\mu_i$. Finally, we say
  that $\mu_i$ is rationalizable if it is $k$-rationalizable for all $k$.
  
  \begin{exercise}
    What is the relation to Nash equilibria?
  \end{exercise}



  \begin{exercise}
    What is the relation to iterated removal of strictly dominated strategies?
  \end{exercise}

  \begin{exercise}
    Does this formally capture ``common knowledge of rationality''?
  \end{exercise}

  \subsection{Agreeing to disagree}

  Let
  $(N,\Omega, \{\mu_i\}_{i \in N},\{\sigalg_i\}_{i \in
    N})$
  be a finite belief space with common priors, so that $\mu_i = \mu$
  for all $i$.  Given a random variable $X \colon \Omega \to \R$, we
  denote by $\E{X}$ the expectation of $X$ according to $\mu$. The
  expectation of $X$ conditioned on player $i$'s information at
  $\omega$ is
  \begin{align*}
    \CondE{X}{\sigalg_i}(\omega) = \frac{\sum_{\omega' \in P_i(\omega)}\mu(\omega')X(\omega')}{\sum_{\omega' \in P_i(\omega)}\mu(\omega')}
  \end{align*}


  Aumann~\cite{aumann1976agreeing} proved the following
  theorem.
  \begin{theorem}[Aumann's Agreement Theorem, 1976]
    \label{thm:agreement}
    Let $X \colon \Omega \to \R$ be a random variable. Suppose that at
    $\omega_0$ it is common knowledge that
    $\CondE{X}{\sigalg_i} = q_i$ for $i=1,\ldots,n$ and some
    $(q_1,q_2,\ldots,q_n) \in \R^n$. Then $q_1=q_2=\cdots=q_n$.
  \end{theorem}
  Note that we implicitly assume that the conditional expectations
  $\CondE{X}{\sigalg_i}$ are well defined everywhere. Before proving
  the Theorem we will recall the law of total expectation. Let $S$ be
  an element of an algebra $\sigalgp \subseteq 2^\Omega$, and let
  $X \colon \Omega \to \R$ be a random variable. Then
  \begin{align}
    \label{eq:total-prob}
    \CondE{X}{S} = \CondE{\CondE{X}{\sigalgp}}{S}.
  \end{align}

  \begin{exercise}
    Prove the law of total expectation for a finite probability
    space. Hint: write $C$ as a disjoint union of elements of the
    partition that generates $\sigalgp$: $C = \cup_j P_j$, with
    $P_j \in \sigalgp$ being elements with no proper, non-empty
    subsets in $\sigalgp$.
  \end{exercise}  
  \begin{proof}[Proof of Theorem~\ref{thm:agreement}]
    Let $A$ be the event that for $i=1,\ldots,n$ it holds that
    $\CondE{X}{\sigalg_i}=q_i$.
    
    
    By the common knowledge hypothesis there is a
    $C \in \sigalg_C = \cap_i\sigalg_i$ such that
    $\omega_0 \in C \subset A$. Hence
    $\CondE{X}{\sigalg_i}(\omega)=q_i$ for all $\omega \in C$. Thus
    \begin{align*}
      \CondE{X}{C} = \CondE{\CondE{X}{\sigalg_i}}{C} = \CondE{q_i}{C}
      = q_i,
    \end{align*}
    and $q_i$ is independent of $i$.
  \end{proof}

  In his paper, Aumann stated this theorem for the case that $X$ is
  the indicator of some event:
  \begin{corollary}
    If two players have common priors over a finite space, and it is
    common knowledge that their posteriors for some event are $q_1$
    and $q_2$, then $q_1=q_2$.
  \end{corollary}

  \newpage
  \subsection{No trade}

  Milgrom and Stokey~\cite{milgrom1982information} apply Aumann's
  theorem to show that rational agents with common priors can never
  agree to trade. Here we give a theorem that is less general than
  their original.
  
  Consider two economic agents. The first one has an indivisible good
  that she might be interested to sell to the second. This good can be
  sold tomorrow at an auction for an unknown price that ranges between
  \$0 and \$1,000, in integer increments. Let $\Omega$ be some subset
  of $T_1 \times T_2 \times T$, and let the common prior be some
  $\mu$. Here $T = \{0,\$1,\ldots,\$1000\}$ represents the auction
  price of the good, and $T_1 \times T_2$ is some finite set that
  describes many possible events that may influence the
  price. Accordingly, $\mu$ is not a product measure, so that
  conditioning on different $(\omega_1,\omega_2) \in T_1 \times T_2$
  yields different conditional distributions on $T$.  Let the players'
  types be given by $t_i(\omega_1,\omega_2,\omega_3) = \omega_i$ for
  $i=1,2$. Let $P \colon \Omega \to T$ be the auction price
  $p(\omega_1,\omega_2,\omega_3) = \omega_3$.

  
  We denote by $Q_1$ player 1's conditional expected price:
  \begin{align*}
    Q_1 = \CondE{P}{t_1}
  \end{align*}
  Analogously,
  \begin{align*}
    Q_2 = \CondE{P}{t_2}.
  \end{align*}


  For example, let $T_1 = T_2 = T$ and $\mu$ be the uniform
  distribution over
  $\{(\omega_1,\omega_2,\omega_3)\,:\,\omega_3 = \omega_1 \mbox{ or }
  \omega_3 =\omega_2\}$.
  Equivalently, pick $\omega_3$ uniformly at random, and then w.p.\
  $1/2$ set $\omega_1=k$ and choose $\omega_2$ uniformly at random,
  and w.p.\ $1/2$ set $\omega_2=k$ and choose $\omega_1$ uniformly at
  random.  Then
  \begin{align*}
    Q_i = \frac{1}{2}\left(\$500+t_i\right).
  \end{align*}

  Thus in any state $\omega$ in which $t_1 < t_2$ we have, for
  $q = \half(t_1+t_2)$, that $Q_1(\omega) < q < Q_2(\omega)$, so both
  players expect a positive return for trading the good for $q$
  dollars. However, note that the players do not know that the other
  player also has positive expectation. What if they knew that the
  other person is willing to trade?
  
  \begin{theorem}[Milgrom and Stokey, 1982]
    \label{thm:no-trade}
    If at some $\omega \in \Omega$ it is common knowledge that
    $Q_1 \leq q \leq Q_2$ then $Q_1(\omega) = q = Q_2(\omega)$.
  \end{theorem}
  \begin{proof}
    Let $A$ be the event that $Q_1 \leq q \leq Q_2$, i.e., $A$ is the
    event that
    $\CondE{P}{\sigalg_1} \leq q \leq \CondE{P}{\sigalg_2}$.  Then $A$
    is common knowledge at $\omega$, and so there is an event
    $C \in \sigalg_C$ with $\omega \in C \subset A$. Hence
    $C \in \sigalg_1$, and so, by~\eqref{eq:total-prob},
    \begin{align*}
      \CondE{P}{C} = \CondE{\CondE{P}{\sigalg_1}}{C} \leq \CondE{q}{C}
      = q.
    \end{align*}
    By the same argument we also get that
    \begin{align*}
      \CondE{P}{C} = \CondE{\CondE{P}{\sigalg_2}}{C} \geq \CondE{q}{C}
      = q.
    \end{align*}
    Hence these are both equalities, and thus, on $C$ (and therefor at
    $\omega$), $\CondE{P}{\sigalg_1} = \CondE{P}{\sigalg_2} = q$.
  \end{proof}

  \begin{exercise}
    Construct an example in which, for some $\omega \in \Omega$,
    $Q_1(\omega) < q$ and $Q_2(\omega) > q$, player 1 knows that
    $Q_2(\omega) > q$ and player 2 knows that $Q_1(\omega) < q$.
  \end{exercise}

  \subsection{Reaching common knowledge}
  \label{sec:reaching-common-knowledge}
%  We suggest that the reader becomes familiar with the content of
%  Appendix~\ref{app:projections} before reading this section.
  
  Geanakoplos and Polemarchakis~\cite{geanakoplos1982we} show that
  repeatedly communicating posteriors leads agents to convergence to a
  common posterior, which is then common knowledge. We state this
  theorem in somewhat greater generality than in the original paper,
  requiring a more abstract mathematical formulation.
  \begin{theorem}[Geanakoplos and Polemarchakis, 1982]
    \label{thm:cant-disagree}
    Let $(\Omega,\sigalg,\mathbb{P})$ be a probability space,
    and fix $A \in \sigalg$. Let $X_1$ and $X_2$ be two random
    variables on this space. Denote $Q_1^0 = \CondP{A}{X_1}$ and
    $Q_2^0 = \CondP{A}{X_2}$. For $t \in \{1,2,\ldots\}$ let
    \begin{align*}
      Q_1^t = \CondP{A}{X_1,Q_2^0,Q_2^1,\ldots,Q_2^{t-1}}
    \end{align*}
    and
    \begin{align*}
      Q_2^t = \CondP{A}{X_2,Q_1^0,Q_1^1,\ldots,Q_1^{t-1}}.
    \end{align*}
    Then $\lim_t Q_1^t$ and $\lim_t Q_2^t$ almost surely exist and are
    equal.
  \end{theorem}
  We first explain why this Theorem holds for finite belief spaces.
  \begin{proof}[Proof for finite $\Omega$]
    Assuming $\Omega$ is finite, let $\sigalg_1^t$ be the algebra
    describing the knowledge of player 1 at time $t$: this is the set
    of unions of subsets of $\Omega$ on which the random variable
    $(X_1,Q_2^1,\ldots,Q_2^{t-1})$ is constant. Define
    $\{\sigalg_2^t\}$ analogously. Then
    \begin{align*}
      Q_1^t = \CondP{A}{\sigalg_1^t}
    \end{align*}
    and
    \begin{align*}
      Q_2^t = \CondP{A}{\sigalg_2^t}.
    \end{align*}
    

    Note that each sequence $(\sigalg_i^1,\sigalg_i^2,\ldots)$ is
    increasing, in the sense that $\sigalg_i^{t+1}$ contains
    $\sigalg_i^t$. Since $\Omega$ is finite, both must stabilize at
    some $T$. At this $T$, by definition, $Q_1^T$ and $Q_2^T$ are
    constant on each partition $P_1^T(\omega)$ and on each partition
    $P_2^T(\omega)$. Thus, at every $\omega$, player 1 knows
    $(Q_1^T,Q_2^T)$, and thus it is common knowledge that she
    does. The same holds for player 2. Hence the players posteriors
    are common knowledge at time $T$, and thus must be identical, by
    Theorem~\ref{thm:agreement}.
  \end{proof}

  
  To prove this theorem in its full generality we will need the
  following classical result in probability.
  \begin{theorem}[L\'evy's Zero-One Law]
    \label{thm:levy-zero-one}
    Let $\{\sigalgp_n\}$ be a filtration, and let $X$ be a random
    variable. Let $\sigalgp_\infty$ be the sigma-algebra generated by
    $\cup_n \sigalgp_n$. Then $\lim_n \CondE{X}{\sigalgp_n}$ exists
    for almost every $\omega \in \Omega$, and is equal to
    $\CondE{X}{\sigalgp_\infty}$.
  \end{theorem}

  
  \begin{proof}[Proof of Theorem~\ref{thm:cant-disagree}]
    Note that by L\'evy's zero-one law (Theorem~\ref{thm:levy-zero-one},
    \begin{align*}
      Q_1^\infty := \lim_t Q_1^t = \CondP{A}{X_1,Q_2^0,Q_2^1,\ldots}
    \end{align*}
    and an analogous statement holds for $\lim_t Q_2^t$. Let
    $\sigalg_1$ be the sigma-algebra generated by
    $\{X_1,Q_2^0,Q_2^1,\ldots\}$, so that
    \begin{align*}
      Q_1^\infty = \CondP{A}{\sigalg_1}.
    \end{align*}
    Since $Q_2^\infty$ is $\sigalg_1$-measurable, it follows that
    \begin{align*}
      Q_1^\infty = \CondP{A}{\sigalg_1} =
      \CondE{\CondP{A}{Q_2^\infty}}{\sigalg_1} =
      \CondE{Q_2^\infty}{\sigalg_1} = Q_2^\infty.
    \end{align*}
  \end{proof}
\newpage
  \subsection{Bayesian games}
  The buyer-seller game described in Section~\ref{sec:beliefs-example}
  is an example of a {\em Bayesian game}. In these games there is
  uncertainty over the payoffs to the players in given pure strategy
  profiles.

  A Bayesian game is a tuple
  $G = (N,\{A_i\}_{i \in N},\Omega,\{T_i\}_{i \in N},\{t_i\}_{i \in
    N},\{\mu_i\}_{i \in
    N},\{u_i\}_{i \in N})$ where
  \begin{itemize}
  \item $(N,\Omega,\{T_i\}_{i \in N},\{t_i\}_{i \in N},\{\mu_i\}_{i \in
    N})$ is a belief space.
  \item $A_i$ is the set of {\em actions} of player $i$.
  \item $u_i \colon A \times \Omega \to \R$ is player $i$'s utility function.
  \end{itemize}

  The set of {\em pure strategies} of player $i$ is the set of
  functions from $T_i$ to $A_i$. That is, a strategy of a
  player is a choice of action, given her private signal
  realization. Given a strategy profile $(s_1,\ldots,s_n)$, player
  $i$'s expected utility is
  \begin{align*}
    \Esub{\mu_i,s}{u_i} = \int_\Omega u_i(s_1(t_1(\omega)), \ldots, s_n(t_n(\omega)),\omega)\dd \mu_i(\omega).
  \end{align*}
  
  A {\em Bayes-Nash equilibrium} is a strategy profile in which no
  player can improve her expected utility by changing her
  strategy. That is, for any player $i$ and strategy $s_i'$ it holds
  that
  \begin{align}
    \label{eq:bayes-nash1}
    \Esub{\mu_i,s}{u_i} \geq \Esub{\mu_i,(s_{-i},s'_i)}{u_i}.
  \end{align}

  An alternative definition of a Bayes-Nash equilibrium is a strategy
  profile in which, for each player $i$ and each type $\tau_i \in T_i$
  it holds that
  \begin{align}
    \label{eq:bayes-nash2}
    \CondEsub{\mu_i,s}{u_i}{t_i=\tau_i} = \int_\Omega u_i(s_1(t_1(\omega)), \ldots, s_i(\tau_i), \ldots, s_n(t_n(\omega)),\omega)\dd \mu_i(\omega|t_i=\tau_i)
  \end{align}
  cannot be improved:
  \begin{align*}
    \CondEsub{\mu_i,s}{u_i}{t_i=\tau_i} \geq
    \CondEsub{\mu_i,(s_{-i},s'_i)}{u_i}{t_i = \tau_i}
  \end{align*}
  for all $s'_i$ and $\tau_i \in T_i$.
  
  This is not an equivalent definition, but the second is stronger
  than the first. 
  \begin{proposition}
    \eqref{eq:bayes-nash2} implies~\eqref{eq:bayes-nash1}. 
  \end{proposition}
  \begin{proof}
    Let $s$ satisfy~\eqref{eq:bayes-nash2}. Then by the law of total
    expectation
    \begin{align*}
      \Esub{\mu_i,s}{u_i}
      &=  \Esub{\mu_i,s}{\CondEsub{\mu_i,s}{u_i}{t_i}}     \\
      &\geq  \Esub{\mu_i,s}{\CondEsub{\mu_i,(s_{-i},s'_i)}{u_i}{t_i}}     \\
      &= \Esub{\mu_i,(s_{-i},s'_i)}{u_i}.
    \end{align*}
  \end{proof}
  Conversely, if $\Omega$ is finite and there is a common prior
  $\mu = \mu_1 = \cdots = \mu_n$ then, if $s$
  satisfies~\eqref{eq:bayes-nash1} then there is an $s'$ that
  satisfies~\eqref{eq:bayes-nash2}, and such that the probability
  (under $\mu$) that $s_i(t_i) \neq s'_i(t_i)$ is zero.

  \begin{exercise}
    Find a finite Bayesian game that has a (pure) strategy profile
    that satisfies~\eqref{eq:bayes-nash1} but does not have one that
    satisfies~\eqref{eq:bayes-nash2}.
  \end{exercise}


  
  % To see that~\eqref{eq:bayes-nash} is {\em strictly} stronger than
  % \eqref{eq:bayes-nash1}, consider the following example. Let
  % $\Omega = \{x, y, z, w\}$ and let $T_1 = T_2 = \{-1,0,+1\}$. Let
  % \begin{align*}
  %   t_1(x) = t_1(y) = -1\quad\quad\mbox{ and }\quad\quadt_1(z) = +1\\
  %   t_2(x) = -1\quad\quad\mbox{ and }\quad\quad t_2(y) = t_2(z) = +1.
  % \end{align*}
  % Let $\mu = \mu_1 = \mu_2$ be given by $\mu(x) = \mu(z) = 1/2$. Let
  % $A_1 = A_2 = \{-1,+1\}$, and for $i=1,2$ let
  % \begin{align*}
  %   u_i(a_1,a_2,\omega) = a_1 \cdot a_2.
  % \end{align*}
  % That is, a player should choose action 1 if she thinks that both
  % types are the same, and $-1$ otherwise. Then it is easy to see that
  % $s_1(-1)=s_1(+1) = +1


  \section{Auctions}

  Auctions have been used throughout history to buy and sell
  goods. They are still today very important in many markets,
  including on-line markets that run massive computerized auctions.

  \subsection{Classical auctions}
  In this section we will consider $n$ players, each of which have a
  fixed valuation $v_i$ for some item that is being auctioned. We
  assume that each $v_i$ is a non-negative integer. Furthermore, to
  avoid having to deal with tie-breaking, we assume that each
  $v_i = i+1 \mod n$. We also assume without loss of generality that
  $v_1 > v_2 > \cdots > v_n$.

  If it is agreed that player $i$ buys the item for some price $p$
  then that player's utility is $v_i - p$. If a player does not buy
  then she pays nothing and her utility is zero.

  We will consider a number of possible auctions.

  \subsubsection{First price, sealed bid auction}
  In this auction each player submits a bid $b_i$, which has to be a
  non-negative integer, congruent to $i \mod n$. Note that this
  means that a player cannot ever bid her valuation (which is congruent to
  $i+1 \mod n$), but can bid one less than her valuation\footnote{Think of
    this as one cent less.}.

  For example, consider the case that $n=2$. Then possible valuations are
  $v_1 = 10$ and $v_2 = 5$, and $b_1$ must be odd while $b_2$ must
  be even.
  
  The bids $b = (b_1,\ldots,b_n)$ are submitted simultaneously. The
  player who submitted the highest bid $b_{\max}(b) = \max_i b_i$ buys
  the item, paying $b_{\max}$.

  Hence player $i$'s utility for strategy profile $b$
  is given by
  \begin{align*}
    u_i(b) =
    \begin{cases}
      v_i - b_i&\mbox{if } b_i = b_{\max}(b)\\
      0&\mbox{otherwise}
    \end{cases}.
  \end{align*}

  We now analyze this game. We first note that $b_i = v_i - 1$
  guarantees utility at least $0$. Next, we note that any $b_i > v_i$
  is weakly dominated by $b_i = v_i - 1$, since it guarantees utility
  at most $0$, but can result in negative utility if $b_i = b_{\max}$.
  Furthermore, it is impossible that in a pure equilibrium the winner
  of the auction bid more than $v_i$, since then she could increase
  her utility by lowering her bid to $v_i - 1$.

  Assume that $b^*$ is an equilibrium.
  \begin{claim}
    Player 1 wins the auction: $b^*_1 = b^*_{\max}$.
  \end{claim}
  \begin{proof}
    Assume by contradiction that player $i > 1$ wins the auction.  As
    we noted above, $b^*_i \leq v_i - 1$. Hence
    $b^*_{\max} = b^*_i \leq v_i - 1 < v_1 - 1$. Hence player 1 could
    improve her utility to 1 by bidding $v_1 - 1$ and winning the
    auction.
  \end{proof}

  We have thus shown that in any equilibrium the first player wins. It
  thus remains to show that one exists.
  \begin{claim}
    \label{clm:classical-first-prize}
    Let $b^*_1$ be the smallest allowed bid\footnote{Congruent to
      $1 \mod n$.} that is larger than $v_2-1$. Let $b_2 = v_2-1$. For
    $i>2$ (if there are more than 2 players) let $b^*_i$ be any
    allowed bid that is less than $v_2$. Then $b^*$ is an equilibrium.
  \end{claim}
  \begin{exercise}
    Prove Claim~\ref{clm:classical-first-prize}.
  \end{exercise}
  
  We note a few facts about this equilibrium.
  \begin{itemize}
  \item The item was allocated to the player who values it the most.
  \item The player who won did not base her bid on her own valuation, but
    on the other players' valuations, and in particular on the second
    highest one.
  \end{itemize}

  Note that other equilibria exist. For example, if $n=2$ and $v_1 =
  10$ and $v_2 = 5$ then $b_1 = 9$ and $b_2 = 8$ is again an
  equilibrium. Player 2 gets zero payoff, but can only decrease her
  utility by raising her price and winning the auction. Player 1
  gets positive utility (1), but cannot improve it by lowering her
  bid.

  
  \subsubsection{Second price, sealed bid auction}
  In this auction each player again submits a bid $b_i$, which this
  time has to be a non-negative integer, congruent to $i+1 \mod n$;
  that is, it {\em can} be equal to $v_i$. Again, the player who
  submitted the highest bid $b_{\max}$ wins. However, in this case she
  does not pay her bid, but rather the second highest bid
  $b_{\nd}$. Hence
  \begin{align*}
    u_i(b) =
    \begin{cases}
      v_i - b_{\nd}&\mbox{if } b_i = b_{\max}(b)\\
      0&\mbox{otherwise}
    \end{cases}.
  \end{align*}

  As in the first price auction, any $b_i > v_i$ is weakly dominated
  by $b_i = v_i$; when bidding more than $v_i$ the player can at most
  make 0, but in some cases may have negative utility, which is not
  possible when bidding $v_i$.
  
  Moreover, in this auction any $b_i < v_i$ is also weakly dominated
  by $b_i = v_i$. To see this, let $b'$ be the highest bid of the rest
  of the players. If $b' > v_i$ then in either bid the player losses
  the auction, and so both strategies yield zero. If $b' < v_i$ then
  bidding $b_i < v_i$ may either cause the loss of the auction and
  utility zero (if $b_i < b'$) or otherwise gaining $v_i - b'$. But
  bidding $b_i=v_i$ guarantees utility $v_i - b'$.

  Hence $b_i=v_i$ is a weakly dominant strategy, and so this is an
  equilibrium. Auctions in which bidding your valuation is weakly
  dominant are called {\em strategy proof} or sometimes {\em
    truthful}.

  Note that in this equilibrium the item is allocated to the player who
  values it the most, as in the first price auction. However, the
  player based her bid on her own valuation, independently of the
  other player's valuations.
   
  
  


  
  
  \subsubsection{English auction}
  This auction is an extensive form game with complete
  information. The players take turns, starting with player 1, then
  player 2 and so on up to player $n$, and then player 1 again
  etc. Each player can, at her turn, either leave the auction or stay
  in. Once a player has left she must choose to leave in all the
  subsequent turns.

  The auction ends when all players but one have left the auction. If
  this happens at round $t$ then the player left wins the auction and
  pays $t-1$.

  \begin{claim}
    \label{clm:english-spe}
    There is a subgame perfect equilibrium of this game in which each
    player $i$ stays until period $t=v_i$ and leaves once $t > v_i$.
  \end{claim}
  \begin{exercise}
    Prove Claim~\ref{clm:english-spe}.
  \end{exercise}

  \begin{exercise}
    What is the relation between this English auction and the second
    price auction?
  \end{exercise}


  \subsubsection{Social welfare}
  Imagine that the person running the auction is also a player in the
  game. Her utility is simply the payment she receives; she has no
  utility for the auctioned object. Then the social welfare, which we
  will for now define to be the sum of all the players' utilities, is
  equal to the utility of the winner --- her value minus her payment ---
  plus the utility of the losers (which is zero), plus the utility of
  the auctioneer, which is equal to the payment. This sum is the value
  of the object to the winner. Hence social welfare is maximized when
  the winner is a person who values the object most. 
\newpage
  \subsection{Bayesian auctions}
  In this section we will consider auctions in which the players do
  not know the others' valuations exactly. Specifically, the auctions
  will be Bayesian games with common priors.

  We will again have $n$ players. Each player's type will be her
  valuation $v_i$, and the players will have some common prior
  $\mathbb{P}$ over $(v_1,\ldots,v_n)$.  Formally, the belief space
  will be $((\R^+)^n,\sigalg,\mathbb{P})$, where $\sigalg$ is the Borel
  sigma-algebra, and $\mathbb{P}$ is some probability distribution.
  Player $i$'s type $t_i$ is given by $t_i(v_1,\ldots,v_n) = v_i$.

  As before, if a player does not win the auction she has utility
  zero. Otherwise, assuming she pays a price $p$, she has utility
  $v_i-p$. Note that the players' utilities indeed depend on their
  types in these Bayesian games.

  \subsubsection{Second price, sealed bid auction}
  As before, the players will submit bids $b_i$. In this case we do
  not restrict the bids, and can allow them to take any value in
  $\R$. Formally, a pure strategy of a player in this game is a
  measurable function $b_i \colon \R^+ \to \R$, assigning a bid to
  each possible type or valuation.

  As before, the player with the highest bid $b_{\max}$ wins and pays the
  second highest bin $b_{\nd}$. Note that despite the fact that two
  valuations can be never be the same, it still may be the case that
  two players choose the same bid. For example, the strategy profile
  could be such that all players always bid 1. Accordingly, we assume
  that there is some tie-breaking mechanism (e.g., choose at random
  from all those with the highest bid), but it will not play a role in
  our analysis.

  \begin{proposition}
    For any joint distribution $\mathbb{P}$, it is weakly dominant for
    each player to choose $b^*_i(v_i) = v_i$.
  \end{proposition}
  The proof of this is identical to the one in the non-Bayesian case.


  As an example, consider the case that the valuations are picked
  i.i.d.\ from some non-atomic distribution with cumulative
  distribution function $F$. Then $b^*_i(v_i) = v_i$ is the unique
  Bayes-Nash equilibrium.

  Assume that there are two players. Player 1 wins the auction if she
  has the highest valuation. Conditioning on her valuations $v_1$, her
  probability of winning is therefore $F(v_1)$. If she wins then she
  expects to pay $\CondEsub{F}{v_2}{v_2 < v_1}$. 
  

  \subsubsection{First price, sealed bid auction}
  In this auction, as in the classical one, each player will submit a
  bid $b_i$, and the player with the highest bid $b_{\max}$ will win
  and pay $b_{\max}$. We assume here that the valuations are picked
  i.i.d.\ from some non-atomic distribution with cumulative
  distribution function $F$ with derivative $f$. To simplify our
  calculations we will assume that there are only two players; the
  general case is almost identical.

  \begin{exercise}
    Show that $b^*_i(v_i) = v_i$ is {\em not} an equilibrium of this
    auction.
  \end{exercise}
  
  
  We will try to construct a Bayes-Nash equilibrium with the following
  properties:
  \begin{itemize}
  \item Symmetry: there is a function $b \colon \R^+ \to \R^+$
    such that $b_i(v_i) = b(v_i)$ for all players.
  \item Monotony and differentiability: $b$ is monotone increasing.
  \end{itemize}


  Thus, to construct such an equilibrium we assume all players play
  $b$, and try to calculate $b$ assuming it is some player's
  (say player 1's) best response.


  Assume then that player 2 plays $b_2(v_2) = b(v_2)$. Fix $v_1$, and
  assume that player 1 bids $b_1$.  Denote by $G$ the cumulative
  distribution function of $b(v_2)$, and let $g$ be its
  derivative. Note that we can write $G$ and $g$ in terms of $F$ and
  $f$:
  \begin{align}
    \label{eq:first-price-G-F}
    F(v) = G(b(v))
  \end{align}
  and 
  \begin{align}
    \label{eq:first-price-g-f}
    f(v) = g(b(v)) \cdot b'(v).
  \end{align}
  The probability that $b_1$ is the highest bid is $G(b_1)$. It
  follows that player 1's expected utility (conditioned on $v_1$) is
  \begin{align*}
    u_1(v_1,b_1) = G(b_1) \cdot (v_1 - b_1).
  \end{align*}
  Therefore, to maximize expected utility, $b_1$ must satisfy
  \begin{align*}
    0 = \frac{\dd u_1(v_1,b_1)}{\dd b_1} = g(b_1)
    \cdot (v_1 - b_1) - G(b_1),
  \end{align*}
  or
  \begin{align*}
    G(b_1) = g(b_1) \cdot (v_1 - b_1).
  \end{align*}
  Note that $b_1 = v_1$ is a solution only if $G(b_1) = 0$.

  Since we are looking for a symmetric equilibrium, we can now plug in
  $b_1 = b(v)$ to arrive at the condition
  \begin{align*}
    G(b(v)) = g(b(v)) \cdot (v - b(v)).    
  \end{align*}
  Translating back to $F$ and $f$ using~\eqref{eq:first-price-G-F}
  and~\eqref{eq:first-price-g-f} yields
  \begin{align*}
    F(v) = \frac{f(v)}{b'(v)} \cdot (v - b(v)).
  \end{align*}
  Rearranging, we can write
  \begin{align*}
    F(v) b'(v) + f(v) \cdot b(v) = f(v) \cdot v
  \end{align*}
  or
  \begin{align*}
    \frac{\dd}{\dd v}\left[F(v) b(v)\right] = f(v) \cdot v.
  \end{align*}
  Now, clearly $b(0) = 0$ is weakly dominant, and so we will assume
  that this is indeed the case. We can therefore solve the above
  expression to arrive at
  \begin{align*}
    b(v) = \frac{1}{F(v)}\int_0^v f(u) \cdot u \dd u.
  \end{align*}
  Note that this is equal to $\CondEsub{F}{v_2}{v_2 < v_1}$, the
  expectation of $v_2$, conditioned on $v_2$ being less than $v$. It
  remains to be shown that this strategy profile is indeed a maximum
  (we only checked the first order condition).

  A player's expected utility, conditioned on having valuation $v$, is
  simply $F(v)$ (the probability that she wins) times $v -
  b(v)$. Interestingly, in the second price auction the expected
  utility is identical: the probability of winning is still $F(v)$,
  and the expected utility is $v-b(v)$, since, conditioned on winning,
  the expected payment is the expected valuation of the other player.

\newpage
  \subsection{Truthful mechanisms and the revelation principle}

  The revelation principle is important in mechanism design. The basic
  idea is due to Gibbard~\cite{gibbard1973manipulation}, with
  generalizations by others~\cite{holmstrom1977incentives,
    myerson1979incentive, dasgupta1979implementation}.

  In this section we will call Bayesian games of incomplete
  information {\em mechanisms}. We will say that a mechanism is {\em
    truthful} if $A_i = T_i$ and $\tilde s(t_i) = t_i$ is an
  equilibrium. Note that sometimes this term is used to describe
  mechanisms in which the same $\tilde s$ is weakly dominant.

  \begin{theorem}
    \label{thm:revelation}
    Let
    $G = (N,\{A_i\}_{i \in N},(\Omega,\sigalg),\{\mu_i\}_{i \in
      N},\{T_i\}_{i \in N},\{t_i\}_{i \in N},\{u_i\}_{i \in N})$
    be a mechanism with an equilibrium $s^*$. Then there exists a
    truthful mechanism
    $G' = (N,\{A'_i\}_{i \in N},(\Omega,\sigalg),\{\mu_i\}_{i \in
      N},\{T_i\}_{i \in N},\{t_i\}_{i \in N},\{u'_i\}_{i \in N})$
    such that
    \begin{align*}
      \CondEsub{\mu_i,\tilde s}{u'_i}{t_i} = \CondEsub{\mu_i,s^*}{u_i}{t_i}.
    \end{align*}
  \end{theorem}
  
  That is, for every game and equilibrium one can design a truthful
  game in which playing truthfully yields the same conditionally
  expected utilities as in the original game. The idea of the proof is
  simple: in the new mechanism, the players reveal their types, the
  mechanism calculates their equilibrium actions, and then implements
  the original mechanism on those actions.
  \begin{proof}[Proof of Theorem~\ref{thm:revelation}]
    Let
    \begin{align*}
      u'_i(\tau_1,\ldots,\tau_n,\omega) = u_i(s^*_1(\tau_1),\ldots,s^*_n(\tau_n),\omega).
    \end{align*}
    Then
    \begin{align*}
      \CondEsub{\mu_i,\tilde s}{u'_i}{t_i=\tau_i}
      &= \int_\Omega u'_i(\tilde s_1(t_1(\omega)), \ldots,\tilde s_n(t_n(\omega)),\omega)\dd \mu_i(\omega|t_i=\tau_i)\\
      &= \int_\Omega u'_i(t_1(\omega), \ldots, t_n(\omega),\omega)\dd \mu_i(\omega|t_i)\\
      &= \int_\Omega u_i(s_1^*(t_1(\omega)), \ldots, s_n^*(t_n(\omega)),\omega)\dd \mu_i(\omega|t_i)\\
      &= \CondEsub{\mu_i,s^*}{u_i}{t_i}.
    \end{align*}
    To see that this mechanism is truthful, note that for any player
    $i$ with type $\tau_i \in T_i$ and action  $\tau_i' \in A'_i  =
    T_i$ it holds that the utility for playing $\tau'_i$ (instead of
    $\tau_i$) is
    \begin{align*}
      &\int_\Omega u'_i(\tilde s_1(t_1(\omega)), \ldots, \tau_i',\ldots,\tilde s_n(t_n(\omega)),\omega)\dd \mu_i(\omega|t_i=\tau_i)\\
      &= \int_\Omega u'_i(t_1(\omega), \ldots, \tau_i',\ldots,t_n(\omega),\omega)\dd \mu_i(\omega|t_i=\tau_i)\\
      &= \int_\Omega u_i(s_1^*(t_1(\omega)), \ldots, s_i^*(\tau'_i),\ldots,s_n^*(t_n(\omega)),\omega)\dd \mu_i(\omega|t_i=\tau_i).
    \end{align*}
    But since $s^*$ is an equilibrium this is 
    \begin{align*}
    &\leq  \int_\Omega u_i(s_1^*(t_1(\omega)), \ldots,
      s_i^*(\tau_i),\ldots,s_n^*(t_n(\omega)),\omega)\dd
      \mu_i(\omega|t_i=\tau_i)\\
   &= \int_\Omega u'_i(\tilde s_1(t_1(\omega)), \ldots,\tilde s_n(t_n(\omega)),\omega)\dd \mu_i(\omega|t_i=\tau_i),
    \end{align*}
    which is the utility for playing according to $\tilde s_i$.
  \end{proof}

  It follows that when designing auctions we can assume without loss
  of generality that the players reveal their types to the auctioneer.
  
\subsection{Revenue equivalence and optimal auctions}  



\section{Extensive form games with chance moves and imperfect
  information}

\subsection{Motivating example: train inspections}
Consider a rail system in which there are no physical barriers to
boarding a train without a ticket, but where occasionally inspectors
check if passengers have tickets.

A ticket to the train costs $C$. The value of the ride to a passenger
is $V > C$. The fine for getting caught on the train without a ticket
is $F$. A passenger can have one of two different types: rich or poor.
The rich passenger has enough money in savings to afford the fine. The
poor passenger does not, and therefore would have to borrow money to
pay the fine, thus paying in addition some amount $I_p > 0$ in
interest. The interest for the rich is $I_r = 0$.

The type of the passenger is chosen at random at the beginning of the
game, and is rich with probability $p$ and poor with probability
$1-p$. The passenger knows her type, but the train company does
not. We imagine that $p$ is small, so that most passengers are poor.

The passenger now has to decide whether or not to buy a ticket
($B/NB$). The company has to decide whether or not to check her for a
ticket ($C/NC$). The cost of such an inspection is $\eps$. We assume
that $V < F$. We will see later that we will also need that
$p \leq \eps / F$.


The payoff to the passenger is the value of the ride (if she choose to
ride), minus any money paid (in fare, fine or interest). The payoff to
the company is any money collected, minus the cost of the inspection,
if made. 

When the passenger has value $V$ for the ride and pays interest $I$ on
a loan to pay a fine, the normal form of the
game is the following:
\begin{center}
  \begin{game}{3}{2}
    & $C$     & $NC$\\
    $B$   & $V-C,C-\eps$  & $V-C,C$\\
    $NB$ & $V-F-I,F-\eps$ & $V,0$
  \end{game}
\end{center}
Now, the company does not know $I$, but believes that, as explained
above, it equals $I_r$ with probability $p$ and $I_p$ with probability
$1-p$. 

We first claim that this game has no pure Nash equilibria. Assume that
the company chooses to always inspect. Then the best response of any
passenger is to ride and buy. But then inspecting is not a best
response for the company.

Assume then that the company does not inspect. Then all passengers
best respond by riding and not buying. Now again the company has a
profitable deviation, which is to inspect. Hence indeed this game has
no pure equilibrium.


We will now build a mixed equilibrium. Assume that the company mixes
and inspects with probability $\sigma_c$. Then the passenger's utility
for riding and buying is $u_p((R,B),\sigma_c) = V-C$. Her utility for
riding and not buying is
\begin{align*}
 u_p((R,NB),\sigma_c)=\sigma_c(V-F-I) + (1-\sigma_c)V = V-\sigma_c (F+I), 
\end{align*}
and her utility for not riding is zero. Hence if we set
$\sigma_c = C/(F+I)$ then the passenger wants to ride, but is
indifferent between buying and not buying. Note that it cannot be that
both the rich and the poor passenger are indifferent, since they pay
different amounts of interest. We will set $\sigma_c = C/(F+I_p)$, so
that the poor passenger is indifferent. Under this choice the utility
for the rich passenger when riding and not buying is
$V-C F / (F+I_p) > V-C$, and so this is her best response.

Assume that the rich passenger rides and does not buy, and that the
poor passenger mixes between riding and buying (with probability
$\sigma_p$) and riding and not buying (with probability
$(1-\sigma_p)$). Then the expected utility for the company for
inspecting is
\begin{align*}
  u_c((R,B),\sigma_p,C)
  &= p (F-\eps) + (1-p)\big[\sigma_p(C-\eps) +
  (1-\sigma_p)(F-\eps)\big]\\
  &= p F-p \eps + (1-p)(C-\eps)\sigma_p +
    (1-p)(F-\eps)-(1-p)(F-\eps)\sigma_p\\
  &=  (C-F)(1-p)\sigma_p +
    F-\eps
\end{align*}
The expected utility for not inspecting is
\begin{align*}
  u_c((R,B),\sigma_p,NC) = C(1-p)\sigma_p  
\end{align*}
For the company to be indifferent we therefore set
\begin{align*}
  \sigma_p = \frac{1-\eps/F}{1-p}.
\end{align*}
Thus if $p \leq \eps/F$ this will not be larger than one, and we will
have our equilibrium. In this equilibrium the rich do not buy a
ticket, as they prefer to risk getting fined. The poor are indifferent
between not riding and riding without buying. The expected utility for
the poor passenger is zero. The expected utility for the rich
passenger is $V-C F / (F+I_p) > 0$, and the expected utility for the
company is $C(1-\eps/F) \geq 0$.

\subsection{Definition}
In this section we introduce two new elements to extensive form games:
{\em chance moves} and {\em imperfect information}. The idea behind
chance moves is to model randomness that is introduced to the game by
an outside force (``nature'') that is not one of the
players. Imperfect information models situations where players do not
observe everything that happened in the past. We will restrict
ourselves to games of {\em perfect recall}: players will not forget
any observations that they made in the past. To simplify matters we
will not allow simultaneous moves\footnote{This is (almost) without
  loss of generality, since simultaneous moves are equivalent to
  sequential moves that are not observed by others until later.}.


In the train inspections game the choice of whether the passenger is
rich or poor is an example of a chance move. The fact that the train
company decides to inspect without knowing the passenger's decision
means that this is a game of imperfect information.

In this section, an extensive form game will be given by
$G = (N,A,H,\cI,P,\sigma_c,\{u_i\})$ where $N$, $A$ and $H$ are as
in games of perfect information
(Section~\ref{sec:extensive-perfect-definition}), $Z$ are again the
terminal histories, and
\begin{itemize}
\item $\cI$ is a partition of the non-terminal histories
  $H \setminus Z$ such that, for all $J \in \cI$ and $h_1,h_2 \in J$,
  it holds that $A(h_1) = A(h_2)$. We therefore define can define
  $A \colon \cI \to A$ by $A(J) = A(h)$ where $h \in J$ is
  arbitrary. We denote by $J(h)$ the partition element $J \in \cI$
  that contains $h \in H \setminus Z$.
  
\item $P \colon \cI \to N \cup \{c\}$ assigns to each non-terminal
  history either a player, or $c$, indicating a {\em chance move}.  We
  sometimes think of the chance moves as belonging to a {\em chance
    player} $c$.

  When $P(J) = i$ we say that $J$ is an {\em information set} of
  player $i$. The collection of the information sets of player $i$ is
  denoted by $\cI_i = P^{-1}(i)$ and is called $i$'s {\em information
    partition}.

\item Let $A_c = \prod_{J \in P^{-1}(c)}A(J)$ be the product of all
  action sets available to the chance player. $\sigma_c$ is a product
  distribution on $A_c$. That is,
  \begin{align*}
    \sigma_c = \prod_{J \in P^{-1}(c)}\sigma_c(\cdot|J),
  \end{align*}
  where $\sigma_c(\cdot|J)$ is a probability distribution on $A(J)$,
  the set of actions available at information set $J$.
  
\item For each player $i$, $u_i \colon Z \to \R$ is her utility for
  each terminal history.
  
\end{itemize}


We will assume that $G$ is a game of {\em perfect recall}: For each
player $i$ and each $h=(a^1,a^2,\ldots,a^n)$ that is in some
information set of $i$, let the {\em experience} $X(h)$ be the
sequence of $i$'s information sets visited by prefixes of $h$, and the
actions $i$ took there. That is, $X(h)$ is the sequence
\begin{align*}
 \big( (J^1,b^1),(J^2,b^2),\ldots,(J^k,b^k) \big)
\end{align*}
where each $J^m$ is an element of $\cI_i$, each $b^m$ is an element of
$A(J^m)$, and $(b^1,\ldots,b^m)$ is the subsequence of $h$ which
includes the actions taken by $i$.


Perfect recall means that for each $J \in \cI$ and $h_1,h_2 \in J$ it
holds that $X(h_1) = X(h_2)$. That is, there is only one possible
experience of getting to $J$, which we can denote by $X(J)$. In
particular, in a game of perfect recall each information set is
visited at most once along any play path.

\newpage
\subsection{Pure strategies, mixed strategies and behavioral strategies}

A pure strategy of player $i$ in $G$ is a map $s_i$ that assigns to
each $J \in \cI_i$ an action $a \in A(J)$. We can think of $s_i$ as an
element of $A_i := \prod_{J \in \cI_j}A(J)$.  A mixed strategy $\sigma_i$ of
a player in an extensive form game is a distribution over pure
strategies. Given a $J \in \cI_i$, we denote by $\sigma_i(\cdot |J)$
the distribution over $A(J)$ given by $\sigma_i$, conditioned on the
experience $X(J)$. That is, $\sigma_i(a|J)$ is the probability, if we
choose $s_i$ according to $\sigma_i$, that $s_i(J) = a$ conditioned on
$s_i(J^1)=b^1, \ldots, s_i(J^k)=b^k$, where
$( (J^1,b^1),(J^2,b^2),\ldots,(J^k,b^k) )$ is the unique experience
that terminates in $J$. Of course, it could be that this conditional
probability is not well defined, in the case that $s_i(J^1)=b^1,
\ldots, s_i(J^k)=b^k$ occurs with zero probability.


Recall that $A_i = \prod_{J \in \cI_i}A(J)$ is the product of all
action sets available to player $i$.  A {\em behavioral strategy}
$\sigma_i$ of player $i$ is a product distribution on $A_i$:
\begin{align*}
  \sigma_i = \prod_{J \in \cI_i}\sigma_i(\cdot|J),
\end{align*}
where $\sigma_i(\cdot|J)$ is a distribution on $A(J)$.  Note that
$\sigma_c$, the chance player's distribution, is a behavioral
strategy. Note also that each element of $\prod_{J \in \cI_i}A(J)$ can
be identified with a function that assigns to each element
$J \in \cI_i$ an element of $A(J)$. Therefore, by our definition of
behavioral strategies, every behavioral strategy is a mixed strategy.

Given a strategy profile $\sigma$ of either pure, mixed or behavioral
strategies (or even a mixture of these), we can define a distribution
over the terminal histories $Z$ by choosing a random pure strategy for
each player (including the chance player), and following the
game path to its terminal history $z$. A player's utility for
$\sigma$ is $u_i(\sigma) = \E{u_i(z)}$, her expected utility at this
randomly picked terminal history.

\begin{proposition}
  \label{prop:mixed-behavioral}
  Under our assumption of perfect recall, for every mixed (resp.,
  behavioral) strategy $\sigma_i$ there is a behavioral (resp., mixed)
  strategy $\sigma_i'$ such that, for every mixed $\sigma_{-i}$ it
  holds that $u_i(\sigma_{-i},\sigma_i) = u_i(\sigma_{-i},\sigma_i')$.
\end{proposition}
We prove this proposition for finite games. Note that our definition
of behavioral strategies as a special case of mixed strategies is
designed for games in which each information set is visited only
once. In the general case, behavioral strategies are defined
differently: they are simply a distribution on each information set,
with the understanding that at each visit a new action is picked
independently.
\begin{proof}[Proof of Proposition~\ref{prop:mixed-behavioral}]
  By our definition of behavioral strategies, every behavioral
  strategy is a mixed strategy, and so if $\sigma_i$ is a behavioral
  strategy we can simply take $\sigma_i' = \sigma_i$.

  To see the other direction, let $\sigma_i$ be a mixed strategy.  For
  $J \in \cI_i$ and $a \in A(J)$, let
  \begin{align*}
    \sigma_i'(a|J) = \sigma_i(a|J),
  \end{align*}
  provided the conditioned event of reaching $J$ has positive
  probability; otherwise let $\sigma_i'(\cdot|J)$ be arbitrary.

  Fix $\sigma_{-i}$ and let $h=(a^1,\ldots,a^k)$ be a history. We
  denote by $\P{a^1,\ldots,a^k}$ the probability that this history is
  played when using the strategy profile
  $(\sigma_{-i},\sigma_i)$. Assume by induction that this probability
  is the same whether we calculate it using $\sigma_i$ or $\sigma_i'$,
  for all histories of length $<k$.

  Note that 
  \begin{align*}
    \P{a^1,\ldots,a^k} = \CondP{a^k}{a^1,\ldots,a^{k-1}} \cdot \P{a^1,\ldots,a^{k-1}}.
  \end{align*}
  Now, by our inductive assumption $\P{a^1,\ldots,a^{k-1}}$ takes
  the same value if we calculate it using $\sigma_i'$ rather than
  $\sigma_i$. If $h=(a^1,\ldots,a^{k-1})$ is a history in an
  information set $J$ that does not belong to $\cI_i$ then clearly
  $\CondP{a^k}{a^1,\ldots,a^{k-1}}$ does not depend on whether we
  use $\sigma_i$ or $\sigma_i'$, and hence $\P{a^1,\ldots,a^k}$ does
  not either.

  Otherwise $J \in \cI_i$. In this case, let $s_i$ be a strategy that
  is picked according to $\sigma_i$. Then
  \begin{align*}
    \CondP{a^k}{(a^1,\ldots,a^{k-1})}
    &= \CondP{s_i(J)=a^k}{a_1,\ldots,a^{k-1}}\\
    &= \CondP{s_i(J)=a^k}{s_i(J^1)=b^1,\ldots,s_i(J^\ell)=b^\ell}\\
    &= \sigma(a^k|J),
  \end{align*}
  where $((J^1,b^1),\ldots,(J^\ell,b^\ell))$ is player $i$'s
  experience at $J$, the partition element of $h$. This holds since
  the other players' choices are independent of $i$'s and hence can be
  left out. Hence, by our definition of $\sigma_i'$,
  $\CondP{a^k}{a^1,\ldots,a^{k-1}}$ is the same under $\sigma_i$ and
  $\sigma_i'$. Therefore the same applies to $\P{a^1,\ldots,a^k}$, and
  in particular to any terminal history. Thus the distribution on
  terminal histories is identical, and hence so are the expected
  utilities.
\end{proof}

\newpage
\subsection{Belief systems and assessments}

Let $G = (N,A,H,\cI,P,\sigma_c,\{u_i\})$ be a finite extensive form
game. A {\em belief system} $\{\mu(\cdot|J)\}_{J \in \cI}$ is a collection of
probability measures, with $\mu(\cdot|J)$ a probability measure over $J$.

Fix a mixed strategy profile $\sigma$, and for a history
$h=(a^1,\ldots,a^k)$ denote, as above, by $\Psub{\sigma}{h}$ the
probability of the event that the path of play includes $h$.  We
likewise denote by $\Psub{\sigma}{J}$ the probability that an
information set $J$ is visited. We say that $\mu(\cdot|J)$ is derived
from $\sigma$ if for any history $h \in J$ such that
$\Psub{\sigma}{J}>0$ it holds that
$\mu(h|J) = \CondPsub{\sigma}{h}{J}$. For $J$ with
$\Psub{\sigma}{J} = 0$, $\mu(\cdot|J)$ can take any value.

An {\em assessment} is a pair $(\sigma,\mu)$ such that\footnote{In the
  literature this requirement is usually not part of the definition.}
$\mu$ is derived from $\sigma$. 

Recall that we say that $\sigma$ is {\em completely mixed} if for all $i$,
$J \in \cI_i$ and $a \in A(J)$ it holds that $\sigma_i(a|J) > 0$. That
is, in every information set every allowed action has positive
probability. In this case $\Psub{\sigma}{J}>0$ for every information
set $J$, and so there is only one belief system $\mu$ that is derived
from $\sigma$. Hence for completely mixed $\sigma$ there is only one
assessment $(\sigma,\mu)$.

\subsection{Sequential rationality and sequential equilibria}

In this section we introduce a concept that is a natural adaptation of
subgame perfection to games with incomplete information.

Given a strategy profile $\sigma$ and a belief system $\mu$, we can
naturally extend each $\mu(\cdot|J)$ to a distribution over all
terminal histories that can be reached from $J$: given a terminal
history $z = (a^1,\ldots,a^k,a^{k+1},\ldots,a^\ell)$ such that
$h=(a^1,\ldots,a^k) \in J$, denote by $J^m := J(a^m)$ the information
set to which $a^m$ belongs, and let
\begin{align*}
  \mu_\sigma(z|J) = \mu(h|J) \cdot \prod_{m=k}^{\ell-1} \sigma_{P(J^m)}(a^{m+1}|J^m).
\end{align*}
Note that $\mu_\sigma(z|J)$ is well defined since for any terminal
history that passes through $J$ there is, by perfect recall, a unique
prefix $h$ that ends in $J$.

Recall from the previous section that an assessment $(\sigma,\mu)$
induces, for each $J \in \cI$, a distribution $\mu(\cdot | J)$ on the
terminal histories reachable from $J$. We say that $(\sigma^*,\mu^*)$ is
{\em sequentially rational} if for each player $i$ and $J \in \cI_i$
it holds that
\begin{align*}
  \Esub{\mu^*_{\sigma^*}(\cdot|J)}{u_i(z)} \geq \Esub{\mu^*_\sigma(\cdot|J)}{u_i(z)}
\end{align*}
for any $\sigma = (\sigma^*_{-i},\sigma_i)$.  Intuitively, sequential
rationality corresponds to subgame perfection: there are no profitable
deviations for any player at any information set. 

\begin{exercise}
  Show that this notion of subgame perfection reduces to the usual
  notion in the case of games of perfect information.
\end{exercise}

Recall that for completely mixed $\sigma$ there is a unique assessment
$(\sigma,\mu)$. However, when $\sigma$ is not completely mixed, there
can be excessive freedom in choosing $\mu$, which can result in
``strange'' belief updates following deviations. For example, consider
the three player game in which players 1 and 2 choose among $\{a,b\}$,
and player 3 only observes player 1's choice, so that her information
sets are $J_a$ and $J_b$, corresponding to player 1's choice. Player 3
then chooses among $\{a,b\}$. Let
$\sigma_1(a) = \sigma_2(a)= \sigma_3(a) = 1$, and let
$\mu(a a|J_a)=1$, $\mu(b b|J_b)=1$; the rest of the information sets
are singletons and therefore have trivial beliefs. The fact that
$\mu(b b|J_a)=1$ means that if player 3 learns that 1 deviated then
she assumes that 2 also deviated. See also the game in~\cite[Figure
4]{watson2015perfect}.

A common way to restrict $\mu$ is to require {\em consistency}: We say
that an assessment $(\sigma,\mu)$ is consistent if there exists a
sequence $\{(\sigma^m,\mu^m)\}_{m \in \N}$ that converges to
$(\sigma,\mu)$ and such that each $\sigma^m$ is completely mixed. We
say that $(\sigma,\mu)$ is a {\em sequential
  equilibrium}~\cite{kreps1982sequential} if it is consistent and
sequentially rational.

\begin{exercise}
  Show that if $G$ has perfect information then $(\sigma,\mu)$ is
  a sequential equilibrium iff it is subgame perfect.
\end{exercise}

\subsection{Trembling hand perfect equilibrium}

In extensive form games one could define trembling hand equilibria as
simply the trembling hand equilibria of the strategic form
game. However, this leads to equilibria that are not subgame perfect
(see, e.g.,~\cite[Figure 250.1]{osborne1994course}).

We therefore define a different notion for extensive form games. To
this end, given a behavioral strategy
$\sigma_i = \prod_{J \in \cI_i}\sigma_i(\cdot|J)$, we think of each
decision made at each information set as being made by a different
agent. This is sometimes called the {\em agent form} of the game. Here
the set of agents is the set of information sets (except those that
belong to the chance player) and the strategy of player $J \in \cI_i$
is $\sigma_i(\cdot|J)$.

An {\em extensive form trembling hand perfect equilibrium} of $G$ is a
behavior strategy profile $\sigma$ that is a trembling hand perfect
equilibrium of the agent form of $G$ (in strategic form).

\subsection{Perfect Bayesian equilibrium}

An assessment that is sequentially rational is said to be a {\em weak
  perfect Bayesian equilibrium}. As we mentioned above, this seems to
be a problematic notion (see~\cite[Figure 4]{watson2015perfect}).

The most widely used notion of perfect equilibrium is that of a {\em
  perfect Bayesian equilibrium}, due to Fudenberg and
Tirole~\cite{fudenberg1991perfect}. However, they only define it for a
small class of extensive form games with incomplete information, and
it is not clear what the (widely used!) definition is for general
games. An excellent discussion and two possible notions are presented
by Watson~\cite{watson2015perfect}. These notions involve two
principles:
\begin{enumerate}
\item {\em Bayesian updating.} Whenever possible beliefs are updated
  using Bayes' rule. This is obviously possible on path, but also
  sometimes in updates following a deviation but not immediately after
  it.
\item {\em Conservation of independence.} A natural assumption is that
  if a player deviates then the others update their beliefs regarding
  her strategy / type, but not the other players', unless
  necessary. More generally, if two events are independent before a
  deviation, and if the deviation is (somehow) independent of one,
  then beliefs regarding the other should not be
  updated~\cite{battigalli1996strategic}.
\end{enumerate}
\newpage
\subsection{Cheap talk}
The contents of this section are taken from~\cite{aumann2003long}.

Consider a game played between a sender $S$ and a receiver $R$. There
is a state of the world $\omega = \in \{H,T\}$,
and both players have the common belief that it is chosen from the
uniform distribution.

The sender observes $\omega$, sends a message $m(\omega)$ to the
receiver. The messages take values in some set $M$, which, as it turns
out, we can assume without loss of generality to be $\{H,T\}$.  The
receiver then chooses an action $a \in A$.

In a {\em pure} strategy profile, the sender strategy consists of a
choice of the function $m$. The receiver's strategy $s_R$ is a
function $s_R \colon M \to A$, which is a choice of action for each
possible received message.

In equilibrium, the receiver knows the sender's strategy, and, upon
receiving the message, updates his belief regarding the state of the
world using Bayes' law. The action that he then chooses is optimal,
given his belief. Likewise, the sender's expected utility is maximized
by sending the message that she sends.

\subsubsection{Example 1.}
Here $A = \{L,R\}$.  When $\omega = H$, the utilities are
given by (the first number is always the sender's)
\begin{center}
  \begin{game}{2}{2}
    & $L$ & $R$ \\
    & $4,4$ & $0,0$
  \end{game}
\end{center}
When $\omega = T$, they are
\begin{center}
  \begin{game}{2}{2}
    & $L$ & $R$ \\
    & $0,0$ & $4,4$
  \end{game}
\end{center}
So both want action $L$ when  $\omega = H$ and $R$ when
$\omega=T$. In this case there are many equilibria:
\begin{itemize}
\item {\em Babbling.} The sender always sends $m(\omega) =
  H$. The receiver ignores this and chooses $L$. Likewise, the sender
  can choose at random (independently of $\omega$) which message to
  send, which the receiver again ignores.
\item {\em Fully revealing.} The sender sends $m(\omega) = \omega$,
  and the receiver choose $L$ if the message was $H$, and $R$
  otherwise. By the cooperative nature of this game, neither has
  incentive to deviate.
\end{itemize}

\subsubsection{Example 2.}
Here again $A = \{L,R\}$.  When $\omega = H$, the utilities are
given by 
\begin{center}
  \begin{game}{2}{2}
    & $L$ & $R$ \\
    & $0,6$ & $6,0$
  \end{game}
\end{center}
When $\omega = T$, they are
\begin{center}
  \begin{game}{2}{2}
    & $L$ & $R$ \\
    & $0,0$ & $4,4$
  \end{game}
\end{center}
A possible interpretation of this game is the following: the sender is
a job applicant who knows whether or not she is qualified. The
receiver wants to hire only qualified applicants. 

Here the sender wants the receiver to choose $R$, regardless of the
state. Without any information, $L$ is the better choice for the
receiver. In this case there are only babbling equilibria. This is
because if there is any message that the sender can send that will
make the receiver choose $R$, then in equilibrium she must send
it. Hence the receiver will ignore this message.


\subsubsection{Example 3.}
Here $A = \{LL,L,C,R,RR\}$.  When $\omega = H$, the utilities are
given by
\begin{center}
  \begin{game}{2}{5}
    & $LL$ & $L$ & $C$ & $R$    & $RR$\\
    & $0,10$ & $1,8$ & $0,5$ & $1,0$ & $0,-8$
  \end{game}
\end{center}
When $\omega = T$, they are
\begin{center}
  \begin{game}{2}{5}
    & $LL$ & $L$ & $C$ & $R$    & $RR$\\
    & $0,-8$ & $1,0$ & $0,5$ & $1,8$ & $0,10$
  \end{game}
\end{center}
So the sender wants actions $L$ or $R$ to be taken, and the receiver
wants to take $LL$ when $\omega = H$ and $RR$ when $\omega=T$.

A possible interpretation is that the receiver is a voter that can
vote for the extreme left or right, for moderate left or right, or to
abstain. The ``correct'' vote depends on the unknown state of the
world. The sender is interested in political stability and wants the
voter to vote for any of the moderate choices.

Again, we will have a babbling equilibrium. More interestingly, there
is a {\em partially revealing equilibrium}. In this equilibrium the
sender chooses $m(\omega) = \omega$ with probability $3/4$, and sends
the opposite signal with probability $1/4$. The receiver chooses $L$
if she got the signal $H$, and $T$ otherwise. A simple calculation
shows that this choice maximizes her expected utility. This is optimal
for the sender, since she gets the highest utility possible.




\newpage
\subsection{The Walmart game}
In this section (based on~\cite[Example 239.1]{osborne1994course}) we
describe a game of perfect information, find its unique subgame
perfect equilibrium, and discuss why this seems an unsatisfactory
description of reality. We then analyze a Bayesian version of the same
game, which seems to have a more attractive solution.

\subsubsection{Perfect information, one round}
A mobster approaches a local grocer and asks for payment in exchange
for ``protection services''. The grocer has two possible courses of
action: comply ($C$) or refuse ($R$). In the latter case the mobster
has two possible responses: punish ($P$) or forgive ($F$). The payoff
matrix in strategic form is the following, with the mobster as the row
player. Here $a > 1$ and $0 < b < 1$.

\begin{center}
  \begin{game}{2}{2}
    & $C$     & $R$\\
    $P$   & $a,0$  & $-1,b-1$\\
    $F$ & $a,0$ & $0,b$
  \end{game}
\end{center}

Alternatively, this can be a model of a game played by Walmart and the
same grocer: Walmart opens a store in town. The grocer has two
possible courses of action: leave town or stay. In the latter case
Walmart has two possible responses: undercut or compete; undercutting
refers to the practice of charging below cost in order to bankrupt the
competition.

A Nash equilibrium of this game is for the grocer to comply, under
threat of punishment by the mobster. However, this is not a credible
threat, and in the unique subgame perfect equilibrium of this game the
grocer refuses and the mobster forgives.

\subsubsection{Perfect information, many rounds}
Consider now the case that there are $n$ grocers that the mobster
engages, one after the other. Thus this is an $n+1$-player game, with
the game between the mobster and each grocer being the one described
above. Note that for the last grocer the unique subgame perfect
equilibrium is again $(R,F)$, and therefore, by backward induction, in
the unique subgame perfect equilibrium of this game each grocer
refuses and the mobster forgives, after any history.

Consider the case that the mobster deviates and punishes the first ten
grocers who refuse. Under this (unique) subgame perfect equilibrium,
the eleventh grocer will not learn the lesson and will again refuse.

\subsubsection{Imperfect information, one round}
Consider now the case that there are two types of mobsters: the sane
mobster ($s$) and the crazy mobster ($c$). The former's utility is as
described above. The latter derives sadistic pleasure from punishing,
and therefore, when playing with a crazy mobster, the utility matrix is
the following.

\begin{center}
  \begin{game}{2}{2}
    & $C$     & $R$\\
    $P$   & $a,0$  & $0,b-1$\\
    $F$ & $a,0$ & $-1,b$
  \end{game}
\end{center}

Consider now a Bayesian game in which the mobster is crazy with
probability $\eps$ and sane with probability $1-\eps$. The mobster
observes his type but the grocer does not. They then play the same
game.

The mobster does have complete information here, and so the analysis
of the subgame perfect equilibrium is still simple. If the grocer
refuses, clearly the sane mobster forgives and the crazy mobster
punishes. Hence the grocer's expected utility for refusing is
$(1-\eps)b + \eps(b-1) = b - \eps$ and his utility for complying is
$0$. We assume that $\eps < b$, and so we again have that the grocer
refuses.

\subsubsection{Imperfect information, many rounds}
We now expand this Bayesian game to a game with $n$ rounds, where, as
before, in each round the mobster engages a new grocer. We number the
rounds $\{0,1,\ldots,n-1\}$. We associate with each round $k$ the
number $b_k = b^{n-k}$.

The mobster's type is picked once in the beginning of the game, and is
not observed by any of the grocers. We think of $\eps$ as small but
fixed, and of $n$ of being very large, so that $b_0 = b^n < \eps$.

We describe an assessment that is sequentially rational, and is in
fact a perfect Bayesian equilibrium, according to the definition in
Fudenberg and Tirole~\cite{fudenberg1991perfect}. In this equilibrium
the mobster will (obviously) punish if he is crazy. However, even if
he is sane, he will punish (except towards the end), to maintain the
grocers' beliefs that he might be crazy. The result is that the
grocers all comply, except for the last few.

Note that the mobster observes his own type and all the grocers'
actions, and so there is no need to define beliefs for him. The
grocers' beliefs are probability distributions over the mobster's
type, and so we denote the belief of grocer $P(h)$ after a history $h$
by $\mu(h)$, which we will take to denote the belief that the mobster
is crazy (rather than having it denote the entire distribution).

The game will have two phases. In the first phase, the mobster will
always punish any grocer that does not comply. This will last $k^*$
rounds, where
\begin{align*}
  k^* = \max \{k \in \N\,:\, \eps > b_k\}.
\end{align*}
In the second phase the sane mobster will use a mixed strategy to
decide whether to punish or forgive, while the crazy mobster will
always punish. Finally, in the last round the sane mobster always
forgives (while the crazy still punishes).

The beliefs are defined as follows:
\begin{itemize}
\item Initially, $\mu(\emptyset) = \eps$; this must be so if this is
  indeed to be an assessment (recall that in assessments we require
  beliefs to be derived from the strategy profile, and in particular
  from the chance moves).

\item When a grocer complies the grocers do not observe any action of
  the mobster, and thus maintain the same belief. That is,
  $\mu(h C) = \mu(h)$ for any history $h$.

\item If the mobster ever forgives a refusal then the grocers
  henceforth believe that he is sane. That is, $\mu(h) = 0$ for any
  history $h$ that contains $F$.

\item Given a history $h$ in which the mobster has never forgiven, and
  which ends in round $k$ in which the mobster punished, the belief
  $\mu(h P) = \max \{\mu(h), b_k\}$.
\end{itemize}

The strategies $\sigma$ are defined as follows, where $h$ is a history
at round $k$:
\begin{itemize}
\item The grocer refuses if $\mu(h) < b_k$. He complies if
  $\mu(h) > b_k$. If $\mu=b_k$ then he complies with
  probability $1/a$ and refuses with probability $1-1/a$.
\item The mobster has to move only if the grocer refused. If the
  mobster is crazy then he always punishes. If he is sane then on the
  last round he always forgives. On other rounds he punishes if
  $\mu(h) > b_k$. If $\mu(h) \leq b_k$ then he punishes with
  probability $p_k$ and forgives with probability $1-p_k$, where
  \begin{align*}
    p_k = \frac{(1-b_{k+1})\mu(h)}{b_{k+1}(1-\mu(h))}.
  \end{align*}
\end{itemize}

We now analyze the game play along the equilibrium path. We assume
that $\eps > b^n$, and thus $k^* \geq 1$. Since
$\mu(\emptyset) = \eps$, in round $0$ we have that $\mu > b_0$, and so
the grocer complies. This leaves $\mu$ unchanged, and so, as long as
the round $k$ is at most $k^*$, we have that $\mu > b_k$ and the
grocers keep complying. This is rational since the mobster (whether
sane or not) punishes when $\mu > b_k$. If any of the grocers were to
deviate and refuse in this phase, the mobster would punish (again,
whether sane or not) and so the grocers would learn nothing and
continue complying.

In the second phase, if $\mu(h) = b_k$ then a sane mobster will punish
with probability $p_k$. Hence the probability that a mobster will
punish is
\begin{align*}
  b_k+(1-b_k)p_k
  &= b_k+(1-b_k)\frac{(1-b_{k+1})\mu(h)}{b_{k+1}(1-\mu(h))}\\
  &= b_k+(1-b_k)\frac{(1-b_{k+1})b_k}{b_{k+1}(1-b_k)}\\
  &= b_k+\frac{(1-b_{k+1})b_k}{b_{k+1}}\\
  &= b_k+(1-b_{k+1})b\\
  &= b.
\end{align*}
It follows that a grocer's utility for complying is
$(b-1)b+b(1-b) = 0$, making him indifferent between complying and
refusing. It is therefore rational for him to play any mixed
strategy. If $\mu(h) < b_k$ then the mobster punishes with probability
less than $b$. In that case the only rational choice of the grocer is
to refuse.

In the second phase, we claim that $\mu$ at round $k$ is always at
most $b_k$. We prove this by induction; it is true by definition at
the first round of the second phase, round $k^*$.

If the grocer refuses and the mobster punishes at round $k > k^*$
(with probability $p_k$), and assuming the he has never forgiven
before, Bayes' law yields that
\begin{align*}
  \frac{\mu(h P)}{1-\mu(h P)}
  &= \frac{\mu(h)}{(1-\mu(h))p_k}\\
  &=
    \frac{\mu(h)}{(1-\mu(h))}\frac{b_{k+1}(1-\mu(h))}{(1-b_{k+1})\mu(h)}\\
  &= \frac{b_{k+1}}{1-b_{k+1}}.
\end{align*}
Hence $\mu(h P) = b_{k+1}$ at round $k+1$. If the grocer refuses and
the mobster forgives then the grocers learn that the mobster is sane
and $\mu(h F) = 0$. If the grocer complies then $\mu$ remains
unchanged since no action is observed, and
$\mu(h C) = \mu(h) < b_{k+1}$.  Thus in any case it indeed holds that
$\mu$ is at most $b_k$. Also, it follows that the grocers' beliefs are
derived from $\sigma$.

Finally, we note (without proof) that the probabilities that the
grocers choose in their mixed strategies make the mobster indifferent,
and thus this assessment is indeed sequentially rational.

\section{Repeated games}


\subsection{Extensive form games with perfect information and
  simultaneous moves}

Recall (Section~\ref{sec:extensive-perfect-definition}) that an
extensive form game with perfect information is given as a tuple
$G = (N,A,H,O,o,P,\{\pleq_i\}_{i \in N})$, where $N$ is the set of
players, $A$ is the set of actions, $H$ is the set of allowed
histories (with $Z$ the terminal histories), $O$ is the set of
outcomes, $o$ is a function $Z \to O$, $P$ is a function
$H \setminus Z \to N$, and for each player $i \in N$, $\pleq_i$ is a
preference relation over $O$.

In this section we slightly extend this definition by allowing two or
more players to make simultaneous moves. The definitions of $N$ and
$A$ remain the same. $P$ will now be a function from $H \setminus Z$
to $2^N$, the power set of the set of players, so that after history
$h \in H$ the set of players who play simultaneously is $P(h)$.

Recall that a history was defined to be a finite sequence in $A$; it
will now be a sequence of tuples $\underline{a}_t$ in $A$, with each
tuple in the sequences potentially of different size. Specifically, a
history $h$ is a sequence $(\underline{a}_1,\underline{a}_2,\ldots)$,
such that, for each $t$, $\underline{a}_t \in A^M$ where
$M = P(\underline{a}_1,\ldots,\underline{a}_{t-1})$. The set of
histories will have to satisfy an additional criterion: if
$h = (\underline{a}_1,\ldots,\underline{a}_n) \in H$ then there must
be for each player $i \in P(h)$ a set $A_i(h) \subset A$ such that for
any $\underline{a} \in \prod_i A_i$ the history
$(\underline{a}_1,\ldots,\underline{a}_n, \underline{a})$ is also in $H$. That is,
each player has a set of allowed moves, and any combination of allowed
moves by the players is allowed.

A strategy in such a game is a function that assigns to each history
$h \in H$ and player $i \in P(h)$ an action in $A_i(h)$.

\subsubsection{Equilibria}
The definitions of a Nash equilibrium, a subgame, and a subgame
perfect equilibrium carry unchanged to this new setting.

Note that Kuhn's Theorem does not apply here: for example, any
strategic form game is a one-period extensive form game with perfect
information and simultaneous moves. But not every such games has a
pure equilibrium.  On the other hand, the one deviation principle
(Theorem~\ref{thm:one-deviation}) still applies; the proof is
identical.



\subsection{Definition of repeated games}

Let $G_0 = (N, \{A_i\}, \{u_i\})$ be a strategic form game, and, as
usual, let $A = \prod_i A_i$. We will only consider games in which $A$
is compact and each $u_i$ is continuous.

Let $T$ be the number of periods (or repetitions) of the repeated
game. $T$ can be either finite or infinite.  A $T$-repeated game of
$G_0$ is an extensive form game
$G = (N,A',H,O,o,P,\{\pleq_i\}_{i \in N})$, where
\begin{itemize}
\item $P(h) = N$ for all $h \in H \setminus Z$.
\item The set of histories $H$ has terminal histories $Z =
  \prod_{t=1}^T A$; recall that $Z$ uniquely determines $H$ as the set
  of all prefixes of $Z$.
\item $A'$ is likewise determined by $H$.
\item $O = Z$ and $o$ is the identity.
\item $\pleq_i$ is some preference relation on $Z$ that satisfies the
  following condition: If $u_i(a^t) \leq u_i(b^t)$ for all $t$ and
  some $(a^1,a^2,\ldots), (b^1,b^2,\ldots) \in Z$ then
  \begin{align*}
   (a^1,a^2,\ldots) \pleq_i (b^1,b^2,\ldots).
  \end{align*}
\end{itemize}
We call $G_0$ the base game of $G$. We call an element of $A$ an
action profile, and an element of $A'$ a strategy profile. Given a
strategy profile which results in an action profile $a^t$ chosen at
period $t$, we call $u_i(a^t)$ the {\em stage utility} of player
$i$ at period $t$.

If we assign utilities $\{v_i\}_{i \in N}$ to elements of $Z$, then we
call $(v_1(a),\ldots,v_n(a))$ the {\em payoff profile} associated with
$a$. Given a strategy profile $s$ of $G$, we likewise define the
payoff profile $(v_1(s),v_2(s),\ldots,v_n(s))$ associated with $s$ to
be the payoff profile associated with the path of play generated by
$s$.

When $T$ is finite then a natural choice is to let the players'
utilities in the repeated game be the sum of their base game utilities
in each of the periods. When $T = \infty$ we will consider two types
of preference relations: {\em discounting} and {\em limit of means},
or {\em limiting mean}. In fact, in both we will define utilities that
induce the equivalence relations.



\subsubsection{Discounting}
We fix some $\delta \in (0,1)$ and let $v_i \colon Z \to \R$ be given
by the discounted sum
\begin{align*}
  v_i(a^1,a^2,\ldots) = (1-\delta)\sum_{t=1}^\infty\delta^{t-1}u_i(a^t).
\end{align*}
These will be the player's utilities in the repeated game $G$, and
$\pleq_i$ will simply be given by these utilities. Note that we chose
the scaling of $v_i$ to make it a weighted average of the
utilities. 

Discounting has the advantage that it is {\em stationary}: every
subgame of $G$ is isomorphic to $G$.

\subsubsection{Limit of means, limiting mean}
In the usual definition of ``limit of means'',
$(a^1,a^2,\ldots) \pgt_i (b^1,b^2,\ldots)$ by player $i$ if
\begin{align*}
  \liminf_\tau \frac{1}{\tau}\sum_{t=1}^\tau
  u_i(a^t)-\frac{1}{\tau}\sum_{t=1}^\tau u_i(b^t) > 0.
\end{align*}
Note that, under this definition, a pair $(a^1,a^2,\ldots)$ and
$(b^1,b^2,\ldots)$ that differ only in finitely many periods are
equivalent.

We will take a slightly different approach to limits of means, using
limiting means. Let $\ell^\infty(\N) \subset \R^\N$ denote the bounded
real sequences.

A {\em mean} $m$ is a map $\ell^\infty(\N) \to \R$ with the following
properties
\begin{itemize}
\item Linearity:
  \begin{align*}
    m(x+y) = m(x)+m(y)
  \end{align*}
  and
  \begin{align*}
    m(\alpha \cdot x) = \alpha \cdot m(x).
  \end{align*}
\item Positivity: if $x_n \geq 0$ for all $n$ then $m(x)
  \geq 0$.
\item Unity: $m(1,1,\ldots) = 1$.
\end{itemize}
For example, if $\sum_{n=1}^\infty\alpha_n = 1$ then
\begin{align*}
  m(x) = \sum_{n=1}^\infty\alpha_n x_n
\end{align*}
is a mean. However, there are also more interesting examples:

\begin{theorem}
  There exists a mean $m$ such that $m(x)$ is always the limit of some
  subsequence of $\{\frac{1}{n}\sum_{i=1}^n x_i\}_{n \in \N}$.
\end{theorem}
In particular, if a pair $x,y \in \ell^\infty(\N)$ differ in only
finitely many coordinates then $m(x) = m(y)$. Note also that such a
mean $m$ is {\em shift-invariant}:
$m(x_1,x_2,x_3,\ldots) = m(x_2,x_3,\ldots)$.


It follows that $m(x_1,x_2,\ldots) > m(y_1,y_2,\ldots)$ whenever
\begin{align*}
  \liminf_n \frac{1}{n}\sum_{i=1}^n x_i-\frac{1}{n}\sum_{i=1}^n y_i > 0.
\end{align*}
Therefore, if we choose such an mean $m$ and let
\begin{align*}
  v_i(a^1,a^2,\ldots) = m(u_i(a^1),u_i(a^2),\ldots)
\end{align*}
then $v_i(a) > v_i(b)$ whenever $a \pgt_i b$. That is, the preference
relation induced by $v_i$ has all the strict preferences that
$\pleq_i$ has, and perhaps also additional ones.

Limiting means utilities, like discounting utilities, are stationary.
\newpage
\subsection{Folk theorems}

\subsubsection{Example}
What payoffs profiles are achievable in Nash equilibria of infinite
repeated games? It turns out that the answer is: more or less all of
them. To get some intuition as to how this is done, consider the
following example. Let $G_0$ be the following prisoner's dilemma
game:
\begin{center}
  \begin{game}{2}{2}
    & $D$     & $C$\\
    $D$   & $0,0$  & $3,-4$\\
    $C$ & $-4,3$ & $2,2$
  \end{game}
\end{center}
Consider the following symmetric strategy profile, called ``grim
trigger'': start with $C$, and keep on playing $C$ until the other
person plays $D$. Then play $D$ henceforth. It is easy to see that
this is an equilibrium under both limiting means and discounting, for
$\delta$ close enough to one.


\subsubsection{Enforceable and feasible payoffs}
We fix an infinitely repeated game $G$ with base game $G_0$.  Define
the {\em minmax payoff} of player $i$ in the base game $G_0$ as the
lowest payoff that the rest of the players can force on $i$:
\begin{align*}
  u^{mm}_i = \min_{a_{-i}}\max_{a_i} u_i(a_{-i},a_i).
\end{align*}
Equivalently, this is the payoff that player one can guarantee for
herself, regardless of the other player's actions.

We say that a payoff profile $w \in \R^n$ is {\em enforceable} if
$w_i \geq u^{mm}_i$ for all $i \in N$. It is {\em strictly
  enforceable} if $w_i > u^{mm}_i$ for all $i \in N$.

\begin{claim}
  Let $s^*$ be a Nash equilibrium of $G$, under either discounting or
  limiting means. Then the payoff profile associated with $s$ is
  enforceable.
\end{claim}
\begin{proof}
  Since player $i$ can guarantee a stage utility of $u^{mm}_i$, she
  can always choose a strategy such that her stage utilities will each
  be at least $u^{mm}_i$. Hence under both discounting and limiting
  means her payoff will be at least $u^{mm}_i$ in $G$.
\end{proof}

We say that a payoff profile $w$ is {\em feasible} if it is a convex
combination of utilities achievable in $G_0$. That is, if for all
$i \in N$
\begin{align*}
  w_i = \sum_{a \in A}\alpha_a \cdot u_i(a)
\end{align*}
for some $\{\alpha_a\}$ that sum to one. Clearly, every payoff profile
in $G$ is feasible.

\begin{exercise}
  Consider the game
  \begin{center}
    \begin{game}{3}{3}
      & $D$     & $C$ & $F$\\
      $D$   & $0,0$   & $1,0$ & $0,1$\\
      $C$ & $0,1$ & $2,2$ & $-2,3$\\
      $F$ & $1,0$ & $2,-3$ & $-2,-2$
    \end{game}
  \end{center}
  Draw a diagram of the feasible and enforceable profiles.
\end{exercise}

\subsection{Nash folk theorems}

Aumann and Shapley~\cite{aumann1994long} proved the Nash folk theorem
for limit of means. We state it for limiting means.
\begin{theorem}
  \label{thm:nash-folk-means}
  For every feasible, enforceable payoff profile $w$ there exists a
  Nash equilibrium of $G$ with limiting means utilities whose
  associated payoff profile is $w$.
\end{theorem}
The construction of these equilibria involves {\em punishing}: players
all play some equilibrium, and if anyone deviates the rest punish
them.
\begin{proof}[Proof of Theorem~\ref{thm:nash-folk-means}]
  Let $w_i = \sum_{a \in A}\alpha_a \cdot u_i(a)$. Let
  $(a^1,a^2,\ldots)$ be a sequence in $A$ such that
  $m(\ind{a^1=a},\ind{a^2=a},\dots) = \alpha_a$. Such a sequence
  exists since (for example) if we choose each $a^t$ independently at
  random to equal $a$ with probability $\alpha_a$ then with
  probability one the sequence has this property. If the coefficients
  $\alpha_a$ are rational then one can simply take a periodic sequence
  with period equal to the lowest common denominator.

  Let $s^*$ be the following strategy profile. For each player $i$ let
  $s^*_i$ be the strategy in which she chooses $a^t_i$, unless in some
  previous period $\tau$ some player $j$ did not choose $a^\tau_j$, in
  which case she chooses a strategy $b_i$, where
  \begin{align*}
    b_{-j}  \in \argmin_{a_{-j}}\max_{a_j} u_j(a_{-j},a_j).
  \end{align*}

  Hence the stage utilities of a player $i$ who deviates will be, from
  the point of deviation on, at most $u^{mm}_i$. Therefore her utility
  will be at most $u^{mm}_i$, since utilities do not depend on any
  finite set of stage utilities. Since $w$ is enforceable, it follows
  that $w_i \geq u^{mm}_i$, and so no deviation is profitable, and
  $s^*$ is an equilibrium.
\end{proof}

A similar proof technique can be used to show the following theorem,
which is due to Fudenberg and Maskin~\cite{fudenberg1986folk}, with an
earlier, weaker version by Friedman~\cite{friedman1971non}.
\begin{theorem}
  \label{thm:nash-folk-discounting}
  For every feasible, {\em strictly} enforceable payoff profile $w$
  and $\eps > 0$ there is a $\delta_0 > 0$ such that for all
  $\delta > \delta_0$ there exists a Nash equilibrium of $G$ with
  $\delta$-discounting utilities whose associated payoff profile $w'$
  satisfies $|w_i'-w_i| < \eps$ for all $i \in N$.
\end{theorem}
The discount factor needs to be large enough to make eternal
punishment pose more of a loss than can be gained by a single
deviation. It also needs to be large enough to allow for the
discounted averages to approximate a given convex combination of the
base game utilities.

We provide here a proof of a weaker statement.
\begin{theorem}
  Let $a$ be an action profile whose associated payoff profile $w$ is
  strictly enforceable\footnote{Since $w$ is a payoff profile of some
    action profile then it is immediately feasible.}. Then there is
  a $\delta_0$ such that, for all $\delta > \delta_0$, there exists a
  Nash equilibrium of $G$ with $\delta$-discounting utilities whose
  associated payoff profile is also $w$.
\end{theorem}
\begin{proof}
  Let $s^*$ be the strategy profile defined in the proof of
  Theorem~\ref{thm:nash-folk-means}, with $\alpha_a=1$. We will show
  that for $\delta$ close enough to $1$ it is also a Nash equilibrium,
  and that its associated payoff profile is $w$. In fact, the latter
  is immediate, since the stage utilities for player $i$ are all equal
  to $w_i$ on the equilibrium path.

  Let $M$ be the largest possible stage utility achievable by any
  player in one period by any deviation. Then the utility of player
  $i$ who first deviates in period $\tau+1$ to some strategy $s_i$ satisfies
  \begin{align*}
    v_i(s^*_{-i},s_i) \leq (1-\delta)\left(\sum_{t=1}^\tau \delta^{t-1}w_i + \delta^{\tau}M + \sum_{t=\tau+2}^\infty \delta^{t-1}u_i^{mm}\right).
  \end{align*}
  Hence
  \begin{align*}
    v_i(s^*)-v_i(s^*_{-i},s_i)
    &\geq (1-\delta)\left(\delta^{\tau}(w_i-M)+\sum_{t=\tau+2}^\infty \delta^{t-1}(w_i-u_i^{mm})\right)\\
    &= (1-\delta)\delta^\tau\left(w_i-M+(w_i-u_i^{mm})\sum_{t=2}^\infty \delta^{t-1}\right)\\
    &= (1-\delta)\delta^\tau\left(w_i-M+(w_i-u_i^{mm})\frac{\delta}{1-\delta}\right).
  \end{align*}
  Now, $\delta/(1-\delta)$ tends to infinity as $\delta$ tends to
  one. Hence the expression in the parentheses is non-negative for
  $\delta$ large enough, and the deviation is not profitable.
\end{proof}
\newpage
\subsection{Perfect folk theorems}
Consider the following base game (taken from Osborne and
Rubinstein~\cite{osborne1994course}):
\begin{center}
  \begin{game}{2}{2}
    & $D$     & $C$\\
    $D$   & $0,1$  & $0,1$\\
    $C$ & $1,5$ & $2,3$
  \end{game}
\end{center}
Here, an equilibrium built in Theorems~\ref{thm:nash-folk-means}
and~\ref{thm:nash-folk-discounting} that achieves payoff profile
$(2,3)$ has the players playing $(C,C)$ on the equilibrium path, and
punishing by playing $D$ forever after a deviation. Note, however,
that for the row player, action $D$ is strictly dominated by
$C$. Hence this equilibrium is not a subgame perfect equilibrium:
regardless of what the column player does, the row player can increase
her subgame utility by at least 1 by always playing $C$ rather than
$D$. It is therefore interesting to ask if there are subgame perfect
equilibria that can achieve the same set of payoff profiles.

\subsubsection{Perfect folk theorem for limiting means}
The following theorem is due to Aumann and
Shapley~\cite{aumann1994long}, as well as
Rubinstein~\cite{rubinstein1980strong}. 
\begin{theorem}
  \label{thm:perfect-folk-means}
  For every feasible, strictly enforceable payoff profile $w$ there
  exists a subgame perfect Nash equilibrium of $G$ with limiting means
  utilities whose associated payoff profile is $w$.
\end{theorem}
The idea behind these equilibria is still of punishing, but just for
some time rather than for all infinity. Since lower stage utilities
are only attained in finitely many periods there is no loss in the
limit.
\begin{proof}[Proof of Theorem~\ref{thm:perfect-folk-means}]
  As in the proof of Theorem~\ref{thm:nash-folk-means}, let
  $w_i = \sum_{a \in A}\alpha_a \cdot u_i(a)$, and let
  $(a^1,a^2,\ldots)$ be a sequence in $A$ such that
  $m(\ind{a^1=a},\ind{a^2=a},\dots) = \alpha_a$. Likewise, for each
  player $i$ let $s^*_i$ be the strategy in which she chooses $a^t_i$,
  unless in some previous period $\tau$ some player $j$ deviated and
  did not choose $a^\tau_j$. In the latter case, we find for each such
  $\tau$ and $j$ a $\tau'$ large enough so that, if all players but
  $j$ play
  \begin{align*}
    b_{-j}  \in \argmin_{a_{-i}}\max_{a_i} u_i(a_{-1},a_i),
  \end{align*}
  in time periods $(\tau + 1,\ldots,\tau')$ then the average of player
  $j$'s payoffs in periods $(\tau,\tau+1,\ldots,\tau')$ is lower than
  $w_j$. Such a $\tau'$ exists since the payoffs in periods
  $(\tau+1,\ldots,\tau')$ will all be at most $u^{mm}_j$, and since
  $w_j > u^{mm}_j$. We let all players but $j$ play $b_{-j}$ in
  time periods $\tau+1,\ldots,\tau'$. We do not consider these
  punishments as punishable themselves, and after period $\tau'$ all
  players return to playing $a^t_i$ (until the next deviation).

  To see that $s^*$ is a subgame perfect equilibrium, we consider two
  cases. First, consider a subgame in which no one is currently being
  punished. In such a subgame anyone who deviates will be punished and
  lose more than they gain for each deviation. Hence a deviant $j$'s
  long run average utility will tend to at most $w_j$, and there is no
  incentive to deviate.

  Second, consider a subgame in which someone is currently being
  punished. In such a subgame the punishers have no incentive to
  deviate, since the punishment lasts only finitely many periods, and
  thus does not affect their utilities; deviating from punishing will
  not have any consequences (i.e., will not be punished) but will also
  not increase utilities, and therefore there is again no incentive to
  deviate.
  
\end{proof}

\subsubsection{Perfect folk theorems for discounting}

We next turn to proving perfect folk theorems for discounted
utilities. An early, simple result is due to
Friedman~\cite{friedman1971non}.
\begin{theorem}
  Let $G_0$ have a pure Nash equilibrium $s^*$ with payoff profile
  $z$. Let $w$ be a payoff profile of some strategy profile $a \in A$
  of $G_0$ such that $w_i > z_i$ for all $i \in \N$.  Then there is a
  $\delta_0 > 0$ such that for all $\delta > \delta_0$ there exists a
  subgame perfect equilibrium of $G$ under discounting, with payoff
  profile $w$.
\end{theorem}
The idea behind this result is simple: the players all play $a$ unless
someone deviates. Once anyone has deviated, they all switch to playing
$s^*$. Given that $\delta$ is close enough to 1, the deviant's utility
from playing $s^*$ henceforth will trump any gains from the
deviation. Since $s^*$ is an equilibrium, there is no reason for the
punishers to deviate from the punishment.

A harder result is due to Fudenberg and
Maskin~\cite{fudenberg1986folk} who, for the two player case, extend
the Nash folk theorem~\ref{thm:nash-folk-discounting} to a perfect
Nash folk theorem.
\begin{theorem}
  \label{thm:perfect-folk-discounting}
  Assume that $|N|=2$.  For every feasible, {\em strictly} enforceable
  payoff profile $w$ and $\eps > 0$ there is a $\delta_0 > 0$ such
  that for all $\delta > \delta_0$ there exists a perfect Nash
  equilibrium of $G$ with $\delta$-discounting utilities whose
  associated payoff profile $w'$ satisfies $|w_i'-w_i| < \eps$ for all
  $i \in N$.
\end{theorem}
Before proving this theorem will we state the following useful
lemma. The proof is straightforward.
\begin{lemma}
  Let $G$ be a repeated game, with $\delta$-discounted utilities. The
  utilities for playing $(b,a^1,a^2,\ldots)$ are given by
  \begin{align*}
    v_i(b,a^1,a^2,\ldots) = (1-\delta)u_i(b) + \delta v_i(a^1,a^2,\ldots).
  \end{align*}
\end{lemma}
More generally,
\begin{align}
  \label{eq:bellman}
  v_i(b^1,\ldots,b^k,a^1,a^2,\ldots) = (1-\delta)\sum_{t=1}^k \delta^{t-1}u_i(b^t) + \delta^k v_i(a^1,a^2,\ldots).  
\end{align}
A useful interpretation of this lemma is the following: the utility
for playing $(b,a^1,a^2,\ldots)$ is $1-\delta$ times the stage utility
for $b$, plus $\delta$ times the utility of $(a^1,a^2,\ldots)$ in the
subgame that starts in the second period. 

We will also use the following lemma, which is a one deviation
principle for repeated game with discounting.
\begin{lemma}
  \label{thm:one-deviation-discouting}
  Let $G$ be a repeated game with $\delta$-discounting. Let $s^*$ be a
  strategy profile that is {\em not} a subgame perfect
  equilibrium. Then there is a subgame $G'$ of $G$ and a player $i$
  who has a profitable deviation in $G'$ that differs from $s^*_i$
  only in the first period of $G'$.
\end{lemma}
\begin{proof}
  Let $s_i$ be a profitable deviation from $s^*_i$. Assume without
  loss of generality that stage utilities take values in $[0,1]$, and
  let $v_i(s^*_{-i},s_i) = v_i(s^*) + \eps$. Let $\bar s_i$ be the
  strategy for player $i$ which is equal to $s_i$ up to some time
  period $\ell > \log(\eps/2)/\log(\delta)$, and thereafter is equal
  to $s^*$. Then $\delta^\ell < \eps/2$, and so,
  by~\eqref{eq:bellman},
  \begin{align*}
    |v_i(s^*_{-i},s_i) - v_i(s^*_{-i},\bar s_i)| \leq \delta^\ell.
  \end{align*}
  Hence $v_i(s^*_{-i},\bar s_i) > v_i(s^*) + \eps/2$, and thus
  $\bar s_i$ is a profitable deviation. Note that $\bar s_i$ differs
  from $s_i^*$ in only finitely many histories.

  Assume now that $s_i$, among $i$'s profitable deviations, has a
  minimal number of histories in which it can differ from $s_i^*$. By
  applying an argument identical to the one used to prove the one
  deviation principle for finite extensive form games, there also
  exists a profitable deviation that differs from $s^*_i$ at only one
  history, in which it matches $s_i$.
\end{proof}


We prove Theorem~\ref{thm:perfect-folk-discounting} for the particular
case that $(w_1,w_2) = (u_1(a),u_2(a))$ for some feasible and strictly
enforceable $a \in A$; in this case we can take $\eps=0$. The proof of
the general case uses the same idea, but requires the usual technique
of choosing a sequence of changing action profiles.

We assume that $u^{mm}_i = 0$. This is without loss of generality,
since otherwise we can define a game $G_0'$ in which the utilities are
$u'_i = u_i - u^{mm}_i$. The analysis of the $G'_0$-repeated game will
be identical, up to an additive constant for each player's utility.

Fix
\begin{align*}
  b_1 \in \argmin_{a_1}\max_{a_2}u_2(a_1,a_2)
\end{align*}
and
\begin{align*}
  b_2 \in \argmin_{a_2}\max_{a_1}u_1(a_1,a_2)
\end{align*}
Note that $u_1(b_1,b_2) \leq 0$ and likewise $u_2(b_1,b_2) \leq 0$,
since we assume that $u^{mm}_1 = u^{mm}_2 = 0$.

As an example, consider the following base game:
\begin{center}
  \begin{game}{3}{3}
    & $D$     & $C$ & $F$\\
    $D$   & $0,0$   & $1,0$ & $0,1$\\
    $C$ & $0,1$ & $2,2$ & $-2,3$\\
    $F$ & $1,0$ & $2,-3$ & $-2,-2$
  \end{game}
\end{center}
With $a=(C,C)$. It is easy to see that $u^{mm}_1=u^{mm}_2=0$ and that
necessarily $b = (F,F)$.

Consider the following strategy profile $s^*$ for the repeated
game. Recall that $(w_1,w_2) = (u_1(a),u_2(a))$ for some feasible and
strictly enforceable $a \in A$. In $s^*$, the game has two ``modes'':
{\em on-path mode} and {\em punishment mode}.
\begin{itemize}
\item In on-path mode each player $i$ plays $a_i$.
\item In punishment mode each player $i$ plays $b_i$.
\end{itemize}
Both players start in the on-path mode. If any player deviates, the
game enters punishment mode for some fixed number of $\ell$
rounds. This also applies when the game is already in punishment
mode: if a player deviates when in punishment mode (i.e., stops
punishing and does not play $b_i$), the game re-enters punishment mode
for $\ell$ rounds.


Player $i$'s utility on path is given by
\begin{align*}
  v_i(s^*) = (1-\delta)\sum_{t=1}^\infty\delta^{t-1}u_i(a) = w_i.
\end{align*}
Denote by $M = \max_{a \in A, i \in N}u_i(a)$ the maximal utility
achievable by any player in $G_0$. Denote the punishment utility
penalty by $p_i = -u_i(b_1,b_2) \geq 0$.

In the example above, $w_1 = w_2 = 2$ and
$u_1(b_1,b_2) = u_2(b_1,b_2) = -2$.


To show that $s^*$ is a subgame perfect equilibrium, we consider the
$\ell+1$ types of possible subgames: the $\ell$ possible subgames that
start in punishment mode (which differ by the number of punishment
periods left), and those that start in on-path mode.

Let the subgame $G^k$ start in punishment mode, with $k$ punishment
periods left.  Then on the (subgame) equilibrium path, player $i$'s
utility is given by
\begin{align*}
  v^k_i &= (1-\delta)\sum_{t=1}^k\delta^{t-1}\cdot u_i(b_1,b_2) +
         (1-\delta)\sum_{t=k+1}^\infty\delta^{t-1}\cdot w_i\\
       &=   \delta^k w_i-(1-\delta^k)p_i.
\end{align*}
Note that this is strictly decreasing in $k$, since $-p_i < w_i$.  In
particular
\begin{align}
  \label{eq:v-ell}
  v^\ell_i = \delta^\ell w_i-(1-\delta^\ell)p_i
\end{align}
is less than $v^k_i$ for all $k < \ell$.

Recall that by Lemma~\ref{thm:one-deviation-discouting} we need only
consider deviations at the first period. Since the other player is
punishing player $i$, the utility for $i$ for deviating at $G^k$ is at most
\begin{align*}
  (1-\delta)u^{mm}_i + \delta v^\ell_i = \delta v^\ell_i
\end{align*}
since, applying  This is independent of $k$,
and so, since $v^\ell_i < v^k_i$ for all $k < \ell$, if it is
profitable to deviate at any $G^k$ then it is profitable to deviate at
$G^\ell$. In order for it to not be profitable to deviate at $G^\ell$
it must be that
\begin{align*}
  \delta v^\ell_i \leq v^\ell_i,
\end{align*}
or that $v^\ell_i \geq 0$. Examining~\eqref{eq:v-ell}, we can achieve
this if we choose $\delta$ and $\ell$ so that $\delta^\ell$ is close
enough to $1$, since $w_i > 0$.


In on-path mode a player's utility for deviating is at most
\begin{align*}
  (1-\delta)M + \delta v^\ell_i.
\end{align*}
Therefore, in order to make this deviation not profitable, we need to
choose $\delta$ and $\ell$ in such a way that
\begin{align}
  \label{eq:perfect-discount-punish}
  w_i - (1-\delta)M - \delta v^\ell_i \geq 0.
\end{align}
Substituting the expression for $v^\ell_i$ and rearranging yields the
condition
\begin{align*}
 (1-\delta)M + \delta^{\ell+1} w_i-\delta(1-\delta^\ell)p_i \leq w_i. 
\end{align*}
Note that there is some balancing that needs to be done between
$\delta$ and $\ell$: The l.h.s.\ is a weighted average, and in order
for it to be lower than $w_i$ the weight of $M$ must be sufficiently
lower than the weight of $p_i$. The ratio between these weights is
\begin{align*}
  \frac{\delta(1-\delta^\ell)}{1-\delta} = \delta+\delta^2+\cdots+\delta^\ell.
\end{align*}
This can be made arbitrarily large by choosing a large enough $\ell$,
and then taking $\delta$ to $1$.  This completes the proof of
Theorem~\ref{thm:perfect-folk-discounting}.


The picture is a little more complicated once the number of players is
increased beyond 2. Consider the following $3$ player base
game: the actions available to each player are $A_i = \{0,1\}$, and
the utility to each player is 1 if all players choose the same action,
and 0 otherwise. Clearly, the minmax utilities here are
$u^{mm}_i = 0$.

If we try to implement the idea of the two person proof to this game
we immediately run into trouble, since there is no strategy profile
$(b_1,b_2,\ldots,b_n)$ such that, for {\em every player} $i$, $b_{-i}$
satisfies
\begin{align*}
  b_{-i} \in \argmin_{a_{-i}}\max_{a_i}u_i(a_{-i},a_i).
\end{align*}
To see this, assume that the above is satisfied for $i=3$; that is,
that $b_{-3}$ is a minmax strategy for player 3. Then $b_1 \neq
b_2$.
Hence either $b_3=b_1$ or $b_3=b_2$. In the first case $b_{-2}$ is not
a minmax strategy for player 2, while in the second case $b_{-1}$ is
not a minmax strategy for player 1. In other words, for any strategy
profile $b$ there is a player who can guarantee a payoff of 1, either
by playing $b$ or by deviating from it.

In fact, it can be shown~\cite{fudenberg1986folk} that in this
repeated game there are no perfect equilibria in which all players have
utility less than $1$! Fix a discount factor $\delta \in (0,1)$, and
let
\begin{align*}
  \alpha = \inf\{w\,:\,\exists \mbox{ a subgame perfect equilibrium with utility $w$ for all players}\}.
\end{align*}
By the above observation, in any subgame there will be a player who
can, by perhaps deviating, guarantee a payoff of at least
$(1-\delta) + \delta \alpha$.

Now, for every $\eps > 0$ there is a subgame perfect equilibrium in
which the utility for each player is at most $\alpha + \eps$. Hence
\begin{align*}
 (1-\delta) + \delta \alpha \leq \alpha + \eps,
\end{align*}
or
\begin{align*}
  1-\frac{\eps}{1-\delta} \leq \alpha. 
\end{align*}
Since this holds for every $\eps$ we have that $\alpha \geq 1$.

Note that in this game the set of feasible, enforceable payoff
profiles is $\{(w,w,w)\,:\,w \in [0,1]\}$, which is one
dimensional. It turns out that in base games in which this set has
full dimension --- i.e., dimension that is equal to the number of
players --- a folk theorem does apply. This result is also due to
Fudenberg and Maskin~\cite{fudenberg1986folk}.
\begin{theorem}
  \label{thm:perfect-folk-discounting-n-player}
  Assume that the set of feasible, enforceable payoff profiles has
  dimension $n$.  For every feasible, {\em strictly} enforceable
  payoff profile $w$ and $\eps > 0$ there is a $\delta_0 > 0$ such
  that for all $\delta > \delta_0$ there exists a perfect Nash
  equilibrium of $G$ with $\delta$-discounting utilities whose
  associated payoff profile $w'$ satisfies $|w_i'-w_i| < \eps$ for all
  $i \in N$.
\end{theorem}



To prove this theorem, let $w$ be a feasible, strictly enforceable
payoff profile. Then there is some payoff profile $z$ so that
$z_j < w_j$ for all $j$. Furthermore, because of the full
dimensionality assumption, for each $i=1,\ldots,n$ there is a payoff
profile $z^i$ such that
\begin{itemize}
\item $z^i_i = z_i$.
\item For $j \neq i$, $z_j < z^i_j < w_j$.
\end{itemize}
As in the two-player case, we will prove
Theorem~\ref{thm:perfect-folk-discounting-n-player} for the case that
there are action profiles $a^0,a^1,\ldots,a^n$ for $G_0$ that,
respectively, realize the payoff profiles $w,z^1,\ldots,z^n$.

For each player $i$ let $b^i$ be the profile given by
\begin{align*}
  b_{-i}^i \in \argmin_{a_{-i}}\max_{a_i}u_i(a_{-i},a_i),
\end{align*}
with $b^i_i$ a best response to $b^i_{-i}$. We consider the strategy
profile $s^*$ with the following modes.
\begin{itemize}
\item In on-path mode the players play $a^0$.
\item In $i$-punishment mode, the players play
  $b^i$.
\item In $i$-reconciliation mode the players play $a^i$.
\end{itemize}

The game starts in on-path mode. Assuming it stays there, the payoff
profile is indeed $w$. If any player $i$ deviates, the game enters
$i$-punishment mode for some number of $\ell$ rounds. After these
$\ell$ rounds the game enters $i$-reconciliation mode, in which it
stays forever. A deviation by player $j$ in $i$-reconciliation model
or $i$-punishment mode are likewise met with entering $j$-punishment
mode for $\ell$ periods, followed by $j$-reconciliation mode.

As in the two player case, denote by $\bar u_i = \max_{a \in A}u_i(a)$
the maximal utility achievable by player $i$ in $G_0$.

For $s^*$ to be an equilibrium we have to verify that there are no
profitable deviations in any of the possible subgames. By
Lemma~\ref{thm:one-deviation-discouting} it suffices to check that
no one-shot profitable deviation exists in them. Note that the
possible subgames correspond to one-path mode, $i$-punishment mode
with $k$ periods left, and $i$-reconciliation mode.

The equilibrium path utility for player $j$ is $w_j$ in on-path
mode. In $i$-punishment mode with $k$ periods left it is
\begin{align*}
  (1-\delta^k)u_j(b^i)+\delta^k z^i_j,
\end{align*}
which we will denote by $v^{i,k}_j$. Note that $u_i(b^i)=0$ by the
definition of $b^i$, and so
\begin{align*}
  v^{i,k}_i = \delta^k z^i_i.
\end{align*}
In $i$-reconciliation mode the utility on equilibrium path for player
$j$ is $z^i_j$.


For a deviation of player $j$ in on-path mode to {\em not} be
profitable it suffices to ensure that
\begin{align*}
  (1-\delta)\bar u_j + \delta v^{j,\ell}_j \leq w_j.
\end{align*}
Substituting $v^{j,\ell}_j$ yields
\begin{align*}
  (1-\delta)\bar u_j + \delta^{\ell+1} z^j_j \leq w_j.
\end{align*}
Since $z^j_j < w_j$ this holds for all $\delta$ close enough to
1. Similarly, in $i$-reconciliation mode it suffices that
\begin{align*}
  (1-\delta)\bar u_j + \delta^{\ell+1} z^j_j \leq z^i_j,
\end{align*}
which holds for all $\delta$ close enough to 1 and $\ell$ large
enough, since $z^j_j \leq z^i_j$.

In $i$-punishment mode with $k$ periods left there is clearly no
profitable deviation for $i$, who is already best-responding to her
punishment $b_{-i}$. For there to not be a profitable deviation for
$j \neq i$, it must hold that
\begin{align*}
  (1-\delta)\bar u_j + \delta v^{j,\ell}_j \leq v^{i,k}_j.
\end{align*}
Substituting yields
\begin{align*}
  (1-\delta)\bar u_j + \delta^{\ell+1} z^j_j \leq (1-\delta^k)u_j(b^i)+\delta^k z^i_j.
\end{align*}
By again choosing $\delta$ close enough to 1 we can make the left hand
side smaller than $\delta^k z^i_j$, since $z^j_j < z^i_j$ (recall that
$j \neq i$), and thus smaller than the right hand side. This completes
the proof of Theorem~\ref{thm:perfect-folk-discounting-n-player}, for
the case that the relevant payoff profiles can be realized using pure
strategy profiles.

\subsection{Finitely repeated games}
In this section we consider a finitely repeated game with $T$
periods. The utility will always be the sum of the stage utilities:
\begin{align*}
  v_i(a^1,a^2,\ldots,a^T) = \frac{1}{T}\sum_{t=1}^T u_i(a^t).
\end{align*}


\subsubsection{Nash equilibria and folk theorems}
A simple but important first observation about finitely repeated games
is the following.
\begin{claim}
  In every Nash equilibrium of a finitely repeated game, the last
  action profile played on path is a Nash equilibrium of the base
  game.
\end{claim}

In general finitely repeated games one cannot hope to prove a folk
theorem that is as strong as those available in infinitely repeated
games, as the following example illustrates.

Let $G_0$ be the following prisoner's dilemma:
\begin{center}
  \begin{game}{2}{2}
    & $D$     & $C$\\
    $D$   & $6,6$  & $14,2$\\
    $C$ & $14,2$ & $10,10$
  \end{game}
\end{center}
\begin{claim}
  In every Nash equilibrium of $G$ both players play $D$ in every
  period on the equilibrium path.
\end{claim}
\begin{proof}
  Let $s^*$ be a Nash equilibrium of the repeated game.  Assume by
  contradiction that, when playing $s^*$, some player $i$ plays $C$ on
  some period, and let $t_\ell$ be the last such period. 

  Let $s_i$ be the strategy for player $i$ that is identical to
  $s_i^*$ in all periods $t < t_\ell$, and under which, for periods
  $t \geq t_\ell$, player $i$ always plays $D$. We claim that $s_i$ is
  a profitable deviation: the stage utilities for $i$ in periods
  $t < t_\ell$ are the same under $s_i$ and $s_i^*$. In period
  $t_\ell$ the utility is strictly larger, since $D$ is a strictly
  dominant strategy. In periods $t > t_\ell$ both players played $D$
  under $s^*$ (by the definition of $t_\ell$), and so the utility
  for player $i$ under $s_i$ is either the same (if the other player
  still plays $D$) or greater than the utility under $s^*$ (if the
  other player now plays $C$ in some of the periods).
\end{proof}

Hence the payoff profile in every Nash equilibrium (subgame perfect or
not) is $(6,6)$. This is in stark contrast to the infinitely
repeated case.

This result can be extended to any game in which every equilibrium
achieves minmax payoff profiles. In contrast we consider games in
which there is a Nash equilibrium in which every player's payoff is
larger than her minmax payoff. In such games we again have a strong
folk theorem~\cite{benoit1985finitely}.

An example of such a game is the following:
\begin{center}
  \begin{game}{3}{3}
    & $D$     & $C$ & $F$ \\
    $D$   & $6,6$  & $14,2$ & $6,6$\\
    $C$ & $2,14$ & $10,10$ & $6,6$\\
     $F$ & $6,6$ & $6,6$ & $7, 7$ 
  \end{game}
\end{center}
In this game there is an equilibrium in which both players play
$(C,C)$ for all periods except the last four, in which both players
play $(F,F)$. If anyone deviates the other plays $D$ henceforth, thus
erasing any possible gains achieved by deviating.



\begin{theorem}
  \label{thm:finite-nash-folk}
  Assume that $G_0$ has a Nash equilibrium $a^*$ whose associated
  payoff profile $w^*$ satisfies $w^*_i > u^{mm}_i$. Let $a$ be an
  action profile in $G_0$ whose payoff profile $w$ is strictly
  enforceable. Then for any $\eps > 0$ and $T$ large enough there is a
  Nash equilibrium of $G$ with payoff profile $w'$ such that
  $|w_i-w'_i| < \eps$ for all $i$.
\end{theorem}

\begin{proof}
  Consider a strategy profile $s^*$ with the following modes:
  \begin{itemize}
  \item In on-path mode, players play $a$ in all periods except the last
    $\ell$ periods, in which they play $a^*$.
  \item In $i$-punishment mode the players play $b^i$ where
    \begin{align*}
      b_{-i}^i \in \argmin_{a_{-i}}\max_{a_i}u_i(a_{-i},a_i)
    \end{align*}
    and $b^i_i$ a best response to $b^i_{-i}$
  \end{itemize}
  The game starts in on-path mode, and switches to $i$-punishment mode
  for the rest of the game if $i$ deviates.

  Fix $T$. We will show that $s^*$ is an equilibrium for an
  appropriate choice of $\ell$, and assuming $T$ is large enough.
  Note that player $i$'s utility when no one deviates is
  \begin{align*}
    T \cdot v_i(s^*) = (T-\ell)w_i + \ell w^*_i.
  \end{align*}

  
  Assume by contradiction that player $i$ has a profitable deviation
  $s_i$, and let $t$ be the last time period in which she does not
  deviate. Clearly, $t$ cannot occur in the last $\ell$ periods, since
  in these the players play an equilibrium and thus there is no
  profitable deviation. Consider then the case that $t$ is not in the
  last $\ell$ periods. Then
  \begin{align*}
   T \cdot v_i(s^*_{-i},s_i) \leq t w_i+M+(T-\ell-t-1)u_i^{mm} + \ell u_i^{mm},
  \end{align*}
  where $M$ is the maximum she can earn at period $t$. In particular, since
  $u_i^{mm} < w_i$ we have that
  \begin{align*}
    T \cdot v_i(s^*_{-i},s_i) < (T-\ell - 1)w_i + M + \ell u_i^{mm}.
  \end{align*}
  Hence
  \begin{align*}
    T \cdot (u_i(s^*) - u_i(s^*_{-i},s_i)) =  w_i - M +\ell (w^*_i - u_i^{mm}).
  \end{align*}
  Therefore, if we choose
  \begin{align*}
    \ell > \frac{M-w_i}{w_i^*-u_i^{mm}},
  \end{align*}
  which is only possible if $T$ is at least this large, then this will
  not be a profitable deviation.

  Finally, the utility for playing $s^*$ can be written as
  \begin{align*}
    v_i(s^*) = w_i + \frac{\ell}{T}(w^*_i-w_i + \ell w^*_i),
  \end{align*}
  and so $|v_i(s^*)-w_i|<\eps$ for $T$ large enough.
\end{proof}



\subsubsection{Perfect Nash equilibria and folk theorems}
\begin{claim}
  In every subgame perfect Nash equilibrium of a finitely repeated
  game, the last action profile played after any history is a Nash
  equilibrium of the base game.
\end{claim}

\begin{exercise}
  Show that if the base game has a unique Nash equilibrium $a^*$ then
  the payoff profile of any subgame perfect equilibrium of the
  repeated game is the same as that of $a^*$.
\end{exercise}

When there are sufficiently many diverse equilibria of the base game
it is possible to prove a perfect folk theorem for the finite repeated
game.

\section{Social learning}

\subsection{Bayesian hypothesis testing}

Consider the following single agent Bayesian game. There is a {\em
  state of nature} $S = \{0,1\}$, which is initially picked with some
probability $p = \P{S=1}$. There is an experiment that the agent can
carry out repeatedly, and where each execution $i=1,\ldots,n$ results
in an observation $X_i$, which is picked from some finite set
$\Omega$. If $S=0$ then the $X_i$'s are distributed i.i.d.\ with some
distribution $\nu_0$. If $S=1$ then they are distributed i.i.d.\ with
distribution $\nu_1$. We say the the {\em private signals}
$\{X_i\}_{i=1}^n$ are {\em conditionally independent}.

A common example is $\Omega=\{H,T\}$, $\nu_0(H) = \nu_1(T)=0.6$ and
$\nu_1(H) = \nu_0(T)=0.4$.  We will assume (as in this example)
that $\nu_0$ and $\nu_1$ both given positive probability to every
$\omega \in \Omega$.

Now, after observing her $n$ signals the agent has to guess whether
the state of nature is $0$ or $1$. That is, she has to take an action
$a \in \{0,1\}$, and her utility is 1 if $a=S$ and zero
otherwise. Hence the agent's expected utility is equal to $\P{a=S}$.

It is easy to see that the only rational choices are to choose $a=1$
if $\CondP{S=1}{X_1,\ldots,X_n} \geq \half$, and to choose $a=0$ if
$\CondP{S=1}{X_1,\ldots,X_n} \leq \half$. We will assume for now 
that $p,\nu_0,\nu_1$ are chosen in such a way that we never have
equality (i.e., indifference), and so
\begin{align*}
  a = \argmax_{s \in \{0,1\}}\CondP{s=S}{X_1,\ldots,X_n}.
\end{align*}

Now,
\begin{align*}
  \P{a=S} = \CondP{a=1}{S=1}\cdot p + \CondP{a=0}{S=0}\cdot(1-p).
\end{align*}
Let us calculate $\CondP{a=1}{S=1}$. By the remarks above the event
$a=1$ is equal to the event $\CondP{S=1}{X_1,\ldots,X_n} > \half$. The
latter is equal to the event that
\begin{align*}
  \frac{\CondP{S=1}{X_1,\ldots,X_n}}{\CondP{S=0}{X_1,\ldots,X_n}} > 1.
\end{align*}
We can rewrite this as
\begin{align*}
  \frac{\CondP{X_1,\ldots,X_n}{S=1}}{\CondP{X_1,\ldots,X_n}{S=0}} \cdot \frac{p}{1-p}> 1.
\end{align*}
By conditional independence, this is the same as
\begin{align*}
  \sum_{i=1}^n\log\frac{\CondP{X_i}{S=1}}{\CondP{X_i}{S=0}}(X_i) +\ell_0 > 0.
\end{align*}
Let
\begin{align*}
  L_i = \log\frac{\nu_1(X_i)}{\nu_0(X_i)}
\end{align*}
be the {\em private log likelihood ratio} of signal $X_i$. Denote
$M_i = \sum_{k=1}^i L_k$. Then we have shown that $a=1$ iff
$\ell_0 +M_n >0$. To simplify calculations henceforth we assume that
$\ell_0=0$.

Note that, conditioned on $S=1$, the $L_i$'s are i.i.d.\ random
variables. Their expectation is
\begin{align*}
  \CondE{L_k}{S=1} = \sum_{\omega \in \Omega}\nu_1(\omega)\cdot\log\frac{\nu_1(\omega)}{\nu_0(\omega)}.
\end{align*}
This is also called the {\em Kullback-Leibler divergence} between
$\nu_1$ and $\nu_0$, and is a measure of how different the
distributions are. It is easy to show that this number is always
non-negative, and is zero iff $\nu_0=\nu_1$.

To estimate $\CondP{a=1}{S=1}$ we need to estimate the probability
that $M_n > 0$. To this end we will need a few definitions. First,
denote $L = L_1$, and let $\varphi \colon \R \to \R$ be given by
\begin{align*}
  \varphi(t) = -\log\CondE{e^{-t \cdot L}}{S=1}.
\end{align*}
Note that $\E{e^{-t \cdot L}}$ is called the {\em Laplace transform}
of $L$.
\begin{proposition}
  \begin{enumerate}
  \item $\varphi(0) = \varphi(1) = 0$.
  \item $\varphi$ is smooth and concave.
  \end{enumerate}
\end{proposition}
We will not prove this claim here. Note that it follows from it that
$\varphi$ is positive in the interval $(0,1)$.



Now, the probability of mistake (that is, the probability that $a=0$
conditioned on $S=1$) is, for any $t > 0$,
\begin{align*}
  \CondP{M_n <0}{S=1} &= \CondP{e^{-t \cdot M_n} > 1}{S=1}.
\end{align*}
Since $e^{-t\cdot M_n}$ is a positive random variable, we can apply Markov's
inequality and write
\begin{align*}
  \CondP{M_n <0}{S=1} \leq \CondE{e^{-t \cdot M_n}}{S=1}.
\end{align*}
Now, recall that $M_n = \sum_i L_i$, and that the $L_i$'s are
conditionally independent. Hence
\begin{align*}
  \CondP{M_n <0}{S=1}
  &\leq \CondE{e^{-t\sum_{i=1}^n L_i}}{S=1}\\
  &= \prod_{i=1}^n\CondE{e^{- t \cdot L_i}}{S=1}\\
  &= e^{-\varphi(t) \cdot n}.
\end{align*}
This holds for any $t > 0$, and so we have show that
\begin{theorem}
  \label{thm:cond-ind-error-prob}
  $\CondP{a \neq 1}{S=1} \leq \inf_{t > 0}e^{-\varphi(t) \cdot n}$.
\end{theorem}
Since $\varphi$ is positive in the interval $(0,1)$, it follows that
$\CondP{a \neq 1}{S=1}$ decreases (at least) exponentially with
$n$. It turns out (but will not be proven here) that this estimate is
asymptotically tight: if we denote $r = \sup_{t>0} \varphi(t)$, then
$\CondP{a \neq 1}{S=1} = e^{-r \cdot n +o(n)}$.

\subsection{Herd behavior}
The text of this section is largely taken
from~\cite{mossel2014opinion}.

Banerjee~\cite{Banerjee:92} and concurrently Bikhchandani, Hirshleifer
and Welch~\cite{BichHirshWelch:92}, consider the following model:
There is a binary state of the world $S \in \{0,1\}$, conditionally
i.i.d.\ private signals with conditional distributions $\nu_1$ and
$\nu_0$. There is an infinite sequence of
agents $N=\{1,2,\ldots\}$, each one with a single private signal
$X_i$. For simplicity, we consider the prior $\P{S=1}=\P{S=0}=1/2$.
We assume that $\nu_0$ and $\nu_1$ satisfy the {\em bounded likelihood
  ratio} assumption: that is, that there is some $M > 0$ such that,
with probability one,
\begin{align*}
  L_i = \log \frac{\dd \nu_1}{\dd \nu_0}(X_i)
\end{align*}
is in $(-M,M)$. This is satisfied, for example, when $\nu_0$ and
$\nu_1$ have the same finite support.


The agents act sequentially, with agent $i$ having to choose $a_i \in
\{0,1\}$ and receiving utility $u_i(a_i,S) = \ind{a_i=S}$. Each agent
$i$, in addition to her private signal, observes the actions of her
predecessors $\{1,2,\ldots,i-1\}$. Hence
\begin{align*}
  a_i = \argmax_{s \in \{0,1\}}\CondP{s=S}{a_1,\ldots,a_{i-1},X_i}.
\end{align*}
We assume that $a_i=1$ whenever the agent is indifferent.

By Theorem~\ref{thm:cond-ind-error-prob}, if agent $i$ had access to
the private signals of her predecessors then she should choose the
correct action, except with exponentially small probability. It turns
out that this is not exactly what happens here.

\begin{theorem}
  \label{thm:herding}
  The limit $\lim_i\P{a_i \neq S}$ exists and is strictly greater than
  zero.
\end{theorem}

To analyze this model it is useful to consider an outside observer $x$
who sees the agents' actions, but not their private signals. Thus the
information available to $x$ at round $i$ is
$\{a_1,a_2,\ldots,a_{i-1}\}$. We denote by
\begin{align*}
  B_x^i = \CondP{S=1}{a_1,\ldots,a_{i-1}}
\end{align*}
$x$'s belief at period $i$. It follows from L\'evy's zero-one law
(Theorem~\ref{thm:levy-zero-one}) that
\begin{align*}
  B_x^\infty := \CondP{S=1}{a_1,a_2,\ldots} = \lim_i B_x^i.
\end{align*}
We also define an action $a_x^i$ for $x$ at round $i$; this is given
by
\begin{align*}
  a_x^i = \argmax_{s \in \{0,1\}}\CondP{s=S}{a_1,\ldots,a_{i-1}},
\end{align*}
where, as with the actual players of the game, indifference results in
choosing $a_x^i=1$.

\begin{claim}
  $a_x^i = a_{i-1}$.
\end{claim}
That is, the outside observer simply copies the action of the last
agent she observes. The proof is simple, and follows from the fact
that at time $i$, agent $i-1$ has more information than $x$ does. It
follows that $\P{a_{i-1} = S} = \P{a_x^i =S}$, which will help us prove
Theorem~\ref{thm:herding}.

We define agent $i$'s log-likelihood ratio by
\begin{align*}
  L_i^a = \log \frac{\CondP{S=1}{a_1,\ldots,a_{i-1},X_i}}{\CondP{S=0}{a_1,\ldots,a_{i-1},X_i}}.
\end{align*}
As before, by Bayes' law we can write this as
\begin{align*}
  L_i^a = \log \frac{\CondP{a_1,\ldots,a_{i-1},X_i}{S=1}}{\CondP{a_1,\ldots,a_{i-1},X_i}{S=0}}.
\end{align*}
Now, the actions $a_1,\ldots,a_{i-1}$ are not conditionally independent. However,
they are conditionally independent of $X_i$, and so
\begin{align*}
  L_i^a = \log
  \frac{\CondP{a_1,\ldots,a_{i-1}}{S=1}}{\CondP{a_1,\ldots,a_{i-1}}{S=0}}
  + \log \frac{\CondP{X_i}{S=1}}{\CondP{X_i}{S=0}}.
\end{align*}
If we denote by
\begin{align*}
  L^i_x = \log \frac{B_x^i}{1-B_x^i} = \log
  \frac{\CondP{a_1,\ldots,a_{i-1}}{S=1}}{\CondP{a_1,\ldots,a_{i-1}}{S=0}}
\end{align*}
the outside observer's log-likelihood ratio then we have that
\begin{align}
  \label{eq:L-i-L-x}
  L_i^a = L^i_x + L_i.
\end{align}


We observe here without proof (although it is straightforward) that
there is a {\em continuous} function
$f \colon [0,1] \times \{0,1\} \to [0,1]$ such that for all rounds $i$
\begin{align}
  \label{eq:B-update}
  B_x^{i+1} = f(B_x^i,a_i).
\end{align}
That is, to update her belief the outside observer need only know the
new action she observes, and this calculation is the same in all
rounds. The key observation behind this is that
\begin{align*}
  B_x^{i+1} = \CondP{S=1}{a_1,\ldots,a_{i-1},a_i} = \CondP{S=1}{B_x^i,a_i} = f(B_x^i,a_i).
\end{align*}
That is, $B_x^i$ already includes all the $S$-relevant information
contained in $a_1,\ldots,a_{i-1}$, and so, given $B_x^i$, the history
before $a_i$ is irrelevant for making inferences regarding $S$.

\begin{theorem}
  The limit $\lim_i a_i$ exists almost surely.
\end{theorem}
\begin{proof}
  As we noted above, $a_i = a_x^{i+1}$, and so it suffices to show
  that $\lim_i a_x^i$ exists almost surely.

  Assume by contradiction that $a_x^i$ takes both values infinitely
  often. Hence $B_x^i$ is infinitely often above $1/2$, and infinitely
  often below $1/2$. It therefore converges to $1/2$.

  Taking the limit of~\eqref{eq:B-update}, it follows from the
  continuity of $f$ that $f(1/2,0) = f(1/2,1)=1$. But $B_x^0 = 1/2$,
  and so $B_x^i =1/2$ for all $i$. Hence $a_x^i=1$ for all $i$, and we
  have reached a contradiction.
\end{proof}

Since $\lim_i a_i$ exists almost surely we can define a random
variable $a = \lim_i a_i = \lim_i a_x^i$; this is the action that
almost all agents choose. To prove Theorem~\ref{thm:herding} it
remains to show that $\P{a=S} \neq 1$. An important observation is
that
\begin{align*}
  \CondP{a_i^x = S}{a_1,\ldots,a_{i-1}} = \max\{B_x^i,1-B_x^i\}.
\end{align*}
It therefore suffices to show that $\lim_i B_x^i$ is almost surely in
$(0,1)$.

Since the private signals have bounded log-likelihood ratios (say with
bound $M$), it follows from~\eqref{eq:L-i-L-x} that when $L_x^i > M$
then, with probability one, $L_i^a > 0$, and hence (again with
probability one) $a_i = 1$. Thus when $L_x^i > M$ it is not
informative to observe $a_i$; the outside observer already knew that
agent $i$ would choose $a_i=1$. Hence, in this case, $B_x^{i+1} =
B_x^i$. It follows that, with probability one, $L_x^i < 2M$, and thus
$B_x^i$ is bounded away from one. An identical argument shows that it
is bounded away from zero. This completes a sketch of the proof of
Theorem~\ref{thm:herding}.


\section{Better response dynamics and potential games}

\subsection{Better response dynamics}
Better response dynamics describe a mechanism by which a group of
players playing a game might find an equilibrium.

Formally, let $G = (N,\{S_i\},\{u_i\})$ be a strategic form game. A
{\em better response path} is a sequence of strategy profiles $s^k$
such that
\begin{enumerate}
\item Each $s^k = (s_1^k,\ldots,s_n^k)$ differs from its successor
  $s^{k+1}$ by exactly one coordinate.
\item If $s^k_i \neq s^{k+1}_i$ then $u_i(s^k) > u_i(s^{k+1})$. That
  is, $s_i'$ is a profitable deviation for $i$.
\end{enumerate}

\begin{exercise}
  Explain why in a game with no Nash equilibria every better response
  path $(s^1,s_2,\ldots,s^k)$ can be extended by some $s^{k+1}$ to a
  better response path $(s^1,s_2,\ldots,s^k)$. Conclude that such
  games have infinite better response paths.
\end{exercise}
\begin{exercise}
  Find a finite game in which there exists an infinite better response
  path, as well as a pure Nash equilibrium.
\end{exercise}
\begin{exercise}
  Explain why there are no infinite better response paths in
  prisoners' dilemma.
\end{exercise}

\begin{proposition}
  \label{prop:better-response}
  If a game has no infinite better response paths then it has a pure
  Nash equilibrium.
\end{proposition}
\begin{proof}
  Since there are no infinite response paths then there must be a path
  $(s^1,s_2,\ldots,s^k)$ that cannot be extended by any $s^{k+1}$ to a
  longer path. Thus in $s^k$ no player has a profitable deviation, and
  so $s^k$ is a pure Nash equilibrium.
\end{proof}

\subsection{A congestion game}
Let $G = (V,E)$ be a finite graph, where we think of each directed
edge $e=(v,w)$ as representing a road between cities $v$ and $w$. For
each edge $e=(v,w)$ let $c_e \colon \N \to \R^+$ be a monotone
increasing {\em congestion function}, where $c_e(k)$ is the travel
time when $k$ cars are on the road from $v$ to $w$.

Consider a finite set of players $N$. Each player $i$ has to travel
from some city $v_i$ to some other city $w_i$, and so has to choose a
path $s_i$ that connects $v_i$ to $w_i$. We assume that the chosen
paths are always {\em simple} (i.e., do not repeat edges) and so we
can think of $s_i$ simply as a subset of $E$.

Consider the game $G$ in which each player $i$'s set of strategies is
the set of all simple paths from $v_i$ to $w_i$. Given a strategy
profile $s = (s_1,\ldots,s_n)$ and an edge $e$, we denote by $n_e(s)$
the number of players who travel on $e$:
\begin{align*}
  n_e(s) = |\{i \in N \,:\, e \in s_i\}|.
\end{align*}
Hence the travel time on $e$ when the players choose $s$ is
$c_e(n_e(s))$. Player $i$'s utility is minus her travel time:
\begin{align*}
  u_i(s) = -\sum_{e \in s_i}c_e(n_e(s)).
\end{align*}

\begin{proposition}
  \label{prop:congestion}
  $G$ has a pure Nash equilibrium.
\end{proposition}
To prove this, let $S = \prod_i S_i$ denote the set of strategy
profiles, and define the function $\Phi \colon S \to \R$ by
\begin{align*}
  \Phi(S) = -\sum_{e \in E}\sum_{k=1}^{n_e(s)}c_e(k).
\end{align*}
Note that $\Phi$ is not the social welfare: that is equal to
$-\sum_e n_e(s)c_e(n_e(s))$.
\begin{claim}
  \label{clm:congestion}
  For every $s=(s_{-i},s_i) \in S$ and $s' = (s_{-i},s_i') \in S_i$ it holds that
  \begin{align*}
    u_i(s') - u_i(s) = \Phi(s') - \Phi(s).
  \end{align*}
\end{claim}
That is, the change in utility for player $i$ when switching from
$s_i$ to $s_i'$ is equal to the change in $\Phi$ that caused by this
switch. The proof of this claim is left as an exercise.

Note that the existence of this $\Phi$ implies that there is a pure NE
for this game, since any $s$ such that $\Phi(s)$ is maximal has to be
a NE, and $\Phi$ attains its maximum since it has finite
domain. Thus we have proved~\ref{prop:congestion}.

In fact, we can prove an even stronger statement:
\begin{claim}
  \label{clm:no-inf-path}
  $G$ has no infinite better response paths.
\end{claim}
\begin{proof}
  Assume by contradiction that $(s^1,s^2,\ldots)$ is an infinite
  better response path. Since the game is finite, there must be some
  $\eps > 0$ such that the improvement in utility for each deviating
  player in each $s^{k+1}$ is at least $\eps$. It then follows from
  Claim~\ref{clm:congestion} that $\Phi(s^{k+1})$ is at least
  $\Phi(s^1) + k \cdot \eps$, for every $k$. But $\Phi$ is bounded
  since it has finite domain, and so we have arrived at a
  contradiction.
\end{proof}

\subsection{Potential games}

Let $G = (N,\{S_i\},\{u_i\})$ be a strategic form game. We say
that $G$ is a potential game if there exists a $\Phi \colon S \to \R$
with the same property as in the example above: For every
$s=(s_{-i},s_i) \in S$ and $s' = (s_{-i},s_i') \in S_i$ it holds that
\begin{align*}
  u_i(s') - u_i(s) = \Phi(s') - \Phi(s).
\end{align*}

The proof of~\ref{clm:no-inf-path} applies to any finite potential game,
showing that they have no infinite better response paths. Thus better
response dynamics always converges to a pure Nash equilibrium for
finite potential games.

\subsection{The conformism game}

Let $G = (V,E)$ be a {\em social network graph}: the nodes are players
and $e = (i,j)$ is an edge if $i$ and $j$ are friends. We assume that
$(i,j) \in E$ iff $(j,i) \in E$, so that all friendships are
bidirectional.

Consider the following strategic form game. For all players the set of
strategies is $\{0,1\}$. A player's payoff is the number of her
neighbors who choose the same strategy:
\begin{align*}
  u_i(s_1,\ldots,s_n) = \sum_{j\,:\, (i,j) \in E}\ind{s_i=s_j}.
\end{align*}

\begin{exercise}
  Show that this is a potential game whenever the number of players is
  finite.
\end{exercise}

The same holds for the {\em hipsters game}, where the utility is
\begin{align*}
  u_i(s_1,\ldots,s_n) = \sum_{j\,:\, (i,j) \in E}\ind{s_i \neq s_j}.
\end{align*}

\begin{exercise}
  Find an infinite graph (but where each player has finitely many
  neighbors) in which this game has an infinite better response path.
\end{exercise}


\begin{exercise}
  Find an infinite connected graph (where each player has finitely
  many neighbors) for which, in this game, every infinite better response
  path includes each player only finitely many times. Find a graph for
  which this is not the case.
\end{exercise}


Given a graph $G=(V,E)$ and a vertex $v \in V$, let $f_v(r)$ equal the
number of vertices that are of distance exactly $r$ from $v$ in $G$.
\begin{theorem}
  If in $G = (V,E)$ there is a bound on the degrees, and if $f_v(r)$
  is sub-exponential, then there exists a $C \in \N$ such that, in any
  better response path, agent $v$ participates at most $C$ times.
\end{theorem}


\section{Social choice}

\subsection{Preferences and constitutions}

Consider a set of $n$ voters $N = \{1,\ldots,n\}$ who each have a
preference regarding $k$ alternatives $A$. A {\em preference}
\footnote{This is usually known in the literature as a strict
  preference.} or a {\em ranking} here is a bijection from $A$ to
$\{1,\ldots,k\}$, so that if some $a \in A$ is mapped to $1$ then it
is the least preferred alternative, and if it is mapped to $k$ then it
is the more preferred. We denote the set of all preferences $P_A$.

A {\em profile (of preferences)}
$\pi = (\pi_1,\ldots,\pi_n) \in P_A^n$ includes a preference for each
voter. A {\em constitution} is a map from $P_A^n$ to $P_A$, assigning
to each profile a preference called the {\em social preference}. Given
a constitution $\varphi \colon P_A^n \to P_A$ and a profile $\pi$ we
will sometimes write $\varphi_\pi$ instead of the usual
$\varphi(\pi)$.

A simple example of a constitution is a {\em dictatorship}: if we
define $d \colon P_A^n \to P_A$ by $d(\pi_1,\ldots,\pi_n) = \pi_1$
then $d$ is a constitution in which the preferences of voter 1 are
always adopted as the social preference.

When $k = 2$ (in which case we will denote $A=\{a,b\}$) and $n$ is
odd, a natural example of a constitution is {\em majority rule}
$m \colon P_A^n \to P_A$ given by
\begin{align*}
  m_\pi(a) =
  \begin{cases}
    1&\mbox{if } |\{i \,:\, \pi_i(a) < \pi_i(b)\}| > n/2\\
    2&\mbox{otherwise}
  \end{cases}
       \cdot
\end{align*}

Majority rule has a few desirable properties that we now define for
a general constitution.
\begin{itemize}
\item A constitution $\varphi$ satisfies {\em non-dictatorship} if it
  is not a dictatorship. It is a dictatorship if there exists an $i
  \in N$ such that $\varphi(pi) = \pi_i$ for all profiles $\pi$.
\item A constitution $\varphi$ is said to satisfy {\em unanimity} if,
  for any profile $\pi$ and pair $a,b \in A$ it holds that if
  $\pi_i(a) < \pi_i(b)$ for all $i \in N$ then
  $\varphi_\pi(a) < \varphi_\pi(b)$.
\item A constitution $\varphi$ is said to satisfy the {\em weak Pareto
    principle} (WPP) if for any profile $\pi$ such that
  $\pi_1=\pi_2=\cdots=\pi_n$ it holds that $\varphi(\pi) =
  \pi_1$. Clearly unanimity implies WPP, but not vice versa.
\item A constitution $\varphi$ is said to be {\em anonymous} if for
  any permutation $\eta \colon N \to N$ it holds that
  $\varphi(\pi_{\eta(1)},\ldots,\pi_{\eta(n)}) =
  \varphi(\pi_1,\ldots,\pi_n)$
  for every profile $\pi$. More generally, we say that a permutation
  $\eta$ is a {\em symmetry} of $\varphi$ if the above holds, and so
  $\varphi$ is anonymous if it has every permutation as a symmetry.
  We say that $\varphi$ is {\em egalitarian}\footnote{This is not
    a standard definition.} if for any two voters $i,j \in V$ there
  exists a symmetry $\eta$ of $\varphi$ such that $\eta(i) =
  j$. That is, $\varphi$ is egalitarian if its group of symmetries
  acts transitively on the set of voters.
\item A constitution $\varphi$ is said to be {\em neutral} if it is
  indifferent to a renaming of the alternatives: for any permutation
  $\zeta \colon A \to A$ it holds that
  $\varphi(\pi_1 \circ \zeta,\ldots,\pi_n \circ \zeta) = \varphi(\pi)
  \circ \zeta$.
\end{itemize}
It is easy to verify that majority rule has these properties.


\subsection{The Condorcet Paradox}
When there are three alternatives or more one could imagine
generalizing majority rule to a constitution $\varphi$ that satisfies
that $\varphi_\pi(a) < \varphi_\pi(b)$ for any $a,b \in A$ such
that $\pi_i(a) < \pi_i(b)$ for the majority of voters. The {\em
  Condorcet paradox} is the observation that this is
impossible~\cite{Condorcet:85}. To see this, consider three voters
with the following preferences:
\begin{align}
  \label{eq:condorcet}
  \pi_1(c) &< \pi_1(b) < \pi_1(a) \nonumber\\
  \pi_2(a) &< \pi_2(c) < \pi_2(b)\\
  \pi_3(b) &< \pi_3(a) < \pi_3(c).\nonumber
\end{align}
Here, two voters prefer $a$ to $b$, two prefer $b$ to $c$, and two
prefer $c$ to $a$. Thus it is impossible to rank the three
alternatives in a way that is consistent with the majority rule
applied to each pair.


\subsection{Arrow's Theorem}

Condorcet's paradox shows us that we cannot choose the relative
ranking of each pair using majority. Can we still choose the relative
ranking of each pair independently, using some other rule?

A constitution $\varphi$ is said to satisfy {\em independence of
  irrelevant alternatives} (IIA) if the relative ranking of $a$ and
$b$ in $\varphi(\pi)$ is determined by their relative rankings in
$\pi$.  Formally, given two alternatives $a,b \in A$ and profiles
$\pi,\pi'$ such that, for all $i \in N$,
\begin{align*}
  \pi_i(a) < \pi_i(b) \mbox{ iff }\pi'_i(a) < \pi'_i(b),
\end{align*}
it holds that
\begin{align*}
  \varphi_{\pi'}(a) < \varphi_{\pi'}(b) \mbox{ iff }
  \varphi_{\pi'}(a) < \varphi_{\pi'}(b). 
\end{align*}

Arrow's Theorem~\cite{Arrow50, Arrow63} shows that any constitution
for three or more alternatives that satisfies IIA is in some sense
trivial.
\begin{theorem}[Arrow's Theorem]
  Let $\varphi$ be a constitution for $|A| \geq 3$ alternatives and
  $|N| \geq 2$ voters. If $\varphi$ satisfies unanimity and IIA then
  $\varphi$ is a dictatorship.
\end{theorem}
In fact, the theorem still holds if we replace unanimity with WPP.


\subsection{The Gibbard-Satterthwaite Theorem}

As above, let $A$ be a set of alternatives and $N$ a set of voters. A
{\em social choice function} $f \colon P_A^n \to A$ chooses a
single alternative, given a preference profile.

We can associate with every social choice function $f$ and
preference profile $\pi$ a natural game $G_{f,\pi}$ played between
the voters. In this game the strategy space is the space of
preferences $P_A$, and voter $i$'s utility $u_i$ when the voters play
$(s_1,\ldots,s_n) \in P_A^n$ is $\pi_i(f(s))$. That is, a voter's
utility is the ranking of the chosen alternative.

We say that a social choice function is {\em strategy-proof} if for
any preference profile $\pi$, in the game $G_{f,\pi}$ it holds that
for every player $i$ the strategy $\pi_i$ is weakly dominant. That is,
$f$ is strategy proof if for every $\pi \in P_A^n$, $i \in N$ and
$\tau_i \in P_A$ it holds that
$\pi_i(f(\pi_{-i},\pi_i)) \geq \pi_i(f(\pi_{-i},\tau_i))$.
Informally, if $f$ is strategy proof then players always get the
best result by reporting their true preferences.

We say that a social choice function $f$ is a {\em dictatorship} if there
is some voter $i$ such that $f(\pi_1,\ldots,\pi_n) =
\argmax_a\pi_i(a)$ for every $\pi \in P_A^n$.

We say that a social choice function $f$ satisfies the {\em Pareto
  principle} if for all $a \in A$ it holds that $f(\pi) \neq a$
whenever there exists a $b \in A$ such that $\pi_i(a) < \pi_i(b)$ for
all $i \in N$.

\begin{claim}
  Let $|N|$ be odd and let $|A|=2$. Then majority rule is
  strategy-proof and satisfies the Pareto principle.
\end{claim}
The proof is left as an exercise to the reader.

In the next claim we define the {\em plurality} social choice function
and prove that it is not strategy proof, but satisfies Pareto
optimality.
\begin{claim}
  Let $|A|=3$, and let the social choice function
  $p \colon P_A^n \to A$ be given by $p(\pi) = a$ if $a$ was ranked
  the highest more times than any other alternative. If there is more
  than one alternative that is ranked highest the most times then
  whichever of the highest ranked alternatives that is
  lexicographically earlier is chosen. Then $f$ is not strategy proof
  and satisfies the Pareto principle.
\end{claim}
\begin{proof}
  We prove for the case that $N = \{1,2,3\}$; the proof for the
  general case is similar.
  
  Let $A = \{a,b,c\}$. Let $\pi_1(a) < \pi_1(b) < \pi_1(c)$,
  $\pi_2(a) < \pi_2(c) < \pi_2(b)$ and $\pi_3(b) < \pi_3(c) <
  \pi_3(a)$. Then $p(\pi) = b$, but $p(\pi_1,\pi_2,\tau_3) = c$, where
  $\tau_3(a) < \tau_3(b) < \tau_3(c)$. Since $\pi_3(b) < \pi_3(c)$ it
  follows that $p$ is not strategy proof.

  If $\pi_i(a) < \pi_i(b)$ for all $i$ then $a$ is ranked highest by
  no voter, and so $f(\pi) \neq a$. Thus $p$ satisfies the Pareto
  principle.
\end{proof}

The Gibbard-Satterthwaite Theorem~\cite{gibbard1973manipulation,
  satterthwaite1975strategy} states that any strategy-proof social
choice function for three or more alternatives is in some sense
trivial.
\begin{theorem}[Gibbard-Satterthwaite]
  \label{thm:gs}
  Let $|A| \geq 3$, and let $f \colon P_A^n \to P_A$ be a social
  choice function that satisfies the Pareto principle. Then if $f$ is
  strategy-proof then it is a dictatorship.
\end{theorem}
In fact, this theorem can be proved even if we replace the Pareto
principle with the condition that for every $a \in A$ there exists a
$\pi \in P_A^n$ such that $f(\pi)=a$.

\bibliographystyle{abbrv}
\bibliography{lectures}
\end{document}


\newpage
\subsection{Moral hazard}
Consider a game played between a {\em principal} and an {\em
  agent}.\footnote{We will refer to the principal using feminine
  pronouns and to the agent using male pronouns.}  The principal hires
the agent to work on a project. The agent has to choose whether to
accept the job, and how much effort $e$ to exert. For simplicity we
will assume that he either exerts effort ($e=1$) or does not
($e=0$). The cost of effort to the agent is $Ce$. For some constant
$C > 0$.

The project has state $\theta \in \{E,H\}$: it is either easy or
hard. The common prior belief is $p^0 = \P{\theta=E}=\P{\theta=H}$. The
project yields revenue $r$. If the agent exerts no
effort then $r=0$. If the agent exerts an effort
then $r = K > 0$ with probability $1 > \mu_E > \mu_H >
0$, depending on whether the project is easy or hard.

The principal observes the state of the project and the revenue, but
cannot observe the effort of the agent. The agent cannot observe the
state of the project until after she exerts the effort. The principal
offers to the agent a contract $W$, giving the agent a wage $w$ that
depends on the revenue $r$, and on the state of the project
$\theta$. Hence the wage is $w = w(\theta,r)$.

The sequence of events is as follows:
\begin{enumerate}
\item The state $\theta$ is revealed to the principal.
\item Principal offers a contract to the agent.
\item Agent accepts or rejects. If he rejects the game ends. Assume
  henceforth that he accepts.
\item Agent chooses whether to exert effort.
\item Revenue $r$ is revealed to the principal and agent.
\item The state $\theta$ is revealed to the agent.
\item The principal pays wage $w = w(\theta,r)$ to the agent.
\end{enumerate}
The principals utility is $u_r = r-w$. The agent's utility is $u_a =
w-Ce$.

We will assume that in both states the project is worth the effort:
\begin{align*}
  \mu_EK &\geq C\\
  \mu_HK &\geq C\\
\end{align*}

Given a contract $W$, the expected utility of the agent for exerting
an effort is
\begin{align*}
  p^0\left[\mu_Ew(E,K)+(1-\mu_E)w(E,0)\right]+
  (1-p^0)\left[\mu_Hw(H,K)+(1-\mu_H)w(H,0)\right] -c.
\end{align*}
The expected utility for not exerting an effort is
\begin{align*}
  p^0w(E,0)+(1-p^0)w(H,0).
\end{align*}
We say that the contract is {\em agent incentive compatible} if the
agent is incentivized to exert an effort, in that the latter
expression is not larger than the former. This simplifies to 
\begin{align*}
  p^0\mu_E\left[w(E,K)-w(E,0)\right]+
  (1-p^0)\mu_H\left[w(H,K)-w(H,0)\right] \geq
  c.
\end{align*}
The principal's expected utility, when the state is $\theta$, and
assuming the agent exerts an effort, is
\begin{align*}
  \mu_\theta\left[r-w(\theta,r)\right]-(1-\mu_\theta)w(\theta,0).
\end{align*}
We say that the contract is {\em principal incentive compatible} if
the principal is incentivized to offer this contract, regardless of
the state, and assuming the agent makes an effort. That is, if for
both $\theta=E$ and $\theta=H$ it holds that
\begin{align*}
  \mu_\theta\left[r-w(\theta,r)\right]-(1-\mu_\theta)w(\theta,0) \geq 0.
\end{align*}

We say that $W^*$ is Pareto optimal if any other contract $W$ is
worse for the principal in one of the two possible states.

Let $p^* = \frac{\mu_E-\mu_H}{2\mu_E-\mu_H}$.  Then the following
contract is agent incentive compatible, principal incentive
compatible and Pareto optimal whenever $p^0 < p^*$:
\vspace{0.2in}

\begin{tabular}{c|c|c}
  &$r=0$&$r=K$\\
  \hline
  $\theta=H$&0&$\frac{c}{\mu_H}$\\
  $\theta=E$&$c\frac{\mu_E-\mu_H}{\mu_E}$&$c\frac{\mu_E-\mu_H}{\mu_E}+\frac{c}{\mu_E}$
\end{tabular}

\vspace{0.2in}

In this case the expected utility of the principal is
$\mu_EK-c\frac{\mu_E-\mu_H}{\mu_E}-c$ when $\theta = E$, and
$\mu_HK-c$ when $\theta=H$. The agent's utilities in these cases are
$c\frac{\mu_E-\mu_H}{\mu_E}$ and $0$, respectively. Thus, when the
project is hard, the principal extracts all the revenue and the agent
gets nothing. When the project is easy they share the revenue.

When $p^0 > p^*$ then the following is Pareto optimal:

\vspace{0.2in}
\begin{tabular}{c|c|c}
  &$r=0$&$r=K$\\
  \hline
  $\theta=H,\theta=L$&0&$\frac{c}{p^0\mu_E+(1-p^0)\mu_H}$
\end{tabular}

\vspace{0.2in}

In this case the principal's expected utility in state $\theta$ in
$\mu_\theta K - \frac{c\mu_\theta}{p^0\mu_E+(1-p^0)\mu_H}$. The
agent's expected utility is zero, but he expects a positive about when
the project is easy and a negative amount when it is hard.


% \appendix

% \section{Conditional expectations as orthogonal projections}
% \label{app:projections}
% Let $(\Omega,\sigalg,\mathbb{P})$ be a finite probability
% space\footnote{All the results in this appendix apply to general
%   (separable) probability spaces, and indeed we will state our
%   claims in language that is sometimes too general for the finite
%   case. The proofs in the more general case are slightly more
%   technical, but use the same ideas.}.  Let $X \colon \Omega \to \R$
% denote a real random variable, and let $\underline{V} = \R^\Omega$
% be the set of all real random variables. We say that
% $X_1,X_2 \in \underline{V}$ are equivalent if $\P{X_1=X_2}=1$; that
% is, if the subset of $\Omega$ on which they agree has full
% measure\footnote{In the general (separable) case we will more
%   precisely require that they are equal on some full measure
%   set.}. Let $V$ be the set of equivalence classes of
% $\underline{V}$; this space is usually denoted
% $L^2(\Omega,\sigalg,\mathbb{P})$. Note that if each singleton
% $\{\omega\} \subset \Omega$ has positive probability then we can
% just take $V = \underline{V}$, and we encourage the uninitiated
% reader to take this point of view.

% As usual, we can define the sum of two random variables in the
% obvious way, and likewise define the product of a random variable by
% a real number. These operations extend naturally to operations on $V$.

% Under the above operations it is straightforward to show that $V$ is
% a vector space. We can furthermore equip $V$ with the $L^2$ norm
% given by $\|X\|^2 = \E{X^2}$.

% \begin{exercise}
%   Prove that $V$, as described above, is indeed a normed vector space.
% \end{exercise}

% We next claim that the expectation of a random variable $X$ is the
% single number that best approximates $X$, in the
% sense of expected distance squared.
% \begin{claim}
%   \begin{align*}
%     \E{X} = \argmin_{z \in \R}\E{(X-z)^2}.
%   \end{align*}
% \end{claim}
% \begin{proof}
%   Note first that
%   \begin{align*}
%     \E{(X-z)^2} = \E{X^2-2z \cdot X+ z^2} = \E{X^2}-2z \cdot \E{X}+z^2.
%   \end{align*}
%   Hence
%   \begin{align*}
%     \frac{\dd\E{(X-z)^2}}{\dd z}
%     &= \frac{\dd(\E{X^2}-2z \E{X}+z^2)}{\dd z}\\
%     &= -2\E{X} + 2z,
%   \end{align*}
%   and the unique extremal point is achieved at $z = \E{X}$. This is
%   a maximum since
%   \begin{align*}
%     \frac{\dd^2 \E{(X-z)^2}}{\dd z^2} = 2.
%   \end{align*}
% \end{proof}

% More generally, if $\sigalgp \subseteq \sigalg$ then
% $\CondE{X}{\sigalgp}$ is the best $\sigalgp$-measurable random variable
% that approximates $X$. Denote by $V_{\sigalgp}$ the set of
% $\sigalgp$-measurable random variables.
% \begin{claim}
%   \label{clm:ex-min-sqr}
%   \begin{align*}
%     \CondE{X}{\sigalgp} = \argmin_{Z \in V_{\sigalgp}}\E{(X-Z)^2}.
%   \end{align*}
% \end{claim}
% \begin{exercise}
%   Prove Claim~\ref{clm:ex-min-sqr}.
% \end{exercise}

% We next note that $V_\sigalgp$ is a vector subspace of $V$; this
% follows immediately from the definitions. We also note that
% $\E{(X-Z)^2}$, the expression that appears in
% Claim~\ref{clm:ex-min-sqr}, is simply $\|X-Z\|^2$. Hence
% $\CondE{X}{\sigalgp}$ is the vector in $V_\sigalgp$ that has minimum
% distance to $X$, and so $\CondE{\cdot}{\sigalgp} \colon V \to V_\sigalgp$ is
% simply the orthogonal projection operator to $V_\sigalgp$. This fact
% has many interesting consequences, since orthogonal projection
% operators have a very simple and rigid structure.
% \begin{claim}
%   \label{clm:orthogonal-projections}
%   Let $E \colon V \to V$ be an orthogonal projection
%   operator. Denote $K = \ker E$ and the range of $E$ be $M = E(V)$.
%   Then $V = K \oplus M$. That is, there is an orthogonal basis of
%   $K$, $(X_1,\ldots,X_k)$, and an orthogonal basis of $M$,
%   $(Y_1,\ldots,Y_m)$, such that $(X_1,\ldots,X_k,Y_1,\ldots,Y_m)$ is
%   an orthogonal basis of $V$.
  
%   Furthermore,
%   \begin{align*}
%     E(\alpha_1X_1+\cdots+\alpha_k X_k+\beta_1 Y_1+\cdots \beta_m
%     Y_m) = \beta_1 Y_1+\cdots \beta_m
%     Y_m. 
%   \end{align*}
%   It follows that $E^2=E$, and that if $E X \neq X$ then
%   $\|E X\| < \|X\|$.
% \end{claim}
% \begin{exercise}
%   Prove Claim~\ref{clm:orthogonal-projections}.
% \end{exercise}

% Using this Claim we can prove L\'evy's zero-one law. Before stating
% it we will introduce the term {\em filtration}: a filtration is a
% sequence of sub-sigma-algebras of $\sigalg$,
% $\{\sigalgp_n\}_{n \in \N}$, such that
% $\sigalgp_{n} \subseteq \sigalgp_{n+1}$ for all $n \in \N$.
% \begin{theorem}[L\'evy's Zero-One Law]
%   \label{thm:levy-zero-one}
%   Let $\{\sigalgp_n\}$ be a filtration, and let $X$ be a random
%   variable. Let $\sigalgp_\infty$ be the sigma-algebra generated by
%   $\cup_n \sigalgp_n$. Then $\lim_n \CondE{X}{\sigalgp_n}$ exists
%   for almost every $\omega \in \Omega$, and is equal to
%   $\CondE{X}{\sigalgp_\infty}$.
% \end{theorem}
% Note that this theorem is trivial for finite probability spaces,
% where there are only finitely many sub-sigma-algebras, and so every
% filtration must stabilize. The more general case can be proved using
% the orthogonal projection approach.


  % \begin{proof}
  %   Let $E_n \colon V \to V$ be the projection operator
  %   $\E{\cdot}{\sigalgp_n}$, denote $V_n = V_{\sigalgp_n}$, and denote
  %   $V_\infty = V_{\sigalgp_\infty}$. It is easy to show that
  %   $V_\infty = \cap_n V_n$.  Denote $K_n = \ker E_n$, so that
  %   $V = V_n \oplus K_n$, by
  %   Claim~\ref{clm:orthogonal-projections}. Note also each $V_{n+1}$
  %   is a subspace of $V_n$ and each $K_n$ is a subspace of $K_{n+1}$,
  %   since $\{\sigalgp_n\}$ is a filtration. Furthermore, if we denote
  %   $K_\infty = \cup_n K_n$ then $V = V_\infty \oplus K_\infty$.

  %   Let $X_\infty = \CondE{X}{\sigalgp_\infty}$ be the projection of
  %   $X$ to $V_\infty$, and let $(Y_1,Y_2,\ldots)$ be an orthogonal
  %   basis for $K_\infty$. In particular, we choose this basis by first
  %   writing down a basis for $K_1$, then adding more vectors to form a
  %   basis of $K_2$, etc. That is, for some sequence $\{m_n\}$ with
  %   $\lim_n m_n= \dim K_\infty = \dim V - \dim V_\infty$, each of the prefixes
  %   $(Y_1,Y_2,\ldots,Y_{m_n})$ is a basis for $K_n$.

  %   Since $V = V_\infty \oplus K_\infty$ we can write $X$ using this
  %   basis as
  %   \begin{align*}
  %     X = X_\infty + \sum_{k=1}^{\dim K_\infty} \alpha_k Y_k.
  %   \end{align*}
  %   Then for each $n$,
  %   \begin{align*}
  %     \CondE{X}{\sigalgp_n} = X_\infty + \sum_{k = m_n + 1}^{\dim K_\infty} \alpha_k Y_k.
  %   \end{align*}
  %   It follows that
  %   \begin{align*}
  %     \|\CondE{X}{\sigalgp_n} - X_\infty\|^2 = \sum_{k = m_n + 1}^{\dim K_\infty}\alpha_k^2.
  %   \end{align*}
  %   Since $\lim_n m_n = \dim K_\infty$ we have that
  %   \begin{align*}
  %     \lim_n\|\CondE{X}{\sigalgp_n} - X_\infty\|^2 =  0,
  %   \end{align*}
  %   and so
  %   \begin{align*}
  %     \lim_n \CondE{X}{\sigalgp_n} = X_\infty.
  %   \end{align*}
  % \end{proof}


  
  
  
  
  
  % \subsection{Samet's intrinsic criterion for common priors}
  % As in Section~\ref{sec:reaching-common-knowledge}, we suggest that
  % the reader becomes familiar with the content of
  % Appendix~\ref{app:projections} before proceeding.

  % Let
  % $(N,(\Omega,\sigalg), \{\mu_i\}_{i \in N},\{\sigalg_i\}_{i \in N})$
  % be a belief space. In the previous sections we made a common priors
  % assumption and derived strong results. However, in order to
  % calculate posterior beliefs, players do not need to know their
  % priors $\mu_i$; it suffices for them to know how to calculate the
  % conditional expectations $\CondE{\cdot}{\sigalg_i}$. Indeed, it is
  % easy to construct two different priors with identical conditional
  % expectation operators, and it seems that both would lead to
  % identical behavoir.

  % Note also that each sub-sigma-algebra $\sigalg_i$ can be
  % reconstructed from its corresponding operator.  Hence, for many
  % (indeed, most) applications, a more parsemonious representation of a
  % belief space is $(N,(\Omega,\sigalg),\{E_i\}_{i \in N})$, where each
  % $E_i$ is a conditional expectation operator
  % $\CondE{\cdot}{\sigalg_i}$ for some $\sigalg_i \subseteq \sigalg$,
  % and taken with respect to some $\mu_i$.

  % Samet~\cite{samet1998iterated} asked what the common priors
  % assumption means for the collection $\{E_i\}$: what intrinsic
  % property does having a common prior correspond to? He also provided
  % a compelling answer, which we present (partially) in two
  % claims. Before stating these claims we will need the following
  % definition: A sequence of players $(i_1,i_2,\ldots)$ in $N$ is
  % called an {\em I-sequence} if each player appears in it infinitely
  % often. Given an I-sequence, we will consider products of the form
  % \begin{align*}
  %   E_{i_t}E_{i_{t-1}}\cdots E_{i_2}E_{i_1}X
  % \end{align*}
  % for some random variable $X$. here $E_{i_1}X$ is player 1's
  % conditional expectation of $X$. $E_{i_2}E_{i_1}X$ is player 2's
  % conditional expectation of player 1's conditional expectations, etc.
  
  % \begin{theorem}[Samet, 1998]
  %   \label{thm:iterated-expectations}
  %   Let
  %   $(N,(\Omega,\sigalg), \{\mu_i\}_{i \in N},\{\sigalg_i\}_{i \in
  %     N})$
  %   be a belief space. Denote by $\{E_i\}_{i \in N}$ the corresponding
  %   conditional expectation operators. Then the following are
  %   equivalent:
  %   \begin{enumerate}
  %   \item There is a common prior $\mu = \mu_1 = \cdots = \mu_n$.
  %   \item There is a probability distribution $\mu$ on
  %     $(\Omega,\sigalg)$ such that for any I-sequence and any random
  %     variable $X$ with $\Esub{\mu}{X^2} < \infty$ it holds that
  %     \begin{align*}
  %       \lim_t E_{i_t}E_{i_{t-1}}\cdots E_{i_2}E_{i_1}X = \CondE{X}{\sigalg_C}
  %     \end{align*}
  %     in $L^2$, where $\CondE{\cdot}{\sigalg_C}$ is taken with respect
  %     to $\mu$.
  %   \end{enumerate}
  % \end{theorem}
  % Convergence in $L^2$ means that
  % \begin{align*}
  %   \lim_t \E{(E_{i_t}E_{i_{t-1}}\cdots E_{i_2}E_{i_1}X -
  %   \CondE{X}{\sigalg_C})^2} = 0.
  % \end{align*}

  % The proof that (1) implies (2) was discovered in various levels of
  % generality (and in a more abstract mathematical setting)
  % before Samet, in particular by von Neumann~\cite{von1950functional},
  % Halperin~\cite{halperin1962product} and
  % Bauschke~\cite{bauschke1995norm}, among others.

  % To understand this result, it is instructive to consider the case
  % that the common knowledge sigma-algebra $\sigalg_C$ is trivial. In
  % this case the Theorem states that iff there is a common prior, then
  % every appropriate iterated application of the conditional
  % expectation operators converges to taking expectation according to
  % this prior. Importantly, the latter condition does not depend on the
  % measures $\mu_i$.

  % We prove that (1) implies (2), and restrict our attention to the
  % case that $\sigalg_C$ is trivial; the general proof easily reduces
  % to this case. Since by (1) there is a common prior $\mu$, all the
  % conditional expectation operators are orthogonal projections on
  % $L^2(\Omega,\sigalg,\mu)$. Denote $V = L^2(\Omega,\sigalg,\mu)$,
  % and, given an $X \in V$, let $\|X\|^2 := \Esub{\mu}{X^2}$. Denote
  % $X_C = \CondE{X}{\sigalg_C}$, and denote
  % $X_t = E_{i_t}E_{i_{t-1}}\cdots E_{i_2}E_{i_1}X$. We prove the claim
  % by showing that
  % \begin{align*}
  %   \lim_t \|X'_t\| = 0,
  % \end{align*}
  % where $X'_t = X_t-X_C$.

  % Denote $V_i = L^2(\Omega,\sigalg_i,\mu) = E_i(V)$; this is the
  % subspace onto which $E_i$ projects $V$. Let $C = \cap_i V_i$. Then
  % it is easy to see that $C = L^2(\Omega,\sigalg_C,\mu)$, where
  % $\sigalg_C = \cap_i \sigalg_i$ is the common knowledge
  % sigma-algebra. Hence we can write each $V_i$ as the direct sum $V_i
  % = C \oplus V'_i$. We can accordingly write $E_i = F_C + F_i$,
  % where $F_C$ is the projection operator to $C$, and $F_i$ is the
  % projection operator to $V'_i$. Note that since $\cap_i V_i = C$ then
  % \begin{align*}
  %   C = \cap_i V_i = \cap_i \left(C \oplus V'_i\right) = C \oplus \cap_i V'_i,
  % \end{align*}
  % and so $\cap_i V'_i$ is trivial.  Note also that since $C$ and
  % $V'_i$ are orthogonal, $F_C F_i = 0$. It follows that
  % \begin{align*}
  %   E_{i_t}E_{i_{t-1}}\cdots E_{i_2}E_{i_1}
  %   &= (F_C + F_{i_t})(F_C+F_{i_{t-1}})\cdots
  %     (F_C+F_{i_2})(F_C+F_{i_1})\\
  %   &= F_C + F_{i_t}F_{i_{t-1}}\cdots F_{i_2}F_{i_1}.
  % \end{align*}
  % Since $X_C = F_C X$,
  % \begin{align*}
  %   X'_t = X_t-X_C = F_{i_t}F_{i_{t-1}}\cdots F_{i_2}F_{i_1}X.
  % \end{align*}


  
  % We will need the following standard claim:
  % \begin{claim}
  %   \label{clm:proj-lower-bnd}
  %   Let $F \colon V \to V$ be an orthogonal projection, and let
  %   $M = F(V)$.  Let $W$ be some closed subspace of $V$. Then either
  %   \begin{enumerate}
  %   \item $W \cap M$ is not trivial, or
  %   \item $W \cap M$ is not trivial, and there is an $\eps > 0$ such
  %     that for each non-zero $X \in W$ it holds that
  %     $\|F X\| < \eps \|X\|$.
  %   \end{enumerate}
  % \end{claim}
  % \begin{exercise}
  %   Prove this claim for the case that $V$ is finite.
  % \end{exercise}

  
  % % Denote $V_i = L^2(\Omega,\sigalg_i,\mu) = E_i(V)$, and given some
  % % $S \subset N$, denote $V_S = \cap_{i \in S}V_i$. Then
  % % $V_N = \cap_i V_i = L^2(\Omega,\sigalg_C,\mu)$.

  
  % Let $S_t = \{i \in N\,:\,X_t' \in V'_i\}$, and denote $W'_t = \cap_{i
  %   \in S_t} V'_i$.
  % Note that $V'_{i_t} \subset W'_t$ since $F_{i_t}$, the operator
  % applied at time $t$, has $V'_{i_t}$ as its range, and since
  % $X'_t = F_{i_t}X'_{t-1}$.
  
  % \begin{claim}
  %   There exists an $\eps >0$ with the following property: if
  %   $V'_{i_t} \not \subseteq W'_{t-1}$ then
  %   $\|X'_t\| < \eps \|X'_{t-1}\|$.
  % \end{claim}
  % \begin{proof}
  %   Noting that $X'_t = F_{i_t}X'_{t-1}$, and since there are only
  %   finitely many possible operators $F_{i_t}$ and spaces $W'_{t-1}$,
  %   this claim follows immediately from
  %   Claim~\ref{clm:proj-lower-bnd}.
  % \end{proof}
  % Thus, if there are infinitely many time periods in which
  % $V'_{i_t} \not \subseteq W'_{t-1}$ then $\lim_t \|X'_t\| = 0$, and
  % we are done. Otherwise, $V'_{i_t} \subseteq W'_{t-1}$ for all $t$
  % large enough. But then, for all $t$ large enough,
  % $X'_t \in W'_{t-1}$, and so $W'_t \supseteq W'_{t-1}$. Since there
  % are only finitely many possible values for $W'_t$, it follows that
  % $W'_t$ eventually stabilizes. But since $(i_1,i_2,\ldots)$ is an
  % I-sequence, and since, as we noted above, $V'_t \subseteq W'_t$, we
  % have that $W'_t$ includes all $V'_i$ for $t$ large enough. Hence
  % $X'_t$ is eventually in $\cap_i V'_i$. But the latter intersection
  % is trivial, and so $X'_t = 0$. We have thus shown that (1) implies
  % (2) in Theorem~\ref{thm:iterated-expectations}.
  
  
