伯克利工业工程系的前辈David Gale教授－稳定婚姻问题
（stable matching or stable marriage problem ）

稳定婚姻，就是指男女结婚后，双方都不会发生出轨行为。那怎样才能做到双方都不出轨呢？如果双方都是对方的最爱，自然不会出轨；如果有一方或双方都不是对方的最爱，则必须保证想出轨的人找不到出轨的对象。简言之，只要满足“除妻子（丈夫）外，我爱的人不爱我，爱我的人我不爱”条件，就可形成稳定的婚姻。

稳定婚姻问题（Stable Marriage Problem）已经被证明是一个NP问题，在过去的几十年里很多人开始对这一课题产生兴趣，同时越来越多的paper对这一问题进行深入的研究。

最为著名的研究是由美国数学家、加州大学伯克利工业工程系教授 David Gale和加州大学洛杉矶分校 Lloyd Shapley在1962年发明的稳定婚姻的寻优策略，人们称之为延迟认可算法（Gale-Shapley算法）。

 先对所有男士进行落选标记，称其为自由男。当存在自由男时，进行以下操作：

① 每一位自由男在所有尚未拒绝她的女士中选择一位被他排名最优先的女士；
 
② 每一位女士将正在追求她的自由男与其当前男友进行比较，选择其中排名优先的男士作为其男友，即若自由男优于当前男友，则抛弃前男友；否则保留其男友，拒绝自由男。    

③ 若某男士被其女友抛弃，重新变成自由男。   

在算法执行期间，自由男们主动出击，依次对最喜欢和次喜欢的女人求爱，一旦被接受，即失去自由身，进入订婚状态；而女人们则采取“守株待兔”和“喜新厌旧”策略，对前来求爱的男士进行选择：若该男子比未婚夫强，则悔婚，选择新的未婚夫；否则拒绝该男子的求婚。被女友抛弃的男人重获自由身，重新拥有了追求女人的权利——当然，新的追求对象比不过前女友。    

这样，在算法执行期间，每个人都有可能订婚多次——也有可能一开始就找到了自己的最爱，从一而终——每订一次婚，女人们的选择就会更有利，而男人们的品味则越来越差。只要男女生的数量相等，则经过多轮求婚，订婚，悔婚和再订婚之后，每位男女最终都会找到合适的伴侣——虽然不一定是自己的最爱（男人没能追到自己的最爱，或女人没有等到自己的最爱来追求），但绝对不会出现“虽然彼此相爱，却不能在一起”的悲剧，所有人都会组成稳定的婚姻。

Gale-Shapley 算法最大的意义就在于，作为一个为这些男女牵线的媒人，你并不需要亲自计算稳定婚姻匹配，甚至根本不需要了解每个人的偏好，只需要按照这个算法组织一个男女配对活动就可以了。你需要做的仅仅是把算法流程当作游戏规则告诉大家，游戏结束后会自动得到一个大家都满意的婚姻匹配。对于男性来说，从最喜欢的女孩儿开始追起是顺理成章的事；对于女性来说，不断选择最好的男人也正好符合她的利益。因此，大家会自动遵守游戏规则，不用担心有人虚报自己的偏好。

历史上，这样的“配对游戏”还真有过实际应用，并且更有意思的是，这个算法的应用居然比算法本身的提出还早 10 年。早在 1952 年，美国就开始用这种办法给医学院的学生安排工作，这被称之为“全国住院医师配对项目”。配对的基本流程就是，各医院从尚未拒绝这一职位的医学院学生中选出最佳人选并发送聘用通知，当学生收到来自各医院的聘用通知后，系统会根据他所填写的意愿表自动将其分配到意愿最高的职位，并拒绝掉其它的职位。如此反复，直到每个学生都分配到了工作。当然，那时人们并不知道这样的流程可以保证工作分配的稳定性，只是凭直觉认为这是很合理的。直到 10 年之后， Gale 和 Shapley 才系统地研究了这个流程，提出了稳定婚姻问题，并证明了这个算法的正确性。
 
伯克利官方资料介绍伯克利工业工程系的前辈David Gale教授
 
David Gale joined Berkeley in 1966 and held appointments in the departments of IEOR, Mathematics, and Economics.  His work was instrumental to the development of game theory, and linear and non-linear programming.  Gale’s unorthodox but influential research paper describes an “algorithmic procedure to find… a stable marriage.”  Their findings from this paper have been expanded and used to match students to schools。

Gale published an influential paper on the so-called stable matching or stable marriage problem with Lloyd S. Shapley, now professor emeritus of mathematics and economics at the University of California, Los Angeles. Gale and Shapley proved that, given an equal number of men and women who rank one another in terms of romantic interest, it is possible so to pair them in marriage that no two people would rather be married to each other than to their partners. They also provided an algorithmic procedure to find such a stable marriage. Gale and Shapley’s theoretical work on this problem legitimized a procedure used to match newly graduated doctors to hospital residency programs. The paper generated an enormous literature, and variations of the matching algorithm are used to match students to schools.