Set systems related to a house allocation problem

Gerbner, Dániel and Keszegh, Balázs and Methuku, Abhishek and Nagy, Dániel and Patkós, Balázs and Tompkins, Casey (2020) Set systems related to a house allocation problem. DISCRETE MATHEMATICS, 343 (7). ISSN 0012-365X

Preview

Text 1910.pdf Available under License Creative Commons Attribution. Download (129kB) | Preview

Abstract

We are given a set of buyers, a set of houses, and for each buyer a preference list, i.e., an ordering of the houses. A house allocation is an injective mapping from to , and is strictly better than another house allocation if for every buyer , does not come before in the preference list of . A house allocation is Pareto optimal if there is no strictly better house allocation. Let be the image of i.e., the set of houses sold in the house allocation . We are interested in the largest possible cardinality of the family of sets for Pareto optimal mappings taken over all sets of preference lists of buyers and all sets of houses. This maximum exists since in a Pareto optimal mapping with buyers, each buyer will always be assigned one of their top choices. We improve the earlier upper bound on given by Asinowski et al. (2016), by making a connection between this problem and some problems in extremal set theory.

Actions (login required)

Edit Item