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(n^2\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(n^3 \log n)$) in the size of the market even for arbitrary
(e.g., linear in the market size) quotas.
