在平行機(jī)博弈排序中的近似強(qiáng)納什均衡問題.pdf

1、分類號： O224 學(xué)校單位代碼：10446 碩 士 學(xué) 位 論 文 論文題目： 論文題目：在平行機(jī)博弈排序中的近似強(qiáng)納什均衡問題 平行機(jī)博弈排序中的近似強(qiáng)納什均衡問題 研 究 生 姓 名 ： 李 松 松學(xué) 科、專 業(yè)： 數(shù)學(xué)、教育經(jīng)濟(jì)與管理 研 究 方 向 ： 排 序 導(dǎo)師姓名、職稱： 張玉忠 教授 論文完成時間： 2013 年 3 月 - 2 - 摘 要 本文研究的是在平行機(jī)博弈排

2、序模型中的近似的強(qiáng)納什均衡的問題。具體的，我們這里所說的平行機(jī)，是指一類最基本，最重要的平行機(jī)模型——同速機(jī)。在平行機(jī)（同速機(jī)）博弈排序模型中，每一個工件（客戶）都要求自主選擇機(jī)器（服務(wù)器）中的一個來加工它自己，這樣每個工件的目標(biāo)就是希望能極小化它自己的成本。在這里它的成本是指它所選擇的那臺機(jī)器的總完工時間（workload）的函數(shù)。顯然，一個已經(jīng)選擇好機(jī)器的工件如果發(fā)現(xiàn)它改選其它的某個機(jī)器會使自己的成本降低的話，它會自主的改變自己原來

3、的選擇。而每個工件的選擇會影響到別的工件的成本。 一個納什均衡是一個工件的排序狀態(tài)（工件的策略組合） 。其中工件的策略是指這個工件選擇哪一臺機(jī)器來加工它自己，而當(dāng)每一個工件都給出一個策略以后，我們就得到了一個工件的策略組合，即一個工件的排序狀態(tài)。作為一個納什均衡，這個工件的策略組合必須滿足以下條件：就是在其它所有工件的策略都不變的情況下，任何一個工件如果單方面的改變自己的策略，那么它自己的成本不會變的比原來更好。顯然納什均衡是一個比較穩(wěn)

4、定的狀態(tài)。在我們所討論的這個博弈排序模型中，要想要找到一個納什均衡是十分簡單的，然而在一個納什均衡中，如果有若干個工件彼此聯(lián)絡(luò)從而形成了一個聯(lián)盟，那么這個聯(lián)盟的一次聯(lián)合改變策略的行動就有可能打破原來的穩(wěn)定狀態(tài)。我們定義一個強(qiáng)納什均衡是一個工件的排序狀態(tài)（工件的策略組合） ，它滿足：對于任何一個工件的聯(lián)盟（也包括單個工件形成的聯(lián)盟） ，在聯(lián)盟外工件都不改變策略的情況下，聯(lián)盟內(nèi)工件都改變自己的策略，那么不會出現(xiàn)聯(lián)盟中的每個工件都受益（嚴(yán)格降

5、低了自己的成本）的情況。雖然強(qiáng)納什均衡有很好的穩(wěn)定性，但一般來說它是難以實現(xiàn)的，所以我們定義近似強(qiáng)納什均衡的概念。 在一個平行機(jī)博弈排序問題中，給出任何一個工件的排序狀態(tài)（工件的策略組合） ，我們定義一個工件一次背離（改變策略）的改進(jìn)率為：它在背離前與背離后的自己的成本的比值。一個工件的改進(jìn)率反映出了這個工件進(jìn)行這次背離行動的動力。一個納什均衡點被稱為 ρ- 近似強(qiáng)納什均衡(ρ≥1)，如果它滿足：任何一個工件的聯(lián)盟都不能通過該聯(lián)盟的一次

6、單獨聯(lián)合背離而使聯(lián)盟內(nèi)的每一個工件都獲得一個嚴(yán)格大于ρ的改進(jìn)率。顯然ρ越小則原來的排序就越穩(wěn)定，當(dāng)ρ=1 時原來的排序就是強(qiáng)納什均衡點。 在本文中，我們證明了對于平行機(jī)博弈排序問題，當(dāng)機(jī)器個數(shù)不超過 8 臺時，任何一個納什均衡點都是一個 5/4 近似強(qiáng)納什均衡，并且這個界是緊的。更進(jìn)一步的，當(dāng)機(jī)器個數(shù)為 m(m≥9)臺時，任何一個納什均衡點都是一個 (32 – 2m-32(m-1)2 ) 近似強(qiáng)納什均衡。 關(guān)鍵詞：納什均衡；平行機(jī)博弈