Pareto optimal matchings in many-to-many markets with ties
From MaRDI portal
Publication:3449579
DOI10.1007/978-3-662-48433-3_3zbMATH Open1358.91076arXiv1507.02866OpenAlexW2732258362MaRDI QIDQ3449579FDOQ3449579
Ioannis Mourtos, Pavlos Eirinakis, Eva Oceľáková, Tamás Fleiner, Dimitrios Magos, Katarina Cechlárová, Baharak Rastegari, David F. Manlove
Publication date: 4 November 2015
Published in: Algorithmic Game Theory (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1507.02866
Recommendations
Cites Work
- Title not available (Why is that?)
- The Impossibility of Bayesian Group Decision Making with Separate Aggregation of Beliefs and Values
- Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems
- Algorithms and Computation
- A new solution to the random assignment problem.
- Queue allocation of indivisible goods
- Algorithmics of Matching Under Preferences
- Random Matching Under Dichotomous Preferences
- Strategy-proofness, solidarity, and consistency for multiple assignment problems
- Pareto optimality in many-to-many matching problems
- Assignment Problem Based on Ordinal Preferences
- A Complexity Approach for Core-Selecting Exchange under Conditionally Lexicographic Preferences
- Pareto optimal matchings in many-to-many markets with ties
- Pareto optimality in coalition formation
Cited In (4)
- Efficient reallocation under additive and responsive preferences
- Matching with indifferences: a comparison of algorithms in the context of course allocation
- 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
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)
