Truthful and Near-Optimal Mechanism Design via Linear Programming

From MaRDI portal
Publication:5395669

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




Related Items (38)

Single-Parameter Combinatorial Auctions with Partially Public ValuationsTruthful mechanism design for multidimensional scheduling via cycle monotonicityTowards More Practical Linear Programming-Based Techniques for Algorithmic Mechanism DesignA simple and fast algorithm for convex decomposition in relax-and-round mechanismsPrimal Beats Dual on Online Packing LPs in the Random-Order ModelSetting lower bounds on truthfulnessTruthfulness in advertising? Approximation mechanisms for knapsack biddersA preference-based, multi-unit auction for pricing and capacity allocationSeparating the Communication Complexity of Truthful and Nontruthful Algorithms for Combinatorial AuctionsApproximate composable truthful mechanism designApproximate Truthful Mechanism Design for Two-Dimensional Orthogonal Knapsack ProblemCost sharing in two-sided marketsA $\frac{4}{3}$-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral CaseOptimization with demand oraclesThe anarchy of scheduling without moneyStrategyproof auction mechanisms for network procurementTruthful randomized mechanisms for combinatorial auctionsLimitations of VCG-based mechanismsA universally-truthful approximation scheme for multi-unit auctionsBlack-box reductions for cost-sharing mechanism designTowards more practical linear programming-based techniques for algorithmic mechanism designTruthfulness with value-maximizing bidders: on the limits of approximation in combinatorial marketsNetwork pollution gamesTruthful mechanism design via correlated tree roundingWelfare maximization with production costs: a primal dual approachCombinatorial auctions with verification are tractableBayesian incentive compatibility via matchingsTruthful approximation mechanisms for restricted combinatorial auctionsNew bounds for truthful scheduling on two unrelated selfish machinesDynamic mechanism designNew Results for Network Pollution GamesBlack-Box Reductions in Mechanism DesignTruthfulness and Approximation with Value-Maximizing BiddersAlgorithms as Mechanisms: The Price of Anarchy of Relax and RoundOn black-box transformations in downward-closed environmentsUnnamed ItemUnnamed ItemIncentive compatible mulit-unit combinatorial auctions: a primal dual approach




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