 Normalform game

In game theory, normal form is a way of describing a game. Unlike extensive form, normalform 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 extensiveform representations. The normalform representation of a game includes all perceptible and conceivable strategies, and their corresponding payoffs, of each player.
In static games of complete, perfect information, a normalform representation of a game is a specification of players' strategy spaces and payoff functions. A strategy space for a player is the set of all strategies available to that player, where a strategy is a complete plan of action for every stage of the game, regardless of whether that stage actually arises in play. A payoff function for a player is a mapping from the crossproduct of players' strategy spaces to that player's set of payoffs (normally the set of real numbers, where the number represents a cardinal or ordinal utility—often cardinal in the normalform representation) of a player, i.e. the payoff function of a player takes as its input a strategy profile (that is a specification of strategies for every player) and yields a representation of payoff as its output.
Contents
An example
A normalform game Player 1 \ Player 2 Player 2 chooses left Player 2 chooses right Player 1 chooses top 4, 3 −1, −1 Player 1 chooses bottom 0, 0 3, 4 The matrix to the right is a normalform representation of a game in which players move simultaneously (or at least do not observe the other player's move before making their own) and receive the payoffs as specified for the combinations of actions played. For example, if player 1 plays top and player 2 plays left, player 1 receives 4 and player 2 receives 3. In each cell, the first number represents the payoff to the row player (in this case player 1), and the second number represents the payoff to the column player (in this case player 2).
Other representations
Often symmetric games (where the payoffs do not depend on which player chooses each action) are represented with only one payoff. This is the payoff for the row player. For example, the payoff matrices on the right and left below represent the same game.
Both players Stag Hare Stag 3, 3 0, 2 Hare 2, 0 2, 2 Just row Stag Hare Stag 3 0 Hare 2 2 Uses of normal form
Dominated strategies
The Prisoner's Dilemma Cooperate Defect Cooperate −1, −1 −5, 0 Defect 0, −5 −2, −2 The payoff matrix facilitates elimination of dominated strategies, and it is usually used to illustrate this concept. For example, in the prisoner's dilemma (to the right), we can see that each prisoner can either "cooperate" or "defect". If exactly one prisoner defects, he gets off easily and the other prisoner is locked up for good. However, if they both defect, they will both be locked up for longer. One can determine that Cooperate is strictly dominated by Defect. One must compare the first numbers in each column, in this case 0 > −1 and −2 > −5. This shows that no matter what the column player chooses, the row player does better by choosing Defect. Similarly, one compares the second payoff in each row; again 0 > −1 and −2 > −5. This shows that no matter what row does, column does better by choosing Defect. This demonstrates the unique Nash equilibrium of this game is (Defect, Defect).
Sequential games in normal form
A sequential game Left, Left Left, Right Right, Left Right, Right Top 4, 3 4, 3 −1, −1 −1, −1 Bottom 0, 0 3, 4 0, 0 3, 4 These matrices only represent games in which moves are simultaneous (or, more generally, information is imperfect). The above matrix does not represent the game in which player 1 moves first, observed by player 2, and then player 2 moves, because it does not specify each of player 2's strategies in this case. In order to represent this sequential game we must specify all of player 2's actions, even in contingencies that can never arise in the course of the game. In this game, player 2 has actions, as before, Left and Right. Unlike before he has four strategies, contingent on player 1's actions. The strategies are:
 Left if player 1 plays Top and Left otherwise
 Left if player 1 plays Top and Right otherwise
 Right if player 1 plays Top and Left otherwise
 Right if player 1 plays Top and Right otherwise
On the right is the normalform representation of this game.
General formulation
In order for a game to be in normal form, we are provided with the following data:
 There is a finite set P of players, which we label {1, 2, ..., m}
 Each player k in P has a finite number of pure strategies
A pure strategy profile is an association of strategies to players, that is an mtuple
such that
A payoff function is a functionwhose intended interpretation is the award given to a single player at the outcome of the game. Accordingly, to completely specify a game, the payoff function has to be specified for each player in the player set P= {1, 2, ..., m}.
Definition: A game in normal form is a structure
where:
is a set of players,
is an mtuple of pure strategy sets, one for each player, and
is an mtuple of payoff functions.
References
 D. Fudenberg and J. Tirole, Game Theory, MIT Press, 1991.
 LeytonBrown, Kevin; Shoham, Yoav (2008), Essentials of Game Theory: A Concise, Multidisciplinary Introduction, San Rafael, CA: Morgan & Claypool Publishers, ISBN 9781598295931, http://www.gtessentials.org. An 88page mathematical introduction; free online at many universities.
 R. D. Luce and H. Raiffa, Games and Decisions, Dover Publications, 1989.
 Shoham, Yoav; LeytonBrown, Kevin (2009), Multiagent Systems: Algorithmic, GameTheoretic, and Logical Foundations, New York: Cambridge University Press, ISBN 9780521899437, http://www.masfoundations.org. A comprehensive reference from a computational perspective; see Chapter 3. Downloadable free online.
 J. Weibull, Evolutionary Game Theory, MIT Press, 1996
 J. von Neumann and O. Morgenstern, Theory of games and Economic Behavior, John Wiley Science Editions, 1964. This book was initially published by Princeton University Press in 1944.
External links
Categories:
Wikimedia Foundation. 2010.
См. также в других словарях:
Game  получить на Академике активный купон DHgate или выгодно game купить по низкой цене на распродаже в DHgate
normal form game — noun Formally, a structure where P = 1,2, ...,m is a set of players, is an m tuple of pure strategy sets, one for each player, and is an m tuple of payoff functions. <! If someone can turn the math to inline math, please do it. See Also:… … Wiktionary
Normal form — may refer to: Normal form (abstract rewriting) Normal form (databases) Normal form (game theory) Normal form (mathematics) In formal language theory: Beta normal form Chomsky normal form Greibach normal form Kuroda normal form Normal form… … Wikipedia
normal form — noun a) Any of various forms of a relational database providing criteria for determining a tables degree of vulnerability to logical inconsistencies and anomalies. b) A matrix that represents the possible outcomes of a game … Wiktionary
extensive form game — noun Informally, a representation of a game as a tree of decision nodes, with the game beginning at a unique initial node, and flowing through the tree along a path determined by the players until a terminal node is reached, where play ends and… … Wiktionary
Extensiveform game — An extensive form game is a specification of a game in game theory. This form represents the game as a tree. Each node (called a decision node) represents every possible state of play of the game as it is played. Play begins at a unique initial… … 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
Game localisation — refers to the preparation of video games for other locales. This adaptation to the standards of other countries covers far more than simply translation of language. There are different areas, such as linguistic, cultural, hardware and software,… … Wikipedia
Game development — is the process by which a game is produced. Today this term most commonly refers to the development of video games.OverviewDevelopment of video games is undertaken by a developer, which may be a single person or a large business. Typically, large … Wikipedia
Game Boy Advance — GBA redirects here. For other uses, see GBA (disambiguation). Game Boy Advance … Wikipedia