Abstract

Let A,BA,B with ∣A∣=m|A| = m and ∣B∣=n≥m|B| = n\ge m be two sets. We assume that every element a∈Aa\in A has a reference list over all elements from BB. We call an injective mapping ττ from AA to BB a matching. A blocking coalition of ττ is a 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 ττ an exchange stable matching (ESM). An element b∈Bb\in B is reachable if there exists an exchange stable matching using bb. The set of all reachable elements is denoted by E∗E^*. We show ∣E∗∣≤∑i=1,…,m⌊mi⌋=Θ(mlog⁡m).|E^*| \leq \sum_{i = 1,\ldots, m}{\left\lfloor\frac{m}{i}\right\rfloor} = Θ(m\log m). This is asymptotically tight. A set E⊆BE\subseteq B is reachable (respectively exactly reachable) if there exists an exchange stable 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 element aa of AA is matched with ℓa\ell_a elements of BB instead of just one. Further, we give complexity results and algorithms for corresponding algorithmic questions. Finally, we characterize unavoidable elements, i.e., elements of BB that are used by all ESM's. This yields efficient algorithms to determine all unavoidable elements.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.