Random paths to pairwise stability in many-to-many matching problems: a study on market equilibration (Q2482665)

A decentralized process in many-to-many matching problems is studied. The pairwise stability of the process (based on the notions and results by Roth and Sotomayor) is studied. The main result of the paper is the following: if we assume that every agent on one side of the market has substitutable preferences, and every agent on the other side has responsive preferences with quota, then there exists a sequence of matchings \(\left\{\mu_t\right\}_{t=0}^{T}\) with \(\mu_{0}\) being a pairwise unstable matching and \(\mu_{T}\) being pairwise-stable, and for all \(t\in \{0, 1, \ldots, T - 1\}\) \(\mu_{t+1}\) is obtained from \(\mu_{t}\) by satisfying a blocking individual or a blocking pair. This implies that an associated stochastic process converges to a pairwise-stable matching in finite time with probability one, if each blocking individual or pair is satisfied with positive probability at each period along the process.