text: 最壞均衡與最佳解比，是賽局理論中的一個概念，目的是為了衡量在一個賽局中，由於參與者的自私所導致整個系統的效能降低。在這個概念中，所謂的系統和效率可以指很多方面。例如在一個城市裡交通中，有A和B兩個地點，有一群人開車從A前往B，而在這兩個地點之間有不止一條道路可以選擇。在這個模型裡，效率指的是這群人到達目的地所需要的平均時間，這些參與者可以透過集中決策從而達成最佳效率，也可以基於自私的立場而決定自己的決策，從而達成一個或多個納什均衡。在這些納什均衡中，最差的效率比上最佳效率就是最壞均衡與最佳解比。數學定義.假設存在賽局formula_1，存在參與者集合formula_2，每個參與者又存在決策集合formula_3和效用函式formula_4。對此，我們還可以定義一個衡量整體好壞的指標formula_6，通常可以是所有參與者效能的總和，即formula_7，或者是所有參與者效能的最小值，即formula_8，當然也可以根據自身需要進行定義。我們先定義一個決策集合formula_9滿足均衡策略，那麼最壞均衡與最佳解比數學定義如下：formula_10當然，對於收益函式，當然是多多益善，但是對於損失函式formula_11，則完全相反：formula_12囚徒困境.在2x2的囚徒困境中，有如下的代價矩陣：定義損失函式為formula_13。在納許均衡中，只有雙方都選擇招供，函式值為2.但是最好的結果是都不招供，函式值為10，故最壞均衡與最佳解比為formula_14。工作排程問題.排程問題其實是最壞均衡與最佳解比的一個例項。有formula_2個參與者，每個參與者都有一個任務要完成，他們可以從formula_16臺機器中選擇一臺來完成任務。在這一問題中最壞均衡與最佳解比對各行其是和集中安排機器進行了比較。每一臺機器都具有速度formula_17，每一項工作都具有權重formula_18。每名參與者都選擇一臺機器來完成工作，因此，每名參與者的決策為formula_19。定義第formula_20臺機器的負載為：formula_21參與者formula_22的成本函式為formula_23，也就是此人所選的機器負載。考慮到平均成本函式formula_24，我們稱之為最大完工時間。我們想到了純策略和混合策略這兩種策略，並且很容易知道混合策略時的最壞均衡與最佳解比肯定大於或等於純策略時的最壞均衡與最佳解比。道理很簡單，那是因為純策略是一種特殊的混合策略，就好比正方形是一種特殊的矩形。首先我們要討論是否存在純納許均衡。宣稱：在排程問題中，至少存在一個納什均衡。證明：我們想要全域最優解formula_25。這意味著按照這一種分配方式，我們能獲得最小的最大完工時間。但是僅知道這些還不夠，可能有多種分配方式有著共同的最大完工時間。因此，在這些分配方式裡面再選出擁有著最小的第二大完工時間的分配方式，以此類推，直到第formula_16大時篩選出唯一的分配方式。我們聲稱這是一個純策略的納什均衡。接下來可以運用反證法證明：假設某個參與者formula_22可以透過從機器formula_20移動到機器formula_29來改進自己的負載。這意味著移動後機器formula_29的負載依然小於移動前機器formula_20的負載。由於移動後機器formula_20的負載必須減少並且沒有其他機器受到影響，這意味著新分配肯定減少了第 formula_20大的負載。但是這樣一來就違背了之前選出的唯一的分配方式。 "Q.E.D."宣稱：對於每個工作排程的賽局，純PoA最多為formula_16。證明：不難求出，在在任何混合策略納許均衡formula_35時所獲得的收益上限為：formula_36為了清楚地說明情況，在純策略formula_37時，不難看出：formula_38由於上述情況也適用於社會最優，比較formula_39和formula_40的比率證明瞭該宣稱。 "Q.E.D"自私路線問題.佈雷斯悖論.考慮右圖中的交通網，有4000輛車打算在其中路上通行。透過的時間從起點到A點和從B點到終點均是路上車的數量除以100，而從起點到B點和從A點到終點均是固定的45分鐘。如果近路不存在，從起點到A點到終點需要的時間是 formula_41，而從起點到B點到終點需要的時間是 formula_42。如果其中一條路的透過時間較短，是不可以達到奈許均衡點的，因為理性的司機都會選擇較短的路。因為有4000輛車，從 formula_43 可以解得平均 formula_44，這樣每條路的平均透過時間都是 formula_45 分鐘。現在假設有了一條近路的時間都變成了85分鐘。如果大家都約定好不走近路，那麼都可以節約15分鐘的時間。但是，由於單個的司機總是能從抄近道上獲益，所以這種約定是不穩定的，佈雷斯悖論便出現了。
metadata: erhwenkuo/wikipedia-zhtw
metadata: 最壞均衡與最佳解比
metadata: https://zh.wikipedia.org/wiki?curid=7697041