Aarhus University Seal / Aarhus Universitets segl

Stable Fractional Matchings

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • Ioannis Caragiannis
  • Aris Filos-Ratsikas, University of Liverpool, United Kingdom
  • Panagiotis Kanellopoulos, University of Essex, United Kingdom
  • Rohit Vaish, Tata Institute for Fundamental Research, India
We study a generalization of the classical stable matching problem that allows for \emph{cardinal} preferences (as opposed to ordinal) and \emph{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 \emph{optimal} (i.e., welfare-maximizing) stable fractional matching. We consider both \emph{exact} and \emph{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
JournalArtificial Intelligence
Volume295
ISSN0004-3702
DOIs
Publication statusPublished - 2021

Bibliographical note

A preliminary version of this article has appeared in the proceedings of the 2019 ACM Conference on Economics and Computation (pp. 21-39).

    Research areas

  • Stable matchings, Cardinal preferences, Welfare maximization

See relations at Aarhus University Citationformats

ID: 202793717