Normal-form game

Last updated

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.

Contents

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 2

Player 1
LeftRight
Top4, 3−1, −1
Bottom0, 03, 4

The matrix provided 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

A partial topology of two-player, two-strategy games, including such games as Prisoner's dilemma, Stag hunt, and Chicken 2x2chart110602.pdf
A partial topology of two-player, two-strategy games, including such games as Prisoner's dilemma, Stag hunt, and Chicken

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
Player 2

Player 1
StagHare
Stag3, 30, 2
Hare2, 02, 2
Just row
Player 2

Player 1
StagHare
Stag30
Hare22

The topological space of games with related payoff matrices can also be mapped, with adjacent games having the most similar matrices. This shows how incremental incentive changes can change the game.

Uses of normal form

Dominated strategies

The Prisoner's Dilemma
Player 2

Player 1
CooperateDefect
Cooperate−1, −1−5, 0
Defect0, −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, 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 a long time. 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 game with subgame imperfect and perfect Nash equilibria marked with red and blue respectively. SGPNEandPlainNE explainingexample.svg
Both extensive and normal form illustration of a sequential game with subgame imperfect and perfect Nash equilibria marked with red and blue respectively.
A sequential game
Player 2

Player 1
Left, LeftLeft, RightRight, LeftRight, Right
Top4, 34, 3−1, −1−1, −1
Bottom0, 03, 40, 03, 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:

  1. Left if player 1 plays Top and Left otherwise
  2. Left if player 1 plays Top and Right otherwise
  3. Right if player 1 plays Top and Left otherwise
  4. 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:

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

such that

A payoff function is a function

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

where:

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.

Related Research Articles

In linear algebra, the determinant is a scalar value that can be computed from the elements of a square matrix and encodes certain properties of the linear transformation described by the matrix. The determinant of a matrix A is denoted det(A), det A, or |A|. Geometrically, it can be viewed as the volume scaling factor of the linear transformation described by the matrix. This is also the signed volume of the n-dimensional parallelepiped spanned by the column or row vectors of the matrix. The determinant is positive or negative according to whether the linear mapping preserves or reverses the orientation of n-space.

In mathematics, a linear map is a mapping VW between two modules that preserves the operations of addition and scalar multiplication. If a linear map is a bijection then it is called a linear isomorphism.

The prisoner's dilemma is a standard example of a game analyzed in game theory that shows why two completely rational individuals might not cooperate, even if it appears that it is in their best interests to do so. It was originally framed by Merrill Flood and Melvin Dresher while working at RAND in 1950. Albert W. Tucker formalized the game with prison sentence rewards and named it "prisoner's dilemma", presenting it as follows:

Two members of a criminal gang are arrested and imprisoned. Each prisoner is in solitary confinement with no means of communicating with the other. The prosecutors lack sufficient evidence to convict the pair on the principal charge, but they have enough to convict both on a lesser charge. Simultaneously, the prosecutors offer each prisoner a bargain. Each prisoner is given the opportunity either to betray the other by testifying that the other committed the crime, or to cooperate with the other by remaining silent. The possible outcomes are:

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.

Normal (geometry) in geometry, an object that is perpendicular to a given object

In geometry, a normal is an object such as a line, ray, or vector that is perpendicular to a given object. For example, in two dimensions, the normal line to a curve at a given point is the line perpendicular to the tangent line to the curve at the point. A normal vector may have length one or its length may represent the curvature of the object ; its algebraic sign may indicate sides.

In mathematics, particularly in matrix theory, a permutation matrix is a square binary matrix that has exactly one entry of 1 in each row and each column and 0s elsewhere. Each such matrix, say P, represents a permutation of m elements and, when used to multiply another matrix, say A, results in permuting the rows or columns of the matrix A.

