Speed up Automated Mechanism Design by Sampling Worst-Case Profiles: An Application to Competitive VCG Redistribution Mechanism for Public Project Problem

Mingyu Guo, Hong Shen

研究成果: Conference contribution同行評審

4 引文 斯高帕斯(Scopus)

摘要

Computationally Feasible Automated Mechanism Design (CFAMD) combines manual mechanism design and optimization. In CFAMD, we focus on a parameterized family of strategy-proof mechanisms, and then optimize within the family by adjusting the parameters. This transforms mechanism design (functional optimization) into value optimization, as we only need to optimize over the parameters. Under CFAMD, given a mechanism (characterized by a list of parameters), we need to be able to efficiently evaluate the mechanism’s performance. Otherwise, parameter optimization is computationally impractical when the number of parameters is large. We propose a new technique for speeding up CFAMD for worst-case objectives. Our technique builds up a set of worst-case type profiles, with which we can efficiently approximate a mechanism’s worst-case performance. The new technique allows us to apply CFAMD to cases where mechanism performance evaluation is computationally expensive. We demonstrate the effectiveness of our approach by applying it to the design of competitive VCG redistribution mechanism for public project problem. This is a well studied mechanism design problem. Several competitive mechanisms have already been proposed. With our new technique, we are able to achieve better competitive ratios than previous results.

原文English
主出版物標題PRIMA 2017
主出版物子標題Principles and Practice of Multi-Agent Systems - 20th International Conference, Proceedings
編輯Ana Bazzan, Serena Villata, Bo An, Joao Leite, Leendert van der Torre
發行者Springer Verlag
頁面127-142
頁數16
ISBN(列印)9783319691305
DOIs
出版狀態Published - 2017
對外發佈
事件20th International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2017 - Nice, France
持續時間: 30 10月 20173 11月 2017

出版系列

名字Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
10621 LNAI
ISSN(列印)0302-9743
ISSN(電子)1611-3349

Conference

Conference20th International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2017
國家/地區France
城市Nice
期間30/10/173/11/17

指紋

深入研究「Speed up Automated Mechanism Design by Sampling Worst-Case Profiles: An Application to Competitive VCG Redistribution Mechanism for Public Project Problem」主題。共同形成了獨特的指紋。

引用此