Computer Science and Engineering Ph.D. candidate Daniel Moeller is scheduled to stage the final defense of his dissertation this week on the topic of "Exploiting Structure in the Stable Matching Problem." His advisor, CSE Prof. Mohan Paturi, will chair the panel that includes fellow CSE professors Sanjoy Dasgupta and Russell Impagliazzo, as well as ECE Prof. Massimo Franceschetti and Joel Sobel, a professor in the Department of Economics.
Date: Friday, October 28
Time: 11am
Location: Room 3109, CSE Building
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(log n) 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.