1.

Basics of Game Theory

Gianni Arioli, Roberto Lucchetti

Politecnico di Milano

1/20
G. Arioli, R. Lucchetti (PoliMI) 1. Basics of Game Theory 1 / 20
Decision theories
Variants with one decision maker:
1 scalar optimization
2 vector optimization
3 deterministic optimization
4 stochastic optimization
5 ...

Variants with many decision makers:

1 Game theory
2 Social choice
3 Mechanism design
4 Machine learning
5 ...

It is much easier to define what is the best choice when there is one decision
maker only. 2/20
G. Arioli, R. Lucchetti (PoliMI) 1. Basics of Game Theory 2 / 20
What is a game
Examples:
1 Chess, checkers,...
2 Two people bargaining how to divide a pie
3 A burglar and a guard
4 Parties in a Parliament
5 ...

Games are efficient models for an enormous amount of everyday life situations

A game is a process consisting in:

1 A set of players (at least two)
2 An initial situation
3 Rules that the players must follow
4 All possible final situations
5 The preferences of all players on the set of the final situations
3/20
G. Arioli, R. Lucchetti (PoliMI) 1. Basics of Game Theory 3 / 20
Assumptions of the theory

Players are
1 Selfish
2 Rational

Selfish means that the players only care about their own preferences on the
outcomes of the game
This is not an ethical issue, but a mathematical assumption. We need it to define
what is the meaning of a rational choice.
Rationality is a much more involved issue.

4/20
G. Arioli, R. Lucchetti (PoliMI) 1. Basics of Game Theory 4 / 20
Preferences

Definition
Let X be a set. A preference relation on X is a binary relation ⪰ such that for all
x, y , z ∈ X :
1 x ⪰ x (reflexive)

2 x ⪰ y or y ⪰ x or both (complete)

3 If x ⪰ y and y ⪰ z, then x ⪰ z (transitive)

The first rationality assumption is:

The players are able to provide a preference relation over the outcomes of the
game.
5/20
G. Arioli, R. Lucchetti (PoliMI) 1. Basics of Game Theory 5 / 20
Utility functions

Definition
Let ⪰ be a preference relation over X . A utility function representing ⪰ is a
function u : X → R such that

u(x) ≥ u(y ) ⇐⇒ x ⪰ y .

1 A utility function may not exist in particular cases, however it exists in

general setting, in particular if X is a finite set
2 When a utility function exists, then infinitely many utility functions exist,
since any strictly increasing transformation of a utility function is a utility
function.

The second rationality assumption reads:

The agents are able to provide a utility function representing their preferences
relations, whenever necessary 6/20
G. Arioli, R. Lucchetti (PoliMI) 1. Basics of Game Theory 6 / 20
Allais experiment 1

Alternative A
gain probability
2500 33%
2400 66%
0 1%

Alternative B:
gain probability
2500 0%
2400 100%
0 0%

In a sample of 72 people exposed to this experiment, 82% of them decided to play

34 33
the Lottery B. This is rational if 100 u(2400) > 100 u(2500).

7/20
G. Arioli, R. Lucchetti (PoliMI) 1. Basics of Game Theory 7 / 20
Allais experiment 2

Alternative C
gain probability
2500 33%
0 67%

Alternative D:
gain probability
2400 34%
0 66%

83% of the people interviewed selected lottery C .

34 33
This is rational if 100 u(2400) < 100 u(2500).

Allais experiment shows that usually agents are not rational players!

8/20
G. Arioli, R. Lucchetti (PoliMI) 1. Basics of Game Theory 8 / 20
Probability issues

The third rationality assumption reads:

The players use consistently the probability laws, in particular they are consistent
with the computation of the expected utilities, they are able to update
probabilities according to Bayes rule...

9/20
G. Arioli, R. Lucchetti (PoliMI) 1. Basics of Game Theory 9 / 20
The beauty contest

Write an integer between 1 and 100.

The mean M is calculated.
Those writing the number at the minimum distance from qM win the game
(0 < q < 1).
A rational player will answer 1, independently of q. And he will probably lose.

10/20
G. Arioli, R. Lucchetti (PoliMI) 1. Basics of Game Theory 10 / 20
Deepness of the analysis

