TY - JOUR
AU - Tziavelis, Nikolaos
AU - Giannakopoulos, Ioannis
AU - Quist Johansen, Rune
AU - Doka, Katerina
AU - Koziris, Nectarios
AU - Karras, Panagiotis
PY - 2020/04/03
Y2 - 2021/04/23
TI - Fair Procedures for Fair Stable Marriage Outcomes
JF - Proceedings of the AAAI Conference on Artificial Intelligence
JA - AAAI
VL - 34
IS - 05
SE - AAAI Technical Track: Multiagent Systems
DO - 10.1609/aaai.v34i05.6218
UR - https://ojs.aaai.org/index.php/AAAI/article/view/6218
SP - 7269-7276
AB - <p>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 <em>optimal</em> match to each agent on one side, and a <em>pessimal</em> one to each on the other side; such a solution may fare well in terms of equity <em>only</em> in highly asymmetric markets. Finding a stable matching that <em>minimizes</em> the <em>sex equality cost</em>, an equity measure expressing the discrepancy of mean happiness among the two sides, is strongly NP-hard. Extant heuristics either <em>(a)</em> oblige some agents to involuntarily abandon their matches, or <em>(b)</em> bias the outcome in favor of some agents, or <em>(c)</em> need high-polynomial or unbounded time.</p><p>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: <em>(a)</em> extant heuristics fail to yield high equity; <em>(b)</em> the best solution found by the GS algorithm can be very far from optimal equity; and <em>(c)</em> our procedures stand out in both efficiency and equity, even when compared to a non-procedurally fair approximation scheme.</p>
ER -