MAT109 · Erich Prisner · Franklin College · 2007-2009

Subgames

Translating sequential games into normal form is often problematic. Consider the following "game" of the situation (as perceived by some unnamed military expert) in Europe in the 60s as an example. In this game, the only solution found by backwards induction is that the Soviets will attack, and the USA will defend Europe conventially. Now the Soviets have two strategies, and the USA also has two strategies---responding with nuclear or conventional weapons when attacked. Therefore the normal form looks as follows:
nuclearconventional
status quo2,22,2
attack0,03,1
It is easy to see that there are two Nash equilibria in pure strategies, namely (status quo,nuclear) with payoffs of (2,2) and (attack,conventional) with payoffs of (3,1). Only the second one is the Zermelo-Kuhn solution found by backwards induction.

This problem was resolved by Selten, who described a way how and why one would consider only some of the Nash equilibria of games originally described in extensive form by looking at so-called subgames. A subgame consist of a vertex x and all its successors provided

  1. x is a single-vertex information set, and
  2. All information sets are totally inside, or totally outside the successor set of x.
A pair (or set) of behavior strategy is subgame perfect if it is a Nash equilibrium for every subgame. Subgame perfect Nash equilibria are found, similar as solutions with backward induction, by working from the end of the game. First a Nash equilibria is found for each end subgame. Then the final subgames are deleted, the former head of it converts into a terminal vertex, and this terminal vertex gets the values of the Nash equilibrium of the deleted subgame as payoffs. Continuing in this way the game is reduced to a single vertex game with start identical to end.

IRGENDWOHIN: If there are subgames, then analysing the subgames first, and using the results to analyze the larger games, is in most cases better than trying to find the reduced normal form and finding the Nash equilibria there. However, if there are no proper subgames, then the route over the reduced normal form is all we have. This is the case in all variants of VNMPOKER or KUHN POKER. The different "modules" there are all linked as information sets in such a way that no proper subgame exists.

The concept of subgame-perfect equilibria was introduced by the German economist Reinhard Selten in 1965. For this and other more complex achievement in Game Theory, Selten reveived the Nobel prize (shared with John Harsanyi and John Nash) in 1994. Selten was also one of the first to conduct experiments in Game Theory.

Reinhard Selten was born 1930 in Breslau/Wroclaw. Grewing up in Hitler Germany as a half-jew was difficult and made Selten interested in Politics and Economics. After the war, he studied mathematics in Frankfurt, obtaining a Ph. D in 1961. He bacame interested in the new topic of Game Theory. In 1975 Selten introduced "trembling hand perfectness", another refinement of Nash equilibrium. He was professor in Berlin, Bielefeld, and Bonn.

Imperfect Information

Stratego5: There are two players, and each one gets 5 cards, a "5", a "4", a "3", a "2", a "1". Then the players reveal one of the cards in their hand simultaneously in rounds. If both are identical, or if one is "1" and the other "5", both cards remain on the desk. Otherwise the player who played the higher card takes it back to her hand, whereas the lower card must remain on the desk. The player having first no card in her hand after a round (after retaking the higher card) looses.

Remember that a game has imperfect information if either there are some simultaneous moves, or all moves are sequential but some player is not aware of the choices of another player having moved before. Games with imperfect information can be analysed using the Normal Form, but the powerful tool of Backwards Induction, yielding a definite solution, is no longer available. However the method described above, yielding sugbame perfect equilibria should be used.

More links

Waiting for Mr Perfect Analysis
Von Neumann-Morgenstern Poker Analysis

Exercises

  1. ...