A lower bound of \(1+\varphi \) for truthful scheduling mechanisms

DOI10.1007/s00453-012-9634-6zbMath1262.68044OpenAlexW1602132852MaRDI QIDQ1949759

Angelina Vidali, Elias Koutsoupias

Publication date: 16 May 2013

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-012-9634-6

zbMATH Keywords

lower boundmechanism designalgorithmic game theorydominant strategiestruthfulscheduling unrelated machinesmultiparameter mechanism design

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Experimental studies (91A90)

Related Items (14)

The VCG Mechanism for Bayesian Scheduling ⋮ Setting lower bounds on truthfulness ⋮ The anarchy of scheduling without money ⋮ Well-behaved online load balancing against strategic jobs ⋮ The price of envy-freeness in machine scheduling ⋮ Incentive compatible mechanisms for scheduling two-parameter job agents on parallel identical machines to minimize the weighted number of late jobs ⋮ Truthful mechanism design via correlated tree rounding ⋮ Average-case approximation ratio of scheduling without payments ⋮ No truthful mechanism can be better than \(n\) approximate for two natural problems ⋮ A new lower bound for deterministic truthful scheduling ⋮ New bounds for truthful scheduling on two unrelated selfish machines ⋮ The Anarchy of Scheduling Without Money ⋮ The Pareto frontier of inefficiency in mechanism design ⋮ Fair by design: multidimensional envy-free mechanisms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for scheduling unrelated parallel machines
• Truthful mechanisms for two-range-values variant of unrelated scheduling
• A lower bound for scheduling mechanisms
• Truthful germs are contagious: a local-to-global characterization of truthfulness
• Optimal Lower Bounds for Anonymous Scheduling Mechanisms
• Envy-Free Makespan Approximation
• Monotonicity and Implementability
• Truthful Approximation Schemes for Single-Parameter Agents
• A Lower Bound of 1 + φ for Truthful Scheduling Mechanisms
• A Characterization of 2-Player Mechanisms for Scheduling
• On Multi-dimensional Envy-Free Mechanisms
• Optimal Auction Design
• Incentives in Teams
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• STACS 2004
• Algorithmic Game Theory
• Algorithms – ESA 2005
• STACS 2005
• Algorithmic mechanism design

This page was built for publication: A lower bound of \(1+\varphi \) for truthful scheduling mechanisms