最壞均衡與最佳解比 （英語：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）.
