Information set (game theory)
The information set is the basis for decision making in a game, which includes the actions available to both sides and the benefits of each action. The information set is an important concept in non-perfect games. In game theory, an information set is the set of all possible actions in the game for a given player, built on their observations and a set for a particular player that, given what that player has observed, shows the decision vertices available to the player which are indistinguishable to them at the current point in the game. For a better idea on decision vertices, refer to Figure 1. If the game has perfect information, every information set contains only one member, namely the point actually reached at that stage of the game, since each player knows the exact mix of chance moves and player strategies up to the current point in the game. Otherwise, it is the case that some players cannot be sure what the game state is; for instance, not knowing what exactly happened in the past or what should be done right now.
Information sets are used in extensive form games and are often depicted in game trees. Game trees show the path from the start of a game and the subsequent paths that can be made depending on each player's next move. For non-perfect information game problems, there is hidden information. That is, each player does not have complete knowledge of the opponent's information, such as cards that do not appear in a poker game. Therefore, when constructing a game tree, it is difficult to determine precisely where a node is located based on known information alone, as we do not know certain information about our opponent. We can only be sure that we are at one of a range of possible nodes. This inability to distinguish the set of nodes in a particular player's game tree is known as the 'information set'. Information sets can be easily depicted in game trees to display each player's possible moves typically using dotted lines, circles or even by just labelling the vertices which shows a particular player's options at the current stage of the game as shown in Figure 1.
More specifically, in the extensive form, an information set is a set of decision nodes such that:
- Every node in the set belongs to one player.
- When the game reaches the information set, the player with the move cannot differentiate between nodes within the information set, i.e. if an information set contains multiple nodes, the participants associated with that information set are uncertain about which node to select for their move.
Games in extensive form often involve each player being able to play multiple moves which results in the formation of multiple information sets as well. A player is to make choices at each of these vertices based on the options in the information set. This is known as the player's strategy and can provide the player's path from the start of the game, to the end which is also known as the play of the game. From the play of the game, the outcome will always be known based on the strategy of each player unless chance moves are involved, then there will not always be a singular outcome. Not all games play's are strategy based as they can also involve chance moves. When chance moves are involved, a vector of strategies can result in the probability distribution of the multiple outcomes of the games that could occur. Multiple outcomes of games can be created when chance is involved as the moves are likely to be different each time. However, based on the strength of the strategy, some outcomes could have higher probabilities than others.
Assuming that there are multiple information sets in a game, the game transforms from a static game to a dynamic game. The key to solving dynamic game is to calculate each player's information set and make decisions based on their choices at different stages. For example, when player A chooses first, the player B will make the best decision for him based on A's choice. Player A, in turn, can predict B's reaction and make a choice in his favour. The notion of information set was introduced by John von Neumann, motivated by studying the game of Poker.
Example
At the right are two versions of the battle of the sexes game, shown in extensive form. Below, the normal form for both of these games is shown as well.
The first game is simply sequential―when player 2 makes a choice, both parties are already 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:
- 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) 2/5 of the time
|
|
See also
- Self-confirming equilibrium
References
- Binmore, Ken (2007). Game Theory: A very short introduction. Oxford University Press. pp. 88–89. ISBN 978-0-19-921846-2.
- v
- t
- e
- Congestion game
- Cooperative game
- Determinacy
- Escalation of commitment
- Extensive-form game
- First-player and second-player win
- Game complexity
- Graphical game
- Hierarchy of beliefs
- Information set
- Normal-form game
- Preference
- Sequential game
- Simultaneous game
- Simultaneous action selection
- Solved game
- Succinct game
concepts
- Bayes correlated equilibrium
- Bayesian Nash equilibrium
- Berge equilibrium
- Core
- Correlated equilibrium
- Epsilon-equilibrium
- Evolutionarily stable strategy
- Gibbs equilibrium
- Mertens-stable equilibrium
- Markov perfect equilibrium
- Nash equilibrium
- Pareto efficiency
- Perfect Bayesian equilibrium
- Proper equilibrium
- Quantal response equilibrium
- Quasi-perfect equilibrium
- Risk dominance
- Satisfaction equilibrium
- Self-confirming equilibrium
- Sequential equilibrium
- Shapley value
- Strong Nash equilibrium
- Subgame perfection
- Trembling hand
of games
- Go
- Chess
- Infinite chess
- Checkers
- Tic-tac-toe
- Prisoner's dilemma
- Gift-exchange game
- Optional prisoner's dilemma
- Traveler's dilemma
- Coordination game
- Chicken
- Centipede game
- Lewis signaling game
- Volunteer's dilemma
- Dollar auction
- Battle of the sexes
- Stag hunt
- Matching pennies
- Ultimatum game
- Rock paper scissors
- Pirate game
- Dictator game
- Public goods game
- Blotto game
- War of attrition
- El Farol Bar problem
- Fair division
- Fair cake-cutting
- Cournot game
- Deadlock
- Diner's dilemma
- Guess 2/3 of the average
- Kuhn poker
- Nash bargaining game
- Induction puzzles
- Trust game
- Princess and monster game
- Rendezvous problem
figures
- Albert W. Tucker
- Amos Tversky
- Antoine Augustin Cournot
- Ariel Rubinstein
- Claude Shannon
- Daniel Kahneman
- David K. Levine
- David M. Kreps
- Donald B. Gillies
- Drew Fudenberg
- Eric Maskin
- Harold W. Kuhn
- Herbert Simon
- Hervé Moulin
- John Conway
- Jean Tirole
- Jean-François Mertens
- Jennifer Tour Chayes
- John Harsanyi
- John Maynard Smith
- John Nash
- John von Neumann
- Kenneth Arrow
- Kenneth Binmore
- Leonid Hurwicz
- Lloyd Shapley
- Melvin Dresher
- Merrill M. Flood
- Olga Bondareva
- Oskar Morgenstern
- Paul Milgrom
- Peyton Young
- Reinhard Selten
- Robert Axelrod
- Robert Aumann
- Robert B. Wilson
- Roger Myerson
- Samuel Bowles
- Suzanne Scotchmer
- Thomas Schelling
- William Vickrey
- All-pay auction
- Alpha–beta pruning
- Bertrand paradox
- Bounded rationality
- Combinatorial game theory
- Confrontation analysis
- Coopetition
- Evolutionary game theory
- First-move advantage in chess
- Glossary of game theory
- List of game theorists
- List of games in game theory
- No-win situation
- Paradox of tolerance
- Solving chess
- Topological game
- Tragedy of the commons
- Tyranny of small decisions