Improved lower bounds for non-utilitarian truthfulness

DOI10.1016/j.tcs.2009.05.012zbMath1206.68065OpenAlexW2161456923MaRDI QIDQ627119

Iftah Gamzu

Publication date: 21 February 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.05.012

zbMATH Keywords

algorithmic mechanism designinter-domain routing problemnon-utilitarian inapproximabilityunrelated machines scheduling problem

Mathematics Subject Classification ID

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

Related Items (2)

Setting lower bounds on truthfulness ⋮ No truthful mechanism can be better than \(n\) approximate for two natural problems

Cites Work

• Approximation algorithms for scheduling unrelated parallel machines
• An approximation algorithm for the generalized assignment problem
• A BGP-based mechanism for lowest-cost routing
• Weak Monotonicity Characterizes Deterministic Dominant-Strategy Implementation
• A Lower Bound of 1 + φ for Truthful Scheduling Mechanisms
• Convex programming for scheduling unrelated parallel machines
• Incentives in Teams
• Mechanism Design for Fractional Scheduling on Unrelated Machines
• Truthful randomized mechanisms for combinatorial auctions
• Algorithmic mechanism design
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Improved lower bounds for non-utilitarian truthfulness