The fourth rationality assumption reads:

The players are able to understand the consequences of all their actions, the
consequences of this information on any other player, the consequences of the
consequences and so on.

11/20
G. Arioli, R. Lucchetti (PoliMI) 1. Basics of Game Theory 11 / 20
Extending decision theory

Finally, the fifth rationality assumption reads:

The players are able to use decision theory, whenever it is possible

that is, given a set of alternatives X , and a utility function u on X , each player
seeks an x̄ ∈ X such that

u(x̄) ≥ u(x) , ∀x ∈ X .

12/20
G. Arioli, R. Lucchetti (PoliMI) 1. Basics of Game Theory 12 / 20
Summary of the rationality assumptions

1 The players are able to rank the outcomes of the game

2 The players are able to provide a utility function for their ranking
3 The players use the expected value to build their utility function in presence
of random events
4 The players are able to analyse all the consequences of their actions, and the
consequences of the consequences and so on
5 The players use the tools of decision theory whenever possible

13/20
G. Arioli, R. Lucchetti (PoliMI) 1. Basics of Game Theory 13 / 20
An immediate and important consequence of the axioms

A player does not take an action a it she has available an action b providing her a
strictly better result, no matter what the other players do.

Principle of elimination of strictly dominated actions.

14/20
G. Arioli, R. Lucchetti (PoliMI) 1. Basics of Game Theory 14 / 20
Bimatrices

Player 1 chooses a row, player 2 a column.

This results in a pair of numbers, respectively the utility of Player 1 and 2.
 
(8, 8) (2, 7)
(7, 2) (0, 0)
Utilities of player 1:
 
8 2
7 0

The second row is strictly dominated by the first, thus player 1 will select the first
row

This principle may seem trivial, but it has important consequences.

15/20
G. Arioli, R. Lucchetti (PoliMI) 1. Basics of Game Theory 15 / 20
Comparisons of games

Game 1:  
(10, 10) (3, 15)
(15, 3) (5, 5)

Game 2:  
(8, 8) (2, 7)
(7, 2) (0, 0)

Observe: in any outcome the players are better off in the first game rather than in
the second:

However it is more convenient for them to play the second!

16/20
G. Arioli, R. Lucchetti (PoliMI) 1. Basics of Game Theory 16 / 20
Less is better than more

The first game:  

(10, 10) (3, 5)
(5, 3) (1, 1)

The second game, containing all possible outcomes the first, and some further
outcomes:  
(1, 1) (11, 0) (4, 0)
 (0, 11) (10, 10) (3, 5) 
(0, 4) (5, 3) (1, 1)

Having less available actions can make the players better off!

17/20
G. Arioli, R. Lucchetti (PoliMI) 1. Basics of Game Theory 17 / 20
Uniqueness issue

 
(0, 0) (1, 1)
(1, 1) (0, 0)

Rational outcomes of this game?

We formally do not know but it is obvious that the rational outcomes will be (1, 1)

(First row, second column) and (second row, first column) cannot be distinguished
and this creates a coordination problem between the players

18/20
G. Arioli, R. Lucchetti (PoliMI) 1. Basics of Game Theory 18 / 20
Elimination of weakly dominated strategies

Strongly dominated strategies may be straightaway eliminated. The following

example shows that weakly dominated strategies are different.
Consider three players who have to decide among alternatives A, B, C . The
players preferences are:
A ⪶1 1 B ⪶1 C

B ⪶2 C ⪶2 A

C ⪶3 A ⪶3 B
In case of three different votes, the alternative selected by player one is chosen.
What can we expect as rational outcome of the game?

1A ⪶ B means A ⪰ B and not B ⪰ A 19/20

G. Arioli, R. Lucchetti (PoliMI) 1. Basics of Game Theory 19 / 20
The voting game

Try with elimination of weakly dominated strategies. . .

Alternative A is a weakly dominant strategy for Player 1
Players 2 and 3 have as weakly dominated strategy to play their worst choice

Thus the game reduces to

A A
C A

The result is the worst one for the first player!

20/20
G. Arioli, R. Lucchetti (PoliMI) 1. Basics of Game Theory 20 / 20