Stable Matchings with Restricted Preferences: Structure & Complexity
Christine Cheng (University of Wisconsin, Milwaukee)
Will Rosenbaum (Amherst College)
Overview
 Background
 Main Results
 Methods
 Open Problems
Stable Marriage Problem
Agents: traditionally, men and women
Stable Marriage Problem
Preferences
Stable Marriage Problem
A matching…
Stable Marriage Problem
… with a blocking pair
Stable Marriage Problem
A stable matching
GaleShapley Algorithm
Gale & Shapley 1962:
 Efficient algorithm that finds a stable matching
 stable matchings always exist!
Limitations of GaleShapley
 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!
Questions
 How many stable matchings does an instance have?
 Can we find fair stable matchings?
 median
 balanced
 sexequal
 …
 Can we sample a uniformly random stable matching?
To address these questions, must understand structure of stable matchings!
Rotations
A stable matching
Rotations
a
’s next best choice
Rotations
c
’s next best choice
Rotations
b
’s next best choice
Rotations
Rotation exposed!
Rotations
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 onetoone with downsets in rotation poset
Theorem (Irving & Leather, 1986):
 Rotation posets can be efficiently computed
 Every (finite) poset is a rotation poset
Structure and Complexity
The following problems are (NP)hard:
 Counting stable matchings
 Finding median, balanced, and sexequal stable matchings
Proof technique: reduction from equivalent (hard) problems on rotation poset

Structure of rotation poset determines complexity of associated task
Question
Do hard SM instances arise in practice?
Restricted Preferences
We consider restricted preference models:
 $k$bounded
 $k$attribute
 $(k_1, k_2)$list
 $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) NPhard problems?
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 #BIScomplete
 finding median stable matchings is #Phard
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
 count and sample stable matchings
 find median, balanced, and sexequal stable matchings
These problems are NPhard in general!
Takeaway Messages
 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
 For all constant $k$, $k$range preference have highly restricted rotation posets
 computational problems may be significantly easier than the general case
Constructions
Goal. Given a poset $\mathcal{P}$, construct an SM instance with
 rotation poset isomorphic to $\mathcal{P}$, and
 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
 Structure of rotation posets for $(k_1, k_2)$list preferences ($k_1, k_2 < \infty$)?
 Generalizations to preferences with ties/indifference?
 Structure of stable matchings on restricted graph families (e.g., planar, bounded genus, …)?