Information set (game theory)

In game theory, an information set is the basis for decision making in a game, which includes the actions available to players and the potential outcomes of each action. It consists of a collection of decision nodes that a player cannot distinguish between when making a move, due to incomplete information about previous actions or the current state of the game. In other words, when a player's turn comes, they may be uncertain about which exact node in the game tree they are currently at, and the information set represents all the possibilities they must consider. Information sets are a fundamental concept particularly important in games with imperfect information.^[1]

In games with perfect information (such as chess or Go), every information set contains exactly one decision node, as each player can observe all previous moves and knows the exact game state. However, in games with imperfect information—such as most card games like poker or bridge—information sets may contain multiple nodes, reflecting the player's uncertainty about the true state of the game.^[2] This uncertainty fundamentally changes how players must reason about optimal strategies.

The concept of information set was introduced by John von Neumann, motivated by his study of poker, and is now essential to the analysis of sequential games and the development of solution concepts such as subgame perfect equilibrium and perfect Bayesian equilibrium.^[3]

Information sets are primarily used in extensive form representations of games and are typically depicted in game trees. A game tree shows all possible paths from the start of a game to its various endings, with branches representing the choices available to players at each decision point.

For games with imperfect information, the challenge lies in representing situations where a player cannot determine their exact position in the game. For example, in a card game, a player knows their own cards but not their opponent's cards, creating uncertainty about the true game state. This uncertainty is modeled using information sets.

Information sets are typically represented in game trees using dotted lines connecting indistinguishable nodes, ovals encompassing multiple nodes, or similar notations indicating that a player cannot tell which of several positions they are actually in. This visual representation helps analyze how uncertainty affects optimal play.

An information set in an extensive form game must satisfy the following properties:

1. Every node in the information set belongs to the same player.
2. The player cannot distinguish between any nodes within the same information set based on their available information.
3. All nodes in the same information set must have identical available actions.
4. No node in an information set can be an ancestor of another node in the same set (this would create a logical impossibility in the game timeline).

The structure of information sets profoundly affects strategic reasoning. When a player faces an information set with multiple nodes, they must formulate strategies that are optimal across all possible game states represented by that information set.

This leads to several important game-theoretic concepts:

• Mixed strategies often become necessary when facing uncertainty, as pure strategies might be exploitable by opponents who can predict them.
• Bayesian updating occurs as players update their beliefs about which node in an information set they are at based on observed actions.
• Signaling and information revelation become strategic considerations, as players may take actions specifically to reveal or conceal information.

In games with multiple information sets, the strategic interaction becomes dynamic rather than static. Players must reason not just about current decisions but about future information sets that might arise.

The standard solution technique for such games is backward induction, where players reason from the end of the game toward the beginning. For example, when player A chooses first, player B will make the best decision for themselves based on A's choice and their own information set at that time. Player A, anticipating this reaction, makes their initial choice to maximize their own payoff.

This sequential reasoning process is complicated in games with imperfect information, requiring more sophisticated solution concepts like sequential equilibrium that account for beliefs about which node in an information set a player is actually at.

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:

1. Both choose opera
2. both choose football
3. or both use a mixed strategy, with player 1 choosing O(pera) 3/5 of the time and choosing football 2/5 of the time, and player 2 choosing f(ootball) 3/5 of the time and opera 2/5 of the time

• Self-confirming equilibrium

• Binmore, Ken (2007). Game Theory: A very short introduction. Oxford University Press. pp. 88–89. ISBN 978-0-19-921846-2.