论文标题
通过反复试验学习稳定匹配的复杂性
The Complexity of Interactively Learning a Stable Matching by Trial and Error
论文作者
论文摘要
在稳定的匹配设置中，我们考虑了一个查询模型，该查询模型允许一种交互式学习算法精确地进行查询：提出匹配，响应是所提出的匹配是稳定的，或者是阻止对（选择的对手），表明这种匹配是不稳定的。对于一对一的匹配市场，我们的主要结果是在确定性查询模型中互动地学习稳定匹配的确定性查询复杂性上，本质上是一个紧密的上限，并具有有效的随机算法，以及具有较高可能性的有效随机算法。对于参与者具有响应良好喜好的多对多匹配市场，我们首先提供了一种交互式学习算法，如果每个代理的最大配额有限，则在市场规模上查询复杂性和运行时间是多项式的；我们对许多市场的主要结果是，即使是任意（例如，在市场尺寸的线性），确定性的查询复杂性也可以在市场的规模上使多项式（更具体地说，更具体地说是$ o（n^3 \ log n）$）。
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.
