# 伯克利工业工程系的前辈David Gale教授－稳定婚姻问题

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

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

① 每一位自由男在所有尚未拒绝她的女士中选择一位被他排名最优先的女士；

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

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

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

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.

https://blog.sciencenet.cn/blog-36947-495991.html

## 全部精选博文导读

GMT+8, 2024-7-17 05:05