Manipulation of stable matchings using minimal blacklists
Manipulation of stable matchings using minimal blacklists
复制标题
使用最小黑名单操纵稳定匹配
DOI：
10.1145/2600057.2602840
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Yannai A. Gonczarowski
中科院分区：
文献类型：
--
作者：
Yannai A. Gonczarowski
Gale和Sotomayor [1985]已经表明，在Gale-Shapley匹配算法[1962]中，（这里指的是女性）可以通过截断她们的偏好列表，策略性地迫使W-最优稳定匹配成为M-最优匹配，每个女性可能会将除了一个男性之外的所有男性列入黑名单。关于通过除了这种偏好列表截断之外的手段（即，还通过置换偏好列表）来实现这一壮举，还不知道结果。我们回答Gusfield和欧文的开放性问题，提供严格的上界的黑名单的数量和它们的组合大小，所需的妇女，以迫使一个给定的匹配的M-最优的稳定匹配，或者，更一般地说，作为唯一的稳定匹配。我们的研究结果表明，联盟的所有妇女可以战略性地迫使任何匹配的唯一稳定的匹配，使用偏好列表中，最多有一半的妇女有非空的黑名单，并在其中的平均黑名单的大小小于1。从某种意义上说，这使妇女能够以一种远比以前意识到的更不显眼的方式操纵市场。当女性比男性少时，我们表明，在没有男性黑名单的情况下，女性可以强制任何匹配作为唯一的稳定匹配，而不会将任何人列入黑名单，而当女性比男性多时，每个不匹配的女性可能不得不将所有男性列入黑名单。总之，这些结果揭示了这样一个问题：在各种条件下，对一方的先验偏好对稳定匹配集施加了多大的限制。本文的所有结果是建设性的，提供了有效的算法计算所需的策略。
Gale and Sotomayor [1985] have shown that in the Gale-Shapley matching algorithm [1962], the proposed-to side W (referred to as women there) can strategically force the W-optimal stable matching as the M-optimal one by truncating their preference lists, each woman possibly blacklisting all but one man. As Gusfield and Irving have already noted in 1989, no results are known regarding achieving this feat by means other than such preference-list truncation, i.e. by also permuting preference lists. We answer Gusfield and Irving's open question by providing tight upper bounds on the amount of blacklists and their combined size, that are required by the women to force a given matching as the M-optimal stable matching, or, more generally, as the unique stable matching. Our results show that the coalition of all women can strategically force any matching as the unique stable matching, using preference lists in which at most half of the women have nonempty blacklists, and in which the average blacklist size is less than 1. This allows the women to manipulate the market in a manner that is far more inconspicuous, in a sense, than previously realized. When there are less women than men, we show that in the absence of blacklists for men, the women can force any matching as the unique stable matching without blacklisting anyone, while when there are more women than men, each to-be-unmatched woman may have to blacklist as many as all men. Together, these results shed light on the question of how much, if at all, do given preferences for one side a priori impose limitations on the set of stable matchings under various conditions. All of the results in this paper are constructive, providing efficient algorithms for calculating the desired strategies.
“简单的不平等经济学：市场设计方法”
DOI：
--
发表时间：
2016
期刊：
影响因子：
--
作者：
須田守;Yasuda Yosuke
通讯作者：
Yasuda Yosuke