We thoroughly study a generalized version of the famous \SM problem, now based on multi-modal preference lists. The central twist herein is to allow each agent to rank its potentially matching counterparts based on more than one ``evaluation mode’’ (e.g., more than one criterion); thus, each agent is equipped with multiple preference lists, each ranking 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. Mostly encountering computational hardness (NP-hardness), we can also spot few islands of tractability and make a surprising connection to the \textsc{Graph Isomorphism} problem. 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 is accepted and going to be presented at EC 2018 and an arxiv version can be found here.