我要我们在一起

木 遥 2012-03

2012年诺贝尔经济学奖得主劳埃德•沙普利早年和另一位名叫大卫•盖尔的数学家一起创立了盖尔-沙普利算法,这一算法是为了解决“稳定匹配难题(Stable Matching Problem)”而提出的:

给定若干个男生和同样多的女生,他们每个人都对所有的异性有一个心理的偏好次序。是否存在一种男女配对组合构成一种稳定的组合关系?这里稳定组合的意思是说,不存在两个非伴侣的异性对彼此的评价比对各自伴侣的评价还要高。(可以理解,那样的异性太容易红杏出墙了,所以是种不稳定因素。)进一步的问题是,在已知每个人对异性的偏好顺序的情况下,怎样求出这种稳定组合方式(如果它存在的话)?你可以理解为这是数学家们替月老问的问题:给定一群孤男寡女,寻找一种牵红线的方式,以确保把红杏扼杀在摇篮里。

以上文章内容选自《数学文化》,详情请见《数学文化第3卷第4期 (2012-03出版)     欢迎网上订阅数学文化