Set systems related to a house allocation problem

Abstract

© 2020 Elsevier B.V. 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 and all sets of houses. This maximum exists since in a Pareto optimal mapping with m buyers, each buyer will always be assigned one of their top m choices. We improve the earlier upper bound on f(m) given by Asinowski et al. (2016), by making a connection between this problem and some problems in extremal set theory