Perfect information

Last updated
Chess is an example of a game of perfect information. Final Position of Lawrence-Tan 2002.png
Chess is an example of a game of perfect information.

In economics, perfect information (sometimes referred to as "no hidden information") is a feature of perfect competition. With perfect information in a market, all consumers and producers have perfect and instantaneous knowledge of all market prices, their own utility, and own cost functions.

Contents

In game theory, a sequential game has perfect information if each player, when making any decision, is perfectly informed of all the events that have previously occurred, including the "initialization event" of the game (e.g. the starting hands of each player in a card game). [1] [2] [3] [4]

Perfect information is importantly different from complete information, which implies common knowledge of each player's utility functions, payoffs, strategies and "types". A game with perfect information may or may not have complete information.

Examples

Backgammon includes chance events, but by some definitions is classified as a game of perfect information. Backgammon lg.png
Backgammon includes chance events, but by some definitions is classified as a game of perfect information.
Texas hold'em is a game of imperfect information, as players do not know the private cards of their opponents Texas Hold 'em Hole Cards.jpg
Texas hold'em is a game of imperfect information, as players do not know the private cards of their opponents

Chess is an example of a game with perfect information as each player can see all the pieces on the board at all times. [2] Other examples of games with perfect information include tic-tac-toe, checkers, infinite chess, and Go. [3]

Card games where each player's cards are hidden from other players such as poker and bridge are examples of games with imperfect information. [5] [6]

Academic literature has not produced consensus on a standard definition of perfect information which defines whether games with chance, but no secret information, and games without simultaneous moves are games of perfect information. [7] [8] [9] [10] [4]

Games which are sequential (players alternate in moving) and which have chance events (with known probabilities to all players) but no secret information, are sometimes considered games of perfect information. This includes games such as backgammon and Monopoly. But there are some academic papers which do not regard such games as games of perfect information because the results of chance themselves are unknown prior to them occurring. [7] [8] [9] [10] [4]

Games with simultaneous moves are generally not considered games of perfect information. This is because each of the players holds information which is secret, and must play a move without knowing the opponent's secret information. Nevertheless, some such games are symmetrical, and fair. An example of a game in this category includes rock paper scissors. [7] [8] [9] [10] [4]

See also

Related Research Articles

Game theory The study of mathematical models of strategic interaction between rational decision-makers

Game theory is the study of mathematical models of strategic interaction among rational decision-makers. It has applications in all fields of social science, as well as in logic, systems science and computer science. Originally, it addressed zero-sum games, in which each participant's gains or losses are exactly balanced by those of the other participants. Today, game theory applies to a wide range of behavioral relations, and is now an umbrella term for the science of logical decision making in humans, animals, and computers.

In game theory, the Nash equilibrium, named after the mathematician John Forbes Nash Jr., is a proposed solution of a non-cooperative 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 their own strategy.

Combinatorial game theory branch of game theory about two-player sequential games with perfect information

Combinatorial game theory (CGT) is a branch of mathematics and theoretical computer science that typically studies sequential games with perfect information. Study has been largely confined to two-player games that have a position in which the players take turns changing in defined ways or moves to achieve a defined winning condition. CGT has not traditionally studied games of chance or those that use imperfect or incomplete information, favoring games that offer perfect information in which the state of the game and the set of available moves is always known by both players. However, as mathematical techniques advance, the types of game that can be mathematically analyzed expands, thus the boundaries of the field are ever changing. Scholars will generally define what they mean by a "game" at the beginning of a paper, and these definitions often vary as they are specific to the game being analyzed and are not meant to represent the entire scope of the field.

In game theory, a player's strategy is any of the options which he or she chooses in a setting where the outcome depends not only on their own actions but on the actions of others. A player's strategy will determine the action which the player will take at any stage of the game.

In game theory, battle of the sexes (BoS) is a two-player coordination game. Some authors refer to the game as Bach or Stravinsky and designate the players simply as Player 1 and Player 2, rather than assigning sex.

Solution concept formal rule for predicting how a strategic game will be played

In game theory, a solution concept is a formal rule for predicting how a game will be played. These predictions are called "solutions", and describe which strategies will be adopted by players and, therefore, the result of the game. The most commonly used solution concepts are equilibrium concepts, most famously Nash equilibrium.

An extensive-form game is a specification of a game in game theory, allowing for the explicit representation of a number of key 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 they make a decision, and their payoffs for all possible game outcomes. Extensive-form games also allow for the representation of incomplete information in the form of chance events modeled as "moves by nature".

In economics and game theory, complete information is an economic situation or game in which knowledge about other market participants or players is available to all participants. The utility functions, payoffs, strategies and "types" of players are thus common knowledge. Complete information is the concept that each player in the game is aware of the sequence, strategies, and payoffs throughout gameplay. Given this information, the players have the ability to plan accordingly based on the information to maximize their own strategies and utility at the end of the game.

Ariel Rubinstein Israeli economist

Ariel Rubinstein is an Israeli economist who works in Economic Theory, Game Theory and Bounded Rationality.

In game theory, normal form is a description of a game. Unlike extensive form, normal-form representations are not graphical per se, but rather represent the game by way of a matrix. While this approach can be of greater use in identifying strictly dominated strategies and Nash equilibria, some information is lost as compared to extensive-form representations. The normal-form representation of a game includes all perceptible and conceivable strategies, and their corresponding payoffs, for each player.

