最壞均衡與最佳解比 （英語：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）.
外部連結 [ 编辑 ] 
