[Back]

J. Chen, P. Skowron, M. Sorge:
"Matchings under Preferences: Strength of Stability and Tradeoffs";
ACM Transactions on Economics and Computation, 9 (2021), 4; 1 - 55.

We propose two solution concepts for matchings under preferences: robustness and near stability. The former
strengthens while the latter relaxes the classical definition of stability by Gale and Shapley (1962). Informally
speaking, robustness requires that a matching must be stable in the classical sense, even if the agents slightly
change their preferences. Near stability, however, imposes that a matching must become stable (again, in the
classical sense) provided the agents are willing to adjust their preferences a bit. Both of our concepts are
quantitative; together they provide means for a fine-grained analysis of the stability of matchings. Moreover,
our concepts allow the exploration of tradeoffs between stability and other criteria of social optimality, such
as the egalitarian cost and the number of unmatched agents.We investigate the computational complexity of
finding matchings that implement certain predefined tradeoffs.We provide a polynomial-time algorithm that,
given agent preferences, returns a socially optimal robust matching (if it exists), and we prove that finding a
socially optimal and nearly stable matching is computationally hard.

http://dx.doi.org/10.1145/3485000

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