Algorithms Seminar

The complexity of Stable Matchings under Substitutable Preferences

Speaker:Yuan Deng
Date: Thursday, April 20, 2017
Time: 12:00pm - 1:00pm
Location: D344 LSRC, Duke


In various matching market settings, such as hospital-doctor matching markets (Hatfield and Milgrom 2005), the existence of stable outcomes depends on substitutability of preferences. But can these stable matchings be computed efficiently, as in the one-to-one matching case? The algorithm of (Hatfield and Milgrom 2005) requires efficient implementation of a choice function over substitutable preferences. We show that even given efficient access to a value oracle or preference relation satisfying substitutability, exponentially many queries may be required in the worst case to implement a choice function. Indeed, this extends to examples where a stable matching requires exponential time to compute. We characterize the computational complexity of stable matchings by showing that efficient computation of a choice function is equivalent to efficient verification—determining whether or not, for a given set, the most preferred subset is the entire set itself. Clearly, verification is necessary for computation, but we show that it is also sufficient: specifically, given a verifier, we design a polynomial-time algorithm for computing a choice function, implying an efficient algorithm for stable matching. We then show that a verifier can be implemented efficiently for various classes of functions, such as submodular unctions, implying efficient stable matching algorithms for a broad range of settings. We also investigate the effect of ties in the preference order, which causes complications both in defining substitutes and in computation. This is a joint work with Debmalya Panigrahi and Bo Waggoner.


Yuan Deng is a second year Ph.D. student at Computer Science Department of Duke University, advised by Professor Vincent Conitzer.

Hosted by:
Vincent Conitzer