最壞均衡與最佳解比

最壞均衡與最佳解比（英語：Price of Anarchy，PoA），是博弈論中的一個概念，目的是為了衡量在一個博弈中，由於參與者的自私所導致整個系統的效能降低。在這個概念中，所謂的系統和效率可以指很多方面。例如在一個城市裏交通中，有A和B兩個地點，有一群人開車從A前往B，而在這兩個地點之間有不止一條道路可以選擇。在這個模型裏，效率指的是這群人到達目的地所需要的平均時間，這些參與者可以通過集中決策從而達成最佳效率，也可以基於自私的立場而決定自己的決策，從而達成一個或多個納殊均衡。在這些納殊均衡中，最差的效率比上最佳效率就是最壞均衡與最佳解比。

數學定義

假設存在博弈$G=(N,S,u)$，存在參與者集合$N$，每個參與者又存在決策集合$S_{i}$和功用函數$u_{i}:S\rightarrow \mathbb {R}$（其中$S=S_{1}\times ...\times S_{n}$也被稱為結果集）。對此，我們還可以定義一個衡量整體好壞的指標$Welf:S\rightarrow \mathbb {R}$，通常可以是所有參與者效能的總和，即$Welf(s)=\sum _{i\in N}u_{i}(s),$，或者是所有參與者效能的最小值，即$Welf(s)=\min _{i\in N}u_{i}(s),$，當然也可以根據自身需要進行定義。

我們先定義一個決策集合$Equil\subseteq S$滿足均衡策略，那麼最壞均衡與最佳解比數學定義如下：

$PoA={\frac {\max _{s\in S}Welf(s)}{\min _{s\in Equil}Welf(s)}}$

當然，對於收益函數，當然是多多益善，但是對於損失函數$Cost:S\rightarrow \mathbb {R}$，則完全相反：

$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})$。在納殊均衡中，只有雙方都選擇招供，函數值為2.但是最好的結果是都不招供，函數值為10，故最壞均衡與最佳解比為$10/2=5$。

工作排程問題

排程問題其實是最壞均衡與最佳解比的一個實例。有$N$個參與者，每個參與者都有一個任務要完成，他們可以從$M$台機器中選擇一台來完成任務。在這一問題中最壞均衡與最佳解比對各行其是和集中安排機器進行了比較。

每一台機器都具有速度$s_{1},\ldots ,s_{M}>0.$，每一項工作都具有權重$w_{1},\ldots ,w_{N}>0.$。每名參與者都選擇一台機器來完成工作，因此，每名參與者的決策為$A_{i}=\{1,2,\ldots ,M\}.$。定義第$j$台機器的負載為：

$L_{j}(a)={\frac {\sum _{i:a_{i}=j}w_{i}}{s_{j}}}.$

參與者$i$的成本函數為$c_{i}(a)=L_{a_{i}}(a),$，也就是此人所選的機器負載。考慮到平均成本函數${\mbox{MS}}(a)=\max _{j}L_{j}(a)$，我們稱之為最大完工時間。

我們想到了純策略和混合策略這兩種策略，並且很容易知道混合策略時的最壞均衡與最佳解比肯定大於或等於純策略時的最壞均衡與最佳解比。道理很簡單，那是因為純策略是一種特殊的混合策略，就好比正方形是一種特殊的矩形。首先我們要討論是否存在純納殊均衡。

宣稱：在排程問題中，至少存在一個納殊均衡。

證明：我們想要全域最優解$a^{*}$。這意味着按照這一種分配方式，我們能獲得最小的最大完工時間。但是僅知道這些還不夠，可能有多種分配方式有着共同的最大完工時間。因此，在這些分配方式裏面再選出擁有着最小的第二大完工時間的分配方式，以此類推，直到第$M$大時篩選出唯一的分配方式。

我們聲稱這是一個純策略的納殊均衡。接下來可以運用反證法證明：假設某個參與者$i$可以通過從機器$j$移動到機器$k$來改進自己的負載。這意味着移動後機器$k$的負載依然小於移動前機器$j$的負載。由於移動後機器$j$的負載必須減少並且沒有其他機器受到影響，這意味着新分配肯定減少了第 $j$大（或排名更高）的負載。但是這樣一來就違背了之前選出的唯一的分配方式。 Q.E.D.

宣稱：對於每個工作排程的博弈，純PoA最多為$M$。

證明：不難求出，在在任何混合策略納殊均衡$\sigma$時所獲得的收益上限為：

$w(\sigma )\leq {\frac {\sum _{i}{w_{i}}}{\max _{j}{s_{j}}}}.$

為了清楚地說明情況，在純策略$a$時，不難看出：

$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(\sigma )$和$w(a)$的比率證明了該宣稱。 Q.E.D

自私路線問題

布雷斯悖論

主條目：布雷斯悖論

布雷斯悖論的例子

考慮右圖中的交通網，有4000輛車打算在其中路上通行。通過的時間從起點到A點和從B點到終點均是路上車的數量除以100，而從起點到B點和從A點到終點均是固定的45分鐘。如果近路不存在（即交通網上只有4條路），從起點到A點到終點需要的時間是 ${\tfrac {A}{100}}+45$，而從起點到B點到終點需要的時間是 ${\tfrac {B}{100}}+45$。如果其中一條路的通過時間較短，是不可以達到奈許均衡點的，因為理性的司機都會選擇較短的路。因為有4000輛車，從 $A+B=4000$ 可以解得平均 $A=B=2000$，這樣每條路的平均通過時間都是 ${\tfrac {2000}{100}}+45=65$ 分鐘。

現在假設有了一條近路（如虛線所示），其通過時間接近於0，在這種情況下，所有的司機都會選擇從起點到A點這條線路，因為就算所有的車都走這條路，通過時間也不過40分鐘，小於起點到B點的45分鐘。到達A點之後，所有的司機都會選擇從用接近0的時間行駛到到B再到終點，因為就算所有的車都走這條路，通過時間也不過40分鐘，小於A點到終點的45分鐘。這樣所有車的通過時間是${\tfrac {4000}{100}}+{\tfrac {4000}{100}}=80$ 分鐘，比不存在近道的時候還多了15分鐘。就算不走這條路，時間也不會縮短，因為原先的路線（起點→A→終點；起點→B→終點）的時間都變成了85分鐘。如果大家都約定好不走近路，那麼都可以節約15分鐘的時間。但是，由於單個的司機總是能從抄近道上獲益，所以這種約定是不穩定的，布雷斯悖論便出現了。

另見

• 最好均衡與最佳解比
• 公地悲劇

外部連結

• 多工玩家排程博弈中的隨機本機政策 （頁面存檔備份，存於互聯網檔案館）