LAUSR

The deferred acceptance algorithm introduced by Gale and Shapley is a centralized algorithm, where a social planner solicits the preferences from two sides of a market and generates a stable matching. On the other hand, the algorithm proposed by Knuth is a decentralized algorithm. In this article, we discuss conditions leading to the convergence of Knuth’s decentralized algorithm. In particular, we show that Knuth’s decentralized algorithm converges to a stable matching if either the Sequential Preference Condition (SPC) holds or if the market admits no cycle. In fact, acyclicity turns out to be a special case of SPC. We then consider markets where agents may prefer to remain single rather than being matched with someone. We introduce a generalized version of SPC for such markets. Under this notion of generalized SPC, we show that the market admits a unique stable matching, and that Knuth’s decentralized algorithm converges. The generalized SPC seems to be the most general condition available in the literature for uniqueness in two-sided matching markets.