Stable Matchings with Restricted Preferences: Structure & Complexity

Christine Cheng (University of Wisconsin, Milwaukee)

Will Rosenbaum (Amherst College)


  1. Background
  2. Main Results
  3. Methods
  4. Open Problems


Stable Marriage Problem

Agents: traditionally, men and women


Stable Marriage Problem



Stable Marriage Problem

A matching…


Stable Marriage Problem

… with a blocking pair


Stable Marriage Problem

A stable matching


Gale-Shapley Algorithm

Gale & Shapley 1962:

  • Efficient algorithm that finds a stable matching
    • stable matchings always exist!

Limitations of Gale-Shapley

  • Finds at most two stable matchings
    • one optimal for men, pessimal for women
    • one optimal for women, pessimal for men
  • Can be exponentially many stable matchings!


  • How many stable matchings does an instance have?
  • Can we find fair stable matchings?
    • median
    • balanced
    • sex-equal
  • Can we sample a uniformly random stable matching?

To address these questions, must understand structure of stable matchings!


A stable matching



a’s next best choice



c’s next best choice



b’s next best choice



Rotation exposed!



Rotation eliminated—new SM found!


Structure of Stable Matchings

Irving & Leather, 1986:

  • All stable matchings obtained by eliminating sequence of rotations
  • Natural precedence relation on rotations: rotation poset
  • Stable matchings one-to-one with downsets in rotation poset

Theorem (Irving & Leather, 1986):

  1. Rotation posets can be efficiently computed
  2. Every (finite) poset is a rotation poset

Structure and Complexity

The following problems are (NP)-hard:

  • Counting stable matchings
  • Finding median, balanced, and sex-equal stable matchings

Proof technique: reduction from equivalent (hard) problems on rotation poset

  • Structure of rotation poset determines complexity of associated task


Do hard SM instances arise in practice?

Restricted Preferences

We consider restricted preference models:

  1. $k$-bounded
  2. $k$-attribute
  3. $(k_1, k_2)$-list
  4. $k$-range

2–4 introduced by Bhatnagar et al. (SODA 2008)

$k$-Bounded Preferences

An SM instance is $k$-bounded if all preference lists have length at most $k$

Motivation. Rarely the case in practice that one would rank all possible partners!

$k$-Attribute Preferences

Each agent $a$ has a profile $(v_a, \phi_a)$

  • $v_a \in \mathbf{R}^k$
  • $\phi_a : \mathbf{R}^k \to \mathbf{R}$, linear
  • $a$’s ranks potential partners $b$ according to $\phi_a(v_b)$

Motivation. Ranking by questionnaires (e.g., dating websites):

  • $v_a$ encodes own responses
  • $\phi_a$ encodes desired responses of ideal partner
  • $k$ is number/dimensions of questions

$(k_1, k_2)$-list Preferences

  • Men/women partitioned into $k_1$ / $k_2$ groups, respectively
  • All agents in each group have identical preference lists

Motivation. Cases where preferences inferred from group identity

  • E.g., all prospective CS majors adopt same rankings of universities

$k$-Range Preferences

  • For each woman $w$, men’s rankings of $w$ differ by at most $k - 1$
  • For each man $m$, women’s rankings of $m$ differ by at most $k - 1$

Motivation. Preference derived from “master preference lists,” but with some noise.

Main Question

What rotation posets are realized by restricted preference models?

  • Can we exploit restricted preference structures to give efficient algorithms for (restricted instances of) NP-hard problems?

Main Results

Hardness Results

Theorem 1. Let $\mathcal{P}$ be an arbitrary finite poset. Then there exist SM instances in the following models realizing $\mathcal{P}$:

  • $k$-bounded for any $k \geq 3$
  • $k$-attribute for any $k \geq 6$
  • $(k, \infty)$-list for any $k \geq 2$

Such instances can be computed from $\mathcal{P}$ in polynomial time.

Hardness Consequences

  • Structural problems are as hard in the following models as the general case:
    • $k$-bounded for any $k \geq 3$
    • $k$-attribute for any $k \geq 6$
    • $(k, \infty)$-list for any $k \geq 2$
  • For example:
    • counting stable matchings is #BIS-complete
    • finding median stable matchings is #P-hard

Algorithmic Results

Theorem 2. For constant $k$, the rotation poset of every $k$-range SM instance has bounded pathwidth.

  • Structure of $k$-range rotation posets is highly restricted.

Theorem 3. Given a poset $\mathcal{P}$ with pathwidth $k$, can efficiently construct an $O(k)$-range SM instance realizing $\mathcal{P}$.

  • Pathwidth characterizes $k$-range rotation posets

Algorithmic Consequences

For any constant $k$, and any $k$-range instance, we can efficiently

  1. count and sample stable matchings
  2. find median, balanced, and sex-equal stable matchings

These problems are NP-hard in general!

Takeaway Messages

  1. For small constant $k$, $k$-bounded, $k$-attribute, and $(k, \infty)$-list preferences realize all finite posets
    • structural problems are as hard as for general instances
  2. For all constant $k$, $k$-range preference have highly restricted rotation posets
    • computational problems may be significantly easier than the general case



Goal. Given a poset $\mathcal{P}$, construct an SM instance with

  1. rotation poset isomorphic to $\mathcal{P}$, and
  2. preferences from a (chosen) restricted family

Start with Rotations


SM 1: Man Optimal


SM 2: $\rho$ Eliminated


SM 3: $\sigma$ Eliminated


SM 4: $\rho, \sigma$ Eliminated


Adding Edge


$\sigma$ Not Exposed…


$\sigma$ Exposed After $\rho$ Eliminated


Added Precedence


Larger Construction


Paper Constructions

  • Formalize “glueing” together rotations to force precedence
  • Generic construction
    • each poset $\implies$ many instances realizing poset
    • construct instances in preference models

Open Problems

  1. Structure of rotation posets for $(k_1, k_2)$-list preferences ($k_1, k_2 < \infty$)?
  2. Generalizations to preferences with ties/indifference?
  3. Structure of stable matchings on restricted graph families (e.g., planar, bounded genus, …)?

Thank You