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

Algorithms

Tamás Fleiner¹ 

[1] Department of Computer Science and Information Theory, Budapest University of Technology and Economics, Magyar tudósok körútja 2., Budapest 1117, Hungary; E-Mail:

关键词: stable matchings;    college admission;    choice function;    lattice;   

DOI  :  10.3390/a7010032

来源: mdpi

【 摘 要 】

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 practical, interesting examples, where non-path independent choice functions play a role, and proves various stability-related results.

【 授权许可】

CC BY   
© 2014 by the authors; licensee MDPI, Basel, Switzerland.