Normal form

Normal form

What is a Normal form?

A normal form describes a simultaneous, finite game using matrix representation. The word „game“ is taken from the game theory which studies how to solve decision problems between participants of the game, most often between people.

Player 1/Player 2	action 1	action 2
action 1	1, 1	2, 2
action 2	3, 3	4, 4

The matrix representation give us a good view to the game so we can describe a game clearly.

A synonym for a normal form is „a strategic form“, because such a form describes strategies used in the game. Think “normal form” and “strategic form” as synonyms. You can use both terms interchangeably.

Tip: If you're unsure about terms I've just used (game, simultaneous, game theory and other weird words), you should skip directly to Terminology section and then come back. Don't be ashamed. Also, take a look at References and resources.

What is not a Normal form?

To be clear, a normal form is just a matrix representation of a game, nothing more.

Normal form is not a game itself.

Also, normal form is not a solution of a game. To solve a game the Nash Equilibrium can be used. The Nash Equilibrium is applied on the table and then results of the game are represented easily.

So a normal form displays assignment, progress and also a result of a game for each player who's playing the game.

Why a table?

Table is a simple thing to draw and to understand. Everyone knows and understands tables. If you put numbers into a table you can apply mathematical/statistical operations on them – for example add, subtract, average, sum and so on. Rows of a table can compete with columns.

So a table is a perfect solution to represent „a battle“ between players and their strategies.

What does „a table“ mean?

Every table has columns and rows. For a normal form table, rows represent all possible actions (we call them strategy profiles) for player 1 and columns represent all possible actions for player 2. A strategy is a set of all steps (strategy profiles).

We try to solve a decision problem between players by selecting the best strategy (how a player should behave to maximize his profit). Each player's decisions compete between other player's decisions. So options for a decision for both players would be the same. In each cell we see 2 numbers. A cell represents crossing of profiles (think decisions) for each player and the result is called a payoff (an outcome). A payoff means what each player is going to get (earn) from the game. So we can think the pair as „a battle“ of two numbers (decisions).

Depends on a strategy, we're trying to find, „the better“ number. The better is the higher or the lower.

Player 1/Player 2	a strategy profile A	a strategy profile B
a strategy profile A	1, 2	3, 4
a strategy profile B	5, 6	1, 8

For example, in the Prisoner's Dilemma problem, numbers can represent how many years each prisoner will stay in jail (the lower is the better) or how high is a utility (the higher is the better). Typically, the problem is formulated such that we're looking for the higher numbers. In such a way, the numbers could be comparable without any awareness. Everyone thinks that the bigger is the better.

If we're interested in a payoff for 1 player only (and ignore a payoff for the second player) the payoff can be just one number.

Player 1/Player 2	a strategy profile A	a strategy profile B
a strategy profile A	1	3
a strategy profile B	5	8

This is the way of Adam Smith's and his Invisible hand of the market [8]. For all time you would get the best profit ignoring the other's profit and the market will take care of itself. You can't apply the Nash equilibrium on this table.

Another thing that is very important is that every table has a finite number of rows and columns. Keep it in mind and keep reading.

Definition of Normal form

Could you imagine an infinite table? Such a table should have unlimited number of rows or columns. This table can be hardly drawn. To draw any table you have to know how many rows and columns you are going to draw. So the table has to be „finite“.

Because the table is finite it can represents just finite games. These games have finite number of players and each player has a finite number of strategies.

Then, the definition of a normal form is following [7].

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left ( I, \textstyle \left \{S^i\right \} _{i=1}^N \right )}

where

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle I = \left \{1,...,N\right \}} is set of players. As you can see, minimal number of players is 1 and maximum is not restricted but it has to be finite.

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left \{S^i\right \} _{i=1}^N = \left \{S^1 ,..., S^N \right \}}

is the set of strategies for player Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle i \in I} .

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle S^i} is finite too.

Definition of a Normal form game

A normal form becomes a normal form game once one specifies, for each player, a payoff function [7].

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle u^i : S \to R}

