Extensive Form Games

'The employer will fire the worker if the worker disagrees.' 'We'll impose sanctions if conditions aren't met.' Threats in negotiations are everywhere. But not all threats are equally convincing. The extensive form and backward induction give a mathematical answer: a threat only works if it's in the threatener's interest to carry it out. This insight transformed negotiation theory, diplomacy, and corporate strategy.

• **Salary negotiation:** who makes the first offer (anchoring effect), who has a better BATNA-all determined by the game tree structure and backward induction
• **Antitrust policy:** Entry Deterrence models why the threat of a price war sometimes deters competitors and sometimes doesn't (depends on credibility)
• **Poker AI (Libratus, Pluribus):** the Carnegie Mellon bot beat world-class players by solving the problem with information sets via Counterfactual Regret Minimization

Предварительные знания

• Zero-Sum Games

The Game Tree

Consider a salary negotiation: the employer makes an offer first, then the candidate accepts or rejects. The normal form (matrix) doesn't show who moves first. The extensive form is a decision tree where each node is someone's turn to act, each edge is a choice, and the leaves are final payoffs.

Defined by: N (players), H (history nodes), Z (terminal nodes/leaves), χ(h) (available actions at node h), ρ(h) (whose turn it is), σ (information sets), u: Z → Rⁿ (payoffs at leaves).

The key advantage of the extensive form: it explicitly shows each player's **information**. In chess both players see the full board-perfect information. In poker the opponent's cards are hidden-imperfect information. The structure of information sets fundamentally changes what optimal strategies look like.

Backward Induction

To find the optimal strategy in a game tree, reason from the end. At the final nodes the choice is clear: each player picks the action with the best payoff. Knowing this, the tree can be 'folded' backward-penultimate nodes are solved knowing what comes next. Continue to the root. This is backward induction.

1. Find all pre-terminal nodes (whose children are all leaves) 2. At each such node, the player picks the action with max payoff 3. Replace the node with the corresponding payoff 4. Repeat until the root Result: a strategy profile that is a subgame perfect equilibrium (SPE).

Backward induction requires that all decisions be rational-including at nodes that will never be reached. This 'perfectness' assumption rules out 'non-credible threats': promises to take actions that the promiser would not rationally carry out.

Subgame Perfect Equilibrium (SPE)

The normal form of the Ultimatum Game has many Nash Equilibria-for example, player 1 offers 10% and player 2 threatens to reject anything below 50%. But this NE is unrealistic: if player 1 actually offers 10%, player 2 is better off accepting (10% > 0%). The threat was 'empty'. Subgame perfect equilibrium (SPE) rules out such threats.

A subgame is a part of the tree starting from a single node and including all its descendants. A strategy profile is an SPE if it is a Nash Equilibrium in EVERY subgame. SPE ⊂ NE: every SPE is an NE, but not every NE is an SPE.

SPE was introduced by Reinhard Selten (Nobel 1994) as a refinement of NE for sequential games. It eliminates equilibria based on 'empty threats'-actions that a player would not rationally carry out when the time comes.

Information Sets

In poker, a player bets without knowing the opponent's cards. In game-theoretic terms: the player cannot distinguish between several nodes in the tree-'did the opponent have an ace or not?' Such a group of indistinguishable nodes is called an information set. A strategy in a game with imperfect information is a plan of action for each information set.

Perfect information: every information set contains exactly one node-the player knows the history exactly (chess, Go). Imperfect information: some information sets contain multiple nodes (poker, negotiations). SPE applies strictly only to perfect information. For imperfect information: Perfect Bayesian Equilibrium (PBE).

Information sets explain why bluffing in poker is rational. If a player only bets with a strong hand, the opponent always folds when facing a bet. The optimal strategy: bluff at the right frequency to make the opponent indifferent between calling and folding. This is a classic mixed strategy equilibrium.

Key ideas

• **Extensive form (game tree):** explicitly models the order of moves and each player's information
• **Backward induction:** solve from leaves to root-finds the optimal strategy in games with perfect information
• **SPE:** rules out 'unrealistic threats'-actions that are not profitable to carry out in the corresponding subgame
• **Information sets:** model imperfect information; bluffing in poker is a rational mixed strategy equilibrium

Related topics

The extensive form is the foundation for analyzing sequential negotiations and mechanisms:

• Nash Equilibrium — SPE is a refinement of NE for games with sequential moves
• Mechanism Design — Mechanisms often use sequential moves, and the revelation principle works via backward induction
• Auction Theory — Auctions are games with bids under incomplete information about opponents' valuations

Вопросы для размышления

• Rubinstein bargaining shows: the more impatient a player (high discount factor), the weaker their bargaining position. How does this apply to real salary negotiations or M&A deals?
• Empty threats in diplomacy are common. What are examples where a threat turned out to be non-credible? Why did that happen?
• Poker is a game with imperfect information. Why can a human professional beat a simple bot, yet lose to Libratus? What does the AI bot do fundamentally differently?

Связанные уроки

• alg-21-dp