Constrained-game and best-response definitions

Definition 1 (Limit of an ε-constrained Nash-equilibrium sequence)

Consider ε-perturbed game $G (ε) = (N, Σ (ε), π)$ where

$Σ_{i} (ε) = {σ_{i} \in Σ_{i} ∣ σ_{i} (s_{i}) \geq ε_{i} (s_{i}), \forall s_{i} \in S_{i}}$

for some $ε_{i} (s_{i})$ such that $0 < ε_{i} (s_{i}) \leq ε$ , and a Nash equilibrium $σ_{ε}$ of $G (ε)$ .

If for some sequence of perturbations $ε^{n}$ such that $ε^{n} \to 0$ , $σ_{ε^{n}} \to σ^{*}$ , $σ^{*}$ is a perfect equilibrium.

Every pure strategy has a small positive probability floor, so feasible profiles are completely mixed. Find a Nash equilibrium of each perturbed game, then let all floors vanish and consider a convergent sequence of these equilibria.

Definition 2 (Limit of a sequence of completely mixed strategies)

$σ^{*}$ is a perfect equilibrium if $\exists σ^{n}$ (a sequence of completely mixed strategies) such that $σ^{n} \to σ^{*}$ and $σ_{i}^{*}$ is a BR to $σ_{- i}^{n}$ , $\forall n$ .

(That is, if for some sequence $σ^{n}$ , $σ^{n} \to σ^{*}$ and $σ_{i}^{*}$ is a BR to $σ_{- i}^{n}$ , $\forall n$ .)

The two definitions are equivalent, as proved below.

Myerson’s definition of the perfect equilibrium

Definition 3 (Limit of an ε-perfect equilibrium sequence)

A completely mixed profile $σ^{ε}$ is ε-perfect if and only if