Then definition of normal form game can be extended as:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle \left ( I, \textstyle \left \{S^i\right \} _{i=1}^N, \left \{ u^i\right \} _{i=1}^N \right )}

At the end, each strategy profile (action) has an outcome.

A utility has to be expressed as a number. These number decisions are „synthetic“ and are made in a „robot way“. They don't reflect any feelings like sadness, happiness, envy, jealous and so on. For example, in The prisoner's dilemma each prison will decide without any sorrow for the other prisoner. In real world, feelings and emotions are a key part of any decision and their mathematical expressions are impossible.

So a utility expressed by a number could be understand as a simplification of the real world.

Finding the Nash equilibrium

Now we have a table representing a game using a normal form. What's next? Let's solve the game using the Nash Equilibrium. There is a rule saying that every finite game has at least one Nash Equilibrium [7]. Nash equilibrium is the best way not only for each player but also the best way for the whole group. Let's find it.

Nash Equilibrium

Player 1/Player 2	Player 2 decision A	Player 2 decision B
Player 1 decision A	1, 2	3, 4
Player 1 decision B	5, 6	1, 8

The best decision for the game is when player 1 chooses B and player 2 chooses A (5,6). Why? If player 2 tries to maximize his profit by selecting (1,8) his outcome would be greater (8>6). But outcome of the player 1 would be lesser (1<5) so this is not the „equilibrium“. Nobody can increase his profit by decreasing some other's profit. And this is what the Nash equilibrium is about.

Asymmetric tables

In this case, “an asymmetric“ means that table has different number of rows and columns. This happens if one of players has different number of strategies or we would like to track a sequential game.

A sequential game is such a game where decisions of one player depends on decisions made by other player. Player 1 saw the step of player 2 and then player 1 moved according to that step. So sequential game tracks game in the time.

To express a sequential game in a better way we can use an Extensive form.

Limitations of a Normal form

Because of representation, a Normal form can show only games where players decide simultaneously or don't know how other players moved before their decision.

Also, except the example mentioned at Asymmetric tables, a Normal form can't describe the time progress of a game.

Due to constraints of two sides (rows and columns) it's also hard to express a game for more than two players even though the formal definition allows it.

Terminology

• Game – in our meaning, game is a decision problem between 2 or more participants, most often people. The important part is that someone have to decide between some options. Any game has to have payoff (an outcome, a utility). If a game doesn't have any payoff, nobody want's to play it.
• Game theory – how to solve problems between people using mathematical models. Game theory studies how people will decide when a conflict occurs.
• Normal form – representation of a game, a description. If you take a look at the normal form then you can explain game for every player in every stage (round) of the game and you know what each player earns (payoffs).
• Strategic form – just another term for a Normal form. A synonym.
• Simultaneous game – a game in which each player decides without a knowledge of other player's decisions. So it's the same as they move simultaneously. In a simultaneous game, no sequence can be described. If we would like to describe a sequence between moves then we should to move to sequential games.
• Sequential game – a game where we use movement descriptions. For example, Adam will choose „Forward“, then Bob will choose „Left“, then Adam „Forward“, and so on.
• Strategy profile – a part of a strategy. One step in a strategy which generates a payoff.
• Strategy – each player of the game has a plan – how he's going to play (behave) in every stage (round) of the game. The set of all actions is called a strategy.
• Strategy space – set of all possible strategies in the game for a player
• Payoff – for each player of a game, this is what a player receives, what he's going to get from the game. A payoff is the reason why player plays the game. Often a payoff is shown as a number which represents a utility or an outcome. So we can say that payoff is a utility function. A payoff determines the meaning of a game.
• Nash equilibrium – a strategy profile with the property that no single player can obtain a higher payoff by deviating unilaterally from this profile [6]. Simple said, nobody can get more at the expense of someone's else.
• Finite game – a game which stops at some time or has limited number of rounds. You can think these games from the beginning to the end.

Examples

The prisoner's dilemma

