Popular Edges and Dominant Matchings

Agnes Cseh () 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
Telikepalli Kavitha: Tata Institute of Fundamental Research, Mumbai, India

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

Abstract: Abstract Given a bipartite graph G=(A[B;E) with strict preference lists and given an edge e 2 E, we ask if there exists a popular matching in G that contains e. We call this the popular edge problem. A matching M is popular if there is no matching M0 such that the vertices that preferM0 toM outnumber those that preferM toM0. It is known that every stable matching is popular; however G may have no stable matching with the edge e. In this paper we identify another natural subclass of popular matchings called “dominant matchings” and show that if there is a popular matching that contains the edge e, then there is either a stable matching that contains e or a dominant matching that contains e. This allows us to design a linear time algorithm for identifying the set of popular edges. When preference lists are complete, we show an O(n3) algorithm to find a popular matching containing a given set of edges or report that none exists, where n = jAj+jBj.

Keywords: popular matching; matching under preferences; dominant matching (search for similar items in EconPapers)
JEL-codes: C63 C78 (search for similar items in EconPapers)
Pages: 24 pages
Date: 2017-09
New Economics Papers: this item is included in nep-des and nep-gth
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://econ.core.hu/file/download/mtdp/MTDP1725.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:1725

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