We study generalizations of stable matching in which agents may be matched fractionally; this models time-sharing assignments. We focus on ordinal stability [Aharoni and Fleiner, J Comb Theory B’03] and cardinal stability [Caragiannis et al., AIJ’20], 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 by Caragiannis et al. 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.
====================================
The conference and long version of the paper can be found on IJCAI21 and arXiv, respectively.