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

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

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

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

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

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