论文标题
通过总二一个完整性的游戏核心，并应用于完美的图形和多功能。
Cores of Games via Total Dual Integrality, with Applications to Perfect Graphs and Polymatroids
论文作者
论文摘要
LP二元理论从这个概念的早期到当前的游戏，在对游戏核心的研究中发挥了核心作用。 Shapley和Shubik \ cite {Shapley1971 Assignment}的经典论文引入了利用该理论力量的“正确”方式，即采摘LP-Relaxations支持Polyhedra具有积分顶点的问题。到目前为止，后一个事实是通过证明基础线性系统的约束矩阵是{\ em完全不可测}来确定的。 我们试图将这种方法用于其逻辑下一步 - {\ em使用Total Dual Entighation} - 从而解决了新的游戏类别，这些游戏起源于组合优化的两种主要理论，即完美的图形和多肌动物。在前者中，我们谈到了稳定的集合和集团游戏，在后者中，我们解决了Matroid Independent Set Game。对于这些游戏中的每一个，我们都证明了核心弹药的集合正是双LPS的最佳解决方案。 另一个新颖的是，游戏的价值在子润滑之间分配。以前的作品遵循分配给单个代理的{\ em自下而上的过程}；分配给子加度仅仅是分配给其代理的总和。我们游戏的{\ em自然过程是自上而下的}。最佳双重分配给大联盟中的“对象”；子钙化继承了其具有非空交叉点的每个对象的分配。
LP-duality theory has played a central role in the study of cores of games, right from the early days of this notion to the present time. The classic paper of Shapley and Shubik \cite{Shapley1971assignment} introduced the "right" way of exploiting the power of this theory, namely picking problems whose LP-relaxations support polyhedra having integral vertices. So far, the latter fact was established by showing that the constraint matrix of the underlying linear system is {\em totally unimodular}. We attempt to take this methodology to its logical next step -- {\em using total dual integrality} -- thereby addressing new classes of games which have their origins in two major theories within combinatorial optimization, namely perfect graphs and polymatroids. In the former, we address the stable set and clique games and in the latter, we address the matroid independent set game. For each of these games, we prove that the set of core imputations is precisely the set of optimal solutions to the dual LPs. Another novelty is the way the worth of the game is allocated among sub-coalitions. Previous works follow the {\em bottom-up process} of allocating to individual agents; the allocation to a sub-coalition is simply the sum of the allocations to its agents. The {\em natural process for our games is top-down}. The optimal dual allocates to "objects" in the grand coalition; a sub-coalition inherits the allocation of each object with which it has non-empty intersection.