A good example for using normal form is a description of a famous Prisoner's dilemma problem. 2 prisoners are in a jail. They can't cooperate together. Both of them would like to avoid imprisonment as much as possible. Each prisoner has a dilemma: should I keep my mouth shut (stay silent) or should I betray the other prisoner? From their point of the view, they're not sure because they don't know how the second prisoner will decide.

If I betray and the second prison will stay silent I can go out without any punishment. But he will get 3 years (I don't mind about him). If I stay silent and the second one betrays he'll be free but I'll get 3 years. If both of us keep silent we'll get 1 year. But if we betray, each of us will be punished by 2 years.

In the worst case I spend 2 years in jail. But if I'm lucky I will get 0 years. The problem can be solved by the Nash equilibrium.

The matrix is in a normal form, so we can say that „prisoner's dilemma problem was put into a normal form" and then the Nash Equilibrium is used to find a solution of the problem.

Prisoner A/Prisoner B	B stays silent	B betrays
A stays silent	1, 1	3, 0
A betrays	0, 3	2, 2

The best strategy is „to betray" for both prisoners and it's the only pure Nash Equilibrium.

The battle of sexes

Another example of using normal form is „the battle of sexes”. It is a two-player coordination game where one of them would like to do something and the another one would like to do something different. A common example is a battle between man and woman where man would like to watch a sport match but woman would like to watch an opera. Both players prefer to stay together and in this case they have to because they have only one TV.

The normal form matrix is described like a table:

Woman/Man	Opera	Match
Opera	3, 2	0, 0
Match	0, 0	2, 3

This game has 2 pure Nash equilibria.

Matching pennies

The last example (but not the last in general, of course) is „the Matching pennies game”. 2 players have a penny with 2 sides (head and tail). Both of them will flip a penny secretly and then reveal the result. If both pennies have heads or tails, player 1 will take both pennies. If they differ (the first penny has head and the second has tail or vice versa), player 2 will take both pennies.

The game can be described in the following form:

Player 1/Player 2	Heads	Tails
Heads	1, -1	-1, 1
Tails	-1, 1	1, -1

The game has no pure Nash equilibrium because there is no a best response to another best response.

Exercises

Find all Nash equilibria for following games.

Example 1

the Battle of sexes

Adam/Betty	watch Blackhawk down	watch The Hobbit
watch Blackhawk down	5, 4	0, 0
watch The Hobbit	0, 0	4, 5

Example 2

the Prisoner's dilemma

Joe/Sam	cooperate	defect
cooperate	10, 10	20, 0
defect	0, 20	1, 1

References and resources

[1] GINTIS, Herbert. Game Theory Evolving. Princeton University Press, 2009. Page 32. ISBN: 978-0-691-14050-6. Also available at http://www.umass.edu/preferen/Game%20Theory%20Evolving/GTE%20Public/GTE%20Game%20Theory%20Basic%20Concepts.pdf

[2] HUGHES, Barry. Normal form games [online]. August 2011. Available at http://www.gametheorystrategies.com/2011/08/03/normal-form-games/

[3] LEVIN, Jonathan. Extensive Form Games [online]. January 2002. Available at http://www.stanford.edu/~jdlevin/Econ%20203/ExtensiveForm.pdf

[4] LEVIN, Jonathan. Normal Form Games [online]. January 2002. Available at http://www.stanford.edu/~jdlevin/Econ%20203/NormalForm.pdf

[5] PRISNER, Erich. Normal Form and Strategies [online]. 2007-2009. Available at http://www.eprisner.de/MAT109/Normal.html

[6] DARITY, William A., International Encyclopedia of the Social Sciences. Macmillan Reference USA. 2008. ISBN: 978-0-028-659-657. Page 540. Also available at http://www.columbia.edu/~rs328/NashEquilibrium.pdf

[7] NACHBAR, John. Game Theory Basics, Strategic Forms and Nash Equilibrium [online]. 2011. Available at http://artsci.wustl.edu/~econ467/GameTheory-I-NE.pdf

[8] JOYCE, Helen. Adam Smith and the Invisible hand [online]. 2011. Available at http://plus.maths.org/content/adam-smith-and-invisible-hand