论文标题
匹配和$ b $匹配游戏的核心归档的新特征
New Characterizations of Core Imputations of Matching and $b$-Matching Games
论文作者
论文摘要
我们为以下游戏提供了新的核心归档特征： *作业游戏。 *并发游戏，即具有非空心核心的一般图形匹配游戏。 *不受约束的两分$ b $匹配游戏（可以多次匹配边缘）。 *受约束的两分$ b $匹配游戏（边缘最多可以匹配一次）。 Shapley和Shubik \ cite {Shapley1971 Assignment}的经典论文表明，分配游戏的核心归咎于这是对游戏LP-Relaxation双重化的最佳解决方案。在此基础上，邓等人。 \ cite {deng1999algorithms}给出了一个通用框架，为几个基本的组合游戏提供了类似的特征。有趣的是，他们的框架不适用于上述最后两场比赛。反过来，我们表明这些游戏的某些核心归咎于最佳双重解决方案，而其他游戏则不对。这导致了理解后者起源的诱人问题。我们还介绍了代理商和团队在前两场比赛中核心推荐的利润的新特征。我们对第一场比赛的表征比第二场比赛要强。根本的原因是，伯克霍夫多层人物的顶点的表征比巴林斯基多层人士强。
We give new characterizations of core imputations for the following games: * The assignment game. * Concurrent games, i.e., general graph matching games having non-empty core. * The unconstrained bipartite $b$-matching game (edges can be matched multiple times). * The constrained bipartite $b$-matching game (edges can be matched at most once). The classic paper of Shapley and Shubik \cite{Shapley1971assignment} showed that core imputations of the assignment game are precisely optimal solutions to the dual of the LP-relaxation of the game. Building on this, Deng et al. \cite{Deng1999algorithms} gave a general framework which yields analogous characterizations for several fundamental combinatorial games. Interestingly enough, their framework does not apply to the last two games stated above. In turn, we show that some of the core imputations of these games correspond to optimal dual solutions and others do not. This leads to the tantalizing question of understanding the origins of the latter. We also present new characterizations of the profits accrued by agents and teams in core imputations of the first two games. Our characterization for the first game is stronger than that for the second; the underlying reason is that the characterization of vertices of the Birkhoff polytope is stronger than that of the Balinski polytope.
