The Pareto Frontier of Inefficiency in Mechanism Design

Aris Filos-Ratsikas (), Yiannis Giannakopoulos () and Philip Lazos ()
Additional contact information
Aris Filos-Ratsikas: Department of Computer Science, University of Liverpool, Liverpool L69 3BX, United Kingdom
Yiannis Giannakopoulos: Department of Data Science, Friedrich-Alexander-Universität Erlangen-Nürnberg, 91058 Erlangen, Germany
Philip Lazos: Department of Computer, Control and Management Engineering, Antonio Ruberti, Sapienza University of Rome, 00185 Roma, Italy

Mathematics of Operations Research, 2022, vol. 47, issue 2, 923-944

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 S P α that lie exactly on this frontier. In particular, these mechanisms range smoothly with respect to parameter α ≥ 1 across the frontier, between the first price ( S P 1 ) and second price ( S P ∞ ) 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.

Keywords: Primary: 91B26; 91A68; secondary: 91A80; 90B35; mechanism design; scheduling unrelated machines; makespan minimization; price of anarchy; price of stability; Pareto frontier (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2021.1154 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:47:y:2022:i:2:p:923-944

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().