The Complexity of Interactively Learning a Stable Matching by Trial and Error

In a stable matching setting, we consider a query model that allows for an interactive learning algorithm to make precisely one type of query: proposing a matching, the response to which is either that the proposed matching is stable, or a blocking pair (chosen adversarially) indicating that this matching is unstable. For one-to-one matching markets, our main result is an essentially tight upper bound of O(n2 log n) on the deterministic query complexity of interactively learning a stable matching in this coarse query model, along with an efficient randomized algorithm that achieves this query complexity with high probability. For many-to-many matching markets in which participants have responsive preferences, we first give an interactive learning algorithm whose query complexity and running time are polynomial in the size of the market if the maximum quota of each agent is bounded; our main result for many-to-many markets is that the deterministic query complexity can be made polynomial (more specifically, O(n3 log n)) in the size of the market even for arbitrary (e.g., linear in the market size) quotas.

The high-level idea for our results is as follows. In each iteration, the algorithm chooses a "speculative" preference order for each agent, consistent with all observed blocking pairs so far. It then computes a stable matching with respect to these speculative preferences. When a blocking pair is revealed, this pins down at least one "mistake" (a transposition) in one agent's speculative order. The crux of the analysis is to show that a judicious choice of speculative orders ensures that any such mistake rules out a constant fraction of all remaining candidate orders for this agent. Such a choice can be made for the one-to-one setting by Yu's Proportional Transitivity Theorem. For the many-to-many setting, we obtain a slightly weaker bound via a direct proof.

In order to achieve computational efficiency, the algorithm must be able to infer the following for each triple of agents x, y, z: what fraction of preference orders for x consistent with all past observations rank y ahead of z? We show that this quantity can be computed sufficiently accurately by sampling linear extensions of a partial order (nearly) uniformly at random. Whether computational efficiency can be achieved for the more complex many-to-many setting is an appealing open question.