TR-2002-08

Some results on stable matchings and fixed points

Tamás Fleiner



Abstract

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 www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2002},
NUMBER = {TR-2002-08}
}


Last modification: 21.9.2017. Please email your comments to Tamás Király!