Game Development Reference
In-Depth Information
for p 1 (
r 2 , and p 2 ( m 1 ,F )= p 2 ( m 1 ,B ), i.e., (using r 2 = 1 and
r 2 = 0 in the above formula for p 2 (
·
)) 2
·
r 2 =1
r 1 ). So r 2 = 3 and r 1 = 3 .
This implies that for these values of r 1 and r 2 ,( m 1 ,m 2 ) is a Nash equilib-
rium in mixed strategies and we have
p 1 ( m 1 ,m 2 )= p 2 ( m 1 ,m 2 )= 3 .
The example of the Matching Pennies game illustrated that some strategic
games do not have a Nash equilibrium. In the case of mixed extensions the
situation changes and we have the following fundamental result due to Nash
[1950].
·
)) r 1 =2
·
(1
Theorem 1.14 (Nash)
Every mixed extension of a finite strategic game
has a Nash equilibrium.
In other words, every finite strategic game has a Nash equilibrium in mixed
strategies. In the case of the Matching Pennies game it is straightforward to
check that ( 2 ·
H + 2 ·
T, 2 ·
H + 2 ·
T ) is such a Nash equilibrium. In this
equilibrium the payoffs to each player are 0.
Nash's Theorem follows directly from the following result due to Kakutani
[1941]. 2
Theorem 1.15 (Kakutani)
Suppose that A is a non-empty compact and
n and
convex subset of
R
Φ: A →P ( A )
such that
Φ( x ) is non-empty and convex for all x
A,
the graph of Φ , so the set
{
( x, y )
|
y
Φ( x )
}
, is closed.
Then x
A exists such that x
Φ( x ) .
Proof of Nash's Theorem . Fix a finite strategic game ( S 1 ,...,S n ,p 1 ,...,p n ).
Define the function best i :
× j = i Δ S j
→P
S i )by
best i ( m −i ):=
{
m i
Δ S i
|
m i is a best response to m −i
}
.
Then define the function best S 1
×
...
×
Δ S n
→P
S 1
×
...
×
Δ S n )by
best ( m ):= best 1 ( m 1 )
×
...
×
best 1 ( m −n ) .
It is now straightforward to check that m is a Nash equilibrium iff m
best ( m ). Moreover, one can easily check that the function best (
·
) satisfies
2 Recall that a subset A of R
n is called compact if it is closed and bounded, and is called
convex if for any x , y ∈ A and α ∈ [0 , 1] we have α x +(1 − α ) y ∈ A .