Information set (game theory)
- Information set (game theory)
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 so far. 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:
# 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.
Example
At the right are two versions of the battle of the sexes (game theory) game, shown in extensive form.
The first game is simply sequential-when player 2 has the chance to move, they are 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, they are 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 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.
Wikimedia Foundation.
2010.
Look at other dictionaries:
Information set — may refer to: * Information set (game theory), in game theory, a particular set of possible moves a player has in a game * XML Information Set or Infoset, a W3C specification dealing with XML documents … Wikipedia
Game theory — is a branch of applied mathematics that is used in the social sciences (most notably economics), biology, engineering, political science, computer science (mainly for artificial intelligence), and philosophy. Game theory attempts to… … Wikipedia
game theory — a mathematical theory that deals with strategies for maximizing gains and minimizing losses within prescribed constraints, as the rules of a card game: widely applied in the solution of various decision making problems, as those of military… … Universalium
List of games in game theory — Game theory studies strategic interaction between individuals in situations called games. Classes of these games have been given names. This is a list of the most commonly studied games.Explanation of featuresGames can have several features, a… … Wikipedia
Strategy (game theory) — In game theory, a player s strategy in a game is a complete plan of action for whatever situation might arise; this fully determines the player s behaviour. A player s strategy will determine the action the player will take at any stage of the… … Wikipedia
Combinatorial game theory — This article is about the theory of combinatorial games. For the theory that includes games of chance and games of imperfect knowledge, see Game theory. Mathematicians playing Konane at a Combinatorial game theory workshop (for technical content … Wikipedia
Core (game theory) — The core is the set of feasible allocations that cannot be improved upon by a subset (a coalition) of the economy s consumers. A coalition is said to improve upon or block a feasible allocation if the members of that coalition are better off… … Wikipedia
Outcome (game theory) — In game theory, an outcome is a set of moves or strategies taken by the players, or their payoffs resulting from the actions or strategies taken by all players. The two are complementary in that, given knowledge of the set of strategies of all… … Wikipedia
Generalized game theory — is an extension of game theory to incorporate social theory concepts such as norm, value, belief, role, social relationship, and institution. The theory was developed by Tom R. Burns and has not had great influence beyond his immediate associates … Wikipedia
Deadlock (game theory) — C D c 1, 1 0, 3 d 3, 0 2, 2 In game theory, Deadlock is a game where the action that is mutually most beneficial is also dominant. (An example payoff matrix for Deadlock is pictured to the right.) This provides a contrast to the Prisoner s… … Wikipedia
