TY - JOUR
T1 - Set systems related to a house allocation problem
AU - Gerbner, Dániel
AU - Keszegh, Balázs
AU - Methuku, Abhishek
AU - Nagy, Dániel T.
AU - Patkós, Balázs
AU - Tompkins, Casey
AU - Xiao, Chuanqi
N1 - We thank the anonymous referee for their remarks which improved the presentation of the paper. The results presented in this note were obtained during the 9th Emléktábla Workshop, in Gárdony, June 2019. The research was supported by the National Research, Development and Innovation Office NKFIH, Hungary under the grants FK132060 , K116769 , K132696 , KH130371 and SNN 129364 . The research of Gerbner was supported by the János Bolyai Research Fellowship, Hungary . The research of Keszegh was supported by the Lendület program of the Hungarian Academy of Sciences (MTA) , under the grant LP2017-19/2017 . The research of Methuku and Tompkins was supported by the grant IBS-R029-C1 from the Institute for Basic Science (IBS) .
We thank the anonymous referee for their remarks which improved the presentation of the paper. The results presented in this note were obtained during the 9th Eml?kt?bla Workshop, in G?rdony, June 2019. The research was supported by the National Research, Development and Innovation Office NKFIH, Hungary under the grants FK132060, K116769, K132696, KH130371 and SNN 129364. The research of Gerbner was supported by the J?nos Bolyai Research Fellowship, Hungary. The research of Keszegh was supported by the Lend?let program of the Hungarian Academy of Sciences (MTA), under the grant LP2017-19/2017. The research of Methuku and Tompkins was supported by the grant IBS-R029-C1 from the Institute for Basic Science (IBS).
PY - 2020/7
Y1 - 2020/7
N2 - 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.
AB - 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.
KW - Disjointly representable
KW - Pareto optimal matching
KW - Set pairs
KW - Set system
UR - https://www.scopus.com/pages/publications/85081545923
UR - https://www.scopus.com/pages/publications/85081545923#tab=citedBy
U2 - 10.1016/j.disc.2020.111886
DO - 10.1016/j.disc.2020.111886
M3 - Article
AN - SCOPUS:85081545923
SN - 0012-365X
VL - 343
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 7
M1 - 111886
ER -