# Stable Fractional Matchings

arXiv: https://arxiv.org/abs/1902.06698 · HTML: https://mlsanity.com/paper/1902.06698/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Feb 2019.

## Built on by (most cited first, 2 of 2)

- [Stable Matching with Ties: Approximation Ratios and Learning](https://mlsanity.com/paper/2411.03270/) (2024)
- [Probably Correct Optimal Stable Matching under Two-Sided Uncertainty](https://mlsanity.com/paper/2607.04824/) (2026)

## Abstract (arXiv)

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.