$π_{i} (s_{i}, σ_{- i}^{ε}) < π_{i} (s_{i}^{'}, σ_{- i}^{ε}) \Rightarrow σ_{i}^{ε} (s_{i}) \leq ε,$

where $s_{i}, s_{i}^{'} \in S_{i}$ .

$σ^{*}$ is perfect if and only if it is a limit of ε-perfect equilibrium.

Theorem 1 (Selten, Myerson)

$Definition 1 ⟺ Definition 2 ⟺ Definition 3 .$

Why the three definitions of trembling-hand perfection agree

Work throughout with a finite normal-form game. The three definitions characterize ordinary trembling-hand perfect equilibrium (THPE). Truly perfect equilibrium (TPE) is a distinct, stronger refinement.

Read the notation first

$S_{i}$ : player $i$ ’s finite pure-action set; $Δ (S_{i})$ : all probability distributions on it.
$q^{k}$ : the entire profile at sequence index $k$ ; $q_{- i}^{k}$ : everybody except $i$ . The superscript is an index, not a power.
$σ^{*}$ : the fixed limiting profile. Its support is $H_{i} = {a : σ_{i}^{*} (a) > 0}$ .
$B_{i} (q_{- i}) = \arg {max}_{a \in S_{i}} π_{i} (a, q_{- i})$ : the pure best responses. A mixed strategy is a best response exactly when all actions in its support belong to this set.
$η_{i}^{k} (a) > 0$ : an action-specific probability floor; $ϵ_{k} > 0$ : a single upper bound on mistake probabilities. These are different objects.

We will prove a cycle of implications: constrained equilibria $\Rightarrow$ $ϵ$ -perfect profiles $\Rightarrow$ the fixed-strategy best-response test $\Rightarrow$ constrained equilibria.

The key fact: only optimal actions can receive probability above their floors

Fix opponents $q_{- i}$ and floors with $\sum_{a} η_{i} (a) < 1$ . Write any feasible strategy as compulsory probabilities plus freely allocated residual mass:

x_{i} (a) = η_{i} (a) + r_{i} (a), r_{i} (a) \geq 0, \sum_{a} r_{i} (a) = 1 - \sum_{a} η_{i} (a) .

The compulsory part has a fixed payoff. The remaining mass must maximize a weighted average of pure-action payoffs, so all of it must go to best responses. Equivalently,

x_{i} is a constrained best response ⟺ x_{i} (a) > η_{i} (a) ⟹ a \in B_{i} (q_{- i}) .

For necessity, if an inferior action has positive slack above its floor, move a small amount of that slack to a best action. Every floor remains satisfied and payoff rises. For sufficiency, distributing all residual mass among best actions already achieves its largest possible payoff. An action exactly at its floor may also be optimal: the condition is only one way.

Numerical example. Suppose $A, B, C$ yield $5, 5, 1$ against the current opponents, and the floors are $(0.01, 0.01, 0.02)$ . The compulsory mass totals $0.04$ ; the remaining $0.96$ goes to $A$ and $B$ . Thus $(0.58, 0.40, 0.02)$ is constrained optimal. Assigning $0.03$ to $C$ would leave slack on an inferior action and cannot be optimal.

1. Constrained-equilibrium limits imply ε-perfect limits

Suppose $q^{k} \in N E (G (η^{k}))$ , $q^{k} \to σ^{*}$ , and every floor tends to zero. Complete mixing follows from the positive floors. By the key fact, every non-best-response action is exactly at its floor. Set $ϵ_{k} = {max}_{i, a} η_{i}^{k} (a)$ . There are finitely many coordinates, so $ϵ_{k} \to 0$ ; every inferior action receives probability at most $ϵ_{k}$ . These are precisely the required $ϵ_{k}$ -perfect profiles.

2. ε-perfect limits imply the fixed-strategy test

Suppose completely mixed $q^{k} \to σ^{*}$ are $ϵ_{k}$ -perfect and $ϵ_{k} \to 0$ . Take any $a \in H_{i}$ . Its limiting probability is positive. Therefore, with $d = σ_{i}^{*} (a) / 2 > 0$ , eventually

q_{i}^{k} (a) > d > ϵ_{k} .

An inferior action would have probability at most $ϵ_{k}$ , so $a$ must be a best response to $q_{- i}^{k}$ . Because there are only finitely many players and supported actions, take the largest of their finitely many thresholds. Beyond that one common index, every action used by $σ_{i}^{*}$ is optimal, for every player. Their mixture $σ_{i}^{*}$ is therefore a best response to $q_{- i}^{k}$ . Discard the finite initial segment and reindex; the condition then holds for every $k$ .

This argument proves more than passing to the limit. Continuity of expected payoffs yields that $σ_{i}^{*}$ is optimal against $σ_{- i}^{*}$ , hence Nash equilibrium. It does not by itself prove optimality of that same fixed strategy against every nearby $q_{- i}^{k}$ . Positive support probabilities and the $ϵ_{k}$ -test supply that stronger conclusion.

3. The fixed-strategy test produces constrained equilibria

Suppose completely mixed $q^{k} \to σ^{*}$ satisfy $σ_{i}^{*} \in B R_{i} (q_{- i}^{k})$ . Keep these witnessing profiles unchanged and, for $k \geq 2$ , choose floors

η_{i}^{k} (a) = {\begin{matrix} q_{i}^{k} (a), & a \notin H_{i}, \\ q_{i}^{k} (a) / k, & a \in H_{i} . \end{matrix}

Every floor is positive and no greater than the corresponding probability. For explicit mass bookkeeping let $m_{i}^{k} = \sum_{a \notin H_{i}} q_{i}^{k} (a)$ . The support carries $1 - m_{i}^{k} > 0$ , so

\sum_{a} η_{i}^{k} (a) = m_{i}^{k} + \frac{1 - m_{i}^{k}}{k} < 1 .

Thus all constraints are feasible. Off-support probabilities tend to zero, while supported floors are at most $1 / k$ ; hence every floor vanishes. The residual mass $(1 - 1 / k) (1 - m_{i}^{k})$ is distributed only over $H_{i}$ , in the proportions $q_{i}^{k} (a) / (1 - m_{i}^{k})$ . This accounts exactly for the mass reserved for off-support trembles. All actions in $H_{i}$ are best responses, so the key fact proves that $q^{k}$ is a Nash equilibrium of $G (η^{k})$ , simultaneously for all players.

The construction chooses some suitable perturbation sequence. Requiring convergence for every prescribed floor sequence is the stronger strictly perfect requirement. Arbitrarily redistributing probabilities, for example replacing each witness by a uniform tremble around $σ^{*}$ , can change opponents’ probabilities and break best-response ties. The proof above avoids that unjustified step.

Self-check. Does probability exactly $ϵ_{k}$ force an action in an $ϵ_{k}$ -perfect profile to be optimal? Answer: no. Inferior actions may receive probability at most $ϵ_{k}$ . The support argument needs the strict inequality $q_{i}^{k} (a) > ϵ_{k}$ .