View source for Software:Information set (game theory)

{{Short description|Concept in 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|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|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 [[Software:Strategy (game theory)|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.
[[File:Cuban Missile Crisis Game Tree.svg|thumb|Figure 1: A game tree which depicts each player's possible information set by showing the options at each vertex (A and B for player's 1 and 2 respectively)]]
Information sets are used in extensive form games and are often depicted in [[Game tree|game tree]]s. 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|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 [[Biography:John von Neumann|John von Neumann]], motivated by studying the game of [[Engineering:Poker|Poker]].

==Example==
[[File:Battle of the sexes - perfect information.png|320 px|right|Battle of the sexes 1]]
[[File:Battle of the sexes - imperfect information.png|320 px|right|Battle of the sexes 2]]

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 {{not a typo|O(pera)}} or {{not a typo|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 {{not a typo|O(pera)}} safely because ''once player 2 knows'' that player 1 has chosen opera, player 2 would rather go along for {{not a typo|o(pera)}} and get '''2''' than choose {{not a typo|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|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 {{not a typo|f(ootball)}} 2/5 of the time

{{col-begin|width=100%}}
{{col-break|width=50%}}
{| class="wikitable" style="margin-left: auto; margin-right: auto; border: none;"
|+ align="bottom"|''Normal form with player 2 aware of player 1's move''
! width="90px" {{diagonal split header|<br />Player 1|Player 2}}
! width="50px"| Oo, Fo
! width="50px"| Oo, Ff
! width="50px"| Of, Fo
! width="50px"| Of, Ff
|-
!O
|{{diagonal split header|{{red|3}} | {{blue|2}} |transparent}}
|{{diagonal split header|{{red|3}}| {{blue|2}} |transparent}}
|{{diagonal split header|{{red|0}}| {{blue|0}} |transparent}}
|{{diagonal split header|{{red|0}} | {{blue|0}}|transparent}}
|-
!F
|{{diagonal split header|{{red|0}}| {{blue|0}} |transparent}}
|{{diagonal split header|{{red|2}} | {{blue|3}}|transparent}}
|{{diagonal split header|{{red|0}} | {{blue|0}}|transparent}}
|{{diagonal split header|{{red|2}} | {{blue|3}} |transparent}}
|}
{{col-break|width=50%}}
{| class="wikitable" style="margin-left: auto; margin-right: auto; border: none;"
|+ align="bottom"|''Normal form with player 2 unaware of player 1's move''
! width="90px" {{diagonal split header|<br />Player 1|Player 2}}
! width="50px"| o
! width="50px"| f
|-
!O
|{{diagonal split header|{{red|3}} | {{blue|2}} |transparent}}
|{{diagonal split header|{{red|0}} | {{blue|0}}|transparent}}
|-
!F
|{{diagonal split header|{{red|0}}| {{blue|0}} |transparent}}
|{{diagonal split header|{{red|2}} | {{blue|3}} |transparent}}
|}
{{col-end}}

==See also==
* Self-confirming equilibrium

==References==
* {{cite book |first=Ken |last=Binmore |title=Game Theory: A very short introduction |publisher=Oxford University Press |year=2007 |isbn=978-0-19-921846-2 |pages=88–89 |url=https://books.google.com/books?id=hRB34xDNc2AC&pg=88 }}

{{Game theory}}

{{DEFAULTSORT:Information Set (Game Theory)}}
[[Category:Game theory]]

{{Sourceattribution|Information set (game theory)|1}}