Skip to main navigation Skip to search Skip to main content

Set systems related to a house allocation problem

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

Research output: Contribution to journal › Article › peer-review

Abstract

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.

Original languageEnglish (US)
Article number111886
JournalDiscrete Mathematics
Volume343
Issue number7
DOIs
StatePublished - Jul 2020
Externally publishedYes

Keywords

  • Disjointly representable
  • Pareto optimal matching
  • Set pairs
  • Set system

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Set systems related to a house allocation problem'. Together they form a unique fingerprint.

Cite this