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

doi:10.1007/s00224-016-9677-1

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

Department of Computer Science

Research output: Contribution to journal › Article (Academic Journal) › peer-review

307 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 language	English
Pages (from-to)	700-721
Number of pages	22
Journal	Theory of Computing Systems
Volume	59
Issue number	4
Early online date	30 Apr 2016
DOIs	https://doi.org/10.1007/s00224-016-9677-1
Publication status	Published - 1 Nov 2016

Keywords

Many-to-many matching
Pareto optimality
Serial dictatorship
Truthfulness

Access to Document

10.1007/s00224-016-9677-1

Full-text PDF (final published version)
This is the final published version of the article (version of record). It first appeared online via Springer at https://doi.org/10.1007/s00224-016-9677-1 . Please refer to any applicable terms of use of the publisher.
Final published version, 618 KBLicence: CC BY

Handle.net

Persistent link

Cite this

@article{ebbfa0fcc4d644eb88fa656d50c4bf17,

title = "Pareto Optimal Matchings in Many-to-Many Markets with Ties",

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.",

keywords = "Many-to-many matching, Pareto optimality, Serial dictatorship, Truthfulness",

author = "Katar{\'i}na Cechl{\'a}rov{\'a} and Pavlos Eirinakis and Tam{\'a}s Fleiner and {Dimitrios Magos}, Dimitrios and David Manlove and Ioannis Mourtos and Eva Ocel{\'a}kov{\'a} and Baharak Rastegari",

year = "2016",

month = nov,

day = "1",

doi = "10.1007/s00224-016-9677-1",

language = "English",

volume = "59",

pages = "700--721",

journal = "Theory of Computing Systems",

issn = "1432-4350",

publisher = "Springer Verlag",

number = "4",

}

TY - JOUR

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

AU - Cechlárová, Katarína

AU - Eirinakis, Pavlos

AU - Fleiner, Tamás

AU - Dimitrios Magos, Dimitrios

AU - Manlove, David

AU - Mourtos, Ioannis

AU - Oceláková, Eva

AU - Rastegari, Baharak

PY - 2016/11/1

Y1 - 2016/11/1

N2 - 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.

AB - 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.

KW - Many-to-many matching

KW - Pareto optimality

KW - Serial dictatorship

KW - Truthfulness

U2 - 10.1007/s00224-016-9677-1

DO - 10.1007/s00224-016-9677-1

M3 - Article (Academic Journal)

SN - 1432-4350

VL - 59

SP - 700

EP - 721

JO - Theory of Computing Systems

JF - Theory of Computing Systems

IS - 4

ER -

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

Abstract

Keywords

Access to Document

Handle.net

Fingerprint

Cite this