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 these 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 SPα that lie exactly on this frontier. In particular, these mechanisms range smoothly with respect to parameter α ≥ 1 across the frontier, between the first price (SP1) and second price (SP∞) mechanisms. En route to these results, we also provide a definitive answer to an important question related to the scheduling problem, namely whether nontruthful mechanisms can provide better makespan guarantees in the equilibrium compared with truthful ones. We answer this question in the negative by proving that the price of anarchy of all scheduling mechanisms is at least n, where n is the number of machines.

The Pareto Frontier of Inefficiency in Mechanism Design / Filos-Ratsikas, Aris; Giannakopoulos, Yiannis; Lazos, Filippos. - In: MATHEMATICS OF OPERATIONS RESEARCH. - ISSN 0364-765X. - (2021). [10.1287/moor.2021.1154]

The Pareto Frontier of Inefficiency in Mechanism Design

Filippos Lazos
2021

Abstract

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 these 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 SPα that lie exactly on this frontier. In particular, these mechanisms range smoothly with respect to parameter α ≥ 1 across the frontier, between the first price (SP1) and second price (SP∞) mechanisms. En route to these results, we also provide a definitive answer to an important question related to the scheduling problem, namely whether nontruthful mechanisms can provide better makespan guarantees in the equilibrium compared with truthful ones. We answer this question in the negative by proving that the price of anarchy of all scheduling mechanisms is at least n, where n is the number of machines.
2021
mechanism design; scheduling unrelated machines; makespan minimization; price of anarchy; price of stability; pareto frontier
01 Pubblicazione su rivista::01a Articolo in rivista
The Pareto Frontier of Inefficiency in Mechanism Design / Filos-Ratsikas, Aris; Giannakopoulos, Yiannis; Lazos, Filippos. - In: MATHEMATICS OF OPERATIONS RESEARCH. - ISSN 0364-765X. - (2021). [10.1287/moor.2021.1154]
File allegati a questo prodotto
File Dimensione Formato  
Filos-Ratsikas_The-Pareto_2021.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 876.15 kB
Formato Adobe PDF
876.15 kB Adobe PDF   Contatta l'autore
Filos-Ratsikas_preprint_The-Pareto_2021.pdf

accesso aperto

Note: https://doi.org/10.1287/moor.2021.1154
Tipologia: Documento in Pre-print (manoscritto inviato all'editore, precedente alla peer review)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 433.11 kB
Formato Adobe PDF
433.11 kB Adobe PDF

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1627751
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact