若干组合优化对策模型中的算法问题
合作对策考虑的是如何将收益v(N)合理地分配给联盟N中的成员。根据不同的合理性要求产生了不同的对策解的概念，如核心，核子等等。在这篇论文中，我们主要讨论的对策模型是由Kalai和Zemel在1982年首先提出的网铬流对策，讨论的内容包括：网络流对策的核心稳定性和网络流对策中核子计算的算法问题，主要结果有：·我们先定义了一种特殊的弧，称之为亚元，亚元满足的性质是：在网络中去掉亚元后不会影响网络的最大流值。基于这一概念，我们证明了简单网络流对策有稳定的核心当且仅当网络中没有亚元。
·我们讨论了三个与核心稳定性密切相关的性质：核心的包容性、对策的精确性和可扩性的等价性，并证明了它们这三个性质与如下条件等价：在简单网络中每个(s，t)一截包含一个最小(s，t)一截。(其中s，t分别表示网络的发点和收点)·证明了可以在多项式时间内求解简单网络流对策的核子。
·证明了对于一般的网络流对策，有关核子的计算问题是NP-困难的。
非合作对策理论中，最重要、最核心的概念是纳什均衡。在论文的最后一部分中，本文讨论了一种基于线性规划约束的多人决策模型。首先，我们运用线性规划和对偶理论给出了纳什均衡点存在的充分必要条件，进而证明了在这种模型下的纳什均衡点可以在多项式时间内求解。其次，在原有的纳什均衡定义的基础上，我们定义了一个强均衡的概念：payoff-proof纳什均衡，并对所述决策模型研究了payoff-proof纳什均衡的性质和存在性。
网络流;核心;核子;对偶理论;纳什均衡;组合优化;对策解
中国海洋大学
硕士
应用数学
方奇志
2006
中文
O225
52
2007-08-07（万方平台首次上网日期，不代表论文的发表时间）