Research Repository

Stable fractional matchings

Caragiannis, Ioannis and Filos-Ratsikas, Aris and Kanellopoulos, Panagiotis and Vaish, Rohit (2021) 'Stable fractional matchings.' Artificial Intelligence, 295 (C). p. 103416. ISSN 0004-3702

Stable-Fractional-Matchings-AIJ.pdf - Accepted Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (628kB) | Preview


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
Divisions: Faculty of Science and Health
Faculty of Science and Health > Computer Science and Electronic Engineering, School of
SWORD Depositor: Elements
Depositing User: Elements
Date Deposited: 23 Nov 2020 14:58
Last Modified: 24 Nov 2022 16:07

Actions (login required)

View Item View Item