發(fā)布時(shí)間：2017-05-28 14:08

  本文關(guān)鍵詞：兩類組合合作博弈的算法研究，由筆耕文化傳播整理發(fā)布。

【摘要】：合作博弈描述了多主體系統(tǒng)中利益合理分配的方式。核心、最小核和核仁是一類可以保證系統(tǒng)穩(wěn)定的分配方式。本文主要研究閾值匹配博弈和通路聯(lián)盟博弈的最小核和核仁的求解問題。閾值匹配博弈定義在無向圖G＝(V,E)上的一類組合合作博弈,其中V是圖G的頂點(diǎn)集合,E是圖G的邊集合,局中人集合為y。給定閾值丁,如果G[司上的最大匹配的基數(shù)不小于T,則一個(gè)聯(lián)盟S(?)V的收益是1；否則,收益為0。本文在第2章介紹了匹配博弈和閾值匹配博弈的定義和其解的計(jì)算復(fù)雜度,并指出閾值匹配博弈是匹配博弈的一種變型。當(dāng)閾值匹配博弈定義在賦權(quán)圖上時(shí)其最小核和核仁的計(jì)算時(shí)NP-難解的,本文主要研究定義在簡單圖上的閾值匹配博弈——閾值基數(shù)匹配博弈。當(dāng)閾值基數(shù)匹配博弈的核心非空時(shí),核心和核仁中的分配都可以在多項(xiàng)式時(shí)間找到。但是當(dāng)其核心為空集時(shí),問題將邊的復(fù)雜的多。第3章討論當(dāng)閩值基數(shù)匹配博弈的核心為空集時(shí)最小核和核仁的算法。首先利用“分離-暗箱”的技術(shù)證明,給定一個(gè)閾值基數(shù)匹配博弈,計(jì)算最小核的值、計(jì)算或者驗(yàn)證最小核里的一個(gè)分配均可以在多項(xiàng)式時(shí)間內(nèi)完成,并且對一大類閾值匹配博弈的最小核給出了直觀的刻畫。這個(gè)刻畫在之后求解核仁時(shí)將起到至關(guān)重要的作用。其次，證明閾值匹配博弈的最小核和匹配攔截博弈的混合策略納什均衡等價(jià)。最后,基予Gallai-Edmonds分解定理,給出了三類閾值基數(shù)匹配博弈的核仁的多項(xiàng)式時(shí)問算法：邊聯(lián)盟博弈(閾值T＝1的情況)、完美圖閾值基數(shù)匹配博弈(當(dāng)圖含有一個(gè)完美匹配的情況)、閾值指派博弈(二部圖上的閾值基數(shù)匹配博弈)。通路聯(lián)盟博弈定義在網(wǎng)絡(luò)D=(V,E；s,t)上的又一類組合合作博弈,其中V是網(wǎng)絡(luò)D的頂點(diǎn)集合,E是網(wǎng)絡(luò)D的弧集合,s和t分別是網(wǎng)絡(luò)D的發(fā)點(diǎn)和收點(diǎn)。根據(jù)局中人集合為E或者V.可以將通路聯(lián)盟博弈分成“路聯(lián)盟博弈”和“點(diǎn)通路聯(lián)盟博弈”。當(dāng)S中包含一條s,t)-路時(shí),聯(lián)盟S取勝；否則S失敗。第4章,首先介紹兩種通路聯(lián)盟博弈的定義和其核心，并指出當(dāng)通路聯(lián)盟博弈的核心非空時(shí),核心和核仁里的分配可以很簡單的求出。其次介紹通路聯(lián)盟博弈的超可加覆蓋——網(wǎng)絡(luò)流博弈,并利用兩者之間的關(guān)系指明了通路聯(lián)盟博弈的CS-核心一定非空,且CS-核心中的分配與網(wǎng)絡(luò)流博弈的核心中的分配一一對應(yīng)。第5章,則討論當(dāng)通路聯(lián)盟博弈的核心為空集時(shí),其最小核和核仁的計(jì)算復(fù)雜度。首先利用通路聯(lián)盟博弈和網(wǎng)絡(luò)流博弈的關(guān)系以及線性規(guī)劃對偶理論,證明邊通路聯(lián)盟博弈的最小核和核仁均可在多項(xiàng)式時(shí)間內(nèi)求解。對于點(diǎn)通路聯(lián)盟博弈的最小核和核仁的求解,可以在多項(xiàng)式時(shí)間內(nèi)將其轉(zhuǎn)化為邊通路聯(lián)盟博弈的情況,進(jìn)而求解。最后證明通過多項(xiàng)式時(shí)間的變換,定義在無向網(wǎng)絡(luò)中的兩種通路聯(lián)盟博弈的最小核和核仁都可以在多項(xiàng)式時(shí)間內(nèi)求解。
【關(guān)鍵詞】：博弈論 線性規(guī)劃 最小核 核仁 閾值匹配博弈 通路聯(lián)盟博弈
【學(xué)位授予單位】：中國海洋大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：O157.5;O225
【目錄】：

