Subgame
Encyclopedia
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 is a notion used in the solution concept
of subgame perfect Nash equilibrium
, a refinement of the Nash equilibrium
that eliminates non-credible threat
s.
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.
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.
Game theory
Game theory is a mathematical method for analyzing calculated circumstances, such as in games, where a person’s success is based upon the choices of others...
, 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
Extensive form game
An extensive-form game is a specification of a game in game theory, allowing explicit representation of a number of important aspects, like the sequencing of players' possible moves, their choices at every decision point, the information each player has about the other player's moves when he...
):
- 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
Solution concept
In game theory, a solution concept is a formal rule for predicting how the game will be played. These predictions are called "solutions", and describe which strategies will be adopted by players, therefore predicting the result of the game...
of subgame perfect Nash equilibrium
Subgame perfect equilibrium
In game theory, a subgame perfect equilibrium is a refinement of a Nash equilibrium used in dynamic games. A strategy profile is a subgame perfect equilibrium if it represents a Nash equilibrium of every subgame of the original game...
, a refinement of the Nash equilibrium
Nash equilibrium
In game theory, Nash equilibrium is a solution concept of a game involving two or more players, in which each player is assumed to know the equilibrium strategies of the other players, and no player has anything to gain by changing only his own strategy unilaterally...
that eliminates non-credible threat
Non-credible threat
A non-credible threat is a term used in game theory and economics to describe a threat in a sequential game that a rational player would actually not carry out, because it would not be in his best interest to do so....
s.
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
Bayesian game
In game theory, a Bayesian game is one in which information about characteristics of the other players is incomplete. Following John C. Harsanyi's framework, a Bayesian game can be modelled by introducing Nature as a player in a game...
). 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
Bayesian game
In game theory, a Bayesian game is one in which information about characteristics of the other players is incomplete. Following John C. Harsanyi's framework, a Bayesian game can be modelled by introducing Nature as a player in a game...
. 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.
Subgame perfection
One of the principal uses of the notion of a subgame is in the solution conceptSolution concept
In game theory, a solution concept is a formal rule for predicting how the game will be played. These predictions are called "solutions", and describe which strategies will be adopted by players, therefore predicting the result of the game...
subgame perfection, which stipulates that an equilibrium strategy profile be a Nash equilibrium
Nash equilibrium
In game theory, Nash equilibrium is a solution concept of a game involving two or more players, in which each player is assumed to know the equilibrium strategies of the other players, and no player has anything to gain by changing only his own strategy unilaterally...
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.