In linear algebra, a square matrix  is called diagonalizable or nondefective if it is similar to a diagonal matrix, i.e., if there exists an invertible matrix  and a diagonal matrix such that , or equivalently . For a finite-dimensional vector space , a linear map  is called diagonalizable if there exists an ordered basis of  consisting of eigenvectors of . These definitions are equivalent: if  has a matrix representation as above, then the column vectors of  form a basis of eigenvectors of , and the diagonal entries of  are the corresponding eigenvalues of ; with respect to this eigenvector basis,  is represented by . Diagonalization is the process of finding the above  and .

Triangular matrix special kind of square matrix

In the mathematical discipline of linear algebra, a triangular matrix is a special kind of square matrix. A square matrix is called lower triangular if all the entries above the main diagonal are zero. Similarly, a square matrix is called upper triangular if all the entries below the main diagonal are zero. A triangular matrix is one that is either lower triangular or upper triangular. A matrix that is both upper and lower triangular is called a diagonal matrix.

In statistics, the matrix normal distribution or matrix Gaussian distribution is a probability distribution that is a generalization of the multivariate normal distribution to matrix-valued random variables.

In linear algebra, linear transformations can be represented by matrices. If is a linear transformation mapping to and is a column vector with entries, then

In linear algebra, a circulant matrix is a special kind of Toeplitz matrix where each row vector is rotated one element to the right relative to the preceding row vector. In numerical analysis, circulant matrices are important because they are diagonalized by a discrete Fourier transform, and hence linear equations that contain them may be quickly solved using a fast Fourier transform. They can be interpreted analytically as the integral kernel of a convolution operator on the cyclic group and hence frequently appear in formal descriptions of spatially invariant linear operations.

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 game theory, a symmetric game is a game where the payoffs for playing a particular strategy depend only on the other strategies employed, not on who is playing them. If one can change the identities of the players without changing the payoff to the strategies, then a game is symmetric. Symmetry can come in different varieties. Ordinally symmetric games are games that are symmetric with respect to the ordinal structure of the payoffs. A game is quantitatively symmetric if and only if it is symmetric with respect to the exact payoffs. A partnership game is a symmetric game where both players receive identical payoffs for any strategy set. That is, the payoff for playing strategy a against strategy b receives the same payoff as playing strategy b against strategy a.

In the mathematical discipline of matrix theory, a Jordan block over a ring is a matrix composed of zeroes everywhere except for the diagonal, which is filled with a fixed element , and for the superdiagonal, which is composed of ones. The concept is named after Camille Jordan.

In linear algebra, eigendecomposition or sometimes spectral decomposition is the factorization of a matrix into a canonical form, whereby the matrix is represented in terms of its eigenvalues and eigenvectors. Only diagonalizable matrices can be factorized in this way.

Trace diagram

In mathematics, trace diagrams are a graphical means of performing computations in linear and multilinear algebra. They can be represented as graphs in which some edges are labeled by matrices. The simplest trace diagrams represent the trace and determinant of a matrix. Several results in linear algebra, such as Cramer's Rule and the Cayley–Hamilton theorem, have simple diagrammatic proofs. They are closely related to Penrose's graphical notation.

A continuous game is a mathematical concept, used in game theory, that generalizes the idea of an ordinary game like tic-tac-toe or checkers (draughts). In other words, it extends the notion of a discrete game, where the players choose from a finite set of pure strategies. The continuous game concepts allows games to include more general sets of pure strategies, which may be uncountably infinite.

In mathematics, and in particular the study of game theory, a function is graph continuous if it exhibits the following properties. The concept was originally defined by Partha Dasgupta and Eric Maskin in 1986 and is a version of continuity that finds application in the study of continuous games.

In game theory, the common ways to describe a game are the normal form and the extensive form. The graphical form is an alternate compact representation of a game using the interaction among participants.

Matrix (mathematics) Two-dimensional array of numbers with specific operations

In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions, arranged in rows and columns. For example, the dimension of the matrix below is 2 × 3, because there are two rows and three columns:

References