• 摘要5-7
• Abstract7-11
• 1 緒論11-21
• 1.1 合作博弈的研究背景及定義11-13
• 1.2 合作博弈的解的概念13-16
• 1.3 簡單博弈16-18
• 1.4 有效算法18-19
• 1.5 本文的主要工作19-21
• 2 閾值匹配博弈21-25
• 2.1 閾值匹配博弈21-23
• 2.2 Gallai-Edmonds分解定理23-25
• 3 閾值基數(shù)匹配博弈的最小核和核仁25-41
• 3.1 閾值基數(shù)匹配博弈的最小核25-28
• 3.2 匹配攔截博弈28-29
• 3.3 閾值匹配博弈的核仁29-41
• 3.3.1 邊聯(lián)盟博弈29-33
• 3.3.2 完美圖的閾值基數(shù)匹配博弈33-37
• 3.3.3 閾值指派博弈37-41
• 4 通路聯(lián)盟博弈41-45
• 4.1 通路聯(lián)盟博弈41-42
• 4.2 通路聯(lián)盟博弈的核心42-45
• 5 通路聯(lián)盟博弈的最小核和核仁45-53
• 5.1 通路聯(lián)盟博弈的最小核45-47
• 5.2 通路聯(lián)盟博弈的核仁47-50
• 5.3 無向網(wǎng)絡(luò)中的通路聯(lián)盟博弈50-53
• 6 結(jié)論與展望53-55
• 參考文獻(xiàn)55-59
• 致謝59-61
• 個(gè)人簡歷、發(fā)表的學(xué)術(shù)論文與研究成果61

【相似文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前10條

1 張瑩,田沁,杜寶劍;纖毛蟲的大核與小核[J];生物學(xué)教學(xué);2001年07期

2 劉星吟,陳琳,金立培;Cis-platin去似織毛蟲Histriculus similes小核的研究[J];中山大學(xué)學(xué)報(bào)(自然科學(xué)版);2003年06期

3 任永娥,劉洪燦,徐純錫,淡家林;發(fā)酵法生產(chǎn)小核菌多糖[J];微生物學(xué)通報(bào);1992年03期

4 劉星吟;毛永真;李甘霖;金立培;;篩選冠突偽尾柱蟲有小核細(xì)胞系和無小核細(xì)胞系饑餓期差異表達(dá)的ESTs[J];水生生物學(xué)報(bào);2006年03期

5 金立培,劉小意,金華中;冠突偽尾柱蟲接合過程中小核的形態(tài)發(fā)生作用[J];動物學(xué)報(bào);2002年03期

6 趙柳;尹飛;倪兵;顧�？�;;華美游仆蟲大、小核的透射電鏡和生化抽提掃描電鏡觀察[J];復(fù)旦學(xué)報(bào)(自然科學(xué)版);2007年06期

7 金立培,金華中;冠突偽尾柱蟲小核對胞口結(jié)構(gòu)穩(wěn)定性的影響[J];動物學(xué)報(bào);2002年02期

8 劉小意,金立培;念珠偽角毛蟲小核體功能初步研究[J];動物學(xué)研究;2002年03期

9 潘重光;趙長生;趙則勝;陳德鑫;;He-Ne激光對蠶豆(Vicia faba)根尖細(xì)胞的誘變效應(yīng)[J];上海農(nóng)學(xué)院學(xué)報(bào);1985年03期

10 劉星吟;金立培;;似織毛蟲的小核體功能的研究[J];中山大學(xué)研究生學(xué)刊(自然科學(xué)、醫(yī)學(xué)版);2002年03期

中國重要會議論文全文數(shù)據(jù)庫 前1條

1 劉星吟;金華中;金立培;;Cis-platin去纖毛蟲小核的研究[A];中國動物學(xué)會原生動物學(xué)分會第十二次學(xué)術(shù)討論會論文摘要匯編[C];2003年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前1條

1 李博;兩類組合合作博弈的算法研究[D];中國海洋大學(xué);2015年

  本文關(guān)鍵詞：兩類組合合作博弈的算法研究，，由筆耕文化傳播整理發(fā)布。

本文編號：402790