论文标题
关于分数匹配的稳定性和激励兼容性的共存
On the Coexistence of Stability and Incentive Compatibility in Fractional Matchings
论文作者
论文摘要
在社会选择文献中对稳定的比赛进行了广泛的研究。重点主要是在整体匹配上，其中两侧的节点完全匹配。部分匹配是积分匹配的凸组合，是积分匹配的自然扩展。仅最近才开始受到分数匹配的稳定性主题。此外，在分数匹配的背景下，激励兼容性很少受到关注。以此为背景，我们的论文研究了机制激励兼容的重要主题，以找到稳定的分数匹配。我们与以红衣主教公用事业形式表达的偏好合作。我们的第一个结果是，不可能的结果是，没有任何产生稳定的分数匹配的机制可以兼容甚至是近似奖励兼容的机制。这提供了寻求特殊类别的匹配实例的动机，这些实例存在激励机制，从而产生稳定的分数匹配。我们的研究导致了一类匹配实例，这些实例接受了独特的稳定分数匹配。我们首先表明，当且仅当给定匹配实例满足有条件的相互偏好（CMFP）属性时，就存在匹配实例的唯一稳定分数匹配。为此，我们提供了一种多项式时间算法，该算法使嫉妒的图形巧妙地使用偏好时，以查找非整合稳定的匹配，并且给定的实例不是CMFP匹配的实例。对于此类的CMFP匹配实例，我们证明，产生独特稳定分数匹配的每种机制都是（a）兼容的激励和进一步的（b）对联盟操作的抗药性。
Stable matchings have been studied extensively in social choice literature. The focus has been mostly on integral matchings, in which the nodes on the two sides are wholly matched. A fractional matching, which is a convex combination of integral matchings, is a natural extension of integral matchings. The topic of stability of fractional matchings has started receiving attention only very recently. Further, incentive compatibility in the context of fractional matchings has received very little attention. With this as the backdrop, our paper studies the important topic of incentive compatibility of mechanisms to find stable fractional matchings. We work with preferences expressed in the form of cardinal utilities. Our first result is an impossibility result that there are matching instances for which no mechanism that produces a stable fractional matching can be incentive compatible or even approximately incentive compatible. This provides the motivation to seek special classes of matching instances for which there exist incentive compatible mechanisms that produce stable fractional matchings. Our study leads to a class of matching instances that admit unique stable fractional matchings. We first show that a unique stable fractional matching for a matching instance exists if and only if the given matching instance satisfies the conditional mutual first preference (CMFP) property. To this end, we provide a polynomial-time algorithm that makes ingenious use of envy-graphs to find a non-integral stable matching whenever the preferences are strict and the given instance is not a CMFP matching instance. For this class of CMFP matching instances, we prove that every mechanism that produces the unique stable fractional matching is (a) incentive compatible and further (b) resistant to coalitional manipulations.
