Scaling behavior in the stable marriage problem

被引：29

作者：

Omero, MJ ^{[1
]}

Dzierzawa, M ^{[1
]}

Marsili, M ^{[1
]}

Zhang, YC ^{[1
]}

机构：

[1] Univ Fribourg, Inst Phys Theor, CH-1700 Fribourg, Switzerland

来源：

JOURNAL DE PHYSIQUE I | 1997年 / 7卷 / 12期

关键词：

D O I：

10.1051/jp1:1997166

中图分类号：

O4 [物理学];

学科分类号：

0702 ;

摘要：

We study the optimization of the stable marriage problem. All individuals at tempt to optimize their own satisfaction, subject to mutually conflicting constraints. We find that the stable solutions are generally not the globally best solution, but reasonably close to it. All the stable solutions form a special sub-set of the meta-stable states, obeying interesting scaling laws. Both numerical and analytical tools are used to derive our results.

引用

页码：1723 / 1732

页数：10

共 8 条

[1]

Fudenberg D, 1998, Game Theory

[2] COLLEGE ADMISSIONS AND STABILITY OF MARRIAGE [J].

GALE, D ;

SHAPLEY, LS .

AMERICAN MATHEMATICAL MONTHLY, 1962, 69 (01) :9-&

[3]

Gusfield D., 1989, STABLE MARRIAGE PROB

[4]

Knuth D, 1976, Mariages stables

[5] Directed polymers with killing [J].

Marsili, M .

JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL, 1996, 29 (17) :5405-5419

[6]

MARSILI M, 1997, IN PRESS PHYSICA A

[7]

MEZARD M, 1985, J PHYS LETT-PARIS, V46, pL771, DOI 10.1051/jphyslet:019850046017077100

[8] EQUILIBRIUM POINTS IN N-PERSON GAMES [J].

NASH, JF .

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 1950, 36 (01) :48-49

← 1 →