Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/134834
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Conference paper |
Title: | Speed up Automated Mechanism Design by Sampling Worst-Case Profiles: An Application to Competitive VCG Redistribution Mechanism for Public Project Problem |
Author: | Guo, M. Shen, H. |
Citation: | Lecture Notes in Artificial Intelligence, 2017 / An, B., Bazzan, A., Leite, J., Villata, S., VanDerTorre, L. (ed./s), vol.10621, pp.127-142 |
Publisher: | Springer |
Publisher Place: | Switzerland |
Issue Date: | 2017 |
Series/Report no.: | Lecture Notes in Artificial Intelligence |
ISBN: | 9783319691305 |
ISSN: | 0302-9743 1611-3349 |
Conference Name: | International Conference on Principles and Practice of Multi-Agent Systems (PRIMA 2017) (30 Oct 2017 - 3 Nov 2017 : Nice, France) |
Editor: | An, B. Bazzan, A. Leite, J. Villata, S. VanDerTorre, L. |
Statement of Responsibility: | Mingyu Guo and Hong Shen |
Abstract: | 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. |
Keywords: | Automated mechanism design; VCG redistribution mechanisms; Dominant strategy implementation; Groves mechanisms; Public good provision |
Rights: | © Springer International Publishing AG 2017 |
DOI: | 10.1007/978-3-319-69131-2_8 |
Grant ID: | http://purl.org/au-research/grants/arc/DP150104871 |
Published version: | http://dx.doi.org/10.1007/978-3-319-69131-2_8 |
Appears in Collections: | Computer Science publications |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.