Fair Procedures for Fair Stable Marriage Outcomes

Authors

  • Nikolaos Tziavelis Northeastern University
  • Ioannis Giannakopoulos National Technical University of Athens
  • Rune Quist Johansen Aalborg University
  • Katerina Doka National Technical University of Athens
  • Nectarios Koziris National Technical University of Athens
  • Panagiotis Karras Aarhus University

DOI:

https://doi.org/10.1609/aaai.v34i05.6218

Abstract

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.

Downloads

Published

2020-04-03

How to Cite

Tziavelis, N., Giannakopoulos, I., Quist Johansen, R., Doka, K., Koziris, N., & Karras, P. (2020). Fair Procedures for Fair Stable Marriage Outcomes. Proceedings of the AAAI Conference on Artificial Intelligence, 34(05), 7269-7276. https://doi.org/10.1609/aaai.v34i05.6218

Issue

Section

AAAI Technical Track: Multiagent Systems