第三卷, 第四期
我要我们在一起

木 遥

数学文化, 3 (2012), pp. 13-16.

查看节选 查看全文 2165 36594
  • 摘要

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

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