阈值基数匹配游戏的最小核与核计算算法

本文主要探讨了阈值基数匹配游戏（Threshold Cardinality Matching Games, TCMG）中的最小核心（Least Core）和核（Nucleolus）算法设计问题。阈值基数匹配游戏是博弈论在图论中的一个重要应用，它考虑了在满足特定条件（如每个个体的阈值限制）下的资源分配问题。最小核心是指游戏中所有可能的核心中支付最少的一组分配，而核则是指一组既不可能被全体成员同时拒绝，又能达到纳什均衡的稳定分配。 首先，研究者证明了在TCMG中计算最小核心价值、查找以及验证最小核心支付的问题都可以在多项式时间内得到解决。这表明尽管这类游戏可能具有复杂性，但在理论上可以通过有效的算法策略来求解核心结构。 接着，文章聚焦于一类特殊TCMG——当阈值T等于1时的情况。在这个场景下，作者利用图论中的Gallai-Edmonds分解理论，给出了核的精确表述。Gallai-Edmonds分解是一种重要的图论工具，它可以帮助分析图的结构，从而简化对核的计算。 然而，当阈值T与输入规模有关时，情况变得更加复杂。论文表明，在二分图和拥有完美匹配的图中，可以实现核的高效计算。这里的“完美匹配”是指图中每条边恰好连接两个不同的顶点，这对于优化核的计算有着重要意义，因为这种图结构提供了额外的结构特性。 这篇论文不仅关注了阈值基数匹配游戏的核心概念，还着重于其算法上的实际应用，尤其是在特定阈值和特定图结构下的核心和核计算问题。这些研究成果对于理解此类博弈模型的性质及其在实际问题中的应用具有重要价值，也为未来的研究者提供了计算上的指导和方法论支持。