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 ().