Normal-form game

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.

In static games of complete, perfect information, a normal-form 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, whereas 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 cross-product 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 normal-form 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.

An example

A normal-form 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 normal-form 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 a shorter time. 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

Both extensive and normal form illustration of a sequential form game with subgame imperfect and perfect Nash equilibriium marked with red and blue respectively.

*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 normal-form 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

S_k = \{1, 2, \ldots, n_k\}.

A pure strategy profile is an association of strategies to players, that is an m-tuple

\vec{s} = (s_1, s_2, \ldots,s_m)

such that

s_1 \in S_1, s_2 \in S_2, \ldots, s_m \in S_m

A payoff function is a function

F: S_1 \times S_2 \times \ldots \times S_m \rightarrow \mathbb{R}.

whose 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

G=\langle P, \mathbf{S}, \mathbf{F}\rangle

where:

P=\{1,2, \ldots , m\}

is a set of players,

\mathbf{S}= \{S_1, S_2, \ldots, S_m\}

is an m-tuple of pure strategy sets, one for each player, and

\mathbf{F} = \{F_1, F_2, \ldots, F_m\}

is an m-tuple of payoff functions.

References

D. Fudenberg and J. Tirole, Game Theory, MIT Press, 1991.
Leyton-Brown, Kevin; Shoham, Yoav (2008), Essentials of Game Theory: A Concise, Multidisciplinary Introduction, San Rafael, CA: Morgan & Claypool Publishers, ISBN 978-1-59829-593-1 . An 88-page mathematical introduction; free online at many universities.
R. D. Luce and H. Raiffa, Games and Decisions, Dover Publications, 1989.
Shoham, Yoav; Leyton-Brown, Kevin (2009), Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations, New York: Cambridge University Press, ISBN 978-0-521-89943-7 . 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. Which was originally published in 1944 by Princeton University Press.

External links

http://www.whalens.org/Sofia/choice/matrix.htm

Topics in game theory

Definitions	Normal-form game Extensive-form game Escalation of commitment Graphical game Cooperative game Succinct game Information set Hierarchy of beliefs Preference

Equilibrium concepts	Nash equilibrium Subgame perfection Mertens-stable equilibrium Bayesian-Nash Perfect Bayesian Trembling hand Proper equilibrium Epsilon-equilibrium Correlated equilibrium Sequential equilibrium Quasi-perfect equilibrium Evolutionarily stable strategy Risk dominance Core Shapley value Pareto efficiency Quantal response equilibrium Self-confirming equilibrium Strong Nash equilibrium Markov perfect equilibrium

Strategies	Dominant strategies Pure strategy Mixed strategy Tit for tat Grim trigger Collusion Backward induction Forward induction Markov strategy

Classes of games	Symmetric game Perfect information Simultaneous game Sequential game Repeated game Signaling game Cheap talk Zero-sum game Mechanism design Bargaining problem Stochastic game n-player game Large Poisson game Nontransitive game Global games Strictly determined game

Games	Prisoner's dilemma Traveler's dilemma Coordination game Chicken Centipede game Volunteer's dilemma Dollar auction Battle of the sexes Stag hunt Matching pennies Ultimatum game Rock-paper-scissors Pirate game Dictator game Public goods game Blotto games War of attrition El Farol Bar problem Fair division Fair cake-cutting Cournot game Deadlock Diner's dilemma Guess 2/3 of the average Kuhn poker Nash bargaining game Screening game Prisoners and hats puzzle Trust game Princess and monster game Monty Hall problem Rendezvous problem

Theorems	Minimax theorem Nash's theorem Purification theorem Folk theorem Revelation principle Arrow's impossibility theorem

Key figures	Albert W. Tucker Amos Tversky Ariel Rubinstein Daniel Kahneman David K. Levine David M. Kreps Donald B. Gillies Drew Fudenberg Eric Maskin Harold W. Kuhn Herbert Simon Hervé Moulin Jean Tirole Jean-François Mertens John Harsanyi John Maynard Smith John Nash John von Neumann Kenneth Arrow Kenneth Binmore Leonid Hurwicz Lloyd Shapley Melvin Dresher Merrill M. Flood Oskar Morgenstern Paul Milgrom Peyton Young Reinhard Selten Robert Aumann Robert B. Wilson Roger Myerson Samuel Bowles Thomas Schelling William Vickrey

See also	All-pay auction Alpha–beta pruning Bertrand paradox Bounded rationality Combinatorial game theory Confrontation analysis Coopetition List of game theorists List of games in game theory No-win situation Tragedy of the commons Tyranny of small decisions

This article is issued from Wikipedia - version of the Thursday, March 17, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.