Skip to yearly menu bar Skip to main content


Poster

Balancing Bias in Two-sided Markets for Fair Stable Matchings

Siyuan Wu · Leong Hou U · Panagiotis Karras

Hall 3 + Hall 2B #515
[ ]
Sat 26 Apr midnight PDT — 2:30 a.m. PDT

Abstract:

The Balanced Stable Marriage (BSM) problem aims to find a stable matching in a two-sided market that minimizes the maximum dissatisfaction among two sides. The classical Deferred Acceptance algorithm merely produces an unfair stable marriage, providing optimal partners for one side while partially assigning pessimal partners to the other. Solving BSM is NP-hard, thwarting attempts to resolve the problem exactly. As the instance size increases in practice, recent studies have explored heuristics for finding a fair stable marriage but have not found an exact optimal solution for BSM efficiently. Nevertheless, in this paper we propose an efficient algorithm, Isorropia, that returns the exact optimal solution to practical BSM problem instances. Isorropia constructs two sets of candidate rotations from which it builds three sets of promising antichains, and performs local search on those three sets of promising antichains. Our extensive experimental study shows that Isorropia surpasses the time-efficiency of baselines that return the exact solution by up to three orders of magnitude.

Live content is unavailable. Log in and register to view live content