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

DOI10.1007/s00224-016-9704-2zbMath1356.91050arXiv1408.1577OpenAlexW1896701397WikidataQ59470968 ScholiaQ59470968MaRDI QIDQ506527

Kurt Mehlhorn, Fahimeh Ramezani, Khaled M. Elbassioni

Publication date: 1 February 2017

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

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

zbMATH Keywords

approximation algorithmsmechanism designalgorithmic game theory

Mathematics Subject Classification ID

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

Related Items (3)

A simple and fast algorithm for convex decomposition in relax-and-round mechanisms ⋮ New bounds for truthful scheduling on two unrelated selfish machines ⋮ Approximation algorithms for cost-robust discrete minimization problems based on their LP-relaxations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Probabilistic construction of deterministic algorithms: approximating packing integer programs
• Geometric algorithms and combinatorial optimization
• A sublinear-time randomized approximation algorithm for matrix games
• 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
• Approximation techniques for utilitarian mechanism design
• Randomized metarounding
• Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems
• Truthful and Near-Optimal Mechanism Design via Linear Programming
• Algorithmic Game Theory
• Approximating Fractional Packings and Coverings in O(1/epsilon) Iterations

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