Random Paths to Popularity in Two-Sided Matching
Aleksei Kondratev () and
Alexander Nesterov
HSE Working papers from National Research University Higher School of Economics
Abstract:
We study practically relevant aspects of popularity in two-sided matching where only one side has preferences. A matching is called popular if there does not exist another matching that is preferred by a simple majority. We show that for a matching to be popular it is necessary and sucient that no coalition of size up to 3 decides to exchange their houses by simple majority.We then constructively show that a market where such coalitions meet at random converges to a popular matching whenever it exists.
Keywords: two-sided matching; popular matching; random paths; house allocation; assignment problem (search for similar items in EconPapers)
JEL-codes: Z (search for similar items in EconPapers)
Pages: 15 pages
Date: 2018
New Economics Papers: this item is included in nep-des, nep-mic and nep-pay
References: View references in EconPapers View complete reference list from CitEc
Citations:
Published in WP BRP Series: Economics / EC, July 2018, pages 1-15
Downloads: (external link)
https://wp.hse.ru/data/2018/07/05/1153007669/195EC2018.pdf (application/pdf)
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:hig:wpaper:195/ec/2018
Access Statistics for this paper
More papers in HSE Working papers from National Research University Higher School of Economics
Bibliographic data for series maintained by Shamil Abdulaev () and Shamil Abdulaev ().