Approximation Techniques for Utilitarian Mechanism Design

DOI10.1137/090772988zbMath1234.68147OpenAlexW1977980414MaRDI QIDQ3225165

Patrick Briest, Berthold Vöcking, Piotr Krysta

Publication date: 15 March 2012

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

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

zbMATH Keywords

approximation algorithmsalgorithmic mechanism designcombinatorial auctionsmultiunit auctionstruthful mechanismsunsplittable multicommodity flow routing problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Optimality conditions and duality in mathematical programming (90C46) Linear programming (90C05) Deterministic network models in operations research (90B10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25)

Related Items (12)

Packing Under Convex Quadratic Constraints ⋮ Welfare Maximization with Deferred Acceptance Auctions in Reallocation Problems ⋮ Approximate composable truthful mechanism design ⋮ Approximate Truthful Mechanism Design for Two-Dimensional Orthogonal Knapsack Problem ⋮ On improved interval cover mechanisms for crowdsourcing markets ⋮ Combinatorial auctions without money ⋮ Improved approximation algorithms for box contact representations ⋮ Algorithms as Mechanisms: The Price of Anarchy of Relax and Round ⋮ On black-box transformations in downward-closed environments ⋮ Truthful mechanism design for bin packing with applications on cloud computing ⋮ Incentive compatible mulit-unit combinatorial auctions: a primal dual approach ⋮ Packing under convex quadratic constraints

This page was built for publication: Approximation Techniques for Utilitarian Mechanism Design