Stable fractional matchings

Ioannis Caragiannis, Aris Filos-Ratsikas, Panagiotis Kanellopoulos, Rohit Vaish

Research output: Contribution to journalArticlepeer-review

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). 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.
Original languageEnglish
Article number103416
Number of pages26
JournalArtificial Intelligence
Volume295
Early online date6 Nov 2020
DOIs
Publication statusPublished - 1 Jun 2021

Keywords

  • Stable matchings
  • Cardinal preferences
  • Welfare maximization

Fingerprint

Dive into the research topics of 'Stable fractional matchings'. Together they form a unique fingerprint.

Cite this