Text

The Pareto Frontier of Inefficiency in Mechanism Design

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.

Ketersediaan

Informasi Detail

Judul Seri

MATHEMATICS OF OPERATIONS RESEARCH; Vol.47 No.2 May 2022

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 923-944

Bahasa

English

ISBN/ISSN

-

Klasifikasi

NONE

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

PRICE OF ANARCHY
MECHANISM DESIGN
SCHEDULING UNRELATED MACHINES
MAKESPAN MINIMIZATION
PARETO FRONTIER
PRICE OF STABILITY

Info Detail Spesifik

https://doi.org/10.1287/moor.2021.1154

Pernyataan Tanggungjawab

Aris Filos-Ratsikas, Yiannis Giannakopoulos, Philip Lazos

Versi lain/terkait

Lampiran Berkas

Komentar