Truthful mechanism design via correlated tree rounding

DOI10.1007/S10107-016-1068-5zbMath1371.91066OpenAlexW2511680749MaRDI QIDQ526848

Martin Hoefer, Rebecca Reiffenhäuser, Idan Maor, Yossi Azar, Berthold Vöcking

Publication date: 15 May 2017

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-016-1068-5

zbMATH Keywords

mechanism designroundingcombinatorial auctionsscheduling mechanisms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Auctions, bargaining, bidding and selling, and other market models (91B26) Approximation algorithms (68W25)

Related Items (1)

New bounds for truthful scheduling on two unrelated selfish machines

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for scheduling unrelated parallel machines
• Inapproximability results for combinatorial auctions with submodular utility functions
• A lower bound for scheduling mechanisms
• An approximation algorithm for the generalized assignment problem
• A lower bound of \(1+\varphi \) for truthful scheduling mechanisms
• Limitations of VCG-based mechanisms
• Limitations of randomized mechanisms for combinatorial auctions
• Truthful approximation mechanisms for scheduling selfish related machines
• A Unified Approach to Truthful Scheduling on Related Machines
• A Deterministic Truthful PTAS for Scheduling Related Machines
• Tight Approximation Algorithms for Maximum Separable Assignment Problems
• Optimal Lower Bounds for Anonymous Scheduling Mechanisms
• Mechanism design for fractional scheduling on unrelated machines
• On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP
• Truthful Approximation Schemes for Single-Parameter Agents
• Online Mechanism Design (Randomized Rounding on the Fly)
• Impossibility Results for Truthful Combinatorial Auctions with Submodular Valuations
• Truth revelation in approximately efficient combinatorial auctions
• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• All-norm approximation algorithms
• Least Majorized Elements and Generalized Polymatroids
• Truthful Generalized Assignments via Stable Matching
• Truthful and Near-Optimal Mechanism Design via Linear Programming
• On the Power of Randomization in Algorithmic Mechanism Design
• From query complexity to computational complexity
• From convex optimization to randomized mechanisms
• Algorithms – ESA 2005
• Algorithmic mechanism design

This page was built for publication: Truthful mechanism design via correlated tree rounding