【博弈论】纳什定理及其证明
一、纳什定理的内容
-
定理内容：
若允许玩家采用混合策略，则任何有限博弈均存在一个纳什均衡。
- 有限博弈的含义是玩家个数有限并且玩家的动作空间有限。满足上述条件的博弈中，至少存在一个混合策略纳什均衡（纯策略纳什均衡可看作特例）。
-
非有限博弈不一定存在纳什均衡（不是一定不存在）。举例说明：两个人玩游戏，每人从
[0
,
1
]
[0,1]
[
0
,
1
]
中选数字比大小，大者获胜。这就是一个非有限博弈，但纳什均衡存在即每个人都选择
11
1
。如果动作空间改成
[0
,
1
)
[0,1)
[
0
,
1
)
，那么这个非有限博弈就不存在纳什均衡（两个人选择逼近
11
1
的数时，总会有一个更大的数使其获得更高的收益）。
二、布劳尔不动点定理的内容
-
定理内容：
在欧式空间中，给定任意的凸紧集
KK
K
，任何从
KK
K
映射到其自身的连续函数
f:
K
→
K
f:K\rightarrow K
f
:
K
→
K
，都存在至少一个不动点，即
∃x
∈
K
\exist x\in K
∃
x
∈
K
使得
f(
x
)
=
x
f(x)=x
f
(
x
)
=
x
。 - 人大高瓴的沈老师给出了一个特别形象的解释：将校园地图放在校园内部的任意一个角落里（假设校园是个凸紧集），那么地图上必定至少存在一个点使得该点与所代表的实际位置重合。
三、纳什定理的证明
- 证明思路：1.构造某个具有特殊性质的连续函数；2.应用布劳尔不动点定理证明其存在不动点；3.证明该不动点就是纳什均衡。（因为一定存在不动点，故一定存在纳什均衡）
对任意的策略组合
s
s
s
，令
c
i
(
s
;
a
i
)
=
m
a
x
{
0
,
u
i
(
a
i
,
s
−
i
)
−
u
i
(
s
)
}
c_i(s;a_i)=max\{0,u_i(a_i,s_{-i})-u_i(s)\}
c
i
(
s
;
a
i
)
=
ma
x
{
0
,
u
i
(
a
i
,
s
−
i
)
−
u
i
(
s
)}
定义函数
f
f
f
是两个策略组合之间的映射
f
(
s
)
=
s
′
f(s)=s’
f
(
s
)
=
s
′
其中对于
s
′
s’
s
′
中的每个玩家
i
i
i
的每个动作
a
i
a_i
a
i
是这么定义的
s
i
′
(
a
i
)
=
s
i
(
a
i
)
+
c
i
(
s
;
a
i
)
1
+
∑
a
i
′
c
i
(
s
;
a
i
′
)
s_i'(a_i)=\frac{s_i(a_i)+c_i(s;a_i)}{1+\sum_{a_i’}c_i(s;a_i’)}
s
i
′
(
a
i
)
=
1
+
∑
a
i
′
c
i
(
s
;
a
i
′
)
s
i
(
a
i
)
+
c
i
(
s
;
a
i
)
（解释一下：分子可以看作对于
s
i
(
a
i
)
s_i(a_i)
s
i
(
a
i
)
的调整，如果
c
i
(
s
;
a
i
)
>
0
c_i(s;a_i)>0
c
i
(
s
;
a
i
)
>
0
那么就响应提高了
a
i
a_i
a
i
对应的概率。分母是为了保证每个玩家所有动作的概率和为1而做的归一化，每个玩家所有动作更新完后不做归一化的和为
1
+
∑
a
i
′
c
i
(
s
;
a
i
′
)
1+\sum_{a_i’}c_i(s;a_i’)
1
+
∑
a
i
′
c
i
(
s
;
a
i
′
)
）
函数的输入与输出均属于集合
Π
i
∈
N
Δ
(
A
i
)
\Pi_{i\in N}\Delta(A_i)
Π
i
∈
N
Δ
(
A
i
)
，且该集合是凸的（两个可行策略组合的凸组合仍是可行的策略组合）、有界的、闭合的即凸紧集。且函数
f
(
s
)
f(s)
f
(
s
)
是关于
s
s
s
的连续函数。
应用布劳尔不动点定理得函数
f
(
s
)
f(s)
f
(
s
)
存在不动点
s
∗
s^*
s
∗
使得
f
(
s
∗
)
=
s
∗
f(s^*)=s^*
f
(
s
∗
)
=
s
∗
，即对于每个玩家得每个动作来说
s
i
∗
(
a
i
)
=
s
i
∗
(
a
i
)
+
c
i
(
s
∗
;
a
i
)
1
+
∑
a
i
′
c
i
(
s
∗
;
a
i
′
)
s^*_i(a_i)=\frac{s_i^*(a_i)+c_i(s^*;a_i)}{1+\sum_{a_i’}c_i(s^*;a_i’)}
s
i
∗
(
a
i
)
=
1
+
∑
a
i
′
c
i
(
s
∗
;
a
i
′
)
s
i
∗
(
a
i
)
+
c
i
(
s
∗
;
a
i
)
由于
c
i
(
s
∗
;
a
i
)
≥
0
c_i(s^*;a_i)\ge 0
c
i
(
s
∗
;
a
i
)
≥
0
，想要上式成立有两种情况：
（1）
∀
i
,
∀
a
i
∈
A
i
,
c
i
(
s
∗
;
a
i
)
>
0
\forall i,\forall a_i\in A_i,c_i(s^*;a_i)>0
∀
i
,
∀
a
i
∈
A
i
,
c
i
(
s
∗
;
a
i
)
>
0
，即
u
i
(
a
i
,
s
−
i
∗
)
>
u
i
(
s
i
∗
,
s
−
i
∗
)
u_i(a_i,s^*_{-i})>u_i(s^*_i,s^*_{-i})
u
i
(
a
i
,
s
−
i
∗
)
>
u
i
(
s
i
∗
,
s
−
i
∗
)
（2）
∀
i
,
∀
a
i
∈
A
i
,
c
i
(
s
∗
;
a
i
)
=
0
\forall i,\forall a_i\in A_i,c_i(s^*;a_i)=0
∀
i
,
∀
a
i
∈
A
i
,
c
i
(
s
∗
;
a
i
)
=
0
，即
u
i
(
a
i
,
s
−
i
∗
)
≤
u
i
(
s
i
∗
,
s
−
i
∗
)
u_i(a_i,s^*_{-i})\le u_i(s^*_i,s^*_{-i})
u
i
(
a
i
,
s
−
i
∗
)
≤
u
i
(
s
i
∗
,
s
−
i
∗
)
情况（1）的意思是对于每个玩家的每个纯策略的收益都要大于
s
∗
s^*
s
∗
这一混合策略的收益，这是显然不成立的（任意混合策略的收益都不可能同时小于所有纯策略收益）。
因此上式成立的唯一情况就是（2），即
s
∗
s^*
s
∗
这一混合策略的收益大于等于所有纯策略收益，分析易得
s
∗
s^*
s
∗
一定是混合策略纳什均衡。因此得证
s
∗
s^*
s
∗
这一混合策略是纳什均衡。因为不动点定理，一定存在不动点
s
∗
s^*
s
∗
，因此一定存在纳什均衡。