Counting houses of Pareto optimal matchings in the house allocation problem

In an instance of the house allocation problem, two sets AA and BB are given. The set AA is referred to as applicants   and the set BB is referred to as houses  . We denote by mm and nn the size of AA and BB, respectively. In the house allocation problem, we assume that every applicant  a∈Aa∈A has a preference list over the set of houses BB. We call an injective mapping ττ from AA to BB a matching. A blocking coalition   of ττ is a non-empty subset A′A′ of AA such that there exists a matching τ′τ′ that differs from ττ only on elements of A′A′, and every element of A′A′ improves in τ′τ′, compared to ττ, according to its preference list. If there exists no blocking coalition, we call the matching ττ a Pareto optimal matching (POM).A house b∈Bb∈B is reachable   if there exists a Pareto optimal matching using bb. The set of all reachable houses is denoted by E∗E∗. We show |E∗|≤∑i=1,…,m⌊mi⌋=Θ(mlogm). This is asymptotically tight. A set E⊆BE⊆B is reachable (respectively exactly reachable  ) if there exists a Pareto optimal matching ττ whose image contains EE as a subset (respectively equals EE). 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 aa of AA is matched with ℓaℓa elements of BB 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.