Counting houses of Pareto optimal matchings in the house allocation problem

DOI10.1016/J.DISC.2016.05.027zbMATH Open1401.91453arXiv1401.5354OpenAlexW2962773501MaRDI QIDQ738845FDOQ738845

Authors: Andrei Asinowski, Balázs Keszegh, Tillmann Miltzow 

Publication date: 16 August 2016

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: Let $A,B$ with $|A|=m$ and $|B|=ngem$ be two sets. We assume that every element $ainA$ has a reference list over all elements from $B$. We call an injective mapping $au$ from $A$ to $B$ a matching. A blocking coalition of $au$ is a subset $A^{\prime }$ of $A$ such that there exists a matching $a{u}^{\prime }$ that differs from $au$ only on elements of $A^{\prime }$, and every element of $A^{\prime }$ improves in $a{u}^{\prime }$, compared to $au$ according to its preference list. If there exists no blocking coalition, we call the matching $au$ an exchange stable matching (ESM). An element $binB$ is reachable if there exists an exchange stable matching using $b$. The set of all reachable elements is denoted by $E^{*}$. We show [|E^*| leq sum_{i = 1,ldots, m}{leftlfloorfrac{m}{i} ight floor} = Theta(mlog m).] This is asymptotically tight. A set $EsubseteqB$ is reachable (respectively exactly reachable) if there exists an exchange stable matching $au$ whose image contains $E$ as a subset (respectively equals $E$). We give bounds for the number of exactly reachable sets. We find that our results hold in the more general setting of multi-matchings, when each element $a$ of $A$ is matched with $el{l}_a$ elements of $B$ instead of just one. Further, we give complexity results and algorithms for corresponding algorithmic questions. Finally, we characterize unavoidable elements, i.e., elements of $B$ that are used by all ESM's. This yields efficient algorithms to determine all unavoidable elements.

Full work available at URL: https://arxiv.org/abs/1401.5354

Recommendations

• Counting houses of Pareto optimal matchings in the house allocation problem
• Algorithms and Computation
• Algorithms and Computation
• Set systems related to a house allocation problem
• Pareto optimality in many-to-many matching problems

zbMATH Keywords

combinatoricsalgorithmcomplexitycounting problemallocation problemPareto optimal matching

Mathematics Subject Classification ID

Multi-objective and goal programming (90C29) Matching models (91B68)

Cites Work

• Algorithmic Game Theory
• Computational Complexity
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• College Admissions and the Stability of Marriage
• Complexity of generalized satisfiability counting problems
• Queue allocation of indivisible goods
• Algorithmics of matching under preferences. With a foreword by Kurt Mehlhorn
• The complexity of counting colourings and independent sets in sparse graphs and hypergraphs
• The computational complexity of random serial dictatorship
• Parametrized algorithms for random serial dictatorship
• Pareto optimality in many-to-many matching problems
• Minimum Partial-Matching and Hausdorff RMS-Distance under Translation: Combinatorics and Algorithms
• The Complexity of Computing the Random Priority Allocation Matrix
• Algorithms and Computation

Cited In (4)

• Partial-matching RMS distance under translation: combinatorics and algorithms
• Algorithms and Computation
• Set systems related to a house allocation problem
• Algorithms and Computation

This page was built for publication: Counting houses of Pareto optimal matchings in the house allocation problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q738845)