The Pareto Frontier of Inefficiency in Mechanism Design



Filos-Ratsikas, Aris ORCID: 0000-0001-7868-8114, Giannakopoulos, Yiannis and Lazos, Philip
(2021) The Pareto Frontier of Inefficiency in Mechanism Design. MATHEMATICS OF OPERATIONS RESEARCH, 47 (2). pp. 923-944.

[img] Text
1809.03454.pdf - Author Accepted Manuscript

Download (443kB) | Preview

Abstract

<jats:p> 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 [Formula: see text] that lie exactly on this frontier. In particular, these mechanisms range smoothly with respect to parameter [Formula: see text] across the frontier, between the first price ([Formula: see text]) and second price ([Formula: see text]) 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. </jats:p>

Item Type: Article
Uncontrolled Keywords: mechanism design, scheduling unrelated machines, makespan minimization, price of anarchy, price of stability, Pareto frontier
Divisions: Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User: Symplectic Admin
Date Deposited: 07 Mar 2022 08:55
Last Modified: 18 Jan 2023 21:11
DOI: 10.1287/moor.2021.1154
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3150120