# Jiehua Chen

Summary

We generalize the famous Stable Marriage problem where each agent has multiple preference lists that rank the counterparts in a possibly different way. We introduce and study three natural concepts of stability, investigate their mutual relations and focus on computational complexity aspects with respect to computing stable matchings in these new scenarios. Assume each agent has $\ell$ (possibly different) preferences lists.

All three concepts are defined for a certain threshold $\alpha$ with $1\le \alpha \le \ell$, which quantifies the strength of stability.

α-layer globally stability

extends the original stability concept in a straightforward way. It assumes that the matched pairs agree on a set $S$ of $\alpha$ layers where no unmatched pair is blocking the matching in any layer from $S$.

α-layer pair stability

changes the blocking ability of the unmatched pairs. It forbids an unmatched pair to block more than $\ell-\alpha$ layers. In other words, each pair of matched agents needs to be stable in some $\alpha$ layers, but the choice of these layers can be different for different pairs.

α-layer individual stability

focuses on the willingness of an agent to stay with its partner. It requires that for each unmatched pair, at least one of the agents prefers to stay with its partner in at least $\alpha$ layers.

====================================

The paper can be found in arxiv.