Improved lower bounds for non-utilitarian truthfulness
From MaRDI portal
Publication:627119
DOI10.1016/j.tcs.2009.05.012zbMath1206.68065MaRDI QIDQ627119
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
algorithmic mechanism design; inter-domain routing problem; non-utilitarian inapproximability; unrelated machines scheduling problem
68M20: Performance evaluation, queueing, and scheduling in the context of computer systems
Related Items
Setting lower bounds on truthfulness, No truthful mechanism can be better than \(n\) approximate for two natural problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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