两类组合合作博弈的算法研究

发布时间：2017-05-28 14:08

  本文关键词：两类组合合作博弈的算法研究，由笔耕文化传播整理发布。

【摘要】：合作博弈描述了多主体系统中利益合理分配的方式。核心、最小核和核仁是一类可以保证系统稳定的分配方式。本文主要研究阈值匹配博弈和通路联盟博弈的最小核和核仁的求解问题。阈值匹配博弈定义在无向图G＝(V,E)上的一类组合合作博弈,其中V是图G的顶点集合,E是图G的边集合,局中人集合为y。给定阈值丁,如果G[司上的最大匹配的基数不小于T,则一个联盟S(?)V的收益是1；否则,收益为0。本文在第2章介绍了匹配博弈和阈值匹配博弈的定义和其解的计算复杂度,并指出阈值匹配博弈是匹配博弈的一种变型。当阈值匹配博弈定义在赋权图上时其最小核和核仁的计算时NP-难解的,本文主要研究定义在简单图上的阈值匹配博弈——阈值基数匹配博弈。当阈值基数匹配博弈的核心非空时,核心和核仁中的分配都可以在多项式时间找到。但是当其核心为空集时,问题将边的复杂的多。第3章讨论当闽值基数匹配博弈的核心为空集时最小核和核仁的算法。首先利用“分离-暗箱”的技术证明,给定一个阈值基数匹配博弈,计算最小核的值、计算或者验证最小核里的一个分配均可以在多项式时间内完成,并且对一大类阈值匹配博弈的最小核给出了直观的刻画。这个刻画在之后求解核仁时将起到至关重要的作用。其次，证明阈值匹配博弈的最小核和匹配拦截博弈的混合策略纳什均衡等价。最后,基予Gallai-Edmonds分解定理,给出了三类阈值基数匹配博弈的核仁的多项式时问算法：边联盟博弈(阈值T＝1的情况)、完美图阈值基数匹配博弈(当图含有一个完美匹配的情况)、阈值指派博弈(二部图上的阈值基数匹配博弈)。通路联盟博弈定义在网络D=(V,E；s,t)上的又一类组合合作博弈,其中V是网络D的顶点集合,E是网络D的弧集合,s和t分别是网络D的发点和收点。根据局中人集合为E或者V.可以将通路联盟博弈分成“路联盟博弈”和“点通路联盟博弈”。当S中包含一条s,t)-路时,联盟S取胜；否则S失败。第4章,首先介绍两种通路联盟博弈的定义和其核心，并指出当通路联盟博弈的核心非空时,核心和核仁里的分配可以很简单的求出。其次介绍通路联盟博弈的超可加覆盖——网络流博弈,并利用两者之间的关系指明了通路联盟博弈的CS-核心一定非空,且CS-核心中的分配与网络流博弈的核心中的分配一一对应。第5章,则讨论当通路联盟博弈的核心为空集时,其最小核和核仁的计算复杂度。首先利用通路联盟博弈和网络流博弈的关系以及线性规划对偶理论,证明边通路联盟博弈的最小核和核仁均可在多项式时间内求解。对于点通路联盟博弈的最小核和核仁的求解,可以在多项式时间内将其转化为边通路联盟博弈的情况,进而求解。最后证明通过多项式时间的变换,定义在无向网络中的两种通路联盟博弈的最小核和核仁都可以在多项式时间内求解。
【关键词】：博弈论 线性规划 最小核 核仁 阈值匹配博弈 通路联盟博弈
【学位授予单位】：中国海洋大学
【学位级别】：硕士
【学位授予年份】：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 阈值基数匹配博弈的最小核和核仁25-41
• 3.1 阈值基数匹配博弈的最小核25-28
• 3.2 匹配拦截博弈28-29
• 3.3 阈值匹配博弈的核仁29-41
• 3.3.1 边联盟博弈29-33
• 3.3.2 完美图的阈值基数匹配博弈33-37
• 3.3.3 阈值指派博弈37-41
• 4 通路联盟博弈41-45
• 4.1 通路联盟博弈41-42
• 4.2 通路联盟博弈的核心42-45
• 5 通路联盟博弈的最小核和核仁45-53
• 5.1 通路联盟博弈的最小核45-47
• 5.2 通路联盟博弈的核仁47-50
• 5.3 无向网络中的通路联盟博弈50-53
• 6 结论与展望53-55
• 参考文献55-59
• 致谢59-61
• 个人简历、发表的学术论文与研究成果61

【相似文献】

中国期刊全文数据库 前10条

1 张莹,田沁,杜宝剑;纤毛虫的大核与小核[J];生物学教学;2001年07期

2 刘星吟,陈琳,金立培;Cis-platin去似织毛虫Histriculus similes小核的研究[J];中山大学学报(自然科学版);2003年06期

3 任永娥,刘洪灿,徐纯锡,淡家林;发酵法生产小核菌多糖[J];微生物学通报;1992年03期

4 刘星吟;毛永真;李甘霖;金立培;;筛选冠突伪尾柱虫有小核细胞系和无小核细胞系饥饿期差异表达的ESTs[J];水生生物学报;2006年03期

5 金立培,刘小意,金华中;冠突伪尾柱虫接合过程中小核的形态发生作用[J];动物学报;2002年03期

6 赵柳;尹飞;倪兵;顾福康;;华美游仆虫大、小核的透射电镜和生化抽提扫描电镜观察[J];复旦学报(自然科学版);2007年06期

7 金立培,金华中;冠突伪尾柱虫小核对胞口结构稳定性的影响[J];动物学报;2002年02期

8 刘小意,金立培;念珠伪角毛虫小核体功能初步研究[J];动物学研究;2002年03期

9 潘重光;赵长生;赵则胜;陈德鑫;;He-Ne激光对蚕豆(Vicia faba)根尖细胞的诱变效应[J];上海农学院学报;1985年03期

10 刘星吟;金立培;;似织毛虫的小核体功能的研究[J];中山大学研究生学刊(自然科学、医学版);2002年03期

中国重要会议论文全文数据库 前1条

1 刘星吟;金华中;金立培;;Cis-platin去纤毛虫小核的研究[A];中国动物学会原生动物学分会第十二次学术讨论会论文摘要汇编[C];2003年

中国硕士学位论文全文数据库 前1条

1 李博;两类组合合作博弈的算法研究[D];中国海洋大学;2015年

  本文关键词：两类组合合作博弈的算法研究，，由笔耕文化传播整理发布。

本文编号：402790