Advancing Stability in Matching Markets: Multi-Modal Preferences and Beyond

In this talk, we explore two recent advances that challenge traditional assumptions and broaden our understanding of what stability can entail.

First, we consider the impact of multi-modal preferences--a scenario in which each agent may possess multiple preference lists, potentially based on different criteria. We introduce three natural stability concepts for this setting, investigate their mutual relations, and focus on the computational complexity associated with determining stable matchings under these concepts.

Next, we shift to novel quantitative stability notions, robustness and near-stability, which respectively strengthen and relax the classical stability definition. These new metrics not only facilitate a fine-grained stability analysis but also enable the exploration of trade-offs between stability and social optimality. We probe the computational challenges posed by these nuanced stability perspectives by showing that determining robustness is easy while finding a socially optimal and nearly stable matching is hard.