【瞻彼淇奥的回答(7票)】:
谢邀。（第一次被邀请回答问题，心里还有点小激动呢（≧?≦））
先上算法：Defered Acceptance Algorithm
Begin with every woman marked as rejected.
While there exist a rejected woman, do as following:
(1) Each woman marked as rejected choose a man whom she ranks highest among all those men who has not yet rejected her.
(2) Each man picked out the woman whom he ranks highest among all those women who have chosen him and whom he has not yet rejected, defers decision on her (and removes her rejection status), and now rejects the others.
From Introductory Combinatorics 5ed, page 332.
这个是稳定婚姻问题中，女性主动求婚的延迟接受算法。
在求职、择校等等问题中（相当于一夫多妻/一妻多夫的稳定婚姻），上述算法稍作修改后即可给出一个stable mathching.
题主给出的链接里给出了一个学生择校的例子，我们拿它做分析：
（原例图表很清晰了，无奈ipad贴不上图片。。。只好文字叙述）
有三所学校1，2，3，和十名学生A，B，…，J。每所学校列出它想接收的学生并为其排序（学校1：ABCD；学校2：EFGD；学校3：ADHI），每名学生列出自己的志愿学校并为其排序（A：123；B：21；C：132；D：132；E：321；F：12；G：132；H：32；I：123；J：213），每所学校最多接收三名学生。
我们把算法改成：学生主动申请（求婚）的（一夫多妻）延迟接受算法，和原算法的差别是：学校会拒掉其接收名单之外的学生；当有三名以上学生申请同一所学校时，学校会按照预先给出的排序，保留排位最高的三名学生，同时拒掉其他人；存在学校名额招不满或学生没学上的可能性。
第一步，所有学生都申请了自己的志愿中排名最靠前的学校，即A、C、D、F、G、I申请学校1；B、J申请学校2；E、H申请学校3。
由于F、G和I不在学校1的接收名单之内，因此这三名学生悲伤的收到了拒信，同理B，E，和J也收到了拒信。
第二步：被拒的六名学生继续申请自己的第二志愿，即B和J申请学校1；E，F和I申请学校2；G申请学校3。
对学校1而言，J不在接收名单内，拒掉。此时学校1有A，B，C，D四名申请者，于是选择排位靠前的A，B，C，拒掉D。
学校2和3同理。这一轮中D，G，I，J收到拒信。
第三步：D申请第二志愿；G，I，J申请第三志愿：G申请学校2，D，I，J申请学校3。J因为不在名单内而被拒，其余学生全部拿到offer。由于J已经被全部三个志愿拒掉，算法结束。
和稳定婚姻类似，可以证明延迟接受算法给出的择校安排是稳定的，即不会出现你情我愿的转学现象。
【RichardXu的回答(8票)】:
谢邀。
由于以下内容将按照与题述的逻辑关联程度论述，而非重要程度列出，因此首先贴出提纲，以便抓住重点。
1. 延迟接受算法（或简称DA算法）在一对多双边市场上的拓展，以及该拓展与一对一双边市场的相互关系；
2. 双边市场（婚姻市场）与单边市场（房屋市场）的差异；
3. （重点）原本的模型：Boston Mechanism；
4. Boston Mechanism的相关性质；
5. （重点）进一步分析：Boston Mechanism 与 Deferred Acceptance Algorithm的联系。
附：相关阅读
摘要：
延迟接受算法可以从一对一双边市场（婚姻市场）拓展到一对多双边市场（学校招生），前提是学校方对于学生的偏好建立在学生个体而非学生的组合上；新的一对多市场等价于将学校拆分成入学名额个学校，学生对于这些拆分后的“学校”偏好相同的一对一市场；
在引入DA算法之前，美国教育系统采用的模型之一是Boston Mechanism，这个算法实际上将学校招生视为单边市场，对于学校来说，它的偏好称为priority而非preference，受到政府限制，不一定代表学校的喜好，这导致单边市场只考虑一边（在这里是学生）的效用，学校的priority本身并没有说明效用。Boston Mechanism的结果满足（对于学生的）帕累托优，即每个学生不可能得到更好的学校，但是不满足stable的条件，同时也不满足strategy proof，也就是说学生有激励去改变自己填报的志愿，假装自己喜欢或者不喜欢某所学校，使得自己能去的学校更好；
但如果将学生选择志愿视为一场博弈的话，非常神奇的是，这个博弈的所有纳什均衡解恰好是所有稳定匹配，而我们又知道稳定匹配对于学生的最优解可以由DA算法由学生方propose来得出，因此，一切又回归到DA算法，将学校招生视为双边市场，考虑学生propose的DA算法，得到的解满足stable（稳定性），M-optimal（学生最优）以及strategy-proof（学生没有激励去伪造自己的真实意愿）；
文中穿插了关于中国高考志愿填报模式的讨论以及DA算法仍然存在的一些不足。
最后，相关阅读包括了一系列有关学校招生的著名论文。
-----------------------------------这里是目录和摘要的分割线---------------------------------
背景阅读-婚姻市场上的DA算法：恋爱中有哪些博弈？ - Richard Xu 的回答
1. 延迟接受算法在一对多双边市场上的拓展，以及该拓展与一对一双边市场的相互关系；
正如 @瞻彼淇奥 所说，只需将在一对一双边市场上的延迟接受算法稍作修改，就能够得到一对多双边市场上的延迟接受算法，这些修改大致包括如下几项：
（1）在婚姻市场上，男性对于所有女性进行排序，女性对于所有男性进行排序，这是非常直观的；在学校招生时，学生只能去一所学校，所以学生对于学校的排序也是很容易理解的；但是，学校对于学生的排序就有两种不同的情况：一种是，学生与学生之间是相互独立的，学校对于单个的学生建立偏好；另一种是，学生与学生之间是有关联的，学校招生的时候对于学生的组合建立偏好。
举例来说，如果一共有3个学生1,2,3，那么前一种情况是，学校觉得1比2好2比3好，或是3比2好2比1好，这是建立在“单个的学生”上的偏好；另一种情况是，学校觉得同时招1和2最好，其次是1和2和3，再次是2和3，再次是1和2，等等，这是建立在“学生的组合”上的偏好。后一种情况在什么时候会发生呢？举个例子，清华每年都要参加首都高校长绳比赛，长绳需要12名队员，选拔长绳队员的时候，并不是从各个院队里一个一个选拔出来（单个的学生的偏好），而是选拔了最好的一个院队（学生的组合的偏好），因为这些学生已经经过长期的磨合和练习，把他们组合在一起将会有协同效应，换上别的院跳得好的同学，反而有可能拖后腿。
后一种情况，正如我在上述另一题的回答中所说，存在反例说明可能并不存在stable matching。然而，对于前一种情况，stable matching总是存在的，原因在下面进一步阐述。
（2）引入quota，即学校的招生名额。这是很自然的，因为是一对多的缘故。
（3）由于quota的存在，对于稳定性的要求也发生了变化：
I.R.: 学生不会选择unacceptable的学校，学校不会选择unacceptable的学生
Pairwise Stability:不存在如下情况：
i. 学校S有空位，且学生s对于学校S是acceptable的，且对于学生s学校S比目前的情况（没有学上或是被另一学校S'录取）更好；
ii. 学校S没有空位，但在录取的学生中有一名学生s'，对于学校S学生s比学生s'更好，且对于学生s学校S比目前的情况更好；
回到上面这个问题，为什么stable matching总是存在的呢？在一对一双边市场上，稳定匹配的存在性是由DA算法构造出来的，因为构造出来的这个匹配是稳定的，所以稳定匹配存在。而对于一对多双边市场，我们不需要再按照证明一对一双边市场上那样完全走一遍，实际上，当学校的偏好建立在“单个的学生”上时（也称为responsive或者separable preference），我们完全可以这样做：
学校A有三个名额，那么我就把学校A拆成学校A1、A2、A3，分别只有一个名额，它们对于学生的偏好和学校A是一样的，而学生认为学校A1、A2和A3是一样好的；对其它学校也是一样处理。DA算法并不要求偏好是strict的（偏好strict的意思是任意两所学校都能分出好坏，或者用报道中的话说，“在最优情况下，这群男女中不会有人同时对两个人喜爱程度相当”，这个要求对于稳定匹配的存在性并没有影响，只影响了最后的稳定解是否是Lattice），这样一拆，相当于构造了一个一对一双边市场，新市场上的稳定匹配存在（由DA算法给出），则原市场上的稳定匹配只需要将A1、A2、A3重新合并回学校A即可。
2. 双边市场（婚姻市场）与单边市场（房屋市场）的差异；
实际上，对于学校招生，还有另外一种模型，即单边市场模型。在单边市场中其实还是存在两边，但是一边是人，另一边是东西，由于我们更关注人的行为，所以称为“单边”。在单边市场上，重要的是将人和东西匹配起来，也就是一个分配的问题。
最基本的单边市场是房屋市场，每个人对于房屋都有自己的偏好，房屋自己不会挑人，随便谁住都可以；但是，当我们考虑学校招生这样一个单边市场模型时，学校对于学生是可以有偏好的，这个偏好不是通常意义上的preference，而被称为priority（两者在形式上接近一致的），原因在 @荣健欣 的答案中也有提到，即这个priority是受限制的。事实上，在学校招生模型中（比如即将提到的BM），学校的priority只能根据一系列的规则来进行，而规则是由政府决定的，例如，政府规定，学校优先招纳距离学校近的学生，在距离差不多的情况下，招纳学分绩更高的学生，在学分绩也相同的情况下，优先招纳女性学生，这样一来政府完全可以不需要学校参与决定这个priority，在这个priority中也完全没有体现出学校自己的意愿，相应地，当我们考虑此时市场的效率（efficiency）时，我们就不需要将priority考虑进来，而只考虑学生对于学校的preference所产生的效用。
由于priority的存在，对于稳定性的要求有了一个新的名词，叫作respecting priority，基本上等价于双边市场中的pairwise stability。
3. （重点）原本的模型：Boston Mechanism；
在DA算法之前，有一个模型在美国学校招生中非常流行，这个模型称为Boston Mechanism，因为其最先在波士顿试水并推广而得名。如果没有猜错的话，纽约在2003年之前使用的就是BM或者BM的变种，因为报道中有两句话非常符合BM的实际情况：“所以有些目标高远、填报了多家热门学校的学生，一旦被写在第一栏的学校拒收，就会在选校表中一落千丈。”（这是BM机制中常有的，参见下面的例子中的学生6）“家长们担心如果选错了，他们的孩子会“浪费”至关重要的首选位置。”（这句话虽然写在新机制运作之后，但表达的是BM的流毒，即浪费首选位置的想法，同样参见下面的例子中的学生6）
首先我来描述一下这个模型，它和DA算法的描述其实只差一句话：
在BM中，如果学生s被学校S录取，那么之后不会被替换掉；而在DA算法中，如果后面有更好的学生，学校S会踢掉学生s。
简单地说，DA算法对于BM最重要也是最神奇的改进只在于：允许“见异思迁”。
是不是觉得这个模型很熟悉？答对了，这其实非常接近目前中国高考的录取模式（当然还有一些小的变动，比如考前填还是考后填还是知道分数填等等执行细则问题），学生填报志愿，高校根据分数提档，如果你被一志愿的高校提档并录取了，没有问题，如果你被提档了但没有录取，那么你基本上没有机会被二三志愿的高校再挑走，它们也差不多招满了，不会再接受提档，即使接受了也不会把前面的学生踢掉，这时候你就得考虑征求平行志愿或者再往下一批次了。
（在这里说明一下题主对于相关模型在中国运用的可能性分析，昨天我和一名博士生学长聊天时，他就提到，中国高考其实并没有表现出很多下面即将提到的BM的弊病，因为BM在一种非常特殊的情况下，和DA（无论由学生还是由学校propose）的结果是完全一致的，那就是所有学生对于学校的偏好一样（而且strict），所有学校对于学生的偏好一样；而我们来看中国的高考，当我们讨论高考分数论英雄的时候，其实恰恰说明学校对于学生的偏好高度标准化，就是按照高考成绩，就是按照分数从高到低，而学生对于学校的偏好也大致相同，清华北大，211、985或者C9，可以看出实际上大家对于学校的偏好也是从高到低排的，当然因为种种原因，填志愿本身仍然构成下面所述的BM机制下的博弈，但是其复杂程度已经被大大削弱了。相比之下，层出不穷的自主招生、体育/竞赛保送生或加分反而是使得BM问题更加严重的原因，这并不是替BM或者中国高考填志愿的模式洗地，也不是反对自主招生或保送（答主对于竞赛保送持强烈支持态度），而恰恰说明中国的确有必要考虑DA算法作为高校录取的办法。）
4. Boston Mechanism的相关性质；
对于机制的考量主要分为三个方面，efficiency效率，stability稳定性，和strategy-proofness是否存在偏离的激励（其实对应于激励相容Incentive Compatibility中的一种，即Bayes-Nash IC）。
efficiency效率的意思是，学生是否得到了可能获得的最好的学校？在DA算法中，我们说学生得到了最好的学校，是指在所有稳定匹配中最好的学校，如果我们考虑不稳定匹配，实际上可能存在不稳定匹配使得学生都能够更好（这里的更好是指帕累托优，即在新的不稳定匹配中，每个人至少和在最好的稳定匹配中的处境一样好，且至少有一个人匹配到了比稳定匹配中他更喜欢的学校），这种现象就发生在了BM模型中，它给出了一个最优但是不稳定的匹配。
考虑下面这样一个例子，有六个学生1~6，四个学校a~d，学校ab各有两个招生名额，cd各有一个招生名额。
学生对于学校的偏好是
R1:a 后略
R2:a 后略
R3:a b 后略
R4:c 后略
R5:c a b d 后略
R6:c a b d 后略
学校对于学生的priority是
a: 6 1 2 3 后略
b: 5 6 3 后略
c: 4 5 6 后略
d: 5 6 后略
根据BM，得到的匹配是
a: 1和2
b: 3和5
c: 4
d: 6
匹配的最优性是由BM的机制决定的，因为每一轮它都把每个学生匹配到了最好的学校，对于任何一个学生来说，他比BM所匹配的学校更喜欢的那些学校在任何匹配中都不可能招收他，这一点是不难证明的。而其不稳定性在上面这个例子就展现出来了，a喜欢学生6胜过1和2，而6喜欢学校a胜过d，说明上面的这个匹配不是稳定匹配。
观察一下6的偏好，可以发现6在第一轮选择了自己最喜欢但是却并不是那么喜欢自己的学校c，这是一个严重的失误，因为同时本来最喜欢他的学校a已经招满了学生，即使6试图在第二轮挽回（选择了a），仍然一再错失机会，最后只得到了排在最后的学校d。这就是“一旦拒收，一落千丈”和“浪费首选位置”的真实体现。
在这里，又不得不提到最后一个考量标准，就是strategy-proofness。这个要求的意思是，任何学生（因为学校的priority是不能更改的）都没有激励不按照自己真实的意愿来报告自己的偏好。而BM给出的模型显然不满足这一点，仍以上面这个例子为例，如果6意识到自己可能被c拒绝并最终不得不进入d，那么他完全可以谎报自己喜欢a胜过喜欢c，这样在第一轮他就把2挤走成功进入了a，尽管他没能进入最想进入的学校c，但是仍然比进入d要高了两档。
综上所述，BM虽然能够给出帕累托优的匹配，但是这个匹配是不稳定的，而且不是激励相容的，学生有谎报自己偏好以获取更高的学校的可能。
5. （重点）进一步分析：Boston Mechanism 与 Deferred Acceptance Algorithm的联系。
不过拍脑袋一想，不对啊，既然你可以改自己的志愿，我也可以改嘛。因此，在BM真正开始分配之前，也就是学生们填报志愿的时候，就已经开始了一场没有硝烟的战争，学生们都会调整自己的志愿，使得能够上到更符合自己偏好的学校，这构成了一场博弈，每个学生是一名玩家player，每个人的策略就是不同的志愿填报顺序R，最终的结果outcome就是根据每个人填报的志愿进行BM分配所得到的学校，相应的payoff就是和自己偏好的相符程度，能得到自己更偏好的学校效用就更高。
在这个博弈中，存在着一系列的纳什均衡，而神奇的是，这些纳什均衡的结果outcome恰好就是所有的稳定匹配，这一点的证明可以在这里稍微表述一下：
首先要证明所有的纳什均衡结果都是稳定匹配，这是显然的，如果存在纳什均衡的结果是不稳定匹配，那么也就意味着有学校S想要学生s来踢掉别人或者填补空位，学生s也想要学校S而非现在匹配的学校，那么s只需要把学校S提到自己志愿的第一位就可以了，也就是他有进一步改变自己志愿的激励，不满足纳什均衡的要求。
其次要证明所有的稳定匹配都是纳什均衡的结果，这就更显然了，只要每个人都把自己在这个稳定匹配中匹配到的学校填在第一位，第一轮百分之百全部录取；任何人单方面的背离都不能是他更好，因为其他人把所有别的坑都填满了，他要么最后还是回去填了自己的坑，要么就没学上。
根据集合的性质，如果集合A和集合B互相包含，那么这两个集合相等，因此所有的纳什均衡结果就是所有的稳定匹配。
这告诉我们什么呢？如果将学生在BM机制下选择志愿视为一场博弈的话，非常神奇的是，这个博弈的所有纳什均衡解恰好是所有稳定匹配，而我们又知道稳定匹配对于学生的最优解可以由DA算法由学生方propose来得出，因此，一切又回归到DA算法，将学校招生视为双边市场，考虑学生propose的DA算法，得到的解满足stable（稳定性），M-optimal（在所有稳定匹配中对于学生来说最优）以及strategy-proof（学生没有激励去伪造自己的真实意愿，可以证明，此处略去）；
这也正是报道中提到的一句话，“按真实的偏好顺序来排列学校。”
顺带说一句，其实这篇报道的记者对于DA算法还不够了解，最重要的是这样一句话“那一年以及之后的每一年，这种算法大致将所有学生中的一半人数分配到他们的首选学校；另外大概三分之一的学生被分配到他们的次优选择或是第三选择的学校。” DA算法关注的并非是首选学校或是非首选学校，这恰恰是BM所关注的重点，BM就是尽量将学生都尽可能分配到首选或者靠前的学校。但是事实上，这个关注重点又是非常无关紧要的，按照给我们授课的教授的说法，如果大家都按照DA算法给出的最优稳定匹配来填，那么BM将会100%的将学生安排到第一志愿，但这有什么意义吗？
其次，在报道中出现了所谓心仪学校、失望的学生这样的说法；如果DA算法没有给学生分配到某所更好的学校，绝不是因为算法故意让你去不成，而恰恰说明在所有的稳定匹配中，都不存在让你去这所学校的可能；甚至回到BM的志愿选择博弈中，无论你如何努力地去调整自己的志愿，最终的均衡结果中（也就是稳定匹配中）同样没有让你去这所学校的可能。这样的失望是没有意义的，就好像分数只有本一线附近的学生指望通过填志愿就进入清北一样，就算你进不了，也不能怪中国的高考志愿填报方式吧。
当然，DA算法也并不是没有问题，最关键的地方在于，strategy-proof还是太不能满足人们的要求了，它假定的是别人如果不偏离，那么你也不应当偏离，但是在别人偏离的情况下，你不是还应当不偏离呢？不一定，要满足这种情况，要求的是dominant strategy incentive compatibility，无论别人选择什么，按照自己真实的偏好填写志愿都是最好的选择（之一），这是比strategy-proof或者说Bayes-Nash incentive compatibility更高的要求，而DA算法并不满足。
-----------------------------------这里是正文和相关阅读的分割线--------------------------
相关阅读：（引用规范暂时先不管了……）
核心内容：
[1]Abdulkadiroglu&Sonmez(2003, AER) "School Choice: A Mechanism Design Approach"
[2]Abdulkadiroglu, Pathak & Roth(2009, AER) "Strategy-proofness versus efficiency in matching with indifferences: redesigning the New York City high school match"
Efficient Resource Allocation under Priorities:
[3]Erdil&Ehlers(2010, JET) "Efficient assignment respecting priorities"
[4]A series of papers by Kumano that "generalize to subtitutable priority ranking"
Boston Mechanisms:
[5]Pathak&Sonmez(2008, AER) "Leveling the playing field: Sincere and sophisticated players in the Boston mechanism"（老师给我们写的是“Naive&Strategic students”……）
[6]A series of papers by Kojima that "generalize to substitutable priority structure"
[7]Abdulkadiroglu, Che&Yosuda(2011, AER) "Resolving Conflicting Preferences in School Choice: The" Boston Mechanism" Reconsidered"
【ShiHou的回答(10票)】:
这是同一个算法。事实上deferred acceptance algorithm, 在1962年被Gale and Shapley从理论上提出的时候，论文的标题就叫"College Admissions and the Stability of Marriage". 由于婚姻匹配问题是简单的一对一匹配问题，之后对deferred acceptance algorithm的许多研究就以婚姻匹配为背景。比如高德纳于1976年用法文写了一本书叫Mariages Stables, 总结了截至当时的结果。
2003年改革前，纽约公立高中招生采用的是这样一种机制：每个申请者填写自己最想进的五所高中作为第一至第五志愿，他们的志愿列表会发给学校，学校决定接收、拒绝还是放进waiting list. 这个过程重复三次，三轮过后仍未被录取的学生接受统一分配，这时候就不看志愿了，基本只看离家远近。学校决定是否招收某个学生时，不仅要看学校对学生的偏好，也看学生把学校列在第几志愿。学校更喜欢招收把它列为第一志愿的学生。
这篇文章（http://economics.mit.edu/files/3962）的附录AII（从pdf的19页开始）描述了改革后的招生机制。总体来说，它的核心就是一个简单的由学生propose的deferred acceptance algorithm, 运作与恋爱中有哪些博弈？ - 恋爱心理 中给的相同。
要讨论改革后的机制相对于原有机制有哪些优点，就要讨论这样一个two-sided matching问题里面，评判机制好坏的几个标准。
1. 稳定性(stability)：稳定性要求，算法跑完之后得到的配置满足个人理性（individual rationality, 举例来说，男生得到的女朋友不能让他觉得 “还是单身好啊”），同时满足不存在blocking pair（举例来说，不存在两对couple中的一男一女想见异思迁组成新家庭）。
纽约公立高中的招生旧机制是不稳定的。表现为有些学校不喜欢这个机制派给它的学生，所以宁可回避掉这个机制。比如说，一个高中校长说，假设学校有100个招生名额，它宁可告诉当局他只要40个，等跑完三轮志愿填报后再通过其他程序招完余下名额。而对于deferred acceptance algorithm就比较简单了，理论证明这个算法必定生成稳定匹配。
2. 学生的福利(student welfare): Gale & Shapley(1962)证明了一个非常有意思的结果：假设所有男女的偏好是严格的（不存在无差异的情形），由男生表白的deferred acceptance algorithm所生成的配置结果是在所有稳定匹配中，对于所有男生都最好的匹配；这个匹配同时也是在所有稳定匹配中，对于所有女生都最差的匹配。（这里的“最好”和“最坏”都是指双方申报的偏好而言。如果申报的偏好与真实的偏好不同，那么产生的匹配有可能不是对于真实偏好最好或最坏的结果。）
招生匹配中，机制设计者的目的是找出对于学生来说最好的稳定匹配。公立学校的偏好一般是被政府抑制的，波士顿机制更甚，学校对于学生本身没有偏好差异，只有政府外生给定的一些排序。比如说家离学校近的排在家离学校远的前面，有兄弟姐妹在校的排在没有兄弟姐妹在校的前面，等等。纽约学校对学生本身有偏好，也存在学业水平考试，政府同样在新机制中压抑了学校偏好的表达，比如说将学生学业成绩粗略地分级排序。总而言之，此类机制的设计目的一般是最大化学生的福利，也就是说，挑选出对于学生来说最优（往往就是对于学校来说最差）的稳定匹配。
原有的机制在学生福利方面做得不够好。有很大比例的学生最后是被分配到自己根本没有填报过志愿的学校去的。在改革后，被分配到未曾表达过志愿的学校的学生数量下降了90%（http://www.nobelprize.org/nobel_prizes/economic-sciences/laureates/2012/popular-economicsciences2012.pdf 第4页）。
3. 学生说真话(students' strategy proofness) : 要求学生真实地表达自己的偏好是他们的占优策略(dominant strategy)。旧机制下是不可能的，原因很简单，既然学校招生看志愿次序，学生就不敢把自己最喜欢，但希望渺茫的学校填在前面。而在新机制下，学生是会说真话的。原因不难理解：students proposing deferred acceptance algorithm产生的是对于所有学生来说，对于他们申报的偏好而言最好的稳定匹配，那么当然申报真实的偏好最好。注意学生说真话不代表学校有说真话的动机，事实上有证明说不存在所有方面都说真话的稳定匹配。但由于学校的偏好表达被政府规制，学校说假话的机会也不太多。
【woeMr的回答(2票)】:
邀请错人了.不好意思我对这个问题没兴趣.
但是下面这篇paper介绍比较详细
http://www.nber.org/papers/w13225.pdf
【成晓宇的回答(1票)】:
楼上的 @Richard Xu是嘉神么。。
题主如果感兴趣，可以浏览一下我在Quora上回答过的一个类似的问题，部分内容和上面答案类似，有一些补充以供参考：
Xiaoyu Cheng's answer to How can game theory improve high school & universities application process?
【DeepReader的回答(1票)】:
是同一个算法。
算法： Gale–Shapley algorithm (a.k.a. 延迟接受算法)
【知乎用户的回答(0票)】:
谢腰
是同一个问题
这是一个选择分配的问题，即所有学校都参与到分配中而不是以各个学校自己为中心进行分配……
在中国恐怕有关部门不会同意
【明晃晃的回答(0票)】:
懈腰～
大家把算法解释得很清晰，我无用武之地了，不过我想不用数学再概括阐释一下它（见a）。之后我主要回答一下题主针对此算法真实应用情况的疑问（见b）和算法是否适用于在中国择校问题的疑问（见c）。
a）算法的无数学版概括
stable matching的本质是一个循环。我们先假设存在理想状况，就是“每个人得到的东西是他最想要的”。这个算法通过“不断把满意的配对（比如学生和学校相互满意，一对伴侣相互满意，肾病病人和肾源配型成功）提出来，剩下的人里，每一次有人不满意时让他重新选择”来不断减少“不满意”的人数，直至每个人都“满意”为止。
明白大意之后我们澄清几个细节。1）“理想状况”：
理想状况在上文被我描述为“每个人得到的东西是他最想要的”。它指的不是“我想上哈佛，上了才满意”，而是我力所能及达到的最好结果。具体举一个例子，比如学生A目标院校是A*（其次是B*，然后是C*等等），但是他被A*拒绝录取了，那么“B*录取他”这种情况就比“C*录取他”更加令他满意。他达到了“能力之内能达到的最好结果”所以满意了，算法把他拎出循坏之外。反之，如果C*录取了他，而他的成绩可以被B*录取，算法把他拉入选择循坏，他可以再次选择。注意，如果B*在接下来的选择中拒绝了他，那么C*成为令他满意的结果。所以请广义理解“能力之内”和“满足”，它的意思是我们接受范围里被客观条件限制以后的最好结果。
2）“理想”（状况）vs. 现实
无论如何以实践为目的进行理论研究，研究模型本身还是抽离了大量事实和现实条件的抽象分析。
理论分析里我们假设每个人有“条理分明/前后一致（coherent）的弱偏好”（翻译不当请无视，下面解释），也就是我的心动学校排序可以是“A*比B*好，B*比C*好，C*和D*一样好”。但对比“A*比B*好，B*比C*好，C*和D*一样好，D*比B*好”，我们发现此人脑子有病，做不到条理分明前后一致。但是细思极恐，我们每个人都有这样混乱的偏好。事实上，行为经济学通过简单的观察和实验早已给我们确诊，而广告和营销学（marketing）更是建立在人消费行为的不理性之上的。
我们发现这种算法的假设存在一定的问题，导致逻辑混乱的非理性正常人哪怕进入无数个“再选择循坏（非术语，个个人基于理解的造词）/stable improvement cycle”，结果都是此人不知道自己想要什么，无最优解。
站在学校层面，有的时面对两个分数持平的学生学校无法抉择。
故事的高潮来了，模型设计者做出了一些努力来杜绝各种以上悲剧的发生。对于学生，他们的不理性偏好是教不了改不好的；对于学校，一切“难以抉择”被人为排序/随机抽签，导致任性随机的结果。
b）算法的应用
b-1）应用范围
延迟接受算法的应用范围广阔，假设性的应用包括婚姻市场，实际的应用目前已经包括美国部分州的（肾脏移植）肾源分配系统、择校和录取系统等等。在百度上还看到一篇此算法在北京市保障性住房分配系统的应用，但是不知道是理论性的文章还是已经进入实践了。
我来分析一下这种算法适用于什么样的市场（没有参考资料的大开脑洞，不适者轻喷）。这种算法适用于个体（学生，学校，病人，医院等等）了解信息不完全或者获取信息的代价高昂的市场，可以以相对小的代价掌握大量信息的公共机构可以利用这种算法提高人们的“满意度”，促进社会的和谐稳定囧。（这种算法的实际应用往往是公共资源分配，没见过国家机关或者别的公共机构组织组织“延迟接受算法帮你找到好老公/好老婆”的相关活动。）
原因一，公共资源分配的过程中，参与人“必须”有（事实上参与人往往真的有）严格偏好。比如：福利房想要位置好（怎么算好因人而异），学校想要升学率高/硬件设施齐全/课外活动多的等等，肾源要和病人配型相同。。但是对于非公共资源的选择来说，参与人往往没有特别有条理有逻辑的偏好。算法的假设条件显而易见适用于公共选择。
此外，对于非公有资源的分配，一个参与人的选择往往对其他参与人造成的影响可以忽略不计。如果有人占用公共资源，比如某学生“上了A*校不满意”（“占着茅坑不拉屎”），那么此学生/此坑位占领者实际上降低了他人的幸福感，白白浪费了社会资源。如果此人换个学校/地方，他能更开心，别人也能更开心。此时算法/政府的存在和宏观调控是有据可依的，因为单独的参与人往往不知道其他利己（也利他）的选择。但是对于感情、旅行（每个景点的客流量调控）等等的选择，一是很难把偏好排序，二则我爱错人不至于侵害别人爱此人的权利而导致社会损失/我去了威尼斯不满意不妨碍别人在威尼斯玩儿得尽兴。因此没有公共机构把这种用于宏观调控的算法浪费时间资源用到这些领域。爱情市场仅仅是个例子，论文里的“排排坐，挑老公”在现实里是几年的相处和选择，不是一个算法能解决的。
b-2）算法在择校问题上的应用
此算法在美国几个州的中学都已经投入使用，研究者统计了“算法结束还不满意的人数”作为衡量成功率的一个参数。我们看看他们的结果：
当初说好“没有一个人不满意了算法才结束”，但是《在大约90000名纽约学生中，1500名学生本来可以去自己更加偏好的学校；相同的择校系统在波士顿基本没有遗留可以增进偏好的情况》（引自网上一论文节选）。说好的幸福呢？
文章作者提出几个问题，1）什么导致了纽约和波士顿的不同结果？2）很多家庭做出一些“策略行为”，比如把名校排在真实偏好前面（万一名校没有招满而招了自己孩子，孩子就“捡漏儿”了），这种行为导致社会损失，如何避免？
纽约一例的结果是，1）不是所有参与者都能达到满意的结果。 2）作者引用其他理论研究，发现无法避免考生择校时采取的策略性行为。纽约这个例子很片面，不足以让我们得出什么结论，但是这些结果是显而易见的，存在以下一些原因。
对于学生来说，不满意由于1）偏好改变：来这个学校以前以为很好，结果悲剧，或者参观了别的学校发现后悔了。2）除了最喜欢的几个选项以外，别的垃圾学校都一样，但是客观条件是好学校就那几所。3）很难给偏好排序，比如在本区（北京市海淀区）的名校硬件好，在另外一个区（北京市朝阳区）的学校升学率高，我家在海淀，孩子喜欢学校的多媒体新设备，姥姥让孩子去自己的母校。。如上等等因素掺杂在一起，往往导致在几个选项之间徘徊。
对于学校，择优录取的“优”也难以竖立成有序的偏好。比如成绩好但是综合素质（不知道什么意思，很多学校解读成三好学生证）vs成绩中等但是运动优秀（体育特长生）。
另外，这个算法的最大问题，也是无法解决的问题就是，这个算法本身叫动态选择，但是实际上仅仅达到了静态平衡。动态“动”在了循坏选择上，静态“静”在了依据考生择校时的偏好决定了他之后几年的学校，而没有考虑到择校这个决定影响的是一个时间跨度，而偏好随时间改变。
这里要结合我在法国交流的经历谈一下法国大学的择校系统。在法国，（“好大学”）大二的学生如果没能达到优秀（20分里平均分12以上为优秀，10为及格）、那么大三必须申请转去其他学校或者其他专业。我身边不少同学都愿意转校，想转专业的同学什么心理不用我剖析，大家都懂的。另外一部分同学觉得智商跟不上（研究性课程难），所以转去其他学校（偏向应用型的院校）本专业就读。我觉得这个系统虽然导致大家压力大等等，但是给了更多人挑战专业方向、课程难度、生活地区。。等等选择的机会，容纳了偏好的改变。
c）算法在中国择校问题上的应用
我觉得是可行的，因为就北京而言，小升初的电脑派位已经执行了超过十年了（暴露年龄了。。）。它就是把学生们的各项资料给学校，让学生们填4-5所学校，然后运行一套类似的算法吧。虽然不是诺贝尔奖得主的研究结果，但肯定也是无数研究人员讨论和小范围实践过n次的应用。我的经历是只有成绩不好的同学和升学率不佳的学校参与电脑派位，剩下的学生和学校通过自主招生（奥林匹克数学竞赛，英语语文各种竞赛）过招，两情相悦地彼此选择。在奥数禁止后，“私会”和“偷情”还是屡禁不止。
我的结论是往往“好”的参与者的偏好（“好学生好学校”）都被满足了，条件差一点的参与者被公共机构以一种宏观调控的方式塞到了另一些参与者手里。他们的所谓“建立在偏好上的匹配”都是放屁，其实他们的选择最终都落到了“垃圾学校”或者“不招也行的学生”里。
客观地说，我觉得很多人是凌驾于这种算法之上的，比如找到真爱的人不去相亲，自主招生成功的人不参加电脑派位。剩下的人里，一部分人报考名校，专业被调剂，是一种（为了踏上人生巅峰的）策略性行为，但是与他真正的偏好不符合，比如他真正喜欢的专业和大学。还有一部分人，灰头土脸地掉到“垃圾学校”，但是慢慢偏好改变，爱上所在的院校。。。
分这些类是想说，1）客观上，算法没能给“好学生好学校”提高满意度，也没能给不佳的参与者减少多少社会损失。2）主观上，我们的“满足”和偏好是变化的，塞翁失马焉知非福（比如我男朋友就喜欢上了本来不喜欢的大学），同时当时的“好学生”到了“好学校”未必过得开心。
我的以上解读很不严密，但是我真的觉得理论算法应用到社会问题上真的和论文里的结果相去甚远。这个算法在理论上消除社会损失可能卓有成效，但现实里“学生择校满意度”不是一个单选题（满意vs不满意）能概括的，当时被满意的录了以后未必开心，反过来未必不开心。
这种算法最多帮政府统计策划一下每年的考试和招生分配，在择校这个领域的“满意度”这种虚无缥缈的东西我觉得不如在病人肾脏配型这些领域的“成功率”靠谱。
把这种算法普及到福利房分配，活体移植配型上，“满意度”有了不经常变化、比较稳定的偏好（房址、血型等等），算法的目标“大家都满意”是可以用客观标准衡量的。
》》》》》》》(￣▽￣)《《《《《《《
以上
欢迎讨论和指正～
【张骏Scorpio的回答(0票)】:
谢邀。我其实是博弈学的门外汉，楼上各位的见解和Paper都挺不错的，推荐楼主看看，我浏览了能懂个大概。
至于算法的应用，我觉得不仅依赖于算法本身，还依赖于模型的完整性。我就说这些。
【夏汀的回答(1票)】:
谢邀，不过有人回答过了我就不说了。倒是被激起新idea啦，开论文去。
原文地址:知乎
联系客服
