KIT | KIT-Bibliothek | Impressum | Datenschutz

Set systems related to a house allocation problem

Gerbner, Dániel; Keszegh, Balázs; Methuku, Abhishek; Nagy, Dániel T.; Patkós, Balázs; Tompkins, Casey; Xiao, Chuanqi


We are given a set A of buyers, a set B of houses, and for each buyer a preference list, i.e., an ordering of the houses. A house allocation is an injective mapping τ from A to B, and τ is strictly better than another house allocation τ′≠τ if for every buyer i, τ′(i) does not come before τ(i) in the preference list of i. A house allocation is Pareto optimal if there is no strictly better house allocation.
Let s(τ) be the image of τ (i.e., the set of houses sold in the house allocation τ). We are interested in the largest possible cardinality f(m) of the family of sets s(τ) for Pareto optimal mappings τ taken over all sets of preference lists of m buyers. We improve the earlier upper bound on f(m) given by Asinowski, Keszegh and Miltzow by making a connection between this problem and some problems in extremal set theory.

Zugehörige Institution(en) am KIT Institut für Algebra und Geometrie (IAG)
Publikationstyp Forschungsbericht/Preprint
Publikationsmonat/-jahr 07.2020
Sprache Englisch
Identifikator KITopen-ID: 1000124780
Nachgewiesen in arXiv
Relationen in KITopen
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page