Understanding popular matchings via stable matchings

Agnes Cseh (), Yuri Faenza (), Telikepalli Kavitha () and Vladlena Powers ()
Additional contact information
Agnes Cseh: Centre for Economic and Regional Studies, Institute of Economics
Yuri Faenza: IEOR, Columbia University, New York, USA
Telikepalli Kavitha: Tata Institute of Fundamental Research, Mumbai, India
Vladlena Powers: IEOR, Columbia University, New York, USA

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

Abstract: An instance of the marriage problem is given by a graph G together with, for each vertex of G, a strict preference order over its neighbors. A matching M of Gis popular in the marriage instance if M does not lose a head-to-head election against anymatching where vertices are voters. Every stable matching is a min-size popular matching; another subclass of popular matchings that always exist and can be easily computed is theset of dominant matchings. A popular matching M is dominant if M wins the head-to-headelection against any larger matching. Thus every dominant matching is a max-size popularmatching and it is known that the set of dominant matchings is the linear image of the set ofstable matchings in an auxiliary graph. Results from the literature seem to suggest that stableand dominant matchings behave, from a complexity theory point of view, in a very similarmanner within the class of popular matchings.The goal of this paper is to show that indeed there are differences in the tractability of stableand dominant matchings, and to investigate further their importance for popular matchings.First, we show that it is easy to check if all popular matchings are also stable, however it isco-NP-hard to check if all popular matchings are also dominant. Second, we show how somenew and recent hardness results on popular matching problems can be deduced from the NP-hardnessof certain problems on stable matchings, also studied in this paper, thus showing thatstable matchings can be employed not only to show positive results on popular matching (as isknown), but also most negative ones. Problems for which we show new hardness results includefinding a min-size (resp. max-size) popular matching that is not stable (resp. dominant). Aknown result for which we give a new and simple proof is the NP-hardness of finding a popularmatching when G is non-bipartite.

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: 28 pages
Date: 2020-01
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/CERSIEWP202003.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:2003

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