The Pareto Frontier of Inefficiency in Mechanism Design
Filos-Ratsikas A, Giannakopoulos Y, Lazos P (2019)
Publication Type: Conference contribution, Original article
Publication year: 2019
Journal
Publisher: Springer
Book Volume: 11920 LNCS
Pages Range: 186-199
Conference Proceedings Title: Proceedings of the 15th Conference on Web and Internet Economics (WINE)
Event location: New York City, NY
ISBN: 9783030353889
DOI: 10.1007/978-3-030-35389-6_14
Open Access Link: https://arxiv.org/abs/1809.03454
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.
Authors with CRIS profile
Involved external institutions
The University of Liverpool
United Kingdom (GB)
Università degli studi "La Sapienza"
Italy (IT)
Technische Universität München (TUM)
Germany (DE)
United Kingdom (GB)
Università degli studi "La Sapienza"
Italy (IT)
Technische Universität München (TUM)
Germany (DE)
How to cite
APA:
Filos-Ratsikas, A., Giannakopoulos, Y., & Lazos, P. (2019). The Pareto Frontier of Inefficiency in Mechanism Design. In Ioannis Caragiannis, Vahab Mirrokni, Evdokia Nikolova (Eds.), Proceedings of the 15th Conference on Web and Internet Economics (WINE) (pp. 186-199). New York City, NY, US: Springer.
MLA:
Filos-Ratsikas, Aris, Yiannis Giannakopoulos, and Philip Lazos. "The Pareto Frontier of Inefficiency in Mechanism Design." Proceedings of the 15th Conference on Web and Internet Economics, WINE 2019, New York City, NY Ed. Ioannis Caragiannis, Vahab Mirrokni, Evdokia Nikolova, Springer, 2019. 186-199.
BibTeX: Download