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 (possibly different) preferences lists.
All three concepts are defined for a certain threshold with , which quantifies the strength of stability.
extends the original stability concept in a straightforward way. It assumes that the matched pairs agree on a set of layers where no unmatched pair is blocking the matching in any layer from .
changes the blocking ability of the unmatched pairs. It forbids an unmatched pair to block more than layers. In other words, each pair of matched agents needs to be stable in some layers, but the choice of these layers can be different for different pairs.
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 layers.
====================================
The paper can be found in arxiv.