Research Repository

Stable fractional matchings

Caragiannis, I and Filos-Ratsikas, A and Kanellopoulos, P and Vaish, R (2021) 'Stable fractional matchings.' Artificial Intelligence, 295. ISSN 0004-3702

[img] Text
Stable-Fractional-Matchings-AIJ.pdf - Accepted Version
Restricted to Repository staff only until 6 November 2021.
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (628kB) | Request a copy


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
Divisions: Faculty of Science and Health > Computer Science and Electronic Engineering, School of
Depositing User: Elements
Date Deposited: 23 Nov 2020 14:58
Last Modified: 04 Jun 2021 05:15

Actions (login required)

View Item View Item