The Complexity of Interactively Learning a Stable Matching by Trial and Error
This addresses the computational complexity of learning stable matchings interactively, which is incremental as it builds on existing query models and matching theory.
The paper tackles the problem of interactively learning a stable matching in matching markets using a coarse query model, establishing an essentially tight upper bound of O(n^2 log n) for one-to-one markets and polynomial bounds for many-to-many markets, with efficient randomized algorithms achieving these complexities.
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.