New Characterizations of Core Imputations of Matching and b-Matching Games
New Characterizations of Core Imputations of Matching and b-Matching Games
复制标题
匹配和 b 匹配游戏核心估算的新特征
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
V. Vazirani
中科院分区：
文献类型：
--
作者：
V. Vazirani
我们为以下游戏给出了核心估算的新特征： * 分配游戏。 * 并发游戏，即非空核心的一般图匹配游戏。 * 无约束的二分 $b$ 匹配游戏（边可以匹配多次）。 * 受限二分$b$匹配游戏（边最多可以匹配一次）。 Shapley 和 Shubik 的经典论文 \cite{Shapley1971assignment} 表明，分配博弈的核心插补恰恰是博弈的 LP 松弛对偶的最优解。在此基础上，邓等人。 \cite{Deng1999algorithms} 给出了一个通用框架，它为几个基本组合游戏产生了类似的特征。有趣的是，他们的框架并不适用于上述最后两款游戏。反过来，我们表明这些游戏的一些核心估算对应于最佳对偶解决方案，而其他则不然。这就引出了理解后者起源的诱人问题。我们还在前两场比赛的核心估算中提出了经纪人和团队所产生的利润的新特征。我们对第一款游戏的描述比第二款游戏的描述更强；根本原因是Birkhoff多胞形的顶点刻画能力强于Balinski多胞形。
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.