Please use this identifier to cite or link to this item:
Cseh, Ágnes
Faenza, Yuri
Kavitha, Telikepalli
Powers, Vladlena
Year of Publication: 
Series/Report no.: 
CERS-IE Working Papers No. CERS-IE WP - 2020/3
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.
popular matching
polynomial algorithm
stable matching
Document Type: 
Working Paper

Files in This Item:
736.83 kB

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