Аннотация:EMPIRICAL STUDIES OF TWO SIDED MATCHING have so far concentrated on markets in which certain kinds of market failures were addressed by resorting to centralized, deterministic matching procedures. Loosely speaking, the results of these studies are that those centralized procedures which achieved stable outcomes resolved the market failures, while those markets organized through procedures that yielded unstable outcomes continued to fail.2 So the market failures seem to be associated with instability of the outcomes. But many entry-level labor markets and other two-sided matching situations don't employ centralized matching procedures, and yet aren't observed to experience such failures. So we can conjecture that at least some of these markets may reach stable outcomes by means of decentralized decision making. And decentralized decision making in complex environments presumably introduces some randomness into what matchings are achieved. However, as far as we are aware, no nondeterministic models leading to stable outcomes have yet been studied. The present paper demonstrates that, starting from an arbitrary matching, the process of allowing randomly chosen blocking pairs to match will converge to a stable matching with probability one. (This resolves an open question raised by Knuth (1976), who showed that such a process may cycle.) Furthermore, every stable matching can arise
