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 (formula presented) that lie exactly on this frontier. In particular, these mechanisms range smoothly, with respect to parameter (formula presented) across the frontier, between the First-Price (formula presented) and Second-Price (formula presented) mechanisms. En route to these results, we also provide a definitive answer to an important question related to the scheduling problem, namely whether non-truthful mechanisms can provide better makespan guarantees in the equilibrium, compared to 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. - 11920:(2019), pp. 186-199. (Intervento presentato al convegno 15th Conference on Web and Internet Economics, WINE 2019 tenutosi a New York City; United States) [10.1007/978-3-030-35389-6_14].

The Pareto Frontier of Inefficiency in Mechanism Design

Filippos Lazos
2019

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 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 (formula presented) that lie exactly on this frontier. In particular, these mechanisms range smoothly, with respect to parameter (formula presented) across the frontier, between the First-Price (formula presented) and Second-Price (formula presented) mechanisms. En route to these results, we also provide a definitive answer to an important question related to the scheduling problem, namely whether non-truthful mechanisms can provide better makespan guarantees in the equilibrium, compared to 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.
2019
15th Conference on Web and Internet Economics, WINE 2019
Mechanism design; Pareto frontier; Price of anarchy; Price of stability
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
The Pareto Frontier of Inefficiency in Mechanism Design / Filos-Ratsikas, Aris; Giannakopoulos, Yiannis; Lazos, Filippos. - 11920:(2019), pp. 186-199. (Intervento presentato al convegno 15th Conference on Web and Internet Economics, WINE 2019 tenutosi a New York City; United States) [10.1007/978-3-030-35389-6_14].
File allegati a questo prodotto
File Dimensione Formato  
Filos-Ratsikas_The-Pareto-Frontier_2019.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 401.04 kB
Formato Adobe PDF
401.04 kB Adobe PDF   Contatta l'autore

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/1399111
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 7
social impact