Popular matchings in complete graphs

Arbeitspapier

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.

Angaben zum Objekt

• Sprache: Englisch

Verweise und Beziehungen

• Erschienen in: Series: CERS-IE Working Papers ; No. CERS-IE WP - 2020/4

Klassifikation und Themen

• Klassifikation: Wirtschaft ; Computational Techniques; Simulation Modeling ; Bargaining Theory; Matching Theory
• Thema: popular matching ; NP-completeness ; polynomial algorithm ; stable 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, Centre for Economic and Regional Studies
• (wo): Budapest
• (wann): 2020

Weitere Informationen

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