Truthful approximation schemes for single-parameter agents

DOI10.1137/080744992MaRDI QIDQ3093628zbMATH OpenOpenAlexFDO

Authors Peerapong Dhangwatnotai, Shahar Dobzinski, Shaddin Dughmi, Tim Roughgarden

Publication date 18 October 2011

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/080744992

zbMATH Keywords

algorithm game theoryalgorithmic mechanism designscheduling

Mathematics Subject Classification ID

Randomized algorithms (68W20) Approximation algorithms (68W25) Deterministic scheduling theory in operations research (90B35) Game theory (91A99)

Recommendations

• scientific article; zbMATH DE number 6297764
• A deterministic truthful PTAS for scheduling related machines
• A unified approach to truthful scheduling on related machines
• A unified approach to truthful scheduling on related machines
• STACS 2005

Cited in

(28)

• Maximizing the minimum load for selfish agents
• Setting lower bounds on truthfulness
• No truthful mechanism can be better than n approximate for two natural problems
• A lower bound of \(1+\varphi \) for truthful scheduling mechanisms
• The cost of selfishness for maximizing the minimum load on uniformly related machines
• Pricing lotteries
• Fair by design: multidimensional envy-free mechanisms
• The anarchy of scheduling without money
• Limitations of VCG-based mechanisms
• A unified approach to truthful scheduling on related machines
• Characterization of truthful mechanisms for one-dimensional single facility location game with payments
• Approximate truthful mechanism design for two-dimensional orthogonal knapsack problem
• Combinatorial Walrasian equilibrium
• The VCG Mechanism for Bayesian Scheduling
• Reducing truth-telling online mechanisms to online optimization
• A truthful constant approximation for maximizing the minimum load on related machines
• Maximizing the minimum load: the cost of selfishness
• Reducing price of anarchy of selfish task allocation with more selfishness
• Truthful mechanism design via correlated tree rounding
• Characterizing Truthful Multi-armed Bandit Mechanisms
• A new lower bound for deterministic truthful scheduling
• Budget-feasible mechanisms for proportionally selecting agents from groups
• Gradient-based local formulations of the Vickrey-Clarke-Groves mechanism for truthful minimization of social convex objectives
• Distributed algorithmic mechanism design for scheduling on unrelated machines
• On the Nisan-Ronen conjecture for submodular valuations
• Truthful allocation in graphs and hypergraphs
• On designing truthful mechanisms for online scheduling
• Mechanisms for scheduling with single-bit private values

This page was built for publication: Truthful approximation schemes for single-parameter agents

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