Popular Matchings in Complete Graphs

Agnes Cseh () and Telikepalli Kavitha ()
Additional contact information
Agnes Cseh: Centre for Economic and Regional Studies, Institute of Economics
Telikepalli Kavitha: Tata Institute of Fundamental Research, Mumbai, India

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

Abstract: Our input is a complete graph G on n vertices where each vertex has a strictranking of all other vertices in G. The goal is to construct a matching in G that is “globallystable” or popular. A matching M is popular if M does not lose a head-to-head election againstany matching M’: here each vertex casts a vote forthe matching in {M,M’} in which it gets abetter assignment. Popular matchings need not exist in the given instance G and the popularmatching problem is to decide whether one exists or not. The popular matching problem in Gis easy to solve for odd n. Surprisingly, the problem becomes NP-hard for even n, as we showhere. This seems to be the first graph theoretic problem that is efficiently solvable when n hasone parity and NP-hard when n has the other parity.

Keywords: popularmatching; NP-completeness; polynomial algorithm; stable matching (search for similar items in EconPapers)
JEL-codes: C63 C78 (search for similar items in EconPapers)
Pages: 22 pages
Date: 2020-04
New Economics Papers: this item is included in nep-des
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mtakti.hu/wp-content/uploads/2020/01/CERSIEWP202004.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:has:discpr:2004

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