布雷斯悖論

布雷斯悖論(英語:Braess's paradox)是1968年由德國數學家迪特里希·布雷斯提出的一個悖論,它是指在一個交通網絡上增加一條路段反而使網絡上的旅行時間增加;這一附加路段不但沒有減少交通延滯,反而降低了整個交通網絡的服務水準。

這一悖論在電網和生物系統中也有相似的例子。理論上,在一些情況下,去除網絡的一部分可能可以改善網絡。這一悖論可以解釋現有主要道路關閉後交通反而改善的例子。這種出力不討好且與人們直觀感受相背的現象主要源於納殊均衡並不一定使社會最優化。

發現和定義

德國波鴻魯爾大學的數學家迪特里希·布雷斯在進行交通建模英語traffic modelling時發現,增加一條新道路可能反而會阻礙路網的交通流。他的理解是,如果每個司機都做出最優化的利己決策,即選擇最快的路線,那麼他們可能會過度使用捷徑來減少出行時間。布雷斯的發現背後的思想是,納殊均衡可能並不意味着通過網絡的整體流量最佳。[1]

悖論的敘述如下

對於路網中的每一點,給定從該點出發的車輛數量和車輛的目的地。在這些條件下,人們希望預估交通流的分佈。一條街道是否優於另一條,不僅取決於道路品質,還取決於車流密度。如果每個司機都選擇看起來對他們最優的道路,由此產生的交通時間未必是最小的。以下例子能夠表明這點:道路網絡的擴展可能導致交通重新分配,導致個人交通時間變長。

在某些情況下,當交通參與者「自私」地選擇路徑時,向網絡添加額外的負載能力反而會降低整體性能。這是因為這樣的系統的納殊均衡不一定是最優的。網絡的變化形成了新的博弈結構,導致了囚徒困境。在納殊均衡中,司機沒有改變路線的動機。當系統不處於納殊均衡時,單個司機可以通過改變他們走的路線來減少各自的出行時間。在布雷斯悖論的情景下,儘管整體性能下降,司機仍會繼續切換路線,直到達到納殊均衡。

例子

 
布雷斯悖論的例子

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

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

參見

參考文獻

  1. ^ New Scientist, 42nd St Paradox: Cull the best to make things better頁面存檔備份,存於互聯網檔案館), 16 January 2014 by Justin Mullins