Three remarks on the many-to-many stable matching problem.

*(English)*Zbl 0951.91045In 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.

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.

Reviewer: O.M.Kosheleva (El Paso)

Full Text:
DOI

##### References:

[1] | Alkan, A., 1986. Nonexistence of stable threesome matchings, Mathematical Social Sciences 16, 207-209. · Zbl 0651.92025 |

[2] | Blair, C., 1988. The lattice structure of the set of stable matchings with multiple partners, Mathematics of Operation Research 13, 619-628. · Zbl 0664.90075 |

[3] | Gale, D., Shapley, L., 1962. College admissions and stability of marriage, American Mathematical Monthly 69, 9-15. · Zbl 0109.24403 |

[4] | Kelso, A.S., Crawford, V., 1982. Job matching, coalition formation and gross substitutes, Econometrica 50(6), 1483-1504. · Zbl 0503.90019 |

[5] | Roth, A., 1984. Stability and polarization of interest in job matching, Econometrica 53, 47-57. · Zbl 0526.90012 |

[6] | Roth, A., 1985. The College Admissions problem is not equivalent to the Marriage Problem, Journal of Economic Theory 36, 277-288. · Zbl 0594.90002 |

[7] | Roth, A., Sotomayor, M., 1990. Two-sided matching. A study in game theoretic modeling and analysis, Econometric Society Monograph Series, No. 18, Cambridge University Press. · Zbl 0726.90003 |

[8] | Sotomayor, M., 1992. The multiple partners game. In: Majumdar, M. (Ed.), Equilibrium and Dynamics: Essays in Honor of David Gale, Macmillan, pp. 322-336. |

[9] | Sotomayor, M., 1996. A non-constructive elementary proof of the existence of stable marriage, Games and Economic Behavior 13(1), 135-137. · Zbl 0853.90003 |

[10] | Sotomayor, M., 1998. The lattice structure of the set of stable outcomes of the Multiple Partners Assignment game, mimeo. · Zbl 0942.91008 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.