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, No 5, 1137-1150

Abstract: 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)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

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.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

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

DOI: 10.1007/s00182-017-0603-9

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 () and Springer Nature Abstracting and Indexing ().