Stable fractional matchings

Caragiannis, Ioannis, Filos-Ratsikas, Aris ORCID: 0000-0001-7868-8114, Kanellopoulos, Panagiotis and Vaish, Rohit
(2020) Stable fractional matchings. Artificial Intelligence.

[img] Text
ARTINT-S-20-00344.pdf - Accepted Version
Access to this file is embargoed until 1 November 2021.

Download (1MB)


We study a generalization of the classical stable matching problem that allows for cardinal preferences (as opposed to ordinal) and fractional matchings (as opposed to integral). In this cardinal setting, stable fractional matchings can have much larger social welfare than stable integral ones. Our goal is to understand the computational complexity of finding an optimal (i.e., welfare-maximizing) stable fractional matching. We consider both exact and approximate stability notions, and provide simple approximation algorithms with weak welfare guarantees. Our main result is that, somewhat surprisingly, achieving better approximations is computationally hard. To the best of our knowledge, these are the first computational complexity results for stable fractional matchings in the cardinal model. En route to these results, we provide a number of structural observations that could be of independent interest.

Item Type: Article
Uncontrolled Keywords: stable matchings, cardinal preferences, welfare maximization
Depositing User: Symplectic Admin
Date Deposited: 18 Nov 2020 11:43
Last Modified: 09 Sep 2021 12:37
DOI: 10.1016/j.artint.2020.103416
Related URLs: