The one-stage deviation principle for subgame perfect equilibria Recall that ui(σ | x) is the…

The one-stage deviation principle for subgame perfect equilibria Recall that ui(σ | x) is the payoff to player i when the players implement the strategy vector σ, given that the play of the game has arrived at the vertex x. Prove that a strategy vector σ∗ = ()i∈N in an extensive-form game with perfect information is a subgame perfect equilibrium if and only if for each player i ∈ N, every decision vertex x, and every strategy  of player i that is identical to  at every one of his decision vertices except for x,

Guidance: To prove that σ ∗ is a subgame perfect equilibrium if the condition above obtains, one needs to prove that the condition ui(σ∗ | x) ≥ ui((σi, σ ∗ −i) | x) holds for every vertex x, every player i, and every strategy σi. This can be accomplished by induction on the number of vertices in the game tree as follows. Suppose that this condition does not hold. Among all the triples (x, i, σi) for which it does not hold, choose a triple such that the number of vertices where σi differs from σ∗i is minimal. Denote by X the set of all vertices such that σi differs from σ∗ i. By assumption, |X| ≥ 1. From the vertices in X, choose a “highest” vertex, i.e., a vertex such that every path from the root to it does not pass through any other vertex in X. Apply the inductive hypothesis to all the subgames beginning at the other vertices in X .