Counting houses of Pareto optimal matchings in the house allocation problem

DOI10.1016/J.DISC.2016.05.027MaRDI QIDQ738845zbMATHOpenAlexFDO

Authors Andrei Asinowski, Balázs Keszegh, Tillmann Miltzow

Publication date 16 August 2016

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

combinatoricsalgorithmcomplexitycounting problemallocation problemPareto optimal matching

Mathematics Subject Classification ID

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

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^{\ast }$. 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.

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

Cites work

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

Cited in

(5)

• Counting houses of Pareto optimal matchings in the house allocation problem
• Algorithms and Computation
• Partial-matching RMS distance under translation: combinatorics and algorithms
• Algorithms and Computation
• Set systems related to a house allocation problem

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)