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
关键词
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 条