UC San Diego
Exploiting Structure in the Stable Matching Problem
- Author(s): Moeller, Daniel Paul
- Advisor(s): Paturi, Ramamohan
- et al.
Stable matching is a widely studied problem in social choice theory. For the basic
centralized case, an optimal quadratic time algorithm is known. However, we present
several notions of structure and use them to provide tighter convergence bounds and
faster stable matching algorithms for structured instances.
First, we consider the decentralized case, where several natural randomized
algorithmic models for this setting have been proposed that have worst case exponential
time in expectation. We describe a novel structure associated with a stable matching on
a matching market. Using this structure, we are able to provide a finer analysis of the complexity of a subclass of decentralized matching markets.
We then study the centralized stable matching problem when the preference
lists are not given explicitly but are represented in a succinct way. We ask whether
the problem becomes computationally easier and investigate other implications of this
structure. We give subquadratic algorithms for finding a stable matching in special cases
of natural succinct representations of the problem, the d-attribute, d-list, geometric, and
single-peaked models. We also present algorithms for verifying a stable matching in the
same models. We further show that for d = w(logn) both finding and verifying a stable
matching in the d-attribute and d-dimensional geometric models requires quadratic time
assuming the Strong Exponential Time Hypothesis. These models are therefore as hard
as the general case for large enough values of d.