论文标题
所有$ \＆$ ac
Two for One $\&$ One for All: Two-Sided Manipulation in Matching Markets
论文作者
论文摘要
传统上，在“单面”操纵环境中研究了双面匹配市场中的战略行为，其中虚假报告的代理商也是预期的受益人。我们的工作调查了对递延接受算法的“双面”操纵，其中错误报告的代理和操纵器（或受益人）处于不同的方面。 Specifically, we generalize the recently proposed accomplice manipulation model (where a man misreports on behalf of a woman) along two complementary dimensions: (a) the two for one model, with a pair of misreporting agents (man and woman) and a single beneficiary (the misreporting woman), and (b) the one for all model, with one misreporting agent (man) and a coalition of beneficiaries (all women). 我们的主要贡献是开发多项式时间算法，以在两种情况下找到最佳操作。尽管事实是，所有策略的最佳结果都不是不明显的，但我们获得了这些结果，而尚不清楚一个策略的最佳两个策略是否满足不明显的属性。我们还研究了保留结果匹配的稳定性的条件。在实验上，我们表明双面操纵更频繁地可用，并且比单方面的操作更优质。
Strategic behavior in two-sided matching markets has been traditionally studied in a "one-sided" manipulation setting where the agent who misreports is also the intended beneficiary. Our work investigates "two-sided" manipulation of the deferred acceptance algorithm where the misreporting agent and the manipulator (or beneficiary) are on different sides. Specifically, we generalize the recently proposed accomplice manipulation model (where a man misreports on behalf of a woman) along two complementary dimensions: (a) the two for one model, with a pair of misreporting agents (man and woman) and a single beneficiary (the misreporting woman), and (b) the one for all model, with one misreporting agent (man) and a coalition of beneficiaries (all women). Our main contribution is to develop polynomial-time algorithms for finding an optimal manipulation in both settings. We obtain these results despite the fact that an optimal one for all strategy fails to be inconspicuous, while it is unclear whether an optimal two for one strategy satisfies the inconspicuousness property. We also study the conditions under which stability of the resulting matching is preserved. Experimentally, we show that two-sided manipulations are more frequently available and offer better quality matches than their one-sided counterparts.
