Analysis of stochastic matching markets (Q378330)

This paper deals with analysis of stochastic matching markets. Firstly the authors study the convergence to stability. It is shown that starting from an arbitrary matching of a solvable stable roommates (SR) instance one can always find a stable matching by successively satisfying blocking pairs; and that starting from an arbitrary matching of an instance of solvable or unsolvable SR one can always find an \(h\)-stable matching by successively satisfying blocking pairs. The proposed proof gives upper bounds for the number of blocking pairs that need to be satisfied to obtain a stable (or \(h\)-stable) matching. Then the authors define the Stable Marriage and Stable Roommates Automata and demonstrate how the probabilistic model checker PRISM can be used to analyse and compare the performance of different instances. As an example, they study two well-known stable marriage instances and a stable roommates instance.