---
title: "Fractional Matchings under Preferences: Stability and Optimality"
authors:
  - "Jiehua Chen"
  - "Sanjukta Roy"
  - "Manuel Sorge"
doi: "10.24963/ijcai.2021/13"
url: "https://ijcai.org/proceedings/2021/13"
pdf: "https://ijcai.org/proceedings/2021/0013.pdf"
venue: "Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence"
year: 2021
pages: "89-95"
track: "Main Track"
keywords:
  - "Agent-based and Multi-agent Systems: Economic Paradigms, Auctions and Market-Based Systems"
  - "Agent-based and Multi-agent Systems: Algorithmic Game Theory"
  - "Agent-based and Multi-agent Systems: Computational Social Choice"
---

# Fractional Matchings under Preferences: Stability and Optimality

Jiehua Chen, Sanjukta Roy, Manuel Sorge

*Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence*, pages 89-95. DOI: [10.24963/ijcai.2021/13](https://doi.org/10.24963/ijcai.2021/13)

## Abstract

We study generalizations of stable matching in which agents may be matched fractionally; this models time-sharing assignments. We focus on the so-called ordinal stability and cardinal stability, and investigate the computational complexity of finding an ordinally stable or cardinally stable fractional matching which either maximizes the social welfare (i.e., the overall utilities of the agents) or the number of fully matched agents (i.e., agents whose matching values sum up to one). We complete the complexity classification of both optimization problems for both ordinal stability and cardinal stability, distinguishing between the marriage (bipartite) and roommates (non-bipartite) cases and the presence or absence of ties in the preferences. In particular, we prove a surprising result that finding a cardinally stable fractional matching with maximum social welfare is NP-hard even for the marriage case without ties. This answers an open question and exemplifies a rare variant of stable marriage that remains hard for preferences without ties. We also complete the picture of the relations of the stability notions and derive structural properties.