THE STABLE ROOMMATES PROBLEM WITH RANDOM PREFERENCES
成果类型：
Article
署名作者：
PITTEL, B
刊物名称：
ANNALS OF PROBABILITY
ISSN/ISSBN：
0091-1798
DOI：
10.1214/aop/1176989126
发表日期：
1993
页码：
1441-1477
关键词：
摘要：
In a set of even cardinality n, each member ranks all the others in order of preference. A stable matching is a partition of the set into n/2 pairs, with the property that no two unpaired members both prefer each other to their partners under matching. It is known that for some problem instances no stable matching exists. What if an instance of the ranking system is chosen uniformly at random? We show that the mean and the variance of the total number of stable matchings for the random problem instance are asymptotic to e1/2 and (pin/4e)1/2 , respectively. Consequently, Prob (a stable matching exists) greater-than-or-similar-to (4e3/pin)1/2. We also prove that, given the last event, in every stable matching the sum of the ranks of all members (as rank ordered by their partners) is asymptotic to n3/2, and the largest rank of a partner is of order n1/2 log n, with superpolynomially high conditional probability. In other words, stable partners are very likely to be relatively close to the tops of each other's preference lists.