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

DOI10.1007/S00224-016-9704-2MaRDI QIDQ506527zbMATH OpenOpenAlexDBLPWikidataFDO

Authors K. Mehlhorn, Fahimeh Ramezani, Khaled Elbassioni

Publication date 1 February 2017

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

Copyright license Creative Commons Attribution 4.0 International

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

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)

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.

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

Cites work

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

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
• scientific article; zbMATH DE number 5309433 (Why is no real title available?)
• 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)