Truthful and Near-Optimal Mechanism Design via Linear Programming

DOI10.1145/2049697.2049699zbMath1281.91091OpenAlexW2621304102MaRDI QIDQ5395669

Ron Lavi, Chaitanya Swamy

Publication date: 17 February 2014

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2049697.2049699

zbMATH Keywords

combinatorial auctiontruthful and computationally-efficient mechanisms

Mathematics Subject Classification ID

Linear programming (90C05) Auctions, bargaining, bidding and selling, and other market models (91B26)

Related Items (38)

Single-Parameter Combinatorial Auctions with Partially Public Valuations ⋮ Truthful mechanism design for multidimensional scheduling via cycle monotonicity ⋮ Towards More Practical Linear Programming-Based Techniques for Algorithmic Mechanism Design ⋮ A simple and fast algorithm for convex decomposition in relax-and-round mechanisms ⋮ Primal Beats Dual on Online Packing LPs in the Random-Order Model ⋮ Setting lower bounds on truthfulness ⋮ Truthfulness in advertising? Approximation mechanisms for knapsack bidders ⋮ A preference-based, multi-unit auction for pricing and capacity allocation ⋮ Separating the Communication Complexity of Truthful and Nontruthful Algorithms for Combinatorial Auctions ⋮ Approximate composable truthful mechanism design ⋮ Approximate Truthful Mechanism Design for Two-Dimensional Orthogonal Knapsack Problem ⋮ Cost sharing in two-sided markets ⋮ A $\frac{4}{3}$-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case ⋮ Optimization with demand oracles ⋮ The anarchy of scheduling without money ⋮ Strategyproof auction mechanisms for network procurement ⋮ Truthful randomized mechanisms for combinatorial auctions ⋮ Limitations of VCG-based mechanisms ⋮ A universally-truthful approximation scheme for multi-unit auctions ⋮ Black-box reductions for cost-sharing mechanism design ⋮ Towards more practical linear programming-based techniques for algorithmic mechanism design ⋮ Truthfulness with value-maximizing bidders: on the limits of approximation in combinatorial markets ⋮ Network pollution games ⋮ Truthful mechanism design via correlated tree rounding ⋮ Welfare maximization with production costs: a primal dual approach ⋮ Combinatorial auctions with verification are tractable ⋮ Bayesian incentive compatibility via matchings ⋮ Truthful approximation mechanisms for restricted combinatorial auctions ⋮ New bounds for truthful scheduling on two unrelated selfish machines ⋮ Dynamic mechanism design ⋮ New Results for Network Pollution Games ⋮ Black-Box Reductions in Mechanism Design ⋮ Truthfulness and Approximation with Value-Maximizing Bidders ⋮ Algorithms as Mechanisms: The Price of Anarchy of Relax and Round ⋮ On black-box transformations in downward-closed environments ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Incentive compatible mulit-unit combinatorial auctions: a primal dual approach

This page was built for publication: Truthful and Near-Optimal Mechanism Design via Linear Programming