Subgame
From Wikipedia, the free encyclopedia
- This article is about subgames in game theory. For subgame as a short video game contained in another, see [[minigame]].
In game theory, a subgame is any part (a subset) of a game that meets the following criteria (the following terms allude to a game described in extensive form):
- It has a single initial node that is the only member of that node's information set (i.e. the initial node is in a singleton information set).
- It contains all the nodes that are successors of the initial node.
- It contains all the nodes that are successors of any node it contains.
- If a node in a particular information set is in the subgame then all members of that information set belong to the subgame.
It is a notion used in the solution concept of subgame perfect Nash equilibrium, a refinement of the Nash equilibrium that eliminates non-credible threats.
The key feature of a subgame is that it, when seen in isolation, constitutes a game in its own right. When the initial node of a subgame is reached in a larger game, players can concentrate only on that subgame; they can ignore the history of the rest of the game (provided they know what subgame they are playing). This is the intuition behind the definition given above of a subgame. It must contain an initial node that is a singleton information set since this is a requirement of a game. Otherwise, it would be unclear where the player with first move should start at the beginning of a game (but see nature's choice. Even if it is clear in the context of the larger game which node of a non-singleton information set has been reached, players could not ignore the history of the larger game once they reached the initial node of a subgame if subgames cut across information sets. Furthermore, a subgame can be treated as a game in its own right, but it must reflect the strategies available to players in the larger game of which it is a subset. This is the reasoning behind 2 and 3 of the definition. All the strategies (or subsets of strategies) available to a player at a node in a game must be available to that player in the subgame the initial node of which is that node.
[edit] Subgame perfection
One of the principle uses of the notion of a subgame is in the solution concept subgame perfection, which stipulates that an equilibrium strategy profile be a Nash equilibrium in every subgame.
In a Nash equilibrium, there is some sense in which the outcome is optimal - every player is playing a best response to the other players. However, in some dynamic games this can yield implausible equilibria. Consider a two player game in which player 1 has a strategy S to which player 2 can play B as a best response. Suppose also that S is a best response to B. Hence, {S,B} is a Nash equilibrium. Let there be another Nash equilibrium {S',B'}, the outcome of which player 1 prefers and B' is the only best response to S'. In a dynamic game, the first Nash equilibrium is implausible (if player 1 moves first) because player 1 will play S', forcing the response (say) B' from player 2 and thereby attaining the second equilibrium (regardless of the preferences of player 2 over the equilibria). The first equilibrium is subgame imperfect because B does not constitute a best response to S' once S' has been played, i.e. in the subgame reached by player 1 playing S', B is not optimal for player 2.
If not all strategies at a particular node were available in a subgame containing that node, it would be unhelpful in subgame perfection. One could trivially call an equilibrium subgame perfect by ignoring playable strategies to which a strategy was not a best response. Furthermore if subgames cut across information sets, then a Nash equilibrium in a subgame might suppose a player had information in that subgame, he did not have in the larger game.
