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

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationPRIMA 2017
Subtitle of host publicationPrinciples and Practice of Multi-Agent Systems - 20th International Conference, Proceedings
EditorsAna Bazzan, Serena Villata, Bo An, Joao Leite, Leendert van der Torre
PublisherSpringer Verlag
Pages127-142
Number of pages16
ISBN (Print)9783319691305
DOIs
Publication statusPublished - 2017
Externally publishedYes
Event20th International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2017 - Nice, France
Duration: 30 Oct 20173 Nov 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10621 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference20th International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2017
Country/TerritoryFrance
CityNice
Period30/10/173/11/17

Keywords

  • Automated mechanism design
  • Dominant strategy implementation
  • Groves mechanisms
  • Public good provision
  • VCG redistribution mechanisms

Fingerprint

Dive into the research topics of 'Speed up Automated Mechanism Design by Sampling Worst-Case Profiles: An Application to Competitive VCG Redistribution Mechanism for Public Project Problem'. Together they form a unique fingerprint.

Cite this