Pareto Optimal Matchings in Many-to-Many Markets with Ties

Katarína Cechlárová, Pavlos Eirinakis, Tamás Fleiner, Dimitrios Dimitrios Magos, David Manlove, Ioannis Mourtos, Eva Oceláková, Baharak Rastegari

Research output: Contribution to journalArticle (Academic Journal)peer-review

255 Downloads (Pure)

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 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.
Original languageEnglish
Pages (from-to)700-721
Number of pages22
JournalTheory of Computing Systems
Volume59
Issue number4
Early online date30 Apr 2016
DOIs
Publication statusPublished - 1 Nov 2016

Keywords

  • Many-to-many matching
  • Pareto optimality
  • Serial dictatorship
  • Truthfulness

Fingerprint Dive into the research topics of 'Pareto Optimal Matchings in Many-to-Many Markets with Ties'. Together they form a unique fingerprint.

Cite this