Research Repository

Stable Fractional Matchings

Caragiannis, Ioannis and Filos-Ratsikas, Aris and Kanellopoulos, Panagiotis and Vaish, Rohit (2019) Stable Fractional Matchings. In: ACM Conference on Economics and Computation, 2019-06-24 - 2019-06-28, Phoenix AZ USA.

[img]
Preview
Text
1902.06698v1.pdf - Submitted Version

Download (408kB) | Preview

Abstract

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). After observing that, in this cardinal setting, stable fractional matchings can have much higher social welfare than stable integral ones, our goal is to understand the computational complexity of finding an optimal (i.e., welfare-maximizing) or nearly-optimal stable fractional matching. We present simple approximation algorithms for this problem with weak welfare guarantees and, rather unexpectedly, we furthermore show that achieving better approximations is hard. This computational hardness persists even for approximate stability. To the best of our knowledge, these are the first computational complexity results for stable fractional matchings. En route to these results, we provide a number of structural observations.

Item Type: Conference or Workshop Item (Paper)
Additional Information: Published proceedings: Proceedings of the 2019 ACM Conference on Economics and Computation - EC '19
Divisions: Faculty of Science and Health > Computer Science and Electronic Engineering, School of
Depositing User: Elements
Date Deposited: 04 Sep 2020 13:05
Last Modified: 04 Sep 2020 13:15
URI: http://repository.essex.ac.uk/id/eprint/25505

Actions (login required)

View Item View Item