Sequential game class of turn-based game in which one player chooses their action before the others choose theirs

In game theory, a sequential game is a game where one player chooses their action before the others choose theirs. Importantly, the later players must have some information of the first's choice, otherwise the difference in time would have no strategic effect. Sequential games hence are governed by the time axis, and represented in the form of decision trees.

Backward induction is the process of reasoning backwards in time, from the end of a problem or situation, to determine a sequence of optimal actions. It proceeds by first considering the last time a decision might be made and choosing what to do in any situation at that time. Using this information, one can then determine what to do at the second-to-last time of decision. This process continues backwards until one has determined the best action for every possible situation at every point in time. It was first used by Zermelo in 1913, to prove that chess has pure optimal strategies.

Determinacy is a subfield of set theory, a branch of mathematics, that examines the conditions under which one or the other player of a game has a winning strategy, and the consequences of the existence of such strategies. Alternatively and similarly, "determinacy" is the property of a game whereby such a strategy exists.

In game theory, trembling hand perfect equilibrium is a refinement of Nash equilibrium due to Reinhard Selten. A trembling hand perfect equilibrium is an equilibrium that takes the possibility of off-the-equilibrium play into account by assuming that the players, through a "slip of the hand" or tremble, may choose unintended strategies, albeit with negligible probability.

In game theory, folk theorems are a class of theorems describing an abundance of Nash equilibrium payoff profiles in repeated games. The original Folk Theorem concerned the payoffs of all the Nash equilibria of an infinitely repeated game. This result was called the Folk Theorem because it was widely known among game theorists in the 1950s, even though no one had published it. Friedman's (1971) Theorem concerns the payoffs of certain subgame-perfect Nash equilibria (SPE) of an infinitely repeated game, and so strengthens the original Folk Theorem by using a stronger equilibrium concept: subgame-perfect Nash equilibria rather than Nash equilibria.

In game theory, a repeated game is an extensive form game that consists of a number of repetitions of some base game. The stage game is usually one of the well-studied 2-person games. Repeated games capture the idea that a player will have to take into account the impact of his or her current action on the future actions of other players; this impact is sometimes called his or her reputation. Single stage game or single shot game are names for non-repeated games.

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. Informally, this means that if the players played any smaller game that consisted of only one part of the larger game, their behavior would represent a Nash equilibrium of that smaller game. Every finite extensive game with perfect recall has a subgame perfect equilibrium.

Simultaneous game class of game where each player chooses their action without knowledge of the actions chosen by other players

In game theory, a simultaneous game or static game is a game where each player chooses their action without knowledge of the actions chosen by other players. Simultaneous games contrast with sequential games, which are played by the players taking turns. In other words, both players normally act at the same time in a simultaneous game. Even if the players do not act at the same time, both players are uninformed of each other's move while making their decisions. Normal form representations are usually used for simultaneous games. Given a continuous game, players will have different information sets if the game is simultaneous than if it is sequential because they have less information to act on at each step in the game. For example, in a two player continuous game that is sequential, the second player can act in response to the action taken by the first player. However, this is not possible in a simultaneous game where both players act at the same time.

The one-shot deviation principle is the principle of optimality of dynamic programming applied to game theory. It says that a strategy profile of a finite extensive-form game is a subgame perfect equilibrium (SPE) if and only if there exist no profitable one-shot deviations for each subgame and every player. In simpler terms, if no player can increase their payoffs by deviating a single decision, or period, from their original strategy, then the strategy that they have chosen is a SPE. As a result, no player can profit from deviating from the strategy for one period and then reverting to the strategy.

References

  1. Osborne, M. J.; Rubinstein, A. (1994). "Chapter 6: Extensive Games with Perfect Information". A Course in Game Theory. Cambridge, Massachusetts: The MIT Press. ISBN   0-262-65040-1.
  2. 1 2 Khomskii, Yurii (2010). "Infinite Games (section 1.1)" (PDF).
  3. 1 2 "Infinite Chess". PBS Infinite Series. March 2, 2017. Perfect information defined at 0:25, with academic sources arXiv : 1302.4377 and arXiv : 1510.08155.
  4. 1 2 3 4 Mycielski, Jan (1992). "Games with Perfect Information". Handbook of Game Theory with Economic Applications. Volume 1. pp. 41–70. doi:10.1016/S1574-0005(05)80006-2.
  5. Thomas, L. C. (2003). Games, Theory and Applications . Mineola New York: Dover Publications. p.  19. ISBN   0-486-43237-8.
  6. Osborne, M. J.; Rubinstein, A. (1994). "Chapter 11: Extensive Games with Imperfect Information". A Course in Game Theory. Cambridge Massachusetts: The MIT Press. ISBN   0-262-65040-1.
  7. 1 2 3 Chen, Su-I Lu, Vekhter. "Game Theory: Rock, Paper, Scissors".CS1 maint: uses authors parameter (link)
  8. 1 2 3 Ferguson, Thomas S. "Game Theory" (PDF). UCLA Department of Mathematics. pp. 56–57.
  9. 1 2 3 Burch; Johanson; Bowling. "Solving Imperfect Information Games Using Decomposition". Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence.
  10. 1 2 3 "Complete vs Perfect Information in Combinatorial Game Theory". Stack Exchange . June 24, 2014.

Further reading