稳定匹配理论的功能

稳定匹配的核心思想是实现一种稳定状态，在这种状态下，在匹配完结时不再存在这样两个市场主体，它们都更中意于他人，胜过它们当前的另一半匹配对象。在现实中，我们熟悉的8分钟相亲、学校和学生匹配等例子就是基于稳定市场匹配理论的思想发展而来的。其中双边模型和延迟接受算法是稳定匹配理论的两块重要基石。

双边匹配模型很多市场及社会制度的主要功能就是让其中的主体能和另一个主体相匹配：例如，学生和学校，职员和公司，适婚男女之间。这种市场匹配主要分为“单边市场匹配”（Single-SidedMarketMatch）和“双边市场匹配”（Two-SidedMarketMatch）。其中“单边市场匹配”指市场中仅存在一个集合，集合中的个体根据各自的偏好相互匹配。然而，单边市场匹配中的“室友”现象会导致匹配的不稳定。当假设存在四个“室友”{1，2，3，4｝，其中1最偏好2，2最偏好3，3最偏好1，且他们把4都列为最不偏好者。在这种情况下，任何两两分组都无法实现稳定，因为和4分在一起的人会结束当前匹配去和已经匹配的人再次匹配，且这次新的匹配将会成功，使得市场一直无法实现稳定（Gale & Shapley，1962）。“双边匹配模型”最早由Gale和Shapley（1962）从研究学生申请学校模型和婚姻稳定问题而提出。所谓的“双边市场”是指存在这样一个市场，市场中有两类个体集合，第一类集合中的个体只能和第二类集合中的个体相匹配。他们证明了在这样一个双边市场中，只要个体的偏好具有完备性及可传递性，以及市场足够的自由，能允许个体进行任何潜在可能的匹配，

那么市场中总是存在稳定匹配。同样以4个室友为例，假设任意2个人睡上铺，2个人睡下铺，现在要求只有睡不同铺的人相互匹配，此时就形成了双边市场匹配模型。同时，Gale和Sha-pley指出市场匹配稳定时满足以下两个条件：（1）市场中不存在来自不同类的两个个体在偏好上可以实现相互匹配，但没有匹配的情况；（2）已经配对成功的个体不会尝试结束当前的配对，并试图与来自另一类且已匹配成功的个体进行匹配。

双边匹配模型存在稳定匹配这一特性，使得其在理论和实践上都得到了广泛的关注，其中一个重要的运用就是劳动力市场的匹配。Shapley和Shubik（1972）利用数学模型抽象了一个充斥着不可分割商品的双边市场，市场中的每一位参与者既是商品的需求者也是商品的供给者。他们发现在这更为一般化的市场中匹配稳定的性质依旧很稳健。

Roth最早对双边匹配模型在解决实践问题中的应用进行了研究。他意识到Shapley有关稳定市场匹配的理论和计算可让市场的运作方式变得更清晰。20世纪50年代，美国内科医生的初级劳动力市场的组织方式能保证绝大多数个体匹配成功，但这种匹配缺乏稳定性。Roth（1984）的后续实验研究将Shapley的匹配设计应用于内科医生的初级劳动力市场，他的研究结果表明该种匹配方法能减少原有组织方式下所产生的匹配不稳定及其它存在的无序问题。