Econ Papers Daily / 期刊论文
松弛随机偏好下的稳定匹配
Stable matchings under relaxed random preferences
摘要
In a stable matching problem, n agents on one side have individual preferences for n agents on another side as a potential match. A matching is called stable if no two unmatched agents prefer each other to their matches. Knuth demonstrated existence of preferences with exponentially many stable matchings, posing a question on expected number of stable matchings for a uniformly random problem instance. Using Knuth’s integral formula, the first author showed that this expectation is quite moderate, asymptotic to $$e^{-1}n\log n$$ , n being the number of agents on each side. In this paper, relaxing stability notion, we declare matching stable if no unmatched pair of agents strongly prefer each other to their partners, with “strength” measured by a parameter $$\varepsilon >0$$ , $$\varepsilon =0$$ corresponding to classic stability. The expected number of $$\varepsilon $$ -stable matchings is proved to be polynomially large if $$\varepsilon $$ of order $$n^{-1}\log n$$ , but it explodes to become super-polynomially large once $$\varepsilon \gg n^{-1}\log n$$ .
中文摘要
在一个稳定匹配问题中，一侧的n个代理对另一侧的n个代理作为潜在匹配对象各有偏好。如果没有一对未匹配的代理彼此都更偏好对方而非各自的匹配对象，则称该匹配是稳定的。Knuth证明了存在具有指数多个稳定匹配的偏好，并提出了关于均匀随机问题实例中稳定匹配期望数量的问题。利用Knuth的积分公式，第一作者证明了该期望相当温和，渐近于$$e^{-1}n\log n$$，其中n为每一侧的代理数量。在本文中，我们放松稳定性概念，若没有未匹配的代理对彼此强烈偏好对方而非其搭档，则称匹配是稳定的，其中“强度”由参数$$\varepsilon >0$$衡量，$$\varepsilon =0$$对应于经典稳定性。当$$\varepsilon $$为$$n^{-1}\log n$$阶时，$$\varepsilon $$-稳定匹配的期望数量被证明为多项式规模；但一旦$$\varepsilon \gg n^{-1}\log n$$，该数量便爆炸性地增长为超多项式规模。