Contents
1 Introduction 2
2 Two Person 0-Sum Games 2
2.1 Strategic Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.2 Matrix Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.3 Dominated Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.4 Best Response . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.5 Saddle points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.6 Maximin Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.7 Mixed Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.8 Safety Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.9 MiniMax Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.10 2-strategy games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.11 Maximin Principle ⇔ Equilibrium Principle . . . . . . . . . . . . . . . . . . . . . . 5
2.12 Finding safety (Optimal) strategies when the value is given . . . . . . . . . . . . . . 5
3 Games in Extensive Form 6
3.1 The Extensive Form of a Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.2 The Game Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.3 Game of Perfect Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.4 Reduction of a Game in Extensive Form to Strategic Form . . . . . . . . . . . . . . 7
4 Bimatrix Games 8
4.1 Two-Person General-Sum Games/General-Sum Strategic Form Games . . . . . . . . 8
4.2 Safety Levels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4.3 Strategic Equilibrium . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.4 Duopoly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.5 Potential Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
5 Correlated Equilibrium 11
6 Evolutionarily Stable Strategies 12
7 The Evolution of Cooperation 12
8 Cooperative Games 14
8.1 Cooperative Games with Transferable Utility . . . . . . . . . . . . . . . . . . . . . . 14
8.2 Cooperative Games with Non-Transferable Utility . . . . . . . . . . . . . . . . . . . 15
9 Games in Coalitional Form 16
9.1 The Shapley Value . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
9.2 The Nucleolus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
9.3 Gately Point . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
10 Ordinal Matching Games 19
1
,1 Introduction
Game Theory can be called “Interactive Decision Theory”. It studies the competition or cooperation
between rational and intelligent decision makers. It has its origin in the entertaining games that
people play, such as chess, tic-tac-toe, bridge etc.
Ernst Zermelo wrote a paper on chess in the beginning of the 20𝑡ℎ century. John von Neumann
proved the Minimax Theorem for 2-person 0-sum games in the 1920’s century. Together with Oskar
Morgenstern they wrote the classic “Theory of Games and Economic Behavior” in 1944 setting the
foundation for Game Theory.
Game Theory is an essential tool in economics but it also finds many important applications in a wide
range of subjects such as political science, philosophy, law, biology, engineering. These interactions
further enrich Game Theory. Game Theory is called “the unified theory for the rational side of
social sciences”.
There are basically three mathematical models to describe a game: Extensive Form, Strategic Form,
Coalition Form.
2 Two Person 0-Sum Games
Games with only two players in which one player wins what the other player loses.
2.1 Strategic Form
The strategic form, or normal form, of a two-person zero-sum game is given by a triplet (𝑋, 𝑌 , 𝐴),
where:
(1) 𝑋 is a nonempty set, the set of strategies of Player I
(2) 𝑌 is a nonempty set, the set of strategies of Player II
(3) 𝐴 is a real-valued function defined on 𝑋 × 𝑌
(Thus, 𝐴(𝑥, 𝑦) is a real number for every 𝑥 ∈ 𝑋 and every 𝑦 ∈ 𝑌 )
The interpretation is as follows:
• Simultaneously, Player I chooses 𝑥 ∈ 𝑋 and Player II chooses 𝑦 ∈ 𝑌 , each unaware of the
choice of the other.
• Then their choices are made known and I wins the amount 𝐴(𝑥, 𝑦) from II.
• If 𝐴 is negative, I pays the absolute value of this amount to II.
• Thus, 𝐴(𝑥, 𝑦) represents the winnings of I and the losses of II.
2.2 Matrix Games
A finite two-person zero-sum game in strategic form, (𝑋, 𝑌 , 𝐴), is sometimes called a matrix game
because the essential information of the game, the payoff function 𝐴, can be represented by a matrix.
If 𝑋 = 𝑥1 , ⋯ , 𝑥𝑚 and 𝑌 = 𝑦1 , ⋯ , 𝑦𝑛 , then by the game matrix or payoff matrix we mean the matrix
𝑎11 ⋯ 𝑎1𝑛
⎛
𝐴=⎜ ⋮ ⋮ ⎞⎟,
𝑎
⎝ 𝑚1 ⋯ 𝑎 𝑚𝑛 ⎠
2
, where 𝑎𝑖𝑗 = 𝐴(𝑥𝑖 , 𝑦𝑗 ).
In this form, Player I chooses a row, Player II chooses a column, and II pays I the entry in the
chosen row and column:
• Player I: the Row choser
• Player II: the Column chooser
Note that the entries of the matrix are the winnings of the row chooser and losses of the column
chooser.
2.3 Dominated Strategies
Definition: We say the 𝑖𝑡ℎ row of a matrix 𝐴 = (𝑎𝑖𝑗 ) dominates the 𝑘𝑡ℎ row if 𝑎𝑖𝑗 ≥ 𝑎𝑘𝑗 for all
𝑗. We say the 𝑖𝑡ℎ row of 𝐴 strictly dominates the 𝑘𝑡ℎ row if 𝑎𝑖𝑗 > 𝑎𝑘𝑗 for all 𝑗. Similarly, the 𝑗𝑡ℎ
column of 𝐴 dominates (strictly dominates) the 𝑘𝑡ℎ column if 𝑎𝑖𝑗 ≤ 𝑎𝑖𝑘 (resp. 𝑎𝑖𝑗 ≤ 𝑎𝑖𝑘 ) for all 𝑖.
2.4 Best Response
Definition: Let (𝑋, 𝑌 , 𝐴) be a matrix game. Let 𝑥 ∈ 𝑋 be a strategy of Player I. Then, 𝑦 ∈ 𝑌 is
called a Best Response (BR) to 𝑥 if 𝐴(𝑥, 𝑦) ≤ 𝐴(𝑥, 𝑦′ ) for any 𝑦′ ∈ 𝑌 . Equivalently, Let 𝑦 ∈ 𝑌 be
a strategy of Player II. Then, 𝑥 ∈ 𝑋 is called a Best Response (BR) to 𝑦 if 𝐴(𝑥, 𝑦) ≥ 𝐴(𝑥′ , 𝑦) for
any 𝑥′ ∈ 𝑋.
Equilibrium Principle: Best Responses to each other.
Maximum Principle: Safety First.
2.5 Saddle points
Pure Strategic Equilibrium, PSE, for 2-person 0-sum games.
If some entry 𝑎𝑖𝑗 of the matrix 𝐴 has the property that:
(1) 𝑎𝑖𝑗 is the minimum of the 𝑖𝑡ℎ row, and
(2) 𝑎𝑖𝑗 is the maximum of the 𝑗𝑡ℎ column,
then we say 𝑎𝑖𝑗 is a saddle point. If 𝑎𝑖𝑗 is a saddle point, then Player I can then win at least
𝑎𝑖𝑗 by choosing row 𝑖, and Player II can keep her loss to at most 𝑎𝑖𝑗 by choosing column 𝑗.
⟨Row 𝑖, Column 𝑗⟩ is then an equilibrium pair, i.e. BR to each other.
2.6 Maximin Principle
Maximin Principle means to find the “risk” for each strategy and then find the strategy, called the
safety strategy, with minimum risk.
2.7 Mixed Strategies
Consider a finite 2-person zero-sum game, (𝑋, 𝑌 , 𝐴), with 𝑚×𝑛 matrix, 𝐴. Let us take the strategy
space 𝑋 to be the first 𝑚 integers, 𝑋 = 1, 2, ⋯ , 𝑚, and similarly, 𝑌 = 1, 2, ⋯ , 𝑛.
3
1 Introduction 2
2 Two Person 0-Sum Games 2
2.1 Strategic Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.2 Matrix Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.3 Dominated Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.4 Best Response . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.5 Saddle points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.6 Maximin Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.7 Mixed Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.8 Safety Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.9 MiniMax Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.10 2-strategy games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.11 Maximin Principle ⇔ Equilibrium Principle . . . . . . . . . . . . . . . . . . . . . . 5
2.12 Finding safety (Optimal) strategies when the value is given . . . . . . . . . . . . . . 5
3 Games in Extensive Form 6
3.1 The Extensive Form of a Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.2 The Game Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.3 Game of Perfect Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.4 Reduction of a Game in Extensive Form to Strategic Form . . . . . . . . . . . . . . 7
4 Bimatrix Games 8
4.1 Two-Person General-Sum Games/General-Sum Strategic Form Games . . . . . . . . 8
4.2 Safety Levels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4.3 Strategic Equilibrium . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.4 Duopoly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.5 Potential Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
5 Correlated Equilibrium 11
6 Evolutionarily Stable Strategies 12
7 The Evolution of Cooperation 12
8 Cooperative Games 14
8.1 Cooperative Games with Transferable Utility . . . . . . . . . . . . . . . . . . . . . . 14
8.2 Cooperative Games with Non-Transferable Utility . . . . . . . . . . . . . . . . . . . 15
9 Games in Coalitional Form 16
9.1 The Shapley Value . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
9.2 The Nucleolus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
9.3 Gately Point . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
10 Ordinal Matching Games 19
1
,1 Introduction
Game Theory can be called “Interactive Decision Theory”. It studies the competition or cooperation
between rational and intelligent decision makers. It has its origin in the entertaining games that
people play, such as chess, tic-tac-toe, bridge etc.
Ernst Zermelo wrote a paper on chess in the beginning of the 20𝑡ℎ century. John von Neumann
proved the Minimax Theorem for 2-person 0-sum games in the 1920’s century. Together with Oskar
Morgenstern they wrote the classic “Theory of Games and Economic Behavior” in 1944 setting the
foundation for Game Theory.
Game Theory is an essential tool in economics but it also finds many important applications in a wide
range of subjects such as political science, philosophy, law, biology, engineering. These interactions
further enrich Game Theory. Game Theory is called “the unified theory for the rational side of
social sciences”.
There are basically three mathematical models to describe a game: Extensive Form, Strategic Form,
Coalition Form.
2 Two Person 0-Sum Games
Games with only two players in which one player wins what the other player loses.
2.1 Strategic Form
The strategic form, or normal form, of a two-person zero-sum game is given by a triplet (𝑋, 𝑌 , 𝐴),
where:
(1) 𝑋 is a nonempty set, the set of strategies of Player I
(2) 𝑌 is a nonempty set, the set of strategies of Player II
(3) 𝐴 is a real-valued function defined on 𝑋 × 𝑌
(Thus, 𝐴(𝑥, 𝑦) is a real number for every 𝑥 ∈ 𝑋 and every 𝑦 ∈ 𝑌 )
The interpretation is as follows:
• Simultaneously, Player I chooses 𝑥 ∈ 𝑋 and Player II chooses 𝑦 ∈ 𝑌 , each unaware of the
choice of the other.
• Then their choices are made known and I wins the amount 𝐴(𝑥, 𝑦) from II.
• If 𝐴 is negative, I pays the absolute value of this amount to II.
• Thus, 𝐴(𝑥, 𝑦) represents the winnings of I and the losses of II.
2.2 Matrix Games
A finite two-person zero-sum game in strategic form, (𝑋, 𝑌 , 𝐴), is sometimes called a matrix game
because the essential information of the game, the payoff function 𝐴, can be represented by a matrix.
If 𝑋 = 𝑥1 , ⋯ , 𝑥𝑚 and 𝑌 = 𝑦1 , ⋯ , 𝑦𝑛 , then by the game matrix or payoff matrix we mean the matrix
𝑎11 ⋯ 𝑎1𝑛
⎛
𝐴=⎜ ⋮ ⋮ ⎞⎟,
𝑎
⎝ 𝑚1 ⋯ 𝑎 𝑚𝑛 ⎠
2
, where 𝑎𝑖𝑗 = 𝐴(𝑥𝑖 , 𝑦𝑗 ).
In this form, Player I chooses a row, Player II chooses a column, and II pays I the entry in the
chosen row and column:
• Player I: the Row choser
• Player II: the Column chooser
Note that the entries of the matrix are the winnings of the row chooser and losses of the column
chooser.
2.3 Dominated Strategies
Definition: We say the 𝑖𝑡ℎ row of a matrix 𝐴 = (𝑎𝑖𝑗 ) dominates the 𝑘𝑡ℎ row if 𝑎𝑖𝑗 ≥ 𝑎𝑘𝑗 for all
𝑗. We say the 𝑖𝑡ℎ row of 𝐴 strictly dominates the 𝑘𝑡ℎ row if 𝑎𝑖𝑗 > 𝑎𝑘𝑗 for all 𝑗. Similarly, the 𝑗𝑡ℎ
column of 𝐴 dominates (strictly dominates) the 𝑘𝑡ℎ column if 𝑎𝑖𝑗 ≤ 𝑎𝑖𝑘 (resp. 𝑎𝑖𝑗 ≤ 𝑎𝑖𝑘 ) for all 𝑖.
2.4 Best Response
Definition: Let (𝑋, 𝑌 , 𝐴) be a matrix game. Let 𝑥 ∈ 𝑋 be a strategy of Player I. Then, 𝑦 ∈ 𝑌 is
called a Best Response (BR) to 𝑥 if 𝐴(𝑥, 𝑦) ≤ 𝐴(𝑥, 𝑦′ ) for any 𝑦′ ∈ 𝑌 . Equivalently, Let 𝑦 ∈ 𝑌 be
a strategy of Player II. Then, 𝑥 ∈ 𝑋 is called a Best Response (BR) to 𝑦 if 𝐴(𝑥, 𝑦) ≥ 𝐴(𝑥′ , 𝑦) for
any 𝑥′ ∈ 𝑋.
Equilibrium Principle: Best Responses to each other.
Maximum Principle: Safety First.
2.5 Saddle points
Pure Strategic Equilibrium, PSE, for 2-person 0-sum games.
If some entry 𝑎𝑖𝑗 of the matrix 𝐴 has the property that:
(1) 𝑎𝑖𝑗 is the minimum of the 𝑖𝑡ℎ row, and
(2) 𝑎𝑖𝑗 is the maximum of the 𝑗𝑡ℎ column,
then we say 𝑎𝑖𝑗 is a saddle point. If 𝑎𝑖𝑗 is a saddle point, then Player I can then win at least
𝑎𝑖𝑗 by choosing row 𝑖, and Player II can keep her loss to at most 𝑎𝑖𝑗 by choosing column 𝑗.
⟨Row 𝑖, Column 𝑗⟩ is then an equilibrium pair, i.e. BR to each other.
2.6 Maximin Principle
Maximin Principle means to find the “risk” for each strategy and then find the strategy, called the
safety strategy, with minimum risk.
2.7 Mixed Strategies
Consider a finite 2-person zero-sum game, (𝑋, 𝑌 , 𝐴), with 𝑚×𝑛 matrix, 𝐴. Let us take the strategy
space 𝑋 to be the first 𝑚 integers, 𝑋 = 1, 2, ⋯ , 𝑚, and similarly, 𝑌 = 1, 2, ⋯ , 𝑛.
3
