Information set
Encyclopedia
In game theory
, an information set is a set that, for a particular player, establishes all the possible moves that could have taken place in the game so far, given what that player has observed. If the game has perfect information
, every information set contains only one member, namely the point actually reached at that stage of the game. Otherwise, it is the case that some players cannot be sure exactly what has taken place so far in the game and what their position is.
More specifically, in the extensive form
, an information set is a set of decision nodes such that:
The notion of information set was introduced by John von Neuman motivated by studying the game of Poker
.
At the right are two versions of the battle of the sexes
game, shown in extensive form
.
The first game is simply sequential-when player 2 has the chance to move, he or she is aware of whether player 1 has chosen O(pera) or F(ootball).
The second game is also sequential, but the dotted line shows player 2's information set. This is the common way to show that when player 2 moves, he or she is not aware of what player 1 did.
This difference also leads to different predictions for the two games. In the first game, player 1 has the upper hand. They know that they can choose O(pera) safely because once player 2 knows that player 1 has chosen opera, player 2 would rather go along for o(pera) and get 2 than choose f(ootball) and get 0. Formally, that's applying subgame perfection
to solve the game.
In the second game, player 2 can't observe what player 1 did, so it might as well be a simultaneous game
. So subgame perfection doesn't get us anything that Nash equilibrium
can't get us, and we have the standard 3 possible equilibria:
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...
, an information set is a set that, for a particular player, establishes all the possible moves that could have taken place in the game so far, given what that player has observed. If the game has perfect information
Perfect information
In game theory, perfect information describes the situation when a player has available the same information to determine all of the possible games as would be available at the end of the game....
, every information set contains only one member, namely the point actually reached at that stage of the game. Otherwise, it is the case that some players cannot be sure exactly what has taken place so far in the game and what their position is.
More specifically, in the 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...
, an information set is a set of decision nodes such that:
- Every node in the set belongs to one player.
- When play reaches the information set, the player with the move cannot differentiate between nodes within the information set, i.e. if the information set contains more than one node, the player to whom that set belongs does not know which node in the set has been reached.
The notion of information set was introduced by John von Neuman motivated by studying the game of Poker
Poker
Poker is a family of card games that share betting rules and usually hand rankings. Poker games differ in how the cards are dealt, how hands may be formed, whether the high or low hand wins the pot in a showdown , limits on bet sizes, and how many rounds of betting are allowed.In most modern poker...
.
Example
Battle of the sexes (game theory)
In game theory, battle of the sexes , also called Bach or Stravinsky, is a two-player coordination game. Imagine a couple that agreed to meet this evening, but cannot recall if they will be attending the opera or a football match. The husband would most of all like to go to the football game. The...
game, shown 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...
.
The first game is simply sequential-when player 2 has the chance to move, he or she is aware of whether player 1 has chosen O(pera) or F(ootball).
The second game is also sequential, but the dotted line shows player 2's information set. This is the common way to show that when player 2 moves, he or she is not aware of what player 1 did.
This difference also leads to different predictions for the two games. In the first game, player 1 has the upper hand. They know that they can choose O(pera) safely because once player 2 knows that player 1 has chosen opera, player 2 would rather go along for o(pera) and get 2 than choose f(ootball) and get 0. Formally, that's applying subgame perfection
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...
to solve the game.
In the second game, player 2 can't observe what player 1 did, so it might as well be a simultaneous game
Simultaneous game
In game theory, a simultaneous game is a game where each player chooses his action without knowledge of the actions chosen by other players. Normal form representations are usually used for simultaneous games....
. So subgame perfection doesn't get us anything that 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...
can't get us, and we have the standard 3 possible equilibria:
- Both choose opera;
- both choose football;
- or both use a mixed strategy, with player 1 choosing O(pera) 3/5 of the time, and player 2 choosing f(ootball) 3/5 of the time.