No truthful mechanism can be better than \(n\) approximate for two natural problems

DOI10.1016/j.geb.2018.05.003zbMath1416.91137arXiv1712.06709OpenAlexW2777733854MaRDI QIDQ1792559

Stefano Leucci, Paolo Penna, Akaki Mamageishvili

Publication date: 12 October 2018

Published in: Games and Economic Behavior (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1712.06709

zbMATH Keywords

lower boundsmechanism designinapproximabilitytruthful mechanismsnon-Utilitarian problems

Mathematics Subject Classification ID

Auctions, bargaining, bidding and selling, and other market models (91B26)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved lower bounds for non-utilitarian truthfulness
• Two simplified proofs for Roberts' theorem
• Truthful mechanism design for multidimensional scheduling via cycle monotonicity
• Multiobjective optimization: Improved FPTAS for shortest paths and nonlinear objectives with applications
• Mechanisms for scheduling with single-bit private values
• Truthful mechanisms for two-range-values variant of unrelated scheduling
• A lower bound for scheduling mechanisms
• A necessary and sufficient condition for rationalizability in a quasilinear context
• A lower bound of \(1+\varphi \) for truthful scheduling mechanisms
• Multi-unit auctions: beyond Roberts
• A Deterministic Truthful PTAS for Scheduling Related Machines
• Optimal Lower Bounds for Anonymous Scheduling Mechanisms
• Weak Monotonicity Characterizes Deterministic Dominant-Strategy Implementation
• The VCG Mechanism for Bayesian Scheduling
• A Characterization of 2-Player Mechanisms for Scheduling
• Optimal Auction Design
• Prior-independent mechanisms for scheduling
• Algorithmic mechanism design

This page was built for publication: No truthful mechanism can be better than \(n\) approximate for two natural problems