博弈論簡單應用之一：

網絡流量的博弈論模型（對應第8章）網絡中的博弈公路交通網十一長假，是否出門？走哪條路線？有意無意中，你會想：別人會怎么樣？博弈論思想的一個典型應用回顧博弈問題討論的核心概念：均衡給定一個博弈設置（參與人，策略，收益），博弈結果會如何？“互為最佳應對”的策略組，即“均衡”每個人，都按照對他人理性行為的預期，決定自己的最佳行動（理性的）每個人實際采取的行動與其他人的預期一致該狀態下所有參與者的策略互為最佳應對，任何個人都沒有理性的理由改變第8章：網絡流量的博弈論模型布雷斯悖論－如果結構不合理，增加資源可能更糟網絡中的博弈：一個簡化的例子參與人：4000位司機策略：“走上面”和“走下面”回報：行駛時間（越小越好），顯然也取決于他人的策略有4000輛車，都要從A到B均衡？一種沒人要調整的選擇狀態4000輛車，要從A到B此時，若某人要改變，則他的行駛時間2001/100+45>65，因此沒人會改變均衡：每條路上2000輛車；對每輛車而言，對應回報為65設想政府要改善民生，新修了一條快速路注意，在沒修這條路前，均衡中行駛時間是65如果某人盤算改變為ADB，則他的行駛時間將變為45/100>80，于是他不會改變！均衡是大家都走：ACDB每人行駛時間為4000/100+0/100=80！！！布雷斯悖論出現！會發生什么情況？為什么大家不像從前那樣？你會很合理地想走ACDB。也就是說，從前那樣的模式在均衡態是不可能的（不均衡，有人有動機改變）你會這么想，其他人呢？會不會變成2000人走ACDB，另外2000人走ADB？若你是決定走上面的2000人之一，看到了這個局面，此時會不會有什么想法？這種問題的一般性如何？對于“任意交通網”和“線性通行時間”

函數，是不是總存在一個均衡？若在一條邊（e）上的通行時間函數可表為：Te(x)=ax+b，其中x為在該邊上的車輛數，則稱在該邊上是線性通行時間函數均衡：在車輛群所體現的行駛路線（即每人的選擇）模式中，沒有司機可通過改變線路縮短自己的通行時間答案是肯定的！如何證明？深度學習材料之一均衡路線模式的存在性證明（1）思路的出發點：給定任意初始交通模式，若不是均衡，那么就存在一個司機，能夠通過改變路線縮短自己的通行時間假設他如此做了，于是得到一個新的交通模式，若不是均衡，那么就存在一個司機，能夠通過改變路線縮短自己的通行時間…如此下去，為什么會停止？（即達到均衡）均衡路線模式的存在性證明（2）在網絡交通模式上定義一個適當的量，使得當一個司機選擇縮短自己行駛時間的路線后，新模式的這個量嚴格減小這個量不能是所有車輛的行駛時間之和，因為一輛車的縮短了，其他的可能因此加長了，總時間的變化難以說清楚PotentialEnergy（勢能）對于一條邊e，Energy(e)=Te(1)+Te(2)+…+Te(x)對于一個交通模式，ΣEnergy(e)然后說明，司機的每一次縮短行駛時間的路線改變都使這個模式勢能下降－－恰好等于他行駛時間的減少Te()為邊e上的通行時間函數如何說明司機改換路線的效果？放棄原來的路線；走一條新路：時間減少設e是原來路線上的一條邊，放棄意味著在那條邊上的車輛數從x變為x-1，對應該邊上的勢能變化為Te(1)+Te(2)+…+Te(x)

Te(1)+Te(2)+…+Te(x-1)即降低的數值恰好為他當前在該邊上的行駛時間走新路，則在一條邊上引起的勢能增加等于新的行駛時間（Te(y+1)）也就是新模式的勢能嚴格小于先前的因為改變路線的車的新老行駛時間要有：深度學習內容（之二）均衡狀態下車輛行駛時間之和（社會成本）可能不是最少（社會最優）的，但也不會太差（嚴格上界為4/3倍）為簡單起見，教材中證明了一個弱一點（不超過2倍）的結果對于每條邊，依然有線性通行時間假設如何說明？以勢能做橋梁，建立它與行駛時間之間的關系均衡態社會成本上界的證明一輛車在邊上的通行時間：Te(x)=aex+be其中e為邊的標識，x為該邊上的車輛數一條邊的勢能：Energy(e)=Te(1)+Te(2)+…+Te(x)一條邊的社會成本：Cost(e)=xTe(x)關鍵認識：對邊求和就得到一個交通模式的總能量與社會成本的關系從通行函數的線性性以及Energy和Cost的表達式容易看出這不等式但我們需要的是均衡模式（Z’）下的社會成本與社會優化模式（Z）下的社會成本之間的關系，即：關鍵思路：從一個社會優化模式開始，不斷施行“最佳應對”，直到達到一個均衡模式，看其間勢能與社會成本的變化，并利用前面的關系聯立即得。從Z（社會優化）

到Z’（均衡）要點博弈論思想的強化均衡：參與者不能