The Pareto frontier of inefficiency in mechanism design

DOI10.1007/978-3-030-35389-6_14zbMATH Open1435.91061arXiv1809.03454OpenAlexW2989950847MaRDI QIDQ777959FDOQ777959

Authors: Aris Filos-Ratsikas, Yiannis Giannakopoulos, Philip Lazos 

Publication date: 30 June 2020

Published in: Mathematics of Operations Research (Search for Journal in Brave)

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 $mathcal{SP}_{a}lpha$ that lie exactly on this frontier. In particular, these mechanisms range smoothly, with respect to parameter $alphageq1$ across the frontier, between the First-Price ($mathcal{SP}_1$) and Second-Price ($mathcal{SP}_{i}nfty$) 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.

Full work available at URL: https://arxiv.org/abs/1809.03454

Recommendations

• The Pareto frontier of inefficiency in mechanism design
• A lower bound for scheduling mechanisms
• A lower bound for scheduling mechanisms
• Recent developments in the mechanism design problem for scheduling
• A Characterization of 2-Player Mechanisms for Scheduling

zbMATH Keywords

price of anarchymechanism designprice of stabilityPareto frontiermakespan minimizationscheduling unrelated machines

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Applications of game theory (91A80) Auctions, bargaining, bidding and selling, and other market models (91B26) Algorithmic game theory and complexity (91A68) Mechanism design theory (91B03)

Cites Work

• Worst-case equilibria
• How bad is selfish routing?
• Title not available (Why is that?)
• Optimal two- and three-stage production schedules with set-up time included
• The Price of Stability for Network Design with Fair Cost Allocation
• Scheduling. Theory, algorithms, and systems.
• The Complexity of Flowshop and Jobshop Scheduling
• Bounds for Certain Multiprocessing Anomalies
• Approximation algorithms for scheduling unrelated parallel machines
• Title not available (Why is that?)
• Optimal Auction Design
• Incentives in Teams
• Algorithmic mechanism design
• Scheduling without payments
• Fifty years of scheduling: a survey of milestones
• Title not available (Why is that?)
• Bounding the inefficiency of outcomes in generalized second price auctions
• Composable and efficient mechanisms
• Heuristic Algorithms for Scheduling Independent Tasks on Nonidentical Processors
• Uniform price auctions: equilibria and efficiency
• Computationally feasible VCG mechanisms
• Truthful mechanism design for multidimensional scheduling via cycle monotonicity
• Algorithms for Scheduling Tasks on Unrelated Processors
• A lower bound for scheduling mechanisms
• A lower bound of \(1+\varphi \) for truthful scheduling mechanisms
• Optimal lower bounds for anonymous scheduling mechanisms
• Mechanism design for fractional scheduling on unrelated machines
• Equilibrium in combinatorial public projects
• Correlated and Coarse Equilibria of Single-Item Auctions
• The Pareto frontier of inefficiency in mechanism design
• A Characterization of 2-Player Mechanisms for Scheduling
• Setting lower bounds on truthfulness
• The anarchy of scheduling without money
• Social welfare in one-sided matchings: random priority and beyond
• The VCG Mechanism for Bayesian Scheduling
• The Price of Anarchy in Auctions
• Bayesian Truthful Mechanisms for Job Scheduling from Bi-criterion Approximation Algorithms
• Prior-independent mechanisms for scheduling
• A new lower bound for deterministic truthful scheduling

Cited In (4)

• Optimal mechanism design when both allocative inefficiency and expenditure inefficiency matter
• A new lower bound for deterministic truthful scheduling
• The Pareto frontier of inefficiency in mechanism design
• The price of anarchy as a classifier for mechanism design in a Pareto-Bayesian-Nash context

This page was built for publication: The Pareto frontier of inefficiency in mechanism design

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q777959)