English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
  Local TagsRelease HistoryDetailsSummary

Released
Paper

Towards More Practical Linear Programming-based Techniques for Algorithmic Mechanism Design

MPS-Authors
/persons/resource/persons44374

Elbassioni,  Khaled
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45021

Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45252

Ramezani,  Fahimeh
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

arXiv:1408.1577.pdf
(Preprint), 304KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Elbassioni, K., Mehlhorn, K., & Ramezani, F. (2014). Towards More Practical Linear Programming-based Techniques for Algorithmic Mechanism Design. Retrieved from http://arxiv.org/abs/1408.1577.


Cite as: https://hdl.handle.net/11858/00-001M-0000-0024-490A-B
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.