Equitable Stable Matchings in Quadratic Time
Can a stable matching that achieves high equity among the two sides of a market be reached in quadratic time? The Deferred Acceptance (DA) algorithm finds a stable matching that is biased in favor of one side; optimizing apt equity measures is strongly NP-hard. A proposed approximation algorithm offers a guarantee only with respect to the DA solutions. Recent work introduced Deferred Acceptance with Compensation Chains (DACC), a class of algorithms that can reach any stable matching in O(n^4) time, but did not propose a way to achieve good equity. In this paper, we propose an alternative that is computationally simpler and achieves high equity too. We introduce Monotonic Deferred Acceptance (MDA), a class of algorithms that progresses monotonically towards a stable matching; we couple MDA with a mechanism we call Strongly Deferred Acceptance (SDA), to build an algorithm that reaches an equitable stable matching in quadratic time; we amend this algorithm with a few low-cost local search steps to what we call Deferred Local Search (DLS), and demonstrate experimentally that it outperforms previous solutions in terms of equity measures and matches the most efficient ones in runtime.
Code (1)
Similar Papers 제목 키워드 기반
Matching markets with farsighted couples
We adopt the notion of the farsighted stable set to determine which matchings are stable when agents are farsighted in matching markets with couples. We show that a singleton matching is a farsighted stable set if and on…
Finding all stable matchings with assignment constraints
In this paper we consider stable matchings subject to assignment constraints. These are matchings that require certain assigned pairs to be included, insist that some other assigned pairs are not, and, importantly, are s…
AllPriority-Neutral Matching Lattices Are Not Distributive
Stable matchings are a cornerstone of market design, with numerous practical deployments backed by a rich, theoretically-tractable structure. However, in school-choice problems, stable matchings are not Pareto optimal fo…
On the many-to-one strongly stable fractional matching set
For a many-to-one matching market where firms have strict and $\boldsymbol{q}$-responsive preferences, we give a characterization of the set of strongly stable fractional matchings as the union of the convex hull of all …
AllModeling Stable Matching Problems with Answer Set Programming
The Stable Marriage Problem (SMP) is a well-known matching problem first introduced and solved by Gale and Shapley (1962). Several variants and extensions to this problem have since been investigated to cover a wider set…