[Zurück]

J. Chen, S. Roy, M. Sorge:
"Fractional Matchings under Preferences: Stability and Optimality";
Vortrag: IJCAI 2021 - 30th International Joint Conference on Artificial Intelligence, Montreal, Canada; 19.08.2021 - 27.08.2021; in: "Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI-21)", (2021), ISBN: 978-0-9992411-9-6; S. 89 - 95.

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.

http://dx.doi.org/10.24963/ijcai.2021/13

https://publik.tuwien.ac.at/files/publik_300295.pdf