Three remarks on the many-to-many stable matching problem
type: Item
instance of: scholarly article
title: Three remarks on the many-to-many stable matching problem
zbMATH Open document ID: 0951.91045
DOI: 10.1016/S0165-4896(98)00048-1
author: Marilda Sotomayor
published in: Mathematical Social Sciences
publication date: 2000-12-17T00:00:00Z
review text: 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. …
Mathematics Subject Classification ID: 91B68
Mathematics Subject Classification ID: 91A12
zbMATH DE Number: 1339476
zbMATH Keywords: matching
zbMATH Keywords: stable matching
zbMATH Keywords: core
reviewed by: Olga Kosheleva
MaRDI profile type: Publication
cites work: Nonexistence of stable threesome matchings
cites work: The Lattice Structure of the Set of Stable Matchings with Multiple Partners
cites work: College Admissions and the Stability of Marriage
cites work: Job Matching, Coalition Formation, and Gross Substitutes
cites work: Stability and Polarization of Interests in Job Matching
cites work: The college admissions problem is not equivalent to the marriage problem
cites work: Q3999327
cites work: A nonconstructive elementary proof of the existence of stable marriages
cites work: The lattice structure of the set of stable outcomes of the multiple partners assignment game
full work available at URL: s0165-4896(98)00048-1
OpenAlex ID: W2070749268
description: scientific article; zbMATH DE number 1339476