TR-2013-10

Choice Function Based Two-Sided Markets: Stability, Lattice Property, Path Independence and Algorithms

Tamás Fleiner, Zsuzsanna Jankó

Published in:
Algorithms 2014, 7(1), 32-59. DOI link

We build an abstract model, closely related to the stable marriage problem and motivated by Hungarian college admissions. We study different stability notions and show that an extension of the lattice property of stable marriages holds in these more general settings, even if the choice function on one side is not path independent. We lean on Tarski's fixed point theorem and the substitutability property of choice functions. The main virtue of the work is that it exhibits practically interesting examples where not path independent choice functions play a role and proves various stability-related results.

Bibtex entry:

@techreport{egres-13-10,

AUTHOR	=	{Fleiner, Tam{\'a}s and Jank{\'o}, Zsuzsanna},
TITLE	=	{Choice Function Based Two-Sided Markets: Stability, Lattice Property, Path Independence and Algorithms},
NOTE	=	{{\tt egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2013},
NUMBER	=	{TR-2013-10}

}