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

DOI10.1007/s00453-012-9634-6zbMath1262.68044MaRDI 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 bound; mechanism design; algorithmic game theory; dominant strategies; truthful; scheduling unrelated machines; multiparameter mechanism design

Mathematics Subject Classification ID

68M20: Performance evaluation, queueing, and scheduling in the context of computer systems

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

91A90: Experimental studies

Related Items

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

Cites Work

• 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
• Mechanism design for fractional scheduling on unrelated machines
• 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