Subgame

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):[1]

  1. 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).
  2. If a node is contained in the subgame then so are all of its successors.
  3. If a node in a particular information set is in the subgame then all members of that information set belong to the subgame.
This article is about subgames in game theory. For subgame as a short video game contained in another, see minigame.

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.

Subgame perfection

One of the principal 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.

gollark: Well, you may want "whitespace" or "not whitespace", deterministic serialization in some way, and control over what happens to invalid types.
gollark: Unfortunately, like many CC things it doesn't seem that customizable and like many neat CC:T things I can't use it because backward compatibility.
gollark: `unserializeJSON` is new, though.
gollark: `textutils.serialiseJSON` exists in CC:T now, fortunately.
gollark: Yes, the async stuff is kind of irritating to reason about and potatOS has a good coroutine manager.

References
  1. "Table of Contents for Morrow, J.D.: Game Theory for Political Scientists". press.princeton.edu. Retrieved 2008-03-26.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.