TR-2001-01

A fixed-point approach to stable matchings and some applications

Tamás Fleiner

Published in:
Mathematics of Operations Research 28 (1) 103-126, 2003

We describe a fixed-point based approach to the theory of bipartite stable matchings. By this, we provide a common framework that links together seemingly distant results, like the stable marriage theorem of Gale and Shapley, the Menelsohn-Dulmage theorem, the Kundu-Lawler theorem, Tarski's fixed point theorem, the Cantor-Bernstein theorem, Pym's linking theorem or the monochromatic path theorem of Sands et al. In this framework, we formulate a matroid-generalization of the stable marriage theorem and study the lattice structure of generalized stable matchings. Based on the theory of lattice polyhedra and blocking polyhedra, we extend results of Vande Vate and Rothblum on the bipartite stable matching polytope.

Keywords:
Stable matchings, Lattices, Matroids, TDI, Lattice polyhedra, Blocking polyhedra

Bibtex entry:

@techreport{egres-01-01,

AUTHOR	=	{Fleiner, Tam{\'a}s},
TITLE	=	{A fixed-point approach to stable matchings and some applications},
NOTE	=	{{\tt egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2001},
NUMBER	=	{TR-2001-01}

}