Popular matchings with two-sided preferences and one-sided ties

Agnes Cseh (), Chien-Chung Huang () and Telikepalli Kavitha ()
Additional contact information
Agnes Cseh: Institute of Economics, Research Centre for Economic and Regional Studies, Hungarian Academy of Sciences, and Corvinus University of Budapest
Chien-Chung Huang: Ecole Normale Superieure, Paris, France
Telikepalli Kavitha: Tata Institute of Fundamental Research, Mumbai, India

No 1723, CERS-IE WORKING PAPERS from Institute of Economics, Centre for Economic and Regional Studies

Abstract: We are given a bipartite graph G = (A[B;E) where each vertex has a preference list ranking its neighbors: in particular, every a 2 A ranks its neighbors in a strict order of preference, whereas the preference list of any b 2 B may contain ties. A matching M is popular if there is no matching M0 such that the number of vertices that prefer M0 to M exceeds the number of vertices that prefer M to M0. We show that the problem of deciding whether G admits a popular matching or not is NP-hard. This is the case even when every b 2 B either has a strict preference list or puts all its neighbors into a single tie. In contrast, we show that the problem becomes polynomially solvable in the case when each b 2 B puts all its neighbors into a single tie. That is, all neighbors of b are tied in b's list and b desires to be matched to any of them. Our main result is an O(n2) algorithm (where n = jA [ Bj) for the popular matching problem in this model. Note that this model is quite di erent from the model where vertices in B have no preferences and do not care whether they are matched or not.

Keywords: popular matching; NP-complete; polynomial algorithm; ties (search for similar items in EconPapers)
JEL-codes: C63 C78 (search for similar items in EconPapers)
Pages: 30 pages
Date: 2017-09
New Economics Papers: this item is included in nep-gth
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://econ.core.hu/file/download/mtdp/MTDP1723.pdf (application/pdf)
Our link check indicates that this URL is bad, the error code is: 500 Can't connect to econ.core.hu:80 (A connection attempt failed because the connected party did not properly respond after a period of time, or established connection failed because connected host has failed to respond.)

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:has:discpr:1723

Access Statistics for this paper

More papers in CERS-IE WORKING PAPERS from Institute of Economics, Centre for Economic and Regional Studies Contact information at EDIRC.
Bibliographic data for series maintained by Nora Horvath ( this e-mail address is bad, please contact ).