Random paths to \(P\)-stability in the roommate problem (Q2482678)

The authors consider roommate problems with strict preferences \((N,(\succ_{x})_{x\in N})\), where \(N\) is a finite set of agents and for each agent \(x\in N\), \(\succ_{x}\) is a strict preference relation defined over \(N\). A matching \(\mu\) is a one to one mapping from \(N\) onto itself such that for all \(x,y\in N\) if \(\mu(x)=y\), then \(\mu(y)=x\). A pair of agents \(\{x,y\}\subset N\) blocks the matching \(\mu\) if \(y\succ_{x}\mu(x)\) and \(x\succ_{y}\mu(y)\). The authors define some specific matchings called \(P\)-stable matching associated with stable partition, which is a partition of the agents into ordered sets satisfying a notion of stability between sets and also within each set. It is proved following result. Let \((N,(\succ_{x})_{x\in N})\) be a roommate problem. Then, for any matching \(\mu\), there exists a finite sequence of matchings \((\mu=\mu_0,\mu_1,\ldots,\mu_{m}=\bar\mu)\) such that for all \(i\in\{1,\ldots,m\}\), \(\mu_{i}\) is obtained from \(\mu_{i-1}\) by satisfying a blocking pair of \(\mu_{i-1}\) and \(\bar\mu\) is a \(P\)-stable matching for some stable partition \(P\).