The Pareto Frontier of Inefficiency in Mechanism Design

Aris Filos-Ratsikas, Yiannis Giannakopoulos, Philip Lazos

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

We study the trade-off between the Price of Anarchy (PoA) and the Price of Stability (PoS) in mechanism design, in the prototypical problem of unrelated machine scheduling. We give bounds on the space of feasible mechanisms with respect to the above metrics, and observe that two fundamental mechanisms, namely the First-Price (FP) and the Second-Price (SP), lie on the two opposite extrema of this boundary. Furthermore, for the natural class of anonymous task-independent mechanisms, we completely characterize the PoA/PoS Pareto frontier; we design a class of optimal mechanisms backslashmathcal SPbackslashalpha that lie exactly on this frontier. In particular, these mechanisms range smoothly, with respect to parameter backslashalpha backslashge 1 across the frontier, between the First-Price (backslashmathcal SP1) and Second-Price (backslashmathcal SPbackslashinfty ) mechanisms.
Original languageEnglish
Title of host publicationWeb and Internet Economics: 15th International Conference, WINE 2019, New York, NY, USA, December 10–12, 2019, Proceedings
EditorsIoannis Caragiannis, Vahab Mirrokni, Evdokia Nikolova
Place of PublicationCham
PublisherSpringer, Cham
Pages186-199
Number of pages14
ISBN (Electronic)978-3-030-35389-6
ISBN (Print)978-3-030-35388-9
DOIs
Publication statusPublished - 3 Dec 2019
EventThe 15th Conference on Web and Internet Economics, 2019 - New York, United States
Duration: 10 Dec 201912 Dec 2019
Conference number: 15
https://wine2019.cs.columbia.edu/call-for-papers.html

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Cham
Volume11920
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceThe 15th Conference on Web and Internet Economics, 2019
Abbreviated titleWINE 2019
Country/TerritoryUnited States
CityNew York
Period10/12/1912/12/19
Internet address

Keywords / Materials (for Non-textual outputs)

  • Mechanism design
  • Price of anarchy
  • Price of stability
  • Pareto frontier

Fingerprint

Dive into the research topics of 'The Pareto Frontier of Inefficiency in Mechanism Design'. Together they form a unique fingerprint.

Cite this