Paths to stability and uniqueness in two-sided matching markets
Vinay Ramani () and
K. S. Mallikarjuna Rao ()
Additional contact information
Vinay Ramani: Indian Institute of Management Udaipur, Mohanlal Sukhadia University Campus
K. S. Mallikarjuna Rao: Indian Institute of Technology Bombay
International Journal of Game Theory, 2018, vol. 47, issue 4, 1137-1150
Abstract 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.
Keywords: Two-sided matching markets; Stability; Uniqueness; Knuth’s decentralized algorithm (search for similar items in EconPapers)
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1) Track citations by RSS feed
Downloads: (external link)
http://link.springer.com/10.1007/s00182-017-0603-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
Persistent link: https://EconPapers.repec.org/RePEc:spr:jogath:v:47:y:2018:i:4:d:10.1007_s00182-017-0603-9
Ordering information: This journal article can be ordered from
http://www.springer. ... eory/journal/182/PS2
Access Statistics for this article
International Journal of Game Theory is currently edited by Shmuel Zamir, Vijay Krishna and Bernhard von Stengel
More articles in International Journal of Game Theory from Springer, Game Theory Society
Bibliographic data for series maintained by Sonal Shukla ().