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

Khaled Elbassioni, Kurt Mehlhorn, Fahimeh Ramezani

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

R. Lavi and C. Swamy (FOCS 2005, J. ACM 58(6), 25, 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.

Original languageBritish English
Pages (from-to)641-663
Number of pages23
JournalTheory of Computing Systems
Volume59
Issue number4
DOIs
StatePublished - 1 Nov 2016

Keywords

  • Algorithmic game theory
  • Approximation algorithms
  • Mechanism design

Fingerprint

Dive into the research topics of 'Towards More Practical Linear Programming-based Techniques for Algorithmic Mechanism Design'. Together they form a unique fingerprint.

Cite this