基于最小费用支撑树的合作对策问题

论文摘要

对策论由于有其特殊的研究领域,且研究方法多种多样,因而与其它数学分支产生了较多的联系。近十年来,随着对策论的发展,它与组合最优化理论的联系越来越密切,两门学科互为对方提供数学手段,共同走向纵深。本文旨在将组合优化中的最小费用支撑树的理论技巧用于解决对策论中一些问题,从而加深它们之间的联系。主要工作如下:1.支付对策中局中人数目变化的合作对策问题,分别给出了局中人数目变化前后该合作对策的分配、核心、核仁、Shapley值的对应情况。2.局中人数目变化的最小费用支撑树对策问题。在局中人数目减少的情况下,给出了顶点相应减少的最小费用支撑树的算法,并基于该算法给出了最小费用支撑树对策联盟K直接离去以后的核心中的分配。因为在可以挽回联盟K的情况下该分配不满足总体支付最小性,所以又给出了可以挽回联盟K的情况下的一个更公平、更合理的分配,且这个分配具有联盟的稳定性和总体支付最小性。在局中人增加的情况下,讨论顶点及边相应增加的最小费用支撑树的变化情况,得出了局中人集合K?加入后的最小费用支撑树对策的核心中的分配。3.最小费用k度限制支撑树对策问题。分别给出了最小费用支撑树的源点度数大于k和小于k时,可行交换的具体形式及复杂性估计,并在此基础上改进了Glover-Klingman算法,给出了改进的Glover-Klingman算法的复杂性估计。利用对策中的威胁理论、旁支付理论制订了两种规则,分别给出了这两种规则对应下的特征函数,并利用这两个特征函数与最小费用支撑树对策特征函数的策略等价关系求出了核心中的分配,从而证明了在这两种规则下最小费用k度限制树对策的核心非空。4.加权最短路树形图对策问题。建立了最短路树形图对策和加权最短路树形图对策模型,并求出了此对策问题在多种意义下的分配。其中问题2、3、4是由最小费用支撑树对策延伸出来的支付对策问题。

论文目录

• 摘要
• Abstract
• 第一章 引言
• 1.1 组合对策的研究现状与发展趋势
• 1.2 论文的组织和安排
• 第二章 预备知识
• 2.1 合作n 人对策
• 2.2 最小费用支撑树对策
• 第三章 局中人数目变化时的支付对策
• 3.1 局中人数目变化时的分配
• 3.2 局中人数目变化时的核心
• 3.3 局中人变化时的核仁
• 3.4 局中人数目变化时的Shapley 值
• 3.5 小结
• 第四章 局中人数目变化的最小费用支撑树对策
• 4.1 局中人减少的最小费用支撑树对策
• 4.2 局中人增加的最小费用支撑树对策
• 4.3 小结
• 第五章 最小费用k 度限制树对策
• 5.1 最小费用k 度限制树
• 5.2 改进的Glover-Klingman 算法
• 5.3 最小费用k 度限制树对策模型
• 5.4 最小费用k 度限制树对策的核心
• 5.5 小结
• 第六章 加权最短路树形图对策
• 6.1 问题背景介绍及对策模型
• 6.2 基本概念
• 6.3 最短路树形图对策
• 6.4 加权最短路树形图对策
• 6.5 小结
• 结论
• 致谢
• 参考文献
• 附录 硕士阶段的主要工作