[Zurück]

J. Chen, A. Chmurovic, F. Jogl, M. Sorge:
"On (Coalitional) Exchange-Stable Matching";
Vortrag: International Symposium on Algorithmic Game Theory, Aarhus, Denmark; 21.09.2021 - 24.09.2021; in: "International Symposium on Algorithmic Game Theory", LNCS / Springer, 12885 (2021), ISBN: 978-3-030-85946-6; S. 205 - 220.

We study (coalitional) exchange stability, which Alcalde
[Economic Design, 1995] introduced as an alternative solution concept for
matching markets involving property rights, such as assigning persons to
two-bed rooms. Here, a matching of a given Stable Marriage or Stable
Roommates instance is called coalitional exchange-stable if it does
not admit any exchange-blocking coalition, that is, a subset S of agents
in which everyone prefers the partner of some other agent in S. The
matching is exchange-stable if it does not admit any exchange-blocking
pair, that is, an exchange-blocking coalition of size two.
We investigate the computational and parameterized complexity of
the Coalitional Exchange-Stable Marriage (resp. Coalitional
Exchange Roommates) problem, which is to decide whether a Stable
Marriage (resp. Stable Roommates) instance admits a coalitional
exchange-stable matching. Our findings resolve an open question
and confirm the conjecture of Cechlárová and Manlove [Discrete Applied
Mathematics, 2005] that Coalitional Exchange-Stable Marriage
is NP-hard even for complete preferences without ties. We also study
bounded-length preference lists and a local-search variant of deciding
whether a given matching can reach an exchange-stable one after at
most k swaps, where a swap is defined as exchanging the partners of the
two agents in an exchange-blocking pair.

http://dx.doi.org/10.1007/978-3-030-85947-3_14

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