Three remarks on the many-to-many stable matching problem (Q1303882): Difference between revisions

In general, in a matching problem, we have two sets of agents \(P\) and \(Q\) and we must connect some agents \(p\in P\) with some agents \(q\in Q\). For each agent \(p\in P\) and for each agent \(q\in Q\), we are given a quota -- the largest possible number \(n(p)\) (corr., \(n(q)\)) of its connections, and a preference, i.e., an ordering (in general, partial ordering) on the set of all possible connecting sets (i.e., subsets \(C\subseteq Q\) of cardinality \(\leq n(P)\)). We want to find a stable matching, i.e., a matching for which no party can improve its situation by violating it. There are several known notions of stability; they are usually defined via defining the corresponding instability. For example, pairwise instability means that some pair \((p,q)\) can improve their situations if they become partners (and maybe drop some of their original partners); pairwise stability means that no such pairs exist. Corewise instability means that there is a set of agents \(A\subset P\cup Q\) such that all agents from \(A\) can improve their status by adding new connections between themselves -- and dropping all partners who are not from \(A\). The author introduces a new natural notion of setwise stability: a matching is called setwise unstable is there exists a subset \(A\subset P\cup Q\) such that all agents from \(A\) can improve their status by adding new connections between themselves -- and maybe dropping some partners who are not from \(A\). (A similar notion was previously introduced for the marriage problem, when all quotas are equal to 1.) Clearly, setwise stability implies pairwise and corewise stability. The author shows that setwise stability is stronger by giving an example of a matching which is pairwise and corewise stable but not setwise stable. In another example of a matching problem, there exist a pairwise-stable matching and a corewise-stable matching, but no matching is both pairwise- and corewise-stable, and thus, no matching is setwise-stable. In addition, the author uses his techniques to prove a new result about the existence of pairwise-stable matchings.