UC San Diego

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.