Counting houses of Pareto optimal matchings in the house allocation problem

详细信息    查看全文

• 作者：Andrei Asinowski^a ; ¹ ; ^{asinowski@fu-berlin.de" class="auth_mail" title="E-mail the corresponding author} ; ^{andrei.asinowski@tuwien.ac.at" class="auth_mail" title="E-mail the corresponding author} ; Balá ; zs Keszegh^b ; ^{keszegh@renyi.hu" class="auth_mail" title="E-mail the corresponding author} ; Tillmann Miltzow^a ; ^{t.m@fu-berlin.de" class="auth_mail" title="E-mail the corresponding author} ; ^{t.miltzow@gmail.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Pareto optimal matching ; Allocation problem ; Complexity ; Algorithm ; Combinatorics ; Counting problem
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 December 2016
• 年：2016
• 卷：339
• 期：12
• 页码：2919-2932
• 全文大小：511 K

文摘

In an instance of the house allocation problem, two sets A$A$ and B$B$ are given. The set A$A$ is referred to as applicants   and the set B$B$ is referred to as houses  . We denote by m$m$ and n$n$ the size of A$A$ and B$B$, respectively. In the house allocation problem, we assume that every applicant  a∈A$a\in A$ has a preference list over the set of houses B$B$. We call an injective mapping τ$\tau$ from A$A$ to B$B$ a matching. A blocking coalition   of τ$\tau$ is a non-empty subset A^′$A^{\prime }$ of A$A$ such that there exists a matching τ^′${\tau }^{\prime }$ that differs from τ$\tau$ only on elements of A^′$A^{\prime }$, and every element of A^′$A^{\prime }$ improves in τ^′${\tau }^{\prime }$, compared to τ$\tau$, according to its preference list. If there exists no blocking coalition, we call the matching τ$\tau$ a Pareto optimal matching (POM).

A house b∈B$b\in B$ is reachable   if there exists a Pareto optimal matching using b$b$. The set of all reachable houses is denoted by E^∗$E^{\ast }$. We show

This is asymptotically tight. A set E⊆B$E\subseteq B$ is reachable (respectively exactly reachable  ) if there exists a Pareto optimal matching τ$\tau$ whose image contains E$E$ as a subset (respectively equals E$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 applicant a$a$ of A$A$ is matched with ℓ_a${\ell }_a$ elements of B$B$ instead of just one. Furthermore, we give complexity results and algorithms for corresponding algorithmic questions. Finally, we characterize unavoidable houses, i.e., houses that are used by all POMs. We obtain efficient algorithms to determine all unavoidable elements.