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.
Code (0)
등록된 구현이 없습니다.
Tasks
BlockingSimilar Papers 제목 키워드 기반
Asymptotically stable matchings and evolutionary dynamics of preference revelation games in marriage problems
The literature on centralized matching markets often assumes that a true preference of each player is known to herself and fixed, but empirical evidence casts doubt on its plausibility. To circumvent the problem, we cons…
On the Complexity of Trial and Error
Motivated by certain applications from physics, biochemistry, economics, and computer science, in which the objects under investigation are not accessible because of various limitations, we propose a trial-and-error mode…
Utility-Based Communication Requirements for Stable Matching in Large Markets
Results from the communication complexity literature have demonstrated that stable matching requires communication: one cannot find or verify a stable match without having access to essentially all of the ordinal prefere…
On the Complexity of Robust Stable Marriage
Robust Stable Marriage (RSM) is a variant of the classical Stable Marriage problem, where the robustness of a given stable matching is measured by the number of modifications required for repairing it in case an unforese…
Sparse Group Lasso: Optimal Sample Complexity, Convergence Rate, and Statistical Inference
We study sparse group Lasso for high-dimensional double sparse linear regression, where the parameter of interest is simultaneously element-wise and group-wise sparse. This problem is an important instance of the simulta…
regression