最壞均衡與最佳解比

最壞均衡與最佳解比（英語：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分钟的时间。但是，由于单个的司机总是能从抄近道上获益，所以这种约定是不稳定的，布雷斯悖论便出现了。

另見

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

外部連結

• 多工玩家排程賽局中的隨機本機政策 （页面存档备份，存于互联网档案馆）