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

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

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

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

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

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

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