Behaviour strategies
Gianni Arioli, Roberto Lucchetti
Politecnico di Milano
1/12 1/12
G. Arioli, R. Lucchetti (PoliMI) Behaviour strategies 1 / 12
Behaviour strategy
Definition
A behaviour strategy for a player in an extensive form game is a map defined on
the collection of her information sets and providing to each information set a
probability distribution over the actions at the information set
Remembering the formal definition of information set for player i:
Definition
An information set for a player i is a pair (Ui , Ai (Ui )) with the following
properties:
1 Ui ⊂ Pi is a nonempty set of vertices v1 , . . . , vk
2 each vj ∈ Ui has the same number of children
3 Ai (Ui ) is a partition of the children of v1 ∪ · · · ∪ vk with the property that
each element of the partition contains exactly one child of each vertex vj
2/12 2/12
G. Arioli, R. Lucchetti (PoliMI) Behaviour strategies 2 / 12
Reference example
For Player I a behaviour strategy is (p, 1 − p), (q, 1 − q), where p represents the
probability attached to choice B1 , q to B2 .
3/12 3/12
G. Arioli, R. Lucchetti (PoliMI) Behaviour strategies 3 / 12
Mixed versus behaviour
The pure strategies for Player 1 are 4, the set of mixed strategies is Σ4 ,
geometrically a three dimensional subset of R4
The set of behaviour strategies is geometrically a square in R2 .
Behaviour strategies are more natural, especially in large games.
4/12 4/12
G. Arioli, R. Lucchetti (PoliMI) Behaviour strategies 4 / 12
Equivalence of strategies
A key issue:
Do behaviour strategies and mixed strategies can be indifferently used?
Formalizing: denote by p(x; σ) the probability that a vertex x is reached under the
strategy σ
Definition
The strategies mixed/behaviour σi and bi are equivalent for Player I if for every
strategy σ−i 1 of the other players it holds
p(x; σi , σ−i ) = p(x; bi , σ−i ).
For the equivalence it is enough to check on the leaves
1σ can be formed by either behaviour or mixed strategies
−i 5/12 5/12
G. Arioli, R. Lucchetti (PoliMI) Behaviour strategies 5 / 12
An example of equivalence
The set of pure strategies for the first player is {B1 B2 , B1 T2 , T1 B2 , T1 T2 }.
Suppose that the second player plays (q, 1 − q). What is a behavioural strategy
equivalent to the mixed ( 13 , 31 , 13 , 0) for the first?
6/12 6/12
G. Arioli, R. Lucchetti (PoliMI) Behaviour strategies 6 / 12
What is equivalence?
Theorem
Let s = (s1 , . . . , sn ) be a mixed strategies equilibrium profile. Let bi be a
behaviour strategy for Player i equivalent to si . Then for every Player j it is
uj (s) = uj (b), where b = (bi , s−i ).
Equivalent strategies provide the same outcome to the players
7/12 7/12
G. Arioli, R. Lucchetti (PoliMI) Behaviour strategies 7 / 12
Mixed not behaviour
Consider the following (strange) game
Consider the mixed strategy ( 12 , 0, 0, 12 ). Does this have an equivalent behaviour
strategy?
8/12 8/12
G. Arioli, R. Lucchetti (PoliMI) Behaviour strategies 8 / 12
Behaviour not mixed
Consider the following (strange) game
Vertex O2 represents home.
Can an absent minded driver go home with a mixed strategy?
What if he uses behaviour strategy?
9/12 9/12
G. Arioli, R. Lucchetti (PoliMI) Behaviour strategies 9 / 12
(Very) different outcomes
Consider
L P1
L R
R
(1, 0) (100, 100)
P2
L R
(5, 1) (2, 2)
What is the expected outcome in mixed strategies? In behaviour strategies?
10/12 10/12
G. Arioli, R. Lucchetti (PoliMI) Behaviour strategies 10 / 12
From behaviour to mixed
Theorem
Suppose Γ is an extensive form game such that every vertex which is not a leaf
has at least two children. Then every behaviour strategy of player i has an
equivalent mixed strategy if and only if each information set of player i intersect
every path starting at the root at most once.
11/12 11/12
G. Arioli, R. Lucchetti (PoliMI) Behaviour strategies 11 / 12
Perfect recall
Definition
We say that player i has perfect recall if
Every path from the root to a leaf intersects every information set of player i
at most once
Every two paths from the root ending in the same information set pass
through the same information sets of i and in the same order; moreover in
each information set the two paths take the same action
A game is called a game with perfect recall if each player has a perfect recall.
Theorem
Let Γ be a game. If player i has perfect recall, then every mixed strategy for
player i has an equivalent behaviour strategy (and then equilibria with mixed
strategies and behaviour strategies are the same).
12/12 12/12
G. Arioli, R. Lucchetti (PoliMI) Behaviour strategies 12 / 12
