The assignment game forms a paradigmatic setting for studying the core -- its pristine structural properties yield an in-depth understanding of this quintessential solution concept within cooperative game theory. In turn, insights gained provide valuable guidance on profit-sharing in real-life situations. In this vein, we raise three basic questions and address them using the following broad idea. Consider the LP-relaxation of the problem of computing an optimal assignment. On the one hand, the worth of the assignment game is given by the optimal objective function value of this LP, and on the other, the classic Shapley-Shubik Theorem \cite{Shapley1971assignment} tells us that its core imputations are precisely optimal solutions to the dual of this LP. These two facts naturally raise the question of viewing core imputations through the lens of complementarity. In turn, this leads to a resolution of all our questions.
翻译:派任游戏形成一个研究核心的范式环境 -- -- 其纯纯结构属性在合作游戏理论中产生了对这一典型解决方案概念的深入理解。 反过来, 获得的洞察力为实际生活中的利润分享提供了宝贵的指导。 本着这一思路, 我们提出三个基本问题, 并用以下广泛想法解决这些问题。 考虑LP松绑计算最佳任务分配的问题。 一方面, 派任游戏的价值是由这个LP的最佳客观功能值给予的, 而另一方面, 经典的 Shaply- Shubik Theorem\cite{Shapley1971straction} 告诉我们, 其核心估算是这个LP的双重目标的最佳解决方案。 这两个事实自然提出了从互补的角度看待核心包涵的问题。 反过来, 这又导致我们所有问题的解决。