最坏均衡与最佳解比 （英语：Price of Anarchy ，PoA ）[1] 赛局理论 中的一个概念，目的是为了衡量在一个赛局中，由于参与者的自私所导致整个系统的效能降低。在这个概念中，所谓的系统和效率可以指很多方面。例如在一个城市里交通中，有A和B两个地点，有一群人开车从A前往B，而在这两个地点之间有不止一条道路可以选择。在这个模型里，效率指的是这群人到达目的地所需要的平均时间，这些参与者可以通过集中决策从而达成最佳效率，也可以基于自私的立场而决定自己的决策，从而达成一个或多个纳什均衡 。在这些纳什均衡中，最差的效率比上最佳效率就是最坏均衡与最佳解比。
数学定义 [ 编辑 ] 假设存在赛局
G
=
(
N
,
S
,
u
)
{\displaystyle G=(N,S,u)}
N
{\displaystyle N}
S
i
{\displaystyle S_{i}}
u
i
:
S
→
R
{\displaystyle u_{i}:S\rightarrow \mathbb {R} }
S
=
S
1
×
.
.
.
×
S
n
{\displaystyle S=S_{1}\times ...\times S_{n}}
W
e
l
f
:
S
→
R
{\displaystyle Welf:S\rightarrow \mathbb {R} }
W
e
l
f
(
s
)
=
∑
i
∈
N
u
i
(
s
)
,
{\displaystyle Welf(s)=\sum _{i\in N}u_{i}(s),}
W
e
l
f
(
s
)
=
min
i
∈
N
u
i
(
s
)
,
{\displaystyle Welf(s)=\min _{i\in N}u_{i}(s),}
我们先定义一个决策集合
E
q
u
i
l
⊆
S
{\displaystyle Equil\subseteq S}
P
o
A
=
max
s
∈
S
W
e
l
f
(
s
)
min
s
∈
E
q
u
i
l
W
e
l
f
(
s
)
{\displaystyle PoA={\frac {\max _{s\in S}Welf(s)}{\min _{s\in Equil}Welf(s)}}}
当然，对于收益函数，当然是多多益善，但是对于损失函数
C
o
s
t
:
S
→
R
{\displaystyle Cost:S\rightarrow \mathbb {R} }
P
o
A
=
max
s
∈
E
q
u
i
l
C
o
s
t
(
s
)
min
s
∈
S
C
o
s
t
(
s
)
{\displaystyle PoA={\frac {\max _{s\in Equil}Cost(s)}{\min _{s\in S}Cost(s)}}}
囚徒困境 [ 编辑 ] 在2x2的囚徒困境 中，有如下的代价矩阵：
出卖
抗供
出卖
1 , 1
7 , 0
抗供
0 , 7
5 , 5
定义损失函数 为
C
(
s
1
,
s
2
)
=
u
1
(
s
1
,
s
2
)
+
u
2
(
s
1
,
s
2
)
{\displaystyle C(s_{1},s_{2})=u_{1}(s_{1},s_{2})+u_{2}(s_{1},s_{2})}
10
/
2
=
5
{\displaystyle 10/2=5}
工作排程问题 [ 编辑 ] 排程问题其实是最坏均衡与最佳解比的一个实例。有
N
{\displaystyle N}
M
{\displaystyle M}
每一台机器都具有速度
s
1
,
…
,
s
M
>
0.
{\displaystyle s_{1},\ldots ,s_{M}>0.}
w
1
,
…
,
w
N
>
0.
{\displaystyle w_{1},\ldots ,w_{N}>0.}
A
i
=
{
1
,
2
,
…
,
M
}
.
{\displaystyle A_{i}=\{1,2,\ldots ,M\}.}
j
{\displaystyle j}
L
j
(
a
)
=
∑
i
:
a
i
=
j
w
i
s
j
.
{\displaystyle L_{j}(a)={\frac {\sum _{i:a_{i}=j}w_{i}}{s_{j}}}.}
参与者
i
{\displaystyle i}
c
i
(
a
)
=
L
a
i
(
a
)
,
{\displaystyle c_{i}(a)=L_{a_{i}}(a),}
MS
(
a
)
=
max
j
L
j
(
a
)
{\displaystyle {\mbox{MS}}(a)=\max _{j}L_{j}(a)}
我们想到了纯策略和混合策略这两种策略，并且很容易知道混合策略时的最坏均衡与最佳解比肯定大于或等于纯策略时的最坏均衡与最佳解比。道理很简单，那是因为纯策略是一种特殊的混合策略，就好比正方形 是一种特殊的矩形 。首先我们要讨论是否存在纯纳许均衡。
宣称 ：在排程问题中，至少存在一个纳什均衡。
证明 ：我们想要全域最优解
a
∗
{\displaystyle a^{*}}
M
{\displaystyle M}
我们声称这是一个纯策略的纳什均衡。接下来可以运用反证法 证明：假设某个参与者
i
{\displaystyle i}
j
{\displaystyle j}
k
{\displaystyle k}
k
{\displaystyle k}
j
{\displaystyle j}
j
{\displaystyle j}
j
{\displaystyle j}
Q.E.D.
宣称 ：对于每个工作排程的赛局，纯PoA最多为
M
{\displaystyle M}
证明 ：不难求出，在在任何混合策略纳许均衡
σ
{\displaystyle \sigma }
w
(
σ
)
≤
∑
i
w
i
max
j
s
j
.
{\displaystyle w(\sigma )\leq {\frac {\sum _{i}{w_{i}}}{\max _{j}{s_{j}}}}.}
为了清楚地说明情况，在纯策略
a
{\displaystyle a}
w
(
a
)
≥
∑
i
w
i
∑
j
s
j
≥
∑
i
w
i
M
⋅
max
j
s
j
.
{\displaystyle w(a)\geq {\frac {\sum _{i}{w_{i}}}{\sum _{j}{s_{j}}}}\geq {\frac {\sum _{i}{w_{i}}}{M\cdot \max _{j}{s_{j}}}}.}
由于上述情况也适用于社会最优，比较
w
(
σ
)
{\displaystyle w(\sigma )}
w
(
a
)
{\displaystyle w(a)}
Q.E.D
自私路线问题 [ 编辑 ] 布雷斯悖论 [ 编辑 ] 布雷斯悖论的例子 考虑右图中的交通网，有4000辆车打算在其中路上通行。通过的时间从起点到A点和从B点到终点均是路上车的数量除以100，而从起点到B点和从A点到终点均是固定的45分钟。如果近路不存在（即交通网上只有4条路），从起点到A点到终点需要的时间是
A
100
+
45
{\displaystyle {\tfrac {A}{100}}+45}
B
100
+
45
{\displaystyle {\tfrac {B}{100}}+45}
奈许均衡点 的，因为理性的司机都会选择较短的路。因为有4000辆车，从
A
+
B
=
4000
{\displaystyle A+B=4000}
A
=
B
=
2000
{\displaystyle A=B=2000}
2000
100
+
45
=
65
{\displaystyle {\tfrac {2000}{100}}+45=65}
现在假设有了一条近路（如虚线所示），其通过时间接近于0，在这种情况下，所有的司机都会选择从起点到A点这条线路，因为就算所有的车都走这条路，通过时间也不过40分钟，小于起点到B点的45分钟。到达A点之后，所有的司机都会选择从用接近0的时间行驶到到B再到终点，因为就算所有的车都走这条路，通过时间也不过40分钟，小于A点到终点的45分钟。这样所有车的通过时间是
4000
100
+
4000
100
=
80
{\displaystyle {\tfrac {4000}{100}}+{\tfrac {4000}{100}}=80}
参考资料 [ 编辑 ]
^ Koutsoupias, Elias; Papadimitriou, Christos. Worst-case Equilibria . Computer Science Review. May 2009, 3 (2): 65–69 [2010-09-12 ] . （原始内容 存档于2016-03-13）.
外部链接 [ 编辑 ] 
