稳定分配理论(stable matchings theory)
目录 |
稳定分配理论是由2012诺奖获得者沙普利使用合作博弈的方法来研究和对比不同的匹配方法而创立的理论。该理论的难点在于要保证一个配对是稳定的。所谓稳定，指的是不存在这样两个市场主体，他们都更中意于彼此、胜过他们当前的另一半。1962年，沙普利和他的同事盖尔找到了一个叫做GS算法(Gale-Shapleyalgorithm)的方法。他们在《College admissions and the stability of marriage》一文介绍了分配理论下的高校问题及稳定婚姻机制。这篇论文也为稳定分配理论提供了理论基础。运用GS算法，他们分别解决了以下两个难题：一是如何使学校招收到更满意的学生，而新生也不必因报错志愿而落榜。二是如何使单身男女实现速配，又不发生与他人私奔的行为。在第二个问题的研究中，他们假设有10名男人和10名女人，设想先让所有男人向自己最满意的女人求婚，然后让所有女人挑选最中意的男人，并剔除所有其他人选；再让没有被选中的男人再次向自己第二满意的女人求婚，然后让所有女人挑选最中意的男人，并剔除所有其他人选。这一过程不断重复，直到所有人找到了配偶为止。他们的这种方法能确保匹配是稳定的，不会出现婚后私奔等现象。沙普利从数学和博弈论的角度，寻求出了这类分配问题的稳定解，为更多经济问题的解决提供了有意义的指导和借鉴。这些方法同时也限制了市场主体操纵匹配过程的动机，而且沙普利设计的方法能够系统性地对两个市场主体中主动的一方有利。
稳定匹配的核心思想是实现一种稳定状态，在这种状态下，在匹配完结时不再存在这样两个市场主体，它们都更中意于他人，胜过它们当前的另一半匹配对象。在现实中，我们熟悉的8分钟相亲、学校和学生匹配等例子就是基于稳定市场匹配理论的思想发展而来的。其中双边模型和延迟接受算法是稳定匹配理论的两块重要基石。
双边匹配模型很多市场及社会制度的主要功能就是让其中的主体能和另一个主体相匹配：例如，学生和学校，职员和公司，适婚男女之间。这种市场匹配主要分为“单边市场匹配”(Single-Sided MarketMatch)和“双边市场匹配”(Two-Sided MarketMatch)。其中“单边市场匹配”指市场中仅存在一个集合，集合中的个体根据各自的偏好相互匹配。然而，单边市场匹配中的“室友”现象会导致匹配的不稳定。当假设存在四个“室友”{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的匹配设计应用于内科医生的初级劳动力市场，他的研究结果表明该种匹配方法能减少原有组织方式下所产生的匹配不稳定及其它存在的无序问题。