Popular edges and dominant matchings

Arbeitspapier

Given a bipartite graph G=(A B, E) with strict preference lists and given an edge e 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 M' such that the vertices that prefer M' to M outnumber those that prefer M to M'. 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 adominant 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 = |A| + |B|.

Angaben zum Objekt

• ISBN: 978-615-5457-15-9
• Sprache: Englisch

Verweise und Beziehungen

• Erschienen in: Series: IEHAS Discussion Papers ; No. MT-DP - 2017/25

Klassifikation und Themen

• Klassifikation: Wirtschaft ; Computational Techniques; Simulation Modeling ; Bargaining Theory; Matching Theory
• Thema: popular matching ; matching under preferences ; dominant matching

Beteiligte, Orts- und Zeitangaben

• Ereignis: Geistige Schöpfung
• (wer): Cseh, Ágnes ; Kavitha, Telikepalli
• Ereignis: Veröffentlichung
• (wer): Hungarian Academy of Sciences, Institute of Economics
• (wo): Budapest
• (wann): 2017

Weitere Informationen

• Handle: http://hdl.handle.net/10419/190486
• Letzte Aktualisierung: 10.03.2025, 11:43 MEZ