通訊網(wǎng)絡(luò)中的算法博弈.pdf

1、在現(xiàn)實世界中的大多數(shù)復雜網(wǎng)絡(luò),例如互聯(lián)網(wǎng),都是由數(shù)以千計的大大小小的用戶(或代理商)組成的,這些用戶都試圖使自己的收益最大化。這樣的用戶被稱為自利的(或者自私的,理性的)的用戶。對于這樣的大規(guī)模非合作網(wǎng)絡(luò)問題,博弈論和數(shù)理經(jīng)濟學為我們提供了很好的研究手段。為了衡量整個系統(tǒng)性能的優(yōu)劣程度,我們設(shè)立一個目標函數(shù)作為評價標準,稱之為系統(tǒng)目標函數(shù),它的最優(yōu)解稱為全局最優(yōu)解。從單獨的用戶來看,每個用戶又都有一個反映其個人偏好的收益函數(shù),理性的用戶

2、都是以最大化其收益函數(shù)來選擇策略的。顯然,所有自利用戶選擇的策略組合往往不是全局最優(yōu),甚至和全局最優(yōu)值相差甚遠。 近年來,計算機科學家們對估計非合作網(wǎng)絡(luò)下的穩(wěn)定狀態(tài)和全局最優(yōu)解的差距表現(xiàn)出濃厚的興趣。Koutsoupias和Papadimitriou在文獻[44;55]中正式提出調(diào)和率的概念,用于研究所有實例下納什均衡對應的系統(tǒng)費用和全局最優(yōu)解的最大比率。這個概念量化了系統(tǒng)在完全缺乏中央調(diào)控的情況下,納什均衡解和全局最優(yōu)解的最大

3、差值。與之相連的另一個概念是穩(wěn)定率,它是所有實例下最好的納什均衡(使系統(tǒng)目標最優(yōu)的納什均衡)和全局最優(yōu)值的最大比率。穩(wěn)定率有著網(wǎng)絡(luò)協(xié)議方面的現(xiàn)實背景,在非合作網(wǎng)絡(luò)中,一方面用戶可以理性的選擇自己的行為策略,網(wǎng)絡(luò)的管理者不能對用戶采取任何強制的措施；另一方面網(wǎng)絡(luò)的管理者又想得到一個系統(tǒng)總收益盡可能大的穩(wěn)定解,怎么才能這滿足兩方面的要求呢?很自然的,網(wǎng)絡(luò)管理者可以想到以下方案：先制定一個系統(tǒng)總收益盡可能大的穩(wěn)定的網(wǎng)絡(luò)用戶協(xié)議(即如果用戶都按

4、照這個協(xié)議行動,那么它構(gòu)成一個納什均衡),并向用戶推薦這個協(xié)議。穩(wěn)定率反映的是面對自利的用戶,在最壞的情況下,網(wǎng)絡(luò)管理者所能得到的最大收益和全局最優(yōu)解的比率。 計算機科學家感興趣的另一個主題是怎么設(shè)計網(wǎng)絡(luò)以有效的避免Braess悖論。Braess悖論并不是說數(shù)學理論上有什么自相矛盾的地方,而是反映一個和人們的直覺相違背的現(xiàn)象。1968年Dietrich Braess[11]舉出了一個實例,說明交通網(wǎng)絡(luò)中增加一條通路不僅沒有改善網(wǎng)

5、絡(luò)交通,反而使網(wǎng)絡(luò)上的出行時間增加了,而且是所有出行者的出行時間都增加了。自此以后,這種出力不討好且與人們直觀感受相背的交通網(wǎng)絡(luò)現(xiàn)象就被命名為Braess悖論。Braess悖論激發(fā)了如下的網(wǎng)絡(luò)設(shè)計問題[60]：即給定一個網(wǎng)絡(luò),這個網(wǎng)絡(luò)中是否存在悖論邊?如何高效地尋找圖中存在的悖論邊并去掉這些邊,使網(wǎng)絡(luò)處于最優(yōu)的納什均衡狀態(tài)(即最壞的納什均衡對應的系統(tǒng)目標值盡量的小)?對這個問題進行進一步推廣,又可以提出另外一個網(wǎng)絡(luò)設(shè)計問題,稱為有選擇性

6、的網(wǎng)絡(luò)設(shè)計問題[5]：給定一個網(wǎng)絡(luò)G=(V,E),以及一個邊子集E1E,如何找出G的一個子圖H,使得H包含邊子集E1,且子圖日上的網(wǎng)絡(luò)處于最優(yōu)的納什均衡狀態(tài)?換句話說,就是在不涉及邊子集E1的情況下,如何高效地尋找圖中存在的悖論邊并去掉這些邊,使網(wǎng)絡(luò)處于最優(yōu)的納什均衡狀態(tài)? 本文分為以下三個方面：首先,我們考慮線性擁塞博弈,對總體加權(quán)延遲函數(shù)、用戶延遲和函數(shù)、資源延遲和函數(shù)等三種系統(tǒng)目標函數(shù),分別給出了穩(wěn)定率的上界。對帶全局優(yōu)先序的擁塞