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

arXiv: https://arxiv.org/abs/2002.07363 · HTML: https://mlsanity.com/paper/2002.07363/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Feb 2020.

## Built on by (most cited first, 3 of 3)

- [Learning Equilibria in Matching Markets from Bandit Feedback](https://mlsanity.com/paper/2108.08843/) (2021)
- [An α-regret analysis of Adversarial Bilateral Trade](https://mlsanity.com/paper/2210.06846/) (2022)
- [Bandit based centralized matching in two-sided markets for peer to peer lending](https://mlsanity.com/paper/2105.02589/) (2021)

## Abstract (arXiv)

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(n2log 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.