%DOCUMENT CLASS
\documentclass{report}
%PACKAGES
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm} %Allows use of \begin & \end{proof]
\usepackage{bbding} %Allows pretty bullet symbols
\usepackage{bm} %Allows typing of bold math (use \boldsymbol)
\usepackage{color} %Allows colorful text
\usepackage[shortlabels]{enumitem} %Allows more enumerate options
\usepackage[margin=1in]{geometry} %Sets page margins to 1 in on all sides
\usepackage{mdframed} %Allows frames
\usepackage[medium]{titlesec} %Shrinks titles of chapters & sections
%HEADER & FOOTER SETTINGS
\usepackage{fancyhdr}
\pagestyle{fancy}
\fancyhf{}
\renewcommand{\chaptermark}[1]{\markboth{#1}{}}
\renewcommand{\footrulewidth}{0.4pt}% Default \footrulewidth is 0pt
\lhead{\textit{Sarah Robinson}}
\chead{\textit{210B}}
\rhead{\textit{\leftmark}}
\lfoot{Version 18}
\rfoot{Page \thepage}
%CUSTOM SETTINGS
\allowdisplaybreaks
\setlength{\parindent}{0pt} %Sets paragraph indent to 0pt
\renewcommand{\qedsymbol}{\rule{0.7em}{0.7em}} %Changes qED symbol to black box
\mdfsetup{linewidth=0.9pt} %Sets line width for mdframed
\newcommand{\FlowerSmall}{\mbox{\raisebox{-1pt}{\small\EightFlowerPetalRemoved}}} %Centers flower bullet
\DeclareMathOperator*{\argmax}{arg\,max\,} %Allows limits underneath
\titlespacing{\chapter}{0pt}{10pt}{10pt}
%BEGIN DOCUMENT
\begin{document}
%Rationalizability and Dominance
\chapter*{1. Rationalizability and Dominance}
\thispagestyle{fancy}
\chaptermark{1. Rationalizability and Dominance} \bigskip
%Defining a game
\section*{Defining a Game}\medskip
A \textbf{normal form (strategic) game} $\langle N,(A_i),(u_i) \rangle$ consists of:
\begin{itemize}
\item{A finite set of players $N$}
\item{For each player $i \in N$, a non-empty set of actions $A_i$}
\item{For each player $i \in N$, a utility function $u_i: \prod_{i=1}^N A_i \rightarrow \mathbb{R}$ \hspace{5pt} ($u_i: A \rightarrow \mathbb{R}$)}
\begin{itemize}
\item Represents preferences over outcomes; we assume $u_i(\cdot)$ captures all concerns
\item When there is uncertainty, we assume that players' preferences can be represented by an expected utility function ($u_i(\cdot)$ represents preferences over the set of lotteries on $\prod_{i=1}^N A_i$ and is a linear combination of the probability of an outcome times the utility of that outcome for sure)
\end{itemize}
\end{itemize} \bigskip
A \textbf{mixed strategy} for player $i$ is any $\sigma_i \in \Delta(A_i)$ (the set of probability distributions over $A_i$)
\begin{itemize}
\item{The set of mixed strategies includes pure strategies}
\item{A \textbf{completely mixed strategy} is one where every $a_i \in A_i$ has some positive probability}
\item{We assume that the players' mixed strategies are independent randomizations}
\end{itemize} \bigskip
A \textbf{belief} of player $i$, $\mu_i$, is a probability measure on $A_{-i}$ (the set of actions by the other players)
\begin{itemize}
\item A belief can be anything, including mixed strategies or correlated strategies between other players
\end{itemize} \bigskip
An action $a_i \in A_i$ is a \textbf{best response} to $\mu_i$ if there is no other action that yields a strictly higher payoff to player $i$ given his belief
\begin{itemize}
\item{There can be more than one best response to a given $\mu_i$}
\end{itemize}
\medskip
%Rationalizability
\section*{Rationalizability}\medskip
An action $a_i \in A_i$ is \textbf{rationalizable} in the strategic game $\langle N,(A_i),(u_i) \rangle$ if for each $j \in N$ there is a set $Z_j \subseteq A_j$ such that (i) $a_i \in Z_i$ and (ii) every action $a_j \in Z_j$ is a best response to a belief $\mu_j$ of player $j$ whose support is a subset of $Z_{-j}$
\begin{itemize}
\item{There can only be positive belief probability on action that are a best response for the other player (definition is self-referencing)}
\item{Given the set of actions that are rationalizable for you, what is rationalizable for me?}
\end{itemize} \medskip
%Dominance
\section*{Dominance}\medskip
An action $a_i \in A_i$ is \textbf{strictly dominated} in the strategic game $\langle N,(A_i),(u_i) \rangle$ if there exists a mixed strategy $\sigma_i$ such that $u_i(\sigma_i,a_{-i}) > u_i(a_i,a_{-i})$ for all $a_{-i} \in A_{-i}$
\begin{itemize}
\item{Some $\sigma_i$ gives strictly better payoffs than $a_i$ for every combination of other player actions}
\end{itemize} \bigskip
\textbf{Iterated Elimination of Strictly Dominated Strategies (IESDS)}
\begin{itemize}
\item{In stage 1, eliminate a strictly dominated pure strategy for a player. In stage 2, consider only the remaining pure strategies and eliminate again. Continue until there are no more remaining strictly dominated pure strategies. The order of elimination does not matter.}
\end{itemize}\bigskip
\textbf{Action \boldsymbol{$a_i$} survives IESDS $\hspace{5pt} \Leftrightarrow \hspace{5pt} \boldsymbol{a_i}$ is rationalizable}
\begin{itemize}
\item{For $N>2$ games, requires that beliefs can be anything, as defined above (including beliefs about correlated strategies between other players); if we restrict beliefs to exclude correlated beliefs, then the set of rationalizable actions is smaller and the relationship with IESDS doesn't hold}
\end{itemize}
\bigskip
An action $a_i \in A_i$ is \textbf{weakly dominated} in the strategic game $\langle N,(A_i),(u_i) \rangle$ if there exists a mixed strategy $\sigma_i$ such that $u_i(\sigma_i,a_{-i}) \geq u_i(a_i,a_{-i})$ for all $a_{-i} \in A_{-i}$ and $u_i(\sigma_i,a_{-i}) > u_i(a_i,a_{-i})$ for some $a_{-i} \in A_{-i}$
\begin{itemize}
\item{Some $\sigma_i$ gives at least the same payoffs than $a_i$, with better payoff in at least one circumstance}
\end{itemize}
\bigskip
A strategic game is \textbf{dominance solvable} if all players are indifferent between outcomes of the pure strategies that survive IEWDS
\begin{itemize}
\item{For IEWDS, \underline{all} weakly dominated pure strategies must be removed in a given stage (order matters)}
\item{Never use IEWSDS for anything other than dominance solvability}
\end{itemize}
\medskip
\begin{mdframed}
\medskip
\begin{center} \textbf{{\large Finding Rationalizable Actions}} \end{center}
\begin{itemize}[label=\FlowerSmall]
\item{Always use IESDS (remove strictly dominated actions of all players in any order)}
\item{Actions may be strictly dominated by mixed strategies}
\item{If an action is never a best response to another pure strategy, that can be a clue that it is strictly dominated (e.g., by a mixed strategy)}
\item{Do \underline{not} try to remove non-rationalizable actions (This would require considering an uncountably infinite number of beliefs. If a pure strategy is strictly dominated, it is worse for any other player action so it's also worse for any mixture.)}
\end{itemize}
\smallskip
\end{mdframed}
\newpage
\begin{mdframed}
\medskip
\begin{center} \textbf{{\large Showing a Game is Dominance Solvable}} \end{center}
\begin{itemize}[label=\FlowerSmall]
\item{Remove all weakly dominated actions of all players simultaneously before moving to the next stage (order matters!) -- if all players are indifferent at the end, the game is dominance solvable}
\end{itemize} \smallskip
\end{mdframed} \bigskip
%Extensive Form Games
\section*{Extensive Form Games}
\begin{itemize}
\item{Are drawn sequentially (as game trees)}
\item Map terminal histories to payoffs
\item{Include more information than normal form games (a normal form game can correspond to multiple extensive form games)}
\item{Include nodes associated with all player actions and with all game histories (including the null history)}
\item{Include information sets (the set of nodes that the acting player can tell the difference between)}
\begin{itemize}
\item{If a player can't distinguish between two or more of his nodes, they are connected with a dotted line or a circle around the nodes}
\item{Within an information set, the actions that the player can take must be identical (otherwise he could tell the difference)}
\end{itemize}
\item{Can include nodes assigned to ``chaos" with a probability measure over the set of possible outcomes}
\end{itemize}\bigskip
\bigskip
\begin{mdframed}
\medskip
\begin{center} \textbf{{\large Converting Extensive Form to Normal Form}} \end{center}
\begin{itemize}[label=\FlowerSmall]
\item{For each player, make a list of their information sets, including the associated history and their potential actions (list must incluce \underline{all} actions, even ones with only one possible choice)}
\item{Examples: $\emptyset: \{A,B\} \hspace{35pt} RrR:\{r,d\} \\ \hspace*{48pt} C/D:\{C,D\} \hspace{15pt}$ (where histories $C$ and $D$ are part of the same information set)}
\item{Create a list of pure strategies for each player -- each strategy will include an action for each listed information set \hspace{15pt} (Example: $S_1 = \{ RR,RD,DR,DD\}$)}
\item{The order of the list of information sets will determine the order of the elements of the strategies (move left to right then top to bottom through the game for consistency)}
\item{Create a normal form game with all pure strategies and their associated payoffs}
\end{itemize}
\smallskip
\end{mdframed}
\newpage
%Actions and Strategies
\section*{Actions $\neq$ Strategies}
Actions are observable (the action that a player actually took) \bigskip
\textbf{Normal Form Games:}
\begin{itemize}
\item Pure strategies = actions
\item $u_i$ maps the actions of all players to payoffs
\item Mixed strategies result in one action; players calculate their expected payoff given the set of actions that might happen
\item Written as tables with player actions on the axes, and the payoffs associated with each action profile in the boxes
\end{itemize} \bigskip
\textbf{Extenstive Form Games:}
\begin{itemize}
\item Pure strategies = an action at every information set
\item $u_i$ maps terminal histories to payoffs
\item When converting to normal form, treat pure strategies as ``actions"
\begin{itemize}
\item Pure strategies go on the axes of the table
\item Pure strategy profiles correspond to histories which are assocciated with payoffs
\end{itemize}
\item When considering best responses, rationalizable actions, strictly dominated actions, weakly dominated actions, etc., consider pure strategies (treat pure strategies as ``actions")
\end{itemize} \bigskip
%Notation
\section*{Notation}\medskip
\begin{tabular}{@{} l l}
$\prod_{i=1}^N A_i = A_1 \times A_2 \times \dots \times A_N$ \hspace{15pt} & Taking one element (one action) from each set\\[10pt]
$\{C, D\}$ & A set of actions (e.g., a player's pure strategies)\\[10pt]
$\{(x,y,z),(a,b,c)\}$ & A set of actions across players (e.g., the set of rationalizable actions)\\[10pt]
$(D, D)$ & A strategy profile (e.g., a Nash Equilibrium)\\[10pt]
$a_{-i}$ & An action by every player other than $i$\\[10pt]
$A_{-i}$ & The set of all combinations of actions by every player other than $i$\\[10pt]
$\sigma_i = (p \circ C, (1 - p) \circ D)$ & A mixed strategy for player $i$ for some $p \in (0,1)$
\end{tabular}
%Equilibrium
\chapter*{2. Equilibrium Concepts {\Large (Complete Information)}}
\thispagestyle{fancy}
\chaptermark{2. Equilibrium Concepts} \bigskip
%Nash Equilibrium
\section*{Nash Equilibrium (NE)}\medskip
Rationalizability is sufficient to predict $(D,D)$ in the Prisoner's Dilemma, because action $C$ is never rationalizable for either player. But it does not let us predict anything for Battle of the Sexes, because both actions are rationalizable. Nash equilibria are a subset of rationalizable action profiles, further assuming each player has correct beliefs about what the other players will do. In Battle of the Sexes, the miscoordinated profiles are not NE because taking the action of the other player as given, it is optimal for me to match. \bigskip
Strategy profile $\sigma^* = (\sigma_1^*,\dots,\sigma_N^*)$ is a \textbf{Nash equilibrium (NE)} in the strategic game $\langle N,(A_i),(u_i) \rangle$ if for all $i$, $\sigma_i^* \in \Delta(A_i)$ and $\sigma_i^*$ is a best response to the belief $\sigma_{-i}^*$
\begin{itemize}
\item{Every player is best responding taking the strategies of the other players as given (no player has any unilateral incentive to deviate)}
\item{Every player is playing a mixed strategy (assumed to be independent randomizations)}
\end{itemize} \bigskip
\textbf{Every strategic game $\boldsymbol{\langle N,(A_i),(u_i) \rangle}$ where all players have finitely many actions has a NE}\\ (may include mixed strategies for one or more players)
\begin{itemize}
\item{A strictly dominated strategy can never be a NE, so IESDS reduces the set under consideration}
\item In a finite strategic game, a mixed strategy is a NE if and only if for all $i$, every pure strategy in the support of $\sigma_i^*$ is a best response to $\sigma_{-i}^*$ (to mix, a player must be indifferent between the extremes)
\item More generally, every game in which each action set is a convex compact subset of a Euclidian space and each payoff function is continuous has a NE
\end{itemize}
\medskip
\begin{mdframed}
\medskip
\begin{center} \textbf{{\large Finding Nash Equilibria: Continuous Action Spaces}}\medskip \end{center}
\begin{itemize}[label=\FlowerSmall]
\item{Taking as given the action of the other player, calculate the best response function}
\item{A NE is any point where the best response functions intersect}
\item Player 1: $\displaystyle\max_{a_1} u_1(a_1,a_2)$ \hspace{5pt} take $\cfrac{\partial u_1}{\partial a_1} = 0$ \hspace{20pt}
Player 2: $\displaystyle\max_{a_2} u_2(a_1,a_2)$ \hspace{5pt} take $\cfrac{\partial u_2}{\partial a_2} = 0$\\[5pt]
Solve the system of equations for $a_1, a_2$
\item $B_1(a_2) = \displaystyle\argmax_{a_1} u_1(a_1,a_2)$ \hspace{20pt} (in NE, $B_1(a_2) = a_1$ and $B_2(a_1) = a_2$)
\item{Drawing a picture can be helpful}
\item{Best response functions can be piecewise (e.g., to prevent negative quantities in firm competition)}
\item{For best response correspondences, the set of NE is where the correspondences overlap}
\item{Best response functions can also be used for discrete action spaces, as a function of $p$ and $q$}
\end{itemize}
\smallskip
\end{mdframed}
\newpage
\begin{mdframed}
\medskip
\begin{center} \textbf{{\large Finding Nash Equilibria: Discrete Action Spaces}}\bigskip \end{center}
\textbf{Do IESDS to eliminate non-rationalizable actions from consideration}\\[10pt]
\textbf{Look for Pure NE}
\begin{itemize}[label=\FlowerSmall]
\item{For each player, for each combination of actions by other players, underline his best response (e.g., for player 1, underline the biggest number in each column)}
\item{Any strategy profile with all underlined payoffs is a pure strategy NE}
\end{itemize} \medskip
\textbf{Look for Mixed NE}
\begin{itemize}[label=\FlowerSmall]
\item{If there is more than one pure NE in a given row or column (a player has a choice between actions that all result in a NE), then any mix between those actions is also a NE}
\item{A player will only play a mixed strategy if he is indifferent to the actions being mixed}
\item{Player 1: Set $\mathbb{E}[X \mid q] = \mathbb{E}[Y \mid q]$ and solve for $q$ \hspace{10pt} (finds $q$ that lets P1 mix between $X$ and $Y$)}
\item{Setting the expected payoffs equal assumes that P1 is mixing between $X$ and $Y$ -- also need to look for cases where P1 plays a pure strategy and P2 mixes}
\end{itemize}\medskip
\textbf{Games with finite NEs \underline{usually} have an odd number (not always)} \\[10pt]
\textbf{Write down \underline{clear strategy profiles} e.g., $\boldsymbol{\sigma^* = (\sigma_1^*,\sigma_2^*)}$ (not the payoffs)}
\smallskip
\end{mdframed}
\bigskip
%SPNE
\section*{Subgame Perfect Nash Equilibrium (SPNE)}\medskip
Subgame perfect Nash equilibria are a subset of Nash equilibria for extensive form games. The Nash equilibrium concept sets no restrictions on player's strategies at information sets that are never reached on the equilibrium path (Nash equilibria can include non-credible threats). SPNE further assume that all players will play optimally at every information set of the game tree. \bigskip \bigskip
A \textbf{subgame} of an extensive game is a subset of the game such that:
\begin{itemize}
\item{The subgame starts at some $h$ that is the only history (node) in its information set}
\item{All histories that follow from $h$ are included in the subgame}
\item{If any history (node) that is part of an information set is part of the subgame, then all histories (nodes) of this information set are part of the subgame}
\end{itemize} \bigskip
Notes about subgames:
\begin{itemize}
\item{The number of subgames = the number of singleton information sets}
\item{The history leading to (above) the subgame can include only part of an information set (e.g., a Prisoner's Dilemma followed by a Coordination Game)}
\item{Proper subgames are subgames that are not the whole game itself}
\item{Maximal subgames are subgames that have no further proper subgames}
\end{itemize} \bigskip
A Nash equilibrium $\sigma^*$ is a \textbf{subgame perfect Nash equilibrium (SPNE)} in an extensive form game if it induces a Nash equilibrium in every subgame of this game \bigskip
\textbf{Every finite game has a SPNE} (may include mixed strategies for one or more players)
\bigskip
\begin{mdframed}
\medskip
\begin{center} \textbf{{\large Finding SPNE (Backward Induction)}} \end{center}
\begin{itemize}[label=\FlowerSmall]
\item{Pick a NE in each maximal subgame}
\item{Replace the subgame with the payoffs from the NE}
\item{Repeat with the reduced game until the whole tree has been replaced}
\item{When pure NE are being selected, use arrows along actions to denote the SPNE path}
\item{If there are multiple NE at any point, then the process should be repeated for each (players can choose any of the NE, can be useful for inducing desired behavior further up in the tree)}
\item{For continuous action spaces, create a list of the actions taken and consider the optimal actions working backwards}
\end{itemize}
\smallskip
\end{mdframed}
\bigskip
%THPE
\section*{Trembling Hand Perfect Equilibrium (THPE)} \medskip
Trembling hand perfect equilibria are a subset of Nash equilibria for normal form games. THPE further assumes that there is a possibility of slight mistakes in a player's beliefs about what the other players will do (the equilibrium strategy must be robust to mistakes). \bigskip \bigskip
A \textbf{trembling hand perfect equilibrium (THPE)} of a finite strategic game is a mixed strategy profile $\sigma^*$ with the property that there exists a sequence $\{\sigma^k\}_{k=0}^\infty$ of completely mixed strategy profiles that converges to $\sigma^*$ such that for each player $i$ the strategy $\sigma_i^*$ is a best response to $\sigma_{-i}^k$ for all values of $k$
\begin{itemize}
\item{To show that a player's strategy can be part of a THPE, there only needs to be one sequence that it is robust to (not robust to every sequence)}
\item{To show that a player's strategy cannot be part of a THPE, there must be an argument for why a sequence cannot be constructed}
\item{Completely mixed NE are automatically THPE, as the sequence can be repetition of the NE itself (the definition does not capture robustmess with respect to completely mixed strategy NE)}
\end{itemize} \bigskip
\textbf{2 Player Games:} \hspace{14pt} $\sigma^*$ is a NE in weakly undominated strategies $\hspace{5pt} \Leftrightarrow \hspace{5pt} \sigma^*$ is a THPE\\
\textbf{3+ Player Games:} \hspace{5pt} $\sigma^*$ is a THPE $\hspace{5pt} \Rightarrow \hspace{5pt} \sigma^*$ is a NE in weakly undominated strategies \bigskip \medskip
\textbf{Every finite strategic game has a THPE} (may include mixed strategies for one or more players)
\newpage
\begin{mdframed}
\medskip
\begin{center} \textbf{{\large Finding THPE: 2 Players}} \end{center}
\begin{itemize}[label=\FlowerSmall]
\item{Identify all of the NE of the game}
\item{Eliminate any NE where a player is using a weakly dominated strategy (do \underline{not} do iterated elimination of any actions when evaluating this)}
\end{itemize}
\smallskip
\end{mdframed}
\bigskip
\begin{mdframed}
\medskip
\begin{center} \textbf{{\large Showing \boldsymbol{$\sigma^*$} is (or is not) a THPE}} \end{center}
\begin{itemize}[label=\FlowerSmall]
\item{Confirm that $\sigma^*$ is a NE -- otherwise, it cannot be THPE}
\begin{itemize}
\item{If asked to identify all THPE, start by identifying all NE of the game}
\item{If $\sigma^*$ is the unique NE of the game, then it must be THPE}
\end{itemize}
\item{Confirm that no player is using a weakly dominated strategy -- otherwise, it cannot be THPE\\ (do \underline{not} do iterated elimination of any actions when evaluating this)}
\item{Check if all players are using completely mixed strategies -- if so, $\sigma^*$ is a THPE by definition}
\item{For each player, let sequence $p_i^k$ converge to $\sigma_i^*$ such that \underline{every} action has probability $\in (0,1)$ along the sequence}
\begin{itemize}
\item{Even strictly dominated strategies must have positive probability along the sequence}
\item{If player $i$ has more than two actions, then $p_i^k$ is a vector\\
Example: $(q_1^k, q_2^k, 1-q_1^k-q_2^k) \rightarrow (1,0,0)$}
\end{itemize}
\item{Identify the conditions under which $\sigma_i^*$ is a best response to $p_{-i}^k \hspace{5pt} \forall k$}\\
Example: $\mathbb{E}[\sigma_1^* \mid q^k] \geq \mathbb{E}[a_1 \neq \sigma_1 \mid q^k]$
\item{Construct a sequence for each player such that the condition is met for all players (or show that the condition is met for any sequence)}
\item{To prove that $\sigma$ is not THPE, assume that it is THPE towards a contradiction; implies there exists sequences meeting the criteria above; then show that for some player, $\sigma_i$ can never be a best response to the sequences}
\end{itemize}
\smallskip
\end{mdframed}
\newpage
%Epsilon Equilibrium
\section*{$\boldsymbol{\varepsilon}$-Equilibrium ($\boldsymbol{\varepsilon}$-E)}\medskip
The $\varepsilon$-equilibrium concept relaxes the assumption that all players are best responding (relaxes strict optimality). In an $\varepsilon$-E, one or more players can have a strictly positive but arbitrarily close to 0 incentive to deviate. $\varepsilon$-E is an expansion of NE in an attempt to better reflect behavior in actual games. \bigskip \smallskip
For any finite strategic game $\langle N,(A_i),(u_i) \rangle$, taking $\varepsilon$ as given, $\sigma^*$ is an \textbf{$\boldsymbol{\varepsilon}$-equilibrium ($\boldsymbol{\varepsilon}$-E)} if\\ $u_i(\sigma^*) \geq u_i(\sigma_i',\sigma_{-i}^*) - \varepsilon$ for all $\sigma_i' \in \Delta(A_i)$ and for all $i \in N$
\begin{itemize}
\item{Every player could get a maximum of $\varepsilon$ additional payoff by switching to any other strategy}
\item{For a big enough $\varepsilon$, any strategy profile could be $\varepsilon$-E ($\varepsilon$ is exogenous)}
\item{A NE is always an $\varepsilon$-E; an $\varepsilon$-E is only an NE if the definition holds for $\varepsilon = 0$}
\end{itemize}
\begin{mdframed}
\medskip
\begin{center} \textbf{{\large Showing $\boldsymbol{\sigma^*}$ is (or is not) an $\boldsymbol{\varepsilon}$-E}} \end{center}
\begin{itemize}[label=\FlowerSmall]
\item{For each player $i$, identify the best response to $\sigma_{-i}^*$ and the associated payoff}
\item{Identify the payoff associated with playing $\sigma_i^*$}
\item{Determine whether the best response payoff is within $\varepsilon$ of playing $\sigma_i^*$}
\end{itemize}
\smallskip
\end{mdframed}
\bigskip
%Correlated Equilibrium
\section*{Correlated Equilibrium (CE)}\medskip
We have assumed that players are using mixed strategies which are independent randomizations. The Correlated Equilibrium concept relaxes this assumption, allowing for players to jointly randomize over action profiles. For example, in Battle of the Sexes, the mixed strategy NE has each player independently randomizing, so with some probability the players will mismatch and both get 0. In a Correlated Equilibrium, the players could agree to play each NE 50\% of the time, with no probability of ever playing the 0 payoff strategy profiles. \bigskip \bigskip
A \textbf{correlated equilibrium (CE)} of a strategic game $\langle N,(A_i),(u_i) \rangle$ consists of:
\begin{itemize}
\item{A finite probability space with set of states $\Omega$ and probability measure $\pi$ on $\Omega$}
\item{For each player $i \in N$, a partition $\mathcal{P}_i$ of $\Omega$ (denotes which states the player can differentiate between)}
\item{For each player $i \in N$, a function $\sigma_i: \Omega \rightarrow A_i$, with $\sigma_i(\omega) = \sigma_i(\omega')$ whenever $\omega \in P_i$ and $\omega' \in P_i$ for some $P_i \in \mathcal{P}_i$ (player $i$'s strategy is the same for every state within a set in his partition)}
\end{itemize}
such that for every $i \in N$ and every function $\tau_i: \Omega \rightarrow A_i$ for which $\tau_i(\omega) = \tau_i(\omega')$ whenever $\omega \in P_i$ and $\omega' \in P_i$ for some $P_i \in \mathcal{P}_i$, we have $\displaystyle\sum_{\omega \in \Omega} \pi(\omega) u_i(\sigma_i(\omega), \sigma_{-i}(\omega))\geq \displaystyle\sum_{\omega \in \Omega} \pi(\omega) u_i(\tau_i(\omega), \sigma_{-i}(\omega))$\bigskip
Notes on CE:
\begin{itemize}
\item For each player, taking $\Omega, \pi(\omega)$, and $\mathcal{P}_i$ as given, he has no reason to deviate to another strategy for any set in his partition
\item Said another way, for every state $\omega \in \Omega$ that occurs with positive probability, the action $\sigma_i(\omega)$ is optimal given the other players' strategies and player $i$'s knowledge about $\omega$
\item We can think about $\Omega$ and $\pi$ as a public correlation device (e.g., a coin or a third party)
\item We can restrict the set of states to pure strategy profiles (every CE can be represented in this way)
\item CE can result in individual or aggregate payoffs that are not possible with NE (mixed strategies) alone
\end{itemize}
\bigskip
\textbf{For every mixed strategy NE $\boldsymbol{\sigma^*}$ of a finite strategic game $\boldsymbol{\langle N,(A_i),(u_i) \rangle}$, there is a correlated equilibrium $\boldsymbol{\langle (\Omega, \pi),(\mathcal{P}_i),(\sigma_i) \rangle}$ in which for each player $\boldsymbol{i \in N}$ the distribution on $\boldsymbol{A_i}$ induced by $\boldsymbol{\sigma_i}$ is $\boldsymbol{\sigma_i^*}$}
\bigskip
%CE Notation
\subsection*{\underline{CE Notation}} \bigskip
\begin{tabular}{@{} l l}
$\Omega = \{x, y, z\}$ & The set of states, each assigned to a pure strategy profile that is part of the CE\\[20pt]
$\pi(x), \pi(y), \pi(z)$ & The probability of each state happening\\[20pt]
$\mathcal{P}_i = \{ \{x\},\{y,z\}\}$ & For each player, a partition of the set of states\\[20pt]
$\sigma_i = \begin{cases}
T & \text{if $\{x\}$}\\
B & \text{if $\{y,z\}$}
\end{cases}$ \hspace{10pt} & For each player, for each element in his partition, an associated pure strategy\\
\end{tabular}
\newpage
\begin{mdframed}
\medskip
\begin{center} \textbf{{\large Constructing a CE with Given Payoffs}} \end{center} \bigskip
\textbf{Identify all pure NE of the game}\\[10pt]
\textbf{Look for a mixed NE with given payoffs}\\[10pt]
\textbf{Try to find a weighted average of pure NE}
\begin{itemize}[label=\FlowerSmall]
\item{Pick a set of pure NE to try weighting between}
\begin{itemize}
\item{Look first at weighting between 2 NE, then 3 NE}
\item{May need to try a few combinations before finding one that works}
\end{itemize}
\item{Assign each NE in the set an unknown probability and construct a system of equations}\\[5pt]
Example: NE $x$ with $p_x$, NE $y$ with $p_y$, NE $z$ with $p_z$\\[5pt]
$p_x \cdot u_1(x) + p_y \cdot u_1(y) + p_z \cdot u_1(z) = a$ \hspace{10pt} (Player 1 expected payoff)\\
$p_x \cdot u_2(x) + p_y \cdot u_2(y) + p_z \cdot u_2(z) = b$ \hspace{10pt} (Player 2 expected payoff)\\
$p_x + p_y + p_z = 1$ \hspace{101pt} (Probabilities must sum to 1) \smallskip
\item{Solve the system of equations (e.g., with row operations on an augmented matrix)}\\[5pt]
Example: $\left[ \begin{array}{@{} c c c | c @{}}
u_1(x) & u_1(y) & u_1(z) & a\\
u_2(x) & u_2(y) & u_2(z) & b\\
1 & 1 & 1 & 1
\end{array} \right]$\\[3pt]
\item{If there is a solution, then a CE has been found where each player's partition differentiates between all states; as the CE uses only pure NE, there is no need to check for incentives to deviate}
\end{itemize}
\bigskip
\textbf{If non-NE must be included:}
\begin{itemize}[label=\FlowerSmall]
\item{Pick a set of pure strategy profiles to try weighting between}
\item{In a CE with the given payoffs in expectation:}
\begin{itemize}
\item{The probabilities across pure strategy profiles will sum to 1}
\item{A player will always know what to play (each element in his partition will correspond to exactly one pure strategy)}
\item{A player will never know for certain that he is not playing an optimal response (his partition will hide that information)}
\item{For each player, for each element in his partition, there is no incentive to deviate from the CE strategy given that the other players follow the plan}
\end{itemize}
\item{When a player does not know the state for sure, it is as though he is facing a mixed strategy\\[5pt]
Example:\\[5pt]
If Player 1 is in $\{x\}$, he knows Player 2 will play $L$ and his best response is $B$ (NE state)\\[5pt]
If Player 1 is in $\{y,z\}$, then Player 2 is in $\{x,y\}$ and plays $L$ with probability $\cfrac{p_y}{1 - p_x}$\\
\hspace*{121pt} Player 2 is in $\{z\}$ and plays $R$ with probability $\cfrac{p_z}{1 - p_x}$\\[5pt]
If we want Player 1 to play T in the second case, then $\mathbb{E}[T \mid \{y,z\}] \geq \mathbb{E}[B \mid \{y,z\}]$
}
\end{itemize}
\smallskip
\end{mdframed}
%Evolutionary Stable Strategies
\section*{Evolutionary Stable Strategies (ESS)}\medskip
Evolutionary Stable Strategies are a refinement of NE to model situations in which the players' actions are determined by the forces of evolution. Consider a sequence of generations playing the same pairwise symmetric game. Strategies are inherited from the previous generation, with some small probability of mutations that lead to experimentation with other strategies. $u(\cdot)$ measures each organism's ability to survive, so strategies that lead to higher payoffs in the previous generation are used more often. Evolutionary Stable Strategies are what we expect to observe being used in the long run. \bigskip
Let $\langle \{1,2\},(A,A),(u_i) \rangle$ be a strategic game where $u_1(a,b) = u_2(b,a) \hspace{5pt} \forall a,b \in A$ (the game is symmetric). An \textbf{evolutionary stable strategy (ESS)} of the game is a mixed strategy $\sigma^*$ for which $(\sigma^*,\sigma^*)$ is a NE and $u(\sigma^*,\sigma) > u(\sigma,\sigma)$ for every best response $\sigma$ to $\sigma^*$ with $\sigma \neq \sigma^*$
\begin{itemize}
\item The intuition is to find strategies where no mutation would ever take hold in the population
\item Typically assumed to be a finite game
\item Every two-player symmetric strategic game in which each player has two pure strategies and the payoffs to the four strategy profiles are different has an ESS (other two-player symmetric games may not)
\end{itemize}
\bigskip
\begin{mdframed}
\medskip
\begin{center} \textbf{{\large Finding ESS}} \end{center}
\begin{itemize}[label=\FlowerSmall]
\item Find all symmetric NE of the game (pure and mixed)
\item For each NE $\sigma^*$, identify the best reponses to $\sigma^*$
\item If $\sigma^*$ is the \underline{only} best response to $\sigma^*$, then $\sigma^*$ is an ESS
\item Otherwise, for each best response $\sigma \neq \sigma^*$, confirm that $u(\sigma,\sigma)$ (mutant vs. mutant payoff) is \underline{strictly less} than $u(\sigma^*,\sigma)$ (non-mutant vs. mutant payoff)
\end{itemize}
\smallskip
\end{mdframed}
\bigskip
%Bayesian Games
\chapter*{3. Bayesian Games}
\thispagestyle{fancy}
\chaptermark{3. Bayesian Games} \bigskip
A game has \textbf{perfect information} if all information sets are singletons \bigskip
A game has \textbf{imperfect information} if at least one information set has multiple nodes \bigskip
A games has \textbf{incomplete information} if at least one player does not know the payoff that some player receives from some strategy profile (or terminal node) \bigskip
We have assumed until now that all players know each other's preferences over all strategy profiles (games of complete information). We want to expand to environments or situations where we are uncertain about the motives or incentives of the people we are acting (games of incomplete information). We transform these games into extensive games with complete but imperfect information. \bigskip \bigskip
A \textbf{Bayesian game} $\langle N,(A_i),(u_i),(\Theta_i),F \rangle$ consists of:
\begin{itemize}
\item{A finite set of players $N$}
\item{For each player $i \in N$, a non-empty set of actions $A_i$}
\item{For each player $i \in N$, a utility function $u_i: \prod_{i=1}^N A_i \times \prod_{i=1}^N \Theta_i \rightarrow \mathbb{R}$ \hspace{5pt} ($u_i: A \times \Theta \rightarrow \mathbb{R}$)}
\begin{itemize}
\item Utility is determined by the actions of every player and the types of every player
\item A player considers his payoffs as an expectation of the types he might face
\end{itemize}
\item For each player $i \in N$, a set of types $\Theta_i$
\begin{itemize}
\item At the beginning of the game, Nature chooses realizations of each random variable $\Theta_i$
\item Each player observes only his own type $\theta_i \in \Theta_i$ but not that of the others
\end{itemize}
\item Prior probability distribution over type profiles $F: \Theta \rightarrow [0,1]$
\begin{itemize}
\item $F$ is common knowledge
\item Typically we assume that the realization of each type is independent\\ (e.g., we consider $\pi_i(H) = \pi_i(L) = \frac{1}{2}$)
\end{itemize}
\end{itemize} \bigskip \bigskip
A \textbf{pure strategy for player $\boldsymbol{i}$ in a Bayesian game (pure decision rule)} is a mapping $s_i: \Theta_i \rightarrow A_i$ where $s_i(\theta_i) \in A_i$ is a pure strategy of the basic game chosen by type $\theta_i$
\begin{itemize}
\item The decision rule specifies what action a player will take for each of her possible type realizations
\item We can similarly consider mixed decision rules
\item Given a profile of decision rules for all players, player $i$'s expected utility is:\\ $\widetilde{u_i}(s_1,\dots,s_N) = \mathbb{E}[u_i(s_1(\theta_1),\dots,s_N(\theta_N), \theta_i, \theta_{-i}]$
\end{itemize} \bigskip \bigskip
A \textbf{Bayesian Nash equilibrium (BNE)} of the Bayesian game $\langle N,(A_i),(u_i),(\Theta_i),F \rangle$ is a profile of decision rules $(s_1,\dots,s_N)$ such that $\widetilde{u_i}(s_i,s_{-i}) \geq \widetilde{u_i}(s_i',s_{-i})$ for all $i$ and all $s_i':\Theta_i \rightarrow A_i$
\begin{itemize}
\item The expected utility for each player of following his decision rule is at least as great as any other decision rule, given the decision rules of all the other players
\end{itemize} \newpage
A profile of decision rules $s$ is a BNE if and only if, for all $i$, for all $\theta_i \in \Theta_i$ occuring with positive probability, and for all $\widetilde{s_i} \in A_i$: \hspace{10pt} $\mathbb{E}_{\theta_{-i}} [u_i(s_i(\theta_i), s_{-i}(\theta_{-i},\theta_i,\theta_{-i}) \mid \theta_i] \geq \mathbb{E}_{\theta_{-i}} [u_i(\widetilde{s}_i(\theta_i), s_{-i}(\theta_{-i},\theta_i,\theta_{-i}) \mid \theta_i]$
\begin{itemize}
\item We can find an optimal response for a player (to the decison rules of all the other players) one of his types at a time (treat each type as a separate player)
\end{itemize}
\bigskip \bigskip
\textbf{Every Bayesian game $\boldsymbol{\langle N,(A_i),(u_i),(\Theta_i),F \rangle}$ where all players have finitely many actions and finitely many types has a (possibly mixed) BNE}
\begin{itemize}
\item We will typically focus on pure, symmetric BNE
\end{itemize}
\bigskip
\bigskip
\begin{mdframed}
\medskip
\begin{center} \textbf{{\large Finding BNE: Discrete Types, Discrete Action Spaces}} \end{center}
\begin{itemize}[label=\FlowerSmall]
\item For each player, identify how many types he has - his strategy must include this many components
\item Consider all possible combinations of types facing each other and write out the potential games
\item For Player 1, construct a``short \& fat" table of expected payoffs for each type (pure strategies for P1 type vs. all possible P2 strategies)
\item Construct an overall table of expected payoffs for Player 1 (all possible P1 strategies vs. all possible P2 strategies)
\item For Player 2, construct a ``tall \& skinny" table of expected payoff for each type (all possible P1 strategies vs. pure strategies for P2 type)
\item Construct an overall table of expected payoffs for Player 2
\item Combine tables into normal form game and find the (pure or mixed) BNE
\item Example: $\pi_1(S) = p, \hspace{5pt} \pi_1(W) = 1-p, \hspace{5pt} \pi_2(S) = q, \hspace{5pt} \pi_2(W) = 1-q$\\[5pt]
Each player will have two components to his strategy, e.g., $A_S N_W$\\[5pt]
4 potential games: $(S,S), (S,W), (W,S), (W,W)$ \hspace{10pt} $(S,W)$ game considers $\{A_S, N_S\}$ vs. $\{A_W, N_W\}$ \\[15pt]
P1=S ``short \& fat" has $\{A_S, N_S \}$ vs. $\{A_S A_W, A_S N_W, N_S N_W, N_S N_W\}$ with payoffs weighted $q$\\[5pt]
P1 overall payoffs has $\{A_S A_W, A_S N_W, N_S N_W, N_S N_W\}$ vs. $\{A_S A_W, A_S N_W, N_S N_W, N_S N_W\}$, and is weighting P1=$S$ vs. P1=$W$ by $p$\\[15pt]
P2=S ``tall \& skinny" has $\{A_S A_W, A_S N_W, N_S N_W, N_S N_W\}$ vs. $\{A_S, N_S \}$ weighted by $p$\\[5pt]
P2 overall payoffs is weighting P2=$S$ vs. P2=$W$ by $q$
\end{itemize}
\smallskip
\end{mdframed}
\bigskip
\newpage
\begin{mdframed}
\medskip
\begin{center} \textbf{{\large Finding BNE: Discrete Types, Continuous Action Spaces}} \end{center}
\begin{itemize}[label=\FlowerSmall]
\item For each player, identify how many types he has - his strategy must include this many components
\item Calculate best response functions for each player type, given the decision rule of the other players and the probability distribution over their types
\item Example:\\
\begin{tabular}[t]{@{} l l l}
Player 1, Type H: & $\displaystyle\max_{a^H_1} u^H_1(a^H_1,a_2)$ & take $\cfrac{\partial u^H_1}{\partial a^H_1} = 0$\\[15pt]
Player 1, Type L: & $\displaystyle\max_{a^L_1} u^L_1(a^L_1,a_2)$ & take $\cfrac{\partial u^L_1}{\partial a^L_1} = 0$\\[15pt]
Player 2: & $\displaystyle\max_{a_2} u_2((\pi(H) a^H_1 + \pi(L) a^L_1),a_2)$ \hspace{10pt} & take $\cfrac{\partial u_2}{\partial a_2} = 0$\\[15pt]
\end{tabular}\\
Solve the system of equations for $a^H_1,a^L_2, a_2$
\end{itemize}
\smallskip
\end{mdframed}
\bigskip
\bigskip
\begin{mdframed}
\medskip
\begin{center} \textbf{{\large Finding BNE: Continuous Types}} \end{center}
\begin{itemize}[label=\FlowerSmall]
\item Find each player's best response function as a function of his type
\begin{itemize}
\item For discrete action spaces, this is a threshold (e.g., accept if $r(\theta) \leq w$, reject if $r(\theta) > w$)
\end{itemize}
\end{itemize}
\smallskip
\end{mdframed}
\bigskip
\newpage
\begin{mdframed}
\medskip
\begin{center} \textbf{{\large Finding BNE: Auctions\\ {\normalsize (Continuous Types, Continuous Action Spaces)}}} \end{center}
\begin{itemize}[label=\FlowerSmall]
\item Assume a strictly increasing, bidding function of a given form
\begin{itemize}
\item Typically linear: $b(s) = \alpha s + c$
\item Can also be quadratic (all-pay), log, etc.
\end{itemize}
\item There is a distribution of signals (e.g., $s_i \sim U[0,1]$)
\item Solve the problem from Player $i$'s perspective
\item $s(b) =$ the signal that induces Player $i$ to bid $b$
\item Assume \underline{opponents} are all using the same bidding function and define $\bar{s}(b) = $ the signal that induces opponents to bid $b$
\item Choose $b \mid s_i$ to maximize $P(\text{win} \mid b) \cdot \mathbb{E}[\text{payoff} \mid \text{win}] + P(\text{lose} \mid b) \cdot \mathbb{E}[\text{payoff} \mid \text{lose}]$
\item $F(\bar{s}(b))=$ the probability one opponent's signal is less than the signal that induces him to bid $b$
\begin{itemize}
\item For $s_i \sim U[0,1]$, $F(\bar{s}(b)) = \bar{s}(b)$
\end{itemize}
\item $\displaystyle\max_{b \mid s_i} = \left\{ F(\bar{s}(b))^{n-1} \cdot \mathbb{E}[\text{payoff} \mid \text{win}] + (1 - F(\bar{s}(b))^{n-1}) \cdot \mathbb{E}[\text{payoff} \mid \text{lose}] \right\}$
\item In all-pay, $\mathbb{E}[\text{payoff} \mid \text{lose}] = b$; otherwise it generally equals 0 so second term goes away
\item In private value, $\mathbb{E}[\text{payoff} \mid \text{win}] = s_i - b$
\item In common value, $\mathbb{E}[\text{payoff} \mid \text{win}] = \mathbb{E}[v \mid s_i, s(b) > s_j, \forall j \neq i] - b$
\begin{itemize}
\item $= \frac{1}{n} \sum s_j - b = \frac{1}{n} \left[ s_i + (n-1) \mathbb{E}[s_j \mid \bar{s}(b)] \right] - b = \frac{1}{n} \left[ s_i + (n-1) \frac{\bar{s}(b)}{2} \right] - b$
\item Because the bidding function is strictly increasing, my bid $>$ opponent bid is the same as my signal $>$ opponent signal
\end{itemize}
\item \underline{Take the derivative} w.r.t. $b$ of $\max$ equation and set = 0
\item \underline{Replace} $\bar{s}'(b)$ with derivative of bidding function form (e.g., linear, $\bar{s}'(b) = \frac{1}{\alpha}$)
\item \underline{Replace $\bar{s}(b) = s_i = s$} (now assume opponents and Player $i$ have the same bidding function)
\item Solve for $b$ as a function of $s$ and simplify
\end{itemize}
\smallskip
\end{mdframed}
\bigskip
\newpage
%Global Games
\section*{Global Games}\medskip
In a game where the underlying state of the world is common knowledge, there may be multiple NE. Even if there is a Pareto-dominant NE, our existing solution concepts do not let us predict how often this NE is played. Global games are games of incomplete information where players receive correlated signals of the underlying state of the world. We use global games to make predictions about what NE would be played as the range of signals goes to zero.
\begin{itemize}
\item Some variable $\theta \sim U[\underline{\theta}, \bar{\theta}]$ is observed with uniform noise on $[\theta - \varepsilon, \theta + \varepsilon]$; noise is iid across players
\item $x_i$ is the signal received by player $i$
\item Because of the uniform distribution, player $i$ knows that the true $\theta$ is distributed uniformly within $\varepsilon$ of his signal; $\theta \sim U[x_i - \varepsilon, x_i + \varepsilon]$ and $\mathbb{E}[\theta \mid x_i] = x_i$
\item $k$ is the threshold signal; we assume a symmetric strategy across all players, where one strategy is followed when $x_i \leq k$ and the other strategy is followed when $x_i > k$ ($k$ is generally a function of $\varepsilon$)
\item We focus on cases where $k$ is sufficiently close to the middle of $[\underline{\theta}, \bar{\theta}]$ and $\varepsilon$ is sufficiently small to not worry about weird edges of distributions
\item At $x_i = k$, $\mathbb{E}[u_i(C) \mid x_i]=\mathbb{E}[u_i(D) \mid x_i]$ (plug in $k$ for $x_i$ at the very end)
\item $\mathbb{E}[u_1(D) \mid x_1] = \displaystyle\int_{x_1 - \varepsilon}^{x_1 + \varepsilon} \left[ u_1(D,C) \cdot P(x_2 > k \mid \theta) + u_1(D,D) \cdot P(x_2 \leq k \mid \theta) \right] f(\theta) d\theta$
\begin{itemize}
\item The expected value to Player 1 integrated over possible values of $\theta$, assuming Player 2 also follows the threshold strategy
\item $P(x_2 \leq k \mid \theta) = \cfrac{k - \theta + \varepsilon}{2 \varepsilon}$
\item $f(\theta) = \cfrac{1}{2\varepsilon}$
\end{itemize}
\item Solve for $k$ as a function of $\varepsilon$ and find $\displaystyle\lim_{\varepsilon \rightarrow 0} k(\varepsilon)$
\item The converged $k$ gives our prediction of which NE will be played for different values of true $\theta$
\end{itemize}
\bigskip \bigskip
\bigskip \bigskip
%PBE and SE
\chapter*{4. Perfect Bayesian and Sequential Equilibria}
\thispagestyle{fancy}
\chaptermark{4. PBE \& SE} \bigskip
SPNE are a refinement of NE that assumes players will play optimally at every node of the game tree (sets restrictions on strategies at nodes off of the equilibrium path). In extensive form games with imperfect information, a similar issue can arise. In particular, a NE may include a non-optimal action at an information set that is never reached. In games of imperfect information, the structure of the game may limit the number of subgames (limiting the relevance of SPNE). \bigskip
Perfect Bayesian Equilibria and Sequential Equilibria set restrictions on how players act at information sets that are off of the equilibrium path. They do this by considering an equilibrium both a strategy profile and a belief system (NE implictly include beliefs that are always correct). \bigskip
Perfect Bayesian Equilibria and Sequential Equilibria each include:
\begin{itemize}
\item A strategy profile $\sigma$ that prescribes actions (or probability distributions over actions) at every\\ information set
\item A belief system $\mu$ that assigns beliefs (or probability distributions) over nodes at every information set
\begin{itemize}
\item When information sets are singletons, beliefs are trivial (the player believs he is at the node with probability 1); only write beliefs for information sets with multiple nodes
\item $\mu_1(a)$ is Player 1's belief that she is at node $a$ conditional upon reaching that information set
\end{itemize}
\end{itemize} \bigskip
%Perfect Bayesian Equilibria
\section*{Perfect Bayesian Equilibrium (PBE)}\medskip
PBE are a subset of NE or BNE (whichever applies), where off-path actions (or probability distributions over actions) are justified by some (any) belief. \bigskip
A strategy profile $\sigma$ is \textbf{sequentially rational} given beliefs $\mu$ if at every information set, given the beliefs prescribed by $\mu$, no individual wants to deviate from the piece of the strategy assigned to her there
\begin{itemize}
\item Taking beliefs as given, individuals are best-responding at every information set
\end{itemize} \bigskip
$(\sigma,\mu)$ is a \textbf{perfect Bayesian equilibrium (PBE)} if $\sigma$ is sequentially rational given $\mu$ and each agent updates beliefs $\mu$ using Bayes' Rule whenever it applies (i.e., at every information set on the equilibrium path)
\begin{itemize}
\item On-path, beliefs must be updated with Bayes' Rule (equivalent to correct beliefs)
\item Off-path, beliefs can be anything
\end{itemize}
\newpage
\begin{mdframed}
\medskip
\begin{center} \textbf{{\large Finding PBE}} \end{center}
\begin{itemize}[label=\FlowerSmall]
\item Identify all NE or BNE
\item For each NE or BNE $\sigma$, check all on-path and off-path information sets:
\item On-Path:
\begin{itemize}
\item For each multi-node information set, specify the associated \textbf{belief} using Bayes' Rule (equivalent to correct beliefs)
\item Since $\sigma$ is a NE or BNE, we know that it is optimal on-path given correct beliefs
\item Otherwise, must also check that $\sigma$ is optimal \underline{for all players} on-path given correct beliefs
\end{itemize}
\item Off-Path:
\begin{itemize}
\item For each information set, find \underline{any} associated \textbf{belief} such that $\sigma$ is \textbf{optimal}
\item For singleton information sets, beliefs are trivial -- but optimality must still be checked!
\end{itemize}
\item Write down the strategy $\sigma$ \underline{and} the belief sysem $\mu$ that support the PBE\\ (alternatively, the range of beliefs that support $\sigma$ as part of a PBE)
\end{itemize}
\smallskip
\end{mdframed}
\bigskip
%Sequential Equilibria
\section*{Sequential Equilibria (SE)}\medskip
SE are a subset of PBE, where off-path actions (or probability distributions over actions) are justified by consistent (``reasonable") beliefs. They are also a subset of SPNE. \bigskip
\bigskip
A system of beliefs $\mu$ is \textbf{consistent} with strategy profile $\sigma$ if there exists a sequence $(\sigma^m,\mu^m)$ of strategy profiles and beliefs such that:
\begin{enumerate}[(i)]
\item $(\sigma^m,\mu^m) \rightarrow (\sigma,\mu)$ as $m\rightarrow \infty$
\item $\sigma^m$ is completely mixed for every $m$ (assigns strictly positive probability to every action at every information set)
\item For each $m$, $\mu^m$ is derived from $\sigma^m$ by applying Bayes' Rule to every information set
\end{enumerate} \bigskip
$(\sigma,\mu)$ is a \textbf{sequential equilibrium (SE)} if $\sigma$ is sequentially rational given $\mu$ and $\mu$ is consistent given $\sigma$
\begin{itemize}
\item On-path, beliefs must be updated with Bayes' Rule (equivalent to correct beliefs)
\item Off-path, beliefs must be ``reasonable" ($\mu^m \rightarrow \mu$ where $\mu^m$ is updated with Bayes' Rule)
\item $\sigma^m$ does \underline{not} need to be best-responding to $\mu^m$ along the sequence (different from THPE)
\end{itemize} \bigskip \bigskip
\textbf{Every finite extensive form game with imperfect information has a (possibly mixed) SE}
\newpage
\begin{mdframed}
\medskip
\begin{center} \textbf{{\large Finding SE}} \end{center}
\begin{itemize}[label=\FlowerSmall]
\item Identify all PBE or SPNE (use SPNE if there are proper subgames)
\item For each PBE or SPNE $\sigma$, check whether every information set is reached with positive probability (if so, then $\sigma$ is an SE)
\item Otherwise, check all off-path information sets
\begin{itemize}
\item Intuitively, the belief must reflect that if an off-path information set is reached, it is more likely that one mistake was made rather than two
\item No need to verify sequences if not explicitly asked for and are sure that $(\sigma,\mu)$ is a SE
\end{itemize}
\item Write a completely mixed $\sigma^m$ that converges to $\sigma$
\begin{itemize}
\item Focus on information sets before the information set in question
\item Write $\sigma^m$ using $\varepsilon^m \rightarrow 0$, etc.
\item For more actions, try $\sigma^m_1 = ((1 - \varepsilon^m - (\varepsilon^m)^2) \circ a, \ \varepsilon^m \circ b, \ (\varepsilon^m)^2 \circ c)$
\end{itemize}
\item Derive $\mu^m$ for the information set using Bayes' Rule
\begin{itemize}
\item $\mu_i^m(a) = \cfrac{\text{Probability Player $i$ is at node $a$}}{\text{Probability at node $a$ + Probability at other nodes in the information set}}$\\[5pt]
\end{itemize}
\item Try to find $\displaystyle\lim_{m \rightarrow \infty} \mu^m = \mu$
\item If $\mu$ equals some number $[0,1]$ for all sequences $\varepsilon^m$, then check that $\sigma$ is optimal given $\mu$
\item If $\mu$ is ambiguous (depends on the exact sequences), then construct any sequences such that $\mu^m \rightarrow \mu$ that makes $\sigma$ optimal
\begin{itemize}
\item There is no information on which the player in question can update (e.g., they don't know which player made a mistake, or given that a mistake happened they don't know which other action was taken)
\item $\mu^m$ can converge anywhere in $[0,1]$
\item Identify the range of $\mu$ such that $\sigma$ is optimal and converge there (only need one sequence to show $\sigma$ is part of an SE)
\item $e^m = \frac{1}{m}$ is a good place to start
\end{itemize}
\item Write down the strategy $\sigma$ \underline{and} the belief system $\mu$ that support the SE \\ (alternatively, the range of beliefs that support $\sigma$ as part of a SE)
\begin{itemize}
\item Include on-path beliefs as well as these are technically part of the SE
\end{itemize}
\item Example for Player 2's information set: $\sigma$ = $(AD,X)$ where $A$ ends the game\\[10pt] $\sigma_1^m = (((1 - \varepsilon^m) \circ A, \varepsilon^m \circ B),(\gamma^m \circ C, (1 - \gamma^m) \circ D))$\\[5pt]
$\mu_2^m(C) = P( \text{at $C$} \mid \text{P2's information set is reached} ) = \cfrac{\varepsilon^m \cdot \gamma^m}{\varepsilon^m \cdot \gamma^m + \varepsilon^m(1 - \gamma^m)} = \cfrac{\varepsilon^m \cdot \gamma^m}{\varepsilon} = \gamma^m$\\[10pt]
$\mu_2^m(C) \rightarrow 0 = \mu_2(C)$\\[10pt]
In order for $\sigma$ to be an SE, $X$ must be optimal given $\mu_2(C) = 0$
\end{itemize}
\smallskip
\end{mdframed}
\bigskip
%Signaling
\section*{Signaling Games}\medskip
Signaling games are a subset of extensive form games with imperfect information where PBEs are used. Player 1 knows his type and uses his action to send a signal that Player 2 observes and can act on.
\begin{itemize}
\item \textbf{Stage 0:} Nature chooses types $\theta \in \Theta$ of player 1 from distribution $p$
\item \textbf{Stage 1:} Player 1 observes $\theta$ and chooses $a_1 \in A_1$
\item \textbf{Stage 2:} Player 2 observes $a_1$ and chooses $a_2 \in A_2$
\item \textbf{Payoffs:} $u_1(a_1,a_2,\theta), u_2(a_1,a_2,\theta)$
\end{itemize} \bigskip \bigskip
A \textbf{PBE in a signaling game} is a strategy profile $s_1(\theta), s_2(a_1),$ and beliefs $\mu_2(\theta \mid a_1)$ such that:
\begin{enumerate}[(i)]
\item \textbf{Player 1's strategy is optimal given Player 2's strategy}\\[5pt]
For all $\theta \in \Theta, s_1(\theta)$ solves $\displaystyle\max_{a_1 \in A_1} u_1(a_1,s_2(a_1),\theta)$ \hspace{20pt}
\item \textbf{Player 2's beliefs are compatible with Bayes' Rule}\\[5pt]
If any type of Player 1 plays $a_1$ with positive probability, $\mu_2(\theta \mid a_1) = \cfrac{P(s_1(\theta) = a_1) p(\theta)}{\displaystyle\sum_{\theta' \in \Theta} P(s_1(\theta')=a_1)p(\theta')}$
\item \textbf{Player 2's strategy is optimal given his beliefs and given Player 1's action}\\[5pt]
For all $a_1 \in A_2, s_2(a_1)$ solves $\displaystyle\max_{a_2 \in A_2} \displaystyle\sum_{\theta \in \Theta} u_2(a_1,a_2,\theta) \mu_2(\theta \mid a_1)$
\end{enumerate} \bigskip \bigskip
PBE in signaling games fall into three categories:
\begin{enumerate}[1]
\item \textbf{Separating:} Each type of Player 1 uses a different strategy. Hence, by observing $a_1$, Player 2 can always back out $\theta$
\item \textbf{Pooling:} All types of Player 1 use the same strategy. Hence, from observing $a_1$, Player 2 cannot infer anything about $\theta$
\item \textbf{Semi-Separating:} Some types of Player 1 use the same strategy, while some types use different strategies. Hence there is some, but not perfect, learning about $\theta$ from $a_1$
\end{enumerate} \bigskip
We typically do not worry about SE in signaling games. Either every information set is reached with positive probability (separating and semi-separating), or there is no information on which to update and beliefs can be anything (Player 2 doesn't know which type of Player 1 made a mistake) \bigskip
\newpage
\begin{mdframed}
\medskip
\begin{center} \textbf{{\large Signaling PBE: Discrete Action Spaces}} \end{center}
\bigskip
\textbf{Separating PBE:}
\begin{itemize}[label=\FlowerSmall]
\item Each type picks a different strategy
\item Assuming the number of types matches the number of strategies, every information set is reached with positive probability so beliefs must be correct
\item Check that no Player 1 given type and no Player 2 given signal has an incentive to deviate
\end{itemize}
\textbf{Pooling PBE:}
\begin{itemize}[label=\FlowerSmall]
\item All types pick the same strategy
\item Try pooling on one strategy first, then another, etc.
\item Beliefs at Player 2's on-path information set must reflect the underlying distribution of types
\item Check that given on-path beliefs, Player 2 is best responding
\item Choose Player 2's off-path strategy such that Player 1 does not have an incentive to deviate
\item Construct \underline{any} belief for Player 2's off-path information set such that his off-path strategy is optimal
\end{itemize}
\textbf{Semi-Separating:}
\begin{itemize}[label=\FlowerSmall]
\item At least one type is mixing between strategies and at least one type is not mixing
\end{itemize}
\textbf{Write down $\boldsymbol{\sigma}$ \underline{and} $\boldsymbol{\mu}$}
\smallskip
\end{mdframed}
\bigskip
\newpage
\begin{mdframed}
\medskip
\begin{center} \textbf{{\large Signaling PBE: Continuous Action Spaces}} \end{center}
\bigskip
Player 2 has some belief function $\mu(a_1) \in [0,1]$\\[5pt]
Player 2 has some action function $\mu \rightarrow A_2$\\[5pt]
\textbf{Separating PBE:}
\begin{itemize}[label=\FlowerSmall]
\item $\mu_Y(a_{1X}) = 0$ and $\mu_Y(a_{1Y})=1$ (for some types $X$ and $Y$), and Player 2 will map these beliefs into distinct actions $a_{2X}$ and $a_{2Y}$
\item Given $a_{2X}$ and $a_{2Y}$, each type of Player 1 will choose $a_1$
\begin{itemize}
\item For the Player 1 ``low type", the worst belief Player 2 can have is already occuring (beliefs can't be used to incent the PBE); this type must be optimizing given they are perfectly identified
\item $u_X(a_{1X}) \geq u_X(a_{1Y})$ (type $X$ must not deviate to type $Y$)
\item $u_Y(a_{1Y}) \geq u_Y(a_{1X})$ (type $Y$ must not deviate to type $X$)
\end{itemize}
\item Off-path, Player 2's beliefs (and thus actions) must be such that no type of Player 1 has an incentive to deviate to any $a_1 \notin \{ a_{1X},a_{1Y} \}$ (this can be ``low" belief / action for everything off-path or more general)
\end{itemize}
\textbf{Pooling PBE:}
\begin{itemize}[label=\FlowerSmall]
\item $a_{1X} = a_{2X} = a_1^*$
\item $\mu(a_1^*)$ must be equal to the prior distribution of types, and Player 2 maps this belief into $a_2^*$
\item Off-path, Player 2's beliefs (and thus actions) must be such that no type of Player 1 has an incentive to deviate to any $a_1 \neq a_1^*$ (this can be ``low belief / action for everything off-path or more general)
\item To check for deviations, identify the most advantageous deviation and the Player 1 type that is more likely to deviate (has lower utility in the PBE, is the ``low" type with nothing to lose, etc.)
\end{itemize}
\textbf{Semi-Separating:}
\begin{itemize}[label=\FlowerSmall]
\item Player 2 will observe two different actions; one that corresponds to a for-sure belief (e.g., $\mu = 0$) and one that corresponds to a Bayes' Rule updated belief $\mu \notin \{0,1\}$
\item The Player 1 type that is mixing must be indifferent to the two actions, while the other type must strictly prefer one action
\item Off-path, Player 2's beliefs (and thus actions) must be such that no type of Player 1 has an incentive to deviate (this can be ``low belief / action for everything off-path or more general)
\end{itemize}
\textbf{Write down $\boldsymbol{\sigma}$ \underline{and} $\boldsymbol{\mu}$}
\smallskip
\end{mdframed}
\bigskip
%Infinitely Repeated Games
\chapter*{5. Infinitely Repeated Games}
\thispagestyle{fancy}
\chaptermark{5. Infinitely Repeated Games} \bigskip
We have until now only considered games over finite time horizons. Infinitely repeated games are a subset of dynamic games where the same strategic interaction occurs over infinite time horizons. They may represent situations where the interaction actually extends forever, or where players know the game is finite but have no knowledge of when it will end. Infinitely repeated games can support a much richer set of possible equilibria, especially when actions are strategically linked over time. \bigskip
A \textbf{stage game} is a one-period simultaneous move (normal-form) game of complete information given by $\langle N, (A_i),(v_i) \rangle$ where $A$ is finite. \bigskip
A \textbf{infinitely repeated game} is a game formed by a repetition of the stage game for $T=\infty$ periods. We assume perfect monitoring such that at the end of every period, every player observes the actions chosen by all players in that period. \bigskip
A \textbf{strategy in a repeated game} is $\sigma_i: \mathcal{H} \rightarrow \Delta (A_i)$ where $\mathcal{H}$ is the space of all possible histories in the repeated game. It specifies what action (or probability distribution over actions) to take in any period following any history at that period. In an infinitely repeated game, clearly $\mathcal{H}$ is also infinite; strategies thus identify ``states" of histories and map these states to actions. \bigskip
\textbf{Payoffs} are written as infinite sequences of expected payoffs: \hspace{10pt} $u_i(\{v_i^t \}_{t=1}^\infty) = (1-\delta) \displaystyle\sum_{t =1}^\infty \delta^{t-1} v_i^t $
\begin{itemize}
\item We assume exponential discount factor $\delta \in [0,1)$
\item The sequence of payoffs is normalized by $(1 - \delta)$ for convenience
\item $v_i^t = v^* \hspace{5pt} \forall t \hspace{5pt} \Rightarrow \hspace{5pt} u_i(\{v_i^t \}_{t=1}^\infty) = v^*$
\item $u_i(\{v_i^t \}_{t=1}^\infty) = (1-\delta) v_i^1 + \delta u_i (\{v_i^t \}_{t=2}^\infty)$
\end{itemize} \bigskip
A \textbf{profitable one-shot deviation (POSD)} for player $i$ is a strategy $\sigma_i' \neq \sigma_i$ such that (a) there is a unique history $h^t$ such that for all $\widetilde{h}^t \neq h^t, \sigma_i'(\widetilde{h}^t) = \sigma_i(\widetilde{h^t})$ and (b) $u_i(\sigma_i',\sigma_{-i} \mid h^t ) > u_i(\sigma \mid h^t)$
\begin{itemize}
\item There is exactly one history where $\sigma_i'$ deviates from $\sigma_i$, and the deviation is profitable conditional on reaching that history
\end{itemize} \bigskip
\textbf{One-Shot Deviation Principle:}
\begin{itemize}
\item \textbf{A strategy profile $\boldsymbol{\sigma}$ is a NE if and only if there are no POSD on the equilibrium path}
\item \textbf{A strategy profile $\boldsymbol{\sigma}$ is a SPNE if and only if there are no POSD anywhere}
\item Intuitively, if there exists a profitable deviation then there exists a POSD
\item These results are powerful because they limit the deviations we have to check from infinity to the smallest possible deviations
\item These results only hold because $\delta < 1$
\end{itemize}
\bigskip
If the stage game has a NE, then the infinitely repeated game has a SPNE (repeat the NE always) \newpage
\begin{mdframed}
\medskip
\begin{center} \textbf{{\large Checking if $\boldsymbol{\sigma}$ is NE / SPNE in Infinitely Repeated Game}} \end{center} \bigskip
\textbf{Given $\boldsymbol{\sigma_i: \mathcal{H} \rightarrow \Delta (A_i)}$, identify:}
\begin{itemize}[label=\FlowerSmall]
\item The set of states $\Omega$ such that $\Omega \rightarrow \Delta (A_i)$ \hspace{10pt}
\begin{itemize}
\item Each $\omega \in \Omega$ maps to a unique action
\item $\omega_{CC}$ represents the state where both players are supposed to play $C$ in the next stage game
\end{itemize}
\item The transition function such that $\Omega \times \prod_{i=1}^n A_i \rightarrow \Omega$
\begin{itemize}
\item For each state, every action profile will create a transition to (another or the same) state
\end{itemize}
\item Which state the game begins in ($\omega_0$ ``transitions" immediately into a state)
\item Diagramming the states and transitions with circles and arrows can be helpful
\end{itemize} \bigskip
\textbf{Check for POSD in On-Path States (NE):}
\begin{itemize}
\item For \underline{every player}, check for POSD in on-path states
\item Compare the value of starting in the state and following the strategy $V_i(\omega)$, to the value of starting in the state, deviating once, and then following the strategy for the rest of time $\widetilde{V}_i(\omega)$
\item Use the diagram to identify the future sequence of states
\item If $V_i(\omega) - \widetilde{V}_i(\omega) \geq 0$ for all $i$ and all on-path $\omega$, then $\sigma$ is a NE
\item Solve for the range of $\delta$ that makes $\sigma$ an NE (use the most restrictive criteria if multiple)
\item If a state maps to playing a NE of the stage game, there is no POSD
\item Example:\\[5pt]
$V_1(\omega_{CC}) = u_1(C,C) + \delta V_1(\omega_{CC}) \hspace{2pt} = (1 - \delta) \left[ 5 + \delta 5 + \delta^2 5 \dots \right]$ \\[10pt]
$\widetilde{V_1}(\omega_{CC}) = u_1(D,C) + \delta V_1(\omega_{DD}) = (1 - \delta) \left[ 6 + \delta 2 + d^2 2 \dots \right]$
\end{itemize}
\textbf{Check for POSD in Off-Path States (SPNE):}
\begin{itemize}
\item For \underline{every player}, check for POSD in \underline{every} off-path state (as above)
\end{itemize}
\smallskip
\end{mdframed}
\bigskip
Some strategies for infinitely repeated Prisoner's Dilemma: (must consider \underline{both} players' strategies):
\begin{itemize}
\item \textbf{Always Defect:} Both players following this strategy is a SPNE (repeating the stage NE always)
\item \textbf{Always Cooperate:} Both players following this strategy is not a NE
\item \textbf{Grim Trigger:} In the first round, play $C$. In subsequent rounds, play $C$ if the history is such that neither player has ever played $D$; otherwise play $D$. For a range of $\delta$ (if players are sufficiently patient), both players following Grim Trigger is a SPNE.
\item \textbf{Tit-for-Tat:} In the first round, play $C$. In subsequent rounds, play whatever the opponent played in the previous period. Both players following Tit-for-Tat is a NE for a range of $\delta$; it is an SPNE for at most one value of $\delta$.
\item If both players use Always Cooperate, Grim Trigger, or Tit-for-Tat, we will observe $(C,C)$ forever, but they are very different strategies
\end{itemize}
%Folk Theorems
\section*{Folk Theorems}\medskip
Folk theorems specify what payoff profiles can be achieved by a SPNE of an infinitely repeated game. \bigskip
The \textbf{set of feasible payoffs, V,} is defined as the convex hull of the set of all payoff vectors that are attained by some action profile of the stage game
\begin{itemize}
\item $V = co(\widetilde{V})$ where $\widetilde{V} = \{ (v_1(a),\dots,v_N(a)) \}_{a \in A}$
\item A convex hull of $\widetilde{V}$ is the smallest convex set that contains $\widetilde{V}$ and all convex combinations of $\widetilde{V}$
\item For 2 players, graph the payoffs of all possible action profiles and connect the points with straight lines
\end{itemize} \bigskip
Player $i$'s \textbf{Nash-threat} payoff is $\underline{v}_i = \inf \{ v_i \mid \exists \text{ stage-game (possibly mixed) NE } \sigma \ni v_i(\sigma) = v_i \}$
\begin{itemize}
\item The lowest payoff player $i$ can receive in a pure or mixed NE
\end{itemize} \bigskip
\textbf{Nash-Threat Folk Theorem:} Given a stage game, pick any $v \in V$ such that for all $i$, $v_i > \underline{v}_i$. There exists a $\underline{\delta} \in [0,1)$ such that for all $\delta > \underline{\delta}$, there is a SPNE of the infinitely repeated game with average discounted payoff profile $v$
\begin{itemize}
\item If players are patient enough, any payoff where all players get more than their Nash-threat payoff can be achieved in an SPNE
\item Intuitively, can incent a player to follow the strategy so long as his payoff on-path is higher than getting his Nash-threat payoff forever
\item For 2 players, find Nash-threats $(\underline{v}_1, \underline{v}_2)$. Anything in $V$ from 12:00 to 3:00 can be achieved in SPNE
\end{itemize} \bigskip
Player $i$'s \textbf{minmax} payoff is given by $v_i^0 = \displaystyle\min_{\sigma_{-i}} \displaystyle\max_{\sigma_i} v_i (\sigma_i,\sigma_{-i})$ and a vector of payoffs $v$ is \textbf{strictly\\ individually rational} if for all $i$, $v_i > v_i^0$
\begin{itemize}
\item $v_i^0$ is the largest payoff that Player $i$ can guarantee himself, even if all of the other players coordinate against him -- check all pure strategies of other players and find the minimum best response
\end{itemize} \bigskip
\textbf{Minmax Folk Theorem:} Given a finite stage game, let $V^* \subset V$ be the subset of feasible and strictly individually rational payoffs. If $v$ is in the interior of $V^*$, then there is a $\underline{\delta} \in [0,1)$ such that for all $\delta > \underline{\delta}$, there is a SPNE of the infinitely repeated stage game with average discounted payoff profile $v$
\bigskip
\begin{mdframed}
\medskip
\begin{center} \textbf{{\large Constructing SPNE in Infinitely Repeated Game}} \end{center}
\begin{itemize}[label=\FlowerSmall]
\item Start by identifying NE of the stage game; no players will ever have a POSD from a NE
\item Easiest construction is a Nash Reversion strategy; if players don't follow the strategy, the punishment is getting a bad NE forever
\item Otherwise try 1- or 2-period ``punishment" states (punishments for deviations don't have to be symmetric across players)
\item SPNE in infinitely repeated games can include public coordination devices, different strategies for even vs. odd rounds, etc.
\end{itemize}
\smallskip
\end{mdframed}
\bigskip
%Relating Concepts
\chapter*{Appendix}
\thispagestyle{fancy}
\chaptermark{Appendix} \bigskip
%Relating Solution Concepts
\section*{Relating Solution Concepts}\medskip
\textbf{Rationalizable Actions:} The broadest solution concept. For each player, there is a set of actions that is rationalizable. Rationalizability allows for correlated strategy beliefs, but does not require correct beliefs. \bigskip \bigskip
\textbf{Nash Equilibria (NE):} A refinement of rationalizable actions, further assuming each player has correct beliefs about what the other player will do. NE are mixed strategy profiles, made up of rationalizable actions by all players, where no player has an incentive to deviate. NE and its refinements do not allow for correlated strategies. \bigskip \bigskip
\textbf{Subgame Perfect Nash Equilibria (SPNE):} A subset of NE for extensive form games. SPNE assumes that all players will play optimally at every information set in a game.\bigskip \bigskip
\textbf{Trembling Hand Perfect Equilibria (THPE):} A subset of NE for normal form games. THPE assumes that there is a possibility of slight mistakes in a player's beliefs about what the other players will do. \bigskip \bigskip
\textbf{SPNE and THPE:} Are two different solution concepts. The THPE of a game may be a subset of the SPNE, or the SPNE may be a subset of the THPE. \bigskip \bigskip
\textbf{$\boldsymbol{\varepsilon}$-Equilibria ($\boldsymbol{\varepsilon}$-E):} $\varepsilon$-equilibrium relaxes the best response assumption, such that one or more players can have a strictly positive but arbitrarily close to 0 incentive to deviate. $\varepsilon$-E is an expansion of NE in an attempt to better reflect behavior in actual games. \bigskip \bigskip
\textbf{Correlated Equilibrium (CE):} NE and its refinements use mixed strategy profiles, which we have assumed are independent randomizations. CE allows for players to use strategies such that they jointly randomize over action profiles. CE requires correct beliefs, but allows correlated strategies. A NE (pure or mixed) is always a CE.\bigskip \bigskip
\textbf{Evolutionary Stable Strategies:} A subset of NE when modeling situations in which the players' actions are determined by the forces of evolution. \bigskip \bigskip
\textbf{Bayesian Nash Equilibrium (BNE):} The equivalent of NE in games of incomplete information that have been transformed into games with complete but imperfect information. Similar to NE, BNE do not place any restrictions on strategies off of the equilibrium path (can include things like non-credible threats). \bigskip \bigskip
\textbf{Mixed NE and BNE:} Consider a sequence of Bayesian games that converges to a complete information normal form game (e.g., two players have different, randomized payoffs but the range of randomizations is approaching zero). In general, every NE (pure or mixed) of the complete information is the limit of NE for the sequence of Bayesian games. As players have a unique best response along the sequence, they are not randomizing. Thus mixed NE in complete information games can be viewed as pure strategy equilibria in a close-by Bayesian game. \bigskip \bigskip
\textbf{Global Games:} Games of incomplete information where players receive correlated signals of the underlying state of the world. We use global games to make predictions about what NE would be played as the range of signals goes to zero. \bigskip \bigskip
\textbf{Perfect Bayesian Equilibrium (PBE):} In games of incomplete information, a subset of NE or BNE (whichever applies) where off-path strategies are justfied by some (any) belief. \bigskip \bigskip
\textbf{Sequential Equilibrium (SE):} A subset of PBE, where off-path actions (or probability distributions over actions) are justified by consistent (``reasonable") beliefs. They are also a subset of SPNE. \bigskip \bigskip
\textbf{NE, PBE, and SE as Long-Term Play:} We can think of NE as an equilibrium reached after long-term play, where players learn about each others' strategies. Similarly, we can think of PBE as where players plan to behave optimally off-path, but have never observed what happens off-path so can believe anything. SE are where the other players make shaky-hand mistakes every so often, so each player learns what happens off-path and plan to behave optimally in response. \bigskip \bigskip
\textbf{Signaling Games:} A subset of extensive form games with imperfect information where PBEs are used. Player 1 knows his type and uses his action to send a signal that Player 2 observes and can act on. \bigskip \bigskip
\textbf{Infinitely Repeated Games:} A subset of dynamic games where the same strategic interaction occurs over infinite time horizons. We look at NE and SPNE in infinitely repeated games. \bigskip \bigskip
\newpage
%Uniform Distribution
\section*{Uniform Distribution}\medskip
\begin{center}
\begin{tabular}{l c c c}
& $\theta \sim U[a,b]$ & \hspace{30pt} & $\theta \sim U[0,1]$\\[15pt]
$\boldsymbol{f(\theta^*) = P(\theta = \theta^*):}$ \hspace{30pt} & $\cfrac{1}{b - a}$ & & 1 \\[15pt]
$\boldsymbol{F(\theta^*) = P(\theta \leq \theta^*):}$ & $\cfrac{\theta^* - a}{b - a}$ & & $\theta^*$\\[15pt]
\textbf{Mean:} & $\cfrac{a+b}{2}$ & & $\cfrac{1}{2}$\\[15pt]
\textbf{Variance:} & $\cfrac{(b-a)^2}{12}$ & & $\cfrac{1}{12}$\\[15pt]
\end{tabular}
\end{center}
\bigskip \bigskip
%Infinite Series
\section*{Geometric Series}\medskip
$(1 - \delta^2) = (1 + \delta)(1-\delta)$ \bigskip
$(1 - \delta^3) = (-1)(\delta - 1)(\delta^2 + \delta + 1)$ \bigskip
$\displaystyle\sum_{t=1}^T \delta^{t-1} a = a + \delta a + \delta^2 a + \delta^3 a \dots \delta^{T-1}a = \cfrac{a - a \cdot \delta^{T-1}}{1 - \delta}$ \bigskip
$\displaystyle\sum_{t=1}^\infty \delta^{t-1} a = a + \delta a + \delta^2 a + \delta^3 a \dots = \cfrac{a}{1 - \delta}$ \hspace{10pt} (in the limit!) \bigskip
$\displaystyle\sum_{t=1}^\infty (\delta^2)^{t-1} a = a + (\delta^2) a + (\delta^2)^2 a + (\delta^2)^3 a \dots = a + \delta^2 a + \delta^4 a + \delta^6 a = \cfrac{a}{1 - \delta^2}$ \bigskip
\end{document}