Fractional Matchings under Preferences: Stability and Optimality
Fractional Matchings under Preferences: Stability and Optimality
Jiehua Chen, Sanjukta Roy, Manuel Sorge
Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence
Main Track. Pages 89-95.
https://doi.org/10.24963/ijcai.2021/13
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.
Keywords:
Agent-based and Multi-agent Systems: Algorithmic Game Theory
Agent-based and Multi-agent Systems: Computational Social Choice
Agent-based and Multi-agent Systems: Economic Paradigms, Auctions and Market-Based Systems