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

Elbassioni, Khaled; Mehlhorn, Kurt; Ramezani, Fahimeh

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

タグ情報を表示リリース履歴を表示詳細要約

公開

成果報告書

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

There are no locators available

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

フルテキスト (公開)

arXiv:1408.1577.pdf
(プレプリント), 304KB

付随資料 (公開)

There is no public supplementary material available

引用

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.

引用: https://hdl.handle.net/11858/00-001M-0000-0024-490A-B

要旨

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.