One Shot Deviation Principle

Posted on April 15, 2016
Tags: game theory

The content here is reproduced from Fudenberg and Tirole’s 1991 text.

In infinite horizon games, the one-shot deviation principle is a useful tool to check whether a strategy profile \(\sigma\) is subgame perfect. Informally, it states that we only need to check deviations \((\sigma_i', \sigma_{-i})\) where \(\sigma_{i}'\) differs from \(\sigma_i\) only at a single history.

We begin with the theorem for finite horizon games.

Theorem 1 (One-Stage-Deviation Principle for Finite Horizon Games). In a finite multi-stage agme with observed actions, strategy profile \(s\) is subgame perfect if and only if it satisfies the one-stage-deviation condition:

there is no player \(i\) and a history \(h^t\) such that player \(i\) has a profitable deviation \(s_i'\) where \(s_i = s_i'\) everywhere except at \(h^t\)

Proof. The “only if” condition is immediate from the definition of subgame perfection. For sufficiency, suppose that a strategy profile \(s\) satisfies the one-stage-deviation condiiton, but is not subgame perfect. Therefore, there is some history \(h^t\) and player \(i\) such that

\begin{equation} \label{eq:1} u_i(s_i', s_{-i}; h^t) > u_i(s; h^t) \quad \text{for some strategy $s_i'$.} \end{equation}

Let \(T\) be the largest \(\tau\) for the set

\begin{equation} \label{eq:2} D(\tau) := \{ h^{\tau} : s_i'(h^{\tau}) \neq s_i(h^{\tau}) \} \end{equation}

is non-empty (i.e. \(T\) is the last stage at where \(s_i'\) and \(s_i\) differs). Since \(s_i = s_i'\) for all \(\tau \geq T+1\), the one-stage-deviation condition implies that

\begin{equation} \label{eq:3} u_i(s; h^T) \geq u_i(s_i', s_{-i}; h^T). \end{equation}

Now define \(s_i''\) to be the strategy that is equal to \(s_i'\) in stages \(t \leq \tau \leq T-1\) and equals \(s_i\) at stage \(T\). By \eqref{eq:1} and \eqref{eq:3}

\begin{equation} \label{eq:4} u_i(s_i'', s_{-i}; h^t) \geq u_i(s_i', s_{-i}; h^t) > u_i(s; h^t). \end{equation}

But \(s_i''\) differs from \(s_i\) only up to \(T-1\). Repeating the process, we obtain \(s_i'''\) satisfying \(u_i(s_i''',s_{-i};h^t)>u_i(s;h^t)\) that differs from \(s_i\) only up to \(T-2\). Thus, this process eventually yields a strategy \(S_i\) with

\begin{equation} \label{eq:5} u_i(S_i, s_{-i}; h^t) > u_i(s_i, s_{-i};h^t) \end{equation}

that only differs from \(s_i\) at time \(t\). This contradicts the one-stage-deviation principle, and complets the proof. \(\square\)

The insight of Theorem 1 carries over for infinite horizon games: it shows that if \(s_i'\) is a profitable deviation over \(s_i\), it must differ from \(s_i\) infinitely often. That is, for every \(T\) there exist \(\tau \geq T\) and a history \(h^{\tau}\) such that \(s_i'(h^{\tau}) \neq s_i(h^{\tau})\). This is made precise below.

Definition. A multi-stage game with observed actions is continuous at infinity if for each player \(i\)

\begin{equation} \label{eq:6} \sup_{h, \eta} |u_i(h) - u_i(\eta)| \to 0 \quad \text{as $t \to \infty$} \end{equation}

where the supremum is taken over all histories \(h\) and \(\eta\) where \(h^t = \eta^t\), and \(h^t\) is the restriction of the infinite history \(h\) to the first \(t\) periods.

In English, this says that for two histories that agree up to the first \(t\) periods, the difference in the utilities for those two histories becomes arbitrarily small as \(t \to \infty\).

Remark. A multi-stage game in which payoffs in each stage are uniformly bounded and players discount at \(\delta < 1\) is continuous at infinity.

Theorem 2 (One-Stage Deviation Principle for Infinite-Horizon Games). In an infinite-horizon multi-stage game with observed actions that is continuous at infinity, a profile \(s\) is subgame perfect if and only if it satisfies the one-stage-deviation condition in Theorem 1.

Proof. Suppose that \(s\) satisfies the one-stage-deviation condition but is not subgame perfect. Then there exists a history \(h^t\) and a strategy \(s_i'\) for which

\begin{equation} \label{eq:7} \epsilon := u_i(s_i', s_{-i}; h^t) - u_i(s; h^t) > 0. \end{equation}

By continuity at infinity, there exists \(T\) large enough such that

\begin{equation} \label{eq:8} |u_i(s_i', s_{-i}; h^t) - u_i(S_i, s_{-i}; h^t)| < \epsilon/2 \end{equation}

where \(S_i\) is strategy which agrees with \(s_i'\) up to period \(T\) and follows strategy \(s_i\) thereafter. Thus, \(S_i\) is a profitable deviation for player \(i\) at \(h^t\) that differs from \(s_i\) in only finitely many periods. This contradicts Theorem 1. \(\square\)