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 $tau$ from $A$ to $B$, and $tau$ is strictly better than another house allocation $tau eq tau$ if for every buyer $i$, $tau(i)$ does not come before $tau(i)$ in the preference list of $i$. A house allocation is Pareto optimal if there is no strictly better house allocation. Let $s(tau)$ be the image of $tau$ (i.e., the set of houses sold in the house allocation $tau$). We are interested in the largest possible cardinality $f(m)$ of the family of sets $s(tau)$ for Pareto optimal mappings $tau$ 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.
Download