Of stable marriages and graphs, and strategy and polytopes

被引：23

作者：

Balinski, M ^{[1
]}

Ratier, G

机构：

[1] Ecole Polytech, CNRS, F-75230 Paris, France

[2] Ecole Polytech, Lab Econometrie, F-75230 Paris, France

[3] Univ Paris 01, Paris, France

来源：

SIAM REVIEW | 1997年 / 39卷 / 04期

关键词：

marriage problem; stable matching; graph; polytope; game; two-sided market;

D O I：

10.1137/S0036144595294515

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

This expository paper develops the principal known results (and some new ones) on the stable matchings of marriage games in the language of directed graphs. This both unifies and simplifies the presentation and renders it more symmetric. In addition, it yields a new algorithm and a new proof for the existence of stable matchings, new proofs for many known facts, and some new results (notably concerning players' strategies and the properties of the stable matching polytope).

引用

页码：575 / 604

页数：30

共 19 条

[11] MCVITIE DG, 1970, BIT, V10, P259
[12] MONGELL S, 1991, AM ECON REV, V81, P441
[13] RATIER G, 1995, THESIS U PARIS 1 PAR
[14] RATIER G, IN PRESS DISCRETE MA
[15] ROTH AE, 1991, AM ECON REV, V81, P415
[16] STABLE MATCHINGS, OPTIMAL ASSIGNMENTS, AND LINEAR-PROGRAMMING
ROTH, AE
ROTHBLUM, UG
VANDEVATE, JH
[J]. MATHEMATICS OF OPERATIONS RESEARCH, 1993, 18 (04) : 803 - 828
[17] Roth AE., 1992, Two-sided matching: a study in game-theoretic modeling and analysis
[18] CHARACTERIZATION OF STABLE MATCHINGS AS EXTREME-POINTS OF A POLYTOPE
ROTHBLUM, UG
[J]. MATHEMATICAL PROGRAMMING, 1992, 54 (01) : 57 - 67
[19] LINEAR-PROGRAMMING BRINGS MARITAL BLISS
VANDEVATE, JH
[J]. OPERATIONS RESEARCH LETTERS, 1989, 8 (03) : 147 - 153

← 1 2 →