Pareto optimal matchings in many-to-many markets with ties

DOI10.1007/978-3-662-48433-3_3MaRDI QIDQ3449579zbMATH OpenOpenAlexFDO

Authors Katarina Cechlárová, Pavlos Eirinakis, Tamás Fleiner, Dimitrios Magos, David F. Manlove, Ioannis Mourtos, Eva Oceľáková, Baharak Rastegari

Publication date 4 November 2015

Published in Algorithmic Game Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.02866, https://research-information.bris.ac.uk/ws/files/116527287/Full_text_PDF_final_published_version_.pdf

zbMATH Keywords

Pareto optimalitymany-to-many matchingserial dictatorshiptruthfulness

Mathematics Subject Classification ID

Multi-objective and goal programming (90C29) Matching models (91B68)

Abstract: We consider Pareto-optimal matchings (POMs) in a many-to-many market of applicants and courses where applicants have preferences, which may include ties, over individual courses and lexicographic preferences over sets of courses. Since this is the most general setting examined so far in the literature, our work unifies and generalizes several known results. Specifically, we characterize POMs and introduce the emph{Generalized Serial Dictatorship Mechanism with Ties (GSDT)} that effectively handles ties via properties of network flows. We show that GSDT can generate all POMs using different priority orderings over the applicants, but it satisfies truthfulness only for certain such orderings. This shortcoming is not specific to our mechanism; we show that any mechanism generating all POMs in our setting is prone to strategic manipulation. This is in contrast to the one-to-one case (with or without ties), for which truthful mechanisms generating all POMs do exist.

Recommendations

• Pareto optimal matchings in many-to-many markets with ties
• Pareto optimality in many-to-many matching problems
• Pareto optimal matchings with lower quotas
• Pareto stable matchings under one-sided matroid constraints
• On computing Pareto stable assignments

Cites work

• A complexity approach for core-selecting exchange under conditionally lexicographic preferences
• A new solution to the random assignment problem.
• Algorithmics of matching under preferences. With a foreword by Kurt Mehlhorn
• Algorithms and Computation
• Assignment Problem Based on Ordinal Preferences
• Network flows. Theory, algorithms, and applications.
• Pareto optimal matchings in many-to-many markets with ties
• Pareto optimality in coalition formation
• Pareto optimality in many-to-many matching problems
• Queue allocation of indivisible goods
• Random Matching Under Dichotomous Preferences
• Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems
• Strategy-proofness, solidarity, and consistency for multiple assignment problems
• The Impossibility of Bayesian Group Decision Making with Separate Aggregation of Beliefs and Values

Cited in

(7)

• Efficient reallocation under additive and responsive preferences
• Matching with indifferences: a comparison of algorithms in the context of course allocation
• Pareto optimality in many-to-many matching problems
• Pareto optimal matchings with lower quotas
• Serial dictatorship vs. Nash in assessing Pareto optimality in many-to-many matchings with an application in water management
• Pareto optimal matchings in many-to-many markets with ties
• Pareto optimal matchings of students to courses in the presence of prerequisites

This page was built for publication: Pareto optimal matchings in many-to-many markets with ties

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3449579)