We give new characterizations of core imputations for the following games: o The assignment game. o Concurrent games, i.e., general graph matching games having non-empty core. o The unconstrained bipartite $b$-matching game (edges can be matched multiple times). o 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.
翻译:我们给出了以下游戏核心估算的新特征: o 分配游戏。 同步游戏, 即普通图形匹配游戏, 具有非空心核心的普通图形匹配游戏 。 o 未受限制的两边美元对齐游戏( 组合可以多次匹配 ) 。 o 受限制的两边美元对齐游戏( 组合最多可以一次匹配 ) 。 经典的 Shapley 和 Shubik 和 Shubik\ cite Shapley1971traction 的纸张对齐了。 经典的 Shabik 和 Shubik Shapley- 1971traction 显示, 分配游戏的核心估算正是LP 放松游戏双轨的最佳解决方案。 以这个游戏为基础, Deng et al.\ cite{ Deng1999algoriths} 提供了一个总框架, 为一些基本的组合游戏提供了相似的描述。 有趣的是, 它们的框架不适用于上述最后两场游戏。 反过来, 我们显示这些游戏的一些核心的估算与第二个游戏的二次对比, 也是我们两个游戏的第二个游戏的累积游戏的分算。