Fair Procedures for Fair Stable Marriage Outcomes
Fair Procedures for Fair Stable Marriage Outcomes
复制标题
公平稳定的婚姻结果的公平程序
DOI：
10.1609/aaai.v34i05.6218
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Panagiotis Karras
中科院分区：
文献类型：
--
作者：
Nikolaos Tziavelis;Ioannis Giannakopoulos;R. Johansen;Katerina Doka;N. Koziris;Panagiotis Karras
在一个双边市场中，每个代理人都根据偏好对另一方的人进行排名，稳定婚姻问题要求找到一个完美的匹配，使得没有一对代理人喜欢对方。最近的研究表明，稳定的解决方案的数量可以在实践中很大。然而，这个问题的经典解决方案，盖尔-沙普利（GS）算法，分配一个最佳匹配的每一个代理在一边，和一个悲观的每一个在另一边;这样的解决方案可能只在高度不对称的市场中的公平方面表现良好。找到一个稳定的匹配，最大限度地减少性别平等的成本，公平的措施，表示双方之间的平均幸福的差异，是强NP-难。现有的算法要么（a）迫使一些代理人不自觉地放弃他们的比赛，要么（B）偏向有利于一些代理人的结果，要么（c）需要高多项式或无限的时间。我们提供了第一个程序公平的算法，输出公平稳定的婚姻，并保证在最立方时间终止;这一突破的关键是监测单调的状态函数和采用接受建议的选择性标准。我们的实验与不同的模拟市场表明：（a）现存的算法无法产生高公平;（B）GS算法找到的最佳解决方案可以是非常远离最优公平;（c）我们的程序脱颖而出，在效率和公平，即使是在一个非程序公平的近似计划。
Given a two-sided market where each agent ranks those on the other side by preference, the stable marriage problem calls for finding a perfect matching such that no pair of agents prefer each other to their matches. Recent studies show that the number of stable solutions can be large in practice. Yet the classical solution to the problem, the Gale-Shapley (GS) algorithm, assigns an optimal match to each agent on one side, and a pessimal one to each on the other side; such a solution may fare well in terms of equity only in highly asymmetric markets. Finding a stable matching that minimizes the sex equality cost, an equity measure expressing the discrepancy of mean happiness among the two sides, is strongly NP-hard. Extant heuristics either (a) oblige some agents to involuntarily abandon their matches, or (b) bias the outcome in favor of some agents, or (c) need high-polynomial or unbounded time.We provide the first procedurally fair algorithms that output equitable stable marriages and are guaranteed to terminate in at most cubic time; the key to this breakthrough is the monitoring of a monotonic state function and the use of a selective criterion for accepting proposals. Our experiments with diverse simulated markets show that: (a) extant heuristics fail to yield high equity; (b) the best solution found by the GS algorithm can be very far from optimal equity; and (c) our procedures stand out in both efficiency and equity, even when compared to a non-procedurally fair approximation scheme.