Please use this identifier to cite or link to this item: http://hdl.handle.net/10419/222072
Authors: 
Cseh, Ágnes
Faenza, Yuri
Kavitha, Telikepalli
Powers, Vladlena
Year of Publication: 
2020
Series/Report no.: 
CERS-IE Working Papers No. CERS-IE WP - 2020/3
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 G is popular in the marriage instance if M does not lose a head-to-head election against any matching 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 the set of dominant matchings. A popular matching M is dominant if M wins the head-to-head election against any larger matching. Thus every dominant matching is a max-size popular matching and it is known that the set of dominant matchings is the linear image of the set of stable matchings in an auxiliary graph. Results from the literature seem to suggest that stable and dominant matchings behave, from a complexity theory point of view, in a very similar manner within the class of popular matchings.
Subjects: 
popular matching
NP-completeness
polynomial algorithm
stable matching
JEL: 
C63
C78
Document Type: 
Working Paper

Files in This Item:
File
Size
736.83 kB





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.