Towards more practical linear programming-based techniques for algorithmic mechanism design

DOI10.1007/S00224-016-9704-2zbMATH Open1356.91050DBLPjournals/mst/ElbassioniMR16arXiv1408.1577OpenAlexW1896701397WikidataQ59470968 ScholiaQ59470968MaRDI QIDQ506527FDOQ506527

Authors: K. Mehlhorn, Fahimeh Ramezani, Khaled Elbassioni 

Publication date: 1 February 2017

Published in: Theory of Computing Systems (Search for Journal in Brave)

Abstract: R. Lavy and C. Swamy (FOCS 2005, J. ACM 2011) introduced a general method for obtaining truthful-in-expectation mechanisms from linear programming based approximation algorithms. Due to the use of the Ellipsoid method, a direct implementation of the method is unlikely to be efficient in practice. We propose to use the much simpler and usually faster multiplicative weights update method instead. The simplification comes at the cost of slightly weaker approximation and truthfulness guarantees.

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

Recommendations

• Towards more practical linear programming-based techniques for algorithmic mechanism design
• Truthful and Near-Optimal Mechanism Design via Linear Programming
• Approximation techniques for utilitarian mechanism design
• Approximation techniques for utilitarian mechanism design
• Fast convex decomposition for truthful social welfare approximation

zbMATH Keywords

approximation algorithmsmechanism designalgorithmic game theory

Mathematics Subject Classification ID

Auctions, bargaining, bidding and selling, and other market models (91B26) Approximation algorithms (68W25) Integer programming (90C10)

Cites Work

• Algorithmic Game Theory
• Geometric algorithms and combinatorial optimization
• A sublinear-time randomized approximation algorithm for matrix games
• The multiplicative weights update method: a meta-algorithm and applications
• Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems
• Truthful and Near-Optimal Mechanism Design via Linear Programming
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• Randomized metarounding
• Approximation techniques for utilitarian mechanism design
• Fast convex decomposition for truthful social welfare approximation
• Nearly-linear time positive LP solver with faster convergence rate
• Towards more practical linear programming-based techniques for algorithmic mechanism design
• Title not available (Why is that?)
• Unified acceleration method for packing and covering problems via diameter reduction
• Approximating Fractional Packings and Coverings in O(1/epsilon) Iterations

Cited In (8)

• Reducing mechanism design to algorithm design via machine learning
• Fast convex decomposition for truthful social welfare approximation
• A simple and fast algorithm for convex decomposition in relax-and-round mechanisms
• Truthful and Near-Optimal Mechanism Design via Linear Programming
• Towards more practical linear programming-based techniques for algorithmic mechanism design
• Title not available (Why is that?)
• New bounds for truthful scheduling on two unrelated selfish machines
• Approximation algorithms for cost-robust discrete minimization problems based on their LP-relaxations

This page was built for publication: Towards more practical linear programming-based techniques for algorithmic mechanism design

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q506527)