Game Development Reference
InDepth 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 nonempty compact and
n
and
convex subset of
R
Φ:
A →P
(
A
)
such that
•
Φ(
x
)
is nonempty 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
.
Search Nedrilad ::
Custom Search