TR-2002-08

Some results on stable matchings and fixed points

Tamás Fleiner

In this survey paper, we explain some interconnections between fixed point theorems and the theory of stable matchings. Namely, we relate the bipartite matching problems to the Knaster-Tarski fixed point theorem and the nonbipartite ones to the Kakutani fixed point theorem. We study the natural lattice structure of stable matchings, and deduce some consequences of it, like linear characterizations of stable matching related polyhedra.

Keywords:
stable marriages, lattices, matroids, polyhedra

Bibtex entry:

@techreport{egres-02-08,

AUTHOR	=	{Fleiner, Tam{\'a}s},
TITLE	=	{Some results on stable matchings and fixed points},
NOTE	=	{{\tt egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2002},
NUMBER	=	{TR-2002-08}

}