Popular matchings with two-sided preferences and one-sided ties

Arbeitspapier

We are given a bipartite graph G = (A B;E) where each vertex has a preference list ranking its neighbors: in particular, every a A ranks its neighbors in a strict order of preference, whereas the preference list of any b B may contain ties. A matching M is popular if there is no matching M' such that the number of vertices that prefer M' to M exceeds the number of vertices that prefer M to M'. We show that the problem of deciding whether G admits a popular matching or not is NP-hard. This is the case even when every b B either has a strict preference list or puts all its neighbors into a single tie. In contrast, we show that the problem becomes polynomially solvable in the case when each b B puts all its neighbors into a single tie. That is, all neighbors of b are tied in b's list and b desires to be matched to any of them. Our main result is an O(n2) algorithm (where n = |A B|) for the popular matching problem in this model. Note that this model is quite different from the model where vertices in B have no preferences and do not care whether they are matched or not.

Angaben zum Objekt

• ISBN: 978-615-5457-13-5
• Sprache: Englisch

Verweise und Beziehungen

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

Klassifikation und Themen

• Klassifikation: Wirtschaft ; Computational Techniques; Simulation Modeling ; Bargaining Theory; Matching Theory
• Thema: popular matching ; NP-complete ; polynomial algorithm ; ties

Beteiligte, Orts- und Zeitangaben

• Ereignis: Geistige Schöpfung
• (wer): Cseh, Ágnes ; Huang, Chien-Chung ; 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/190484
• Letzte Aktualisierung: 10.03.2025, 11:43 MEZ