A Caltech Library Service

Limits on Computationally Efficient VCG-Based Mechanisms for Combinatorial Auctions and Public Projects


Buchfuhrer, David Isaac (2011) Limits on Computationally Efficient VCG-Based Mechanisms for Combinatorial Auctions and Public Projects. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/N0M7-C473.


A natural goal in designing mechanisms for auctions and public projects is to maximize the social welfare while incentivizing players to bid truthfully. If these are the only concerns, the problem is easily solved by use of the VCG mechanism. Unfortunately, this mechanism is not computationally efficient in general and there are currently no other general methods for designing truthful mechanisms. However, it is possible to design computationally efficient VCG-based mechanisms which approximately maximize the social welfare.

We explore the design space of computationally efficient VCG-based mechanisms under submodular valuations and show that the achievable approximation guarantees are poor, even compared to efficient non-truthful algorithms. Some of these approximation hardness results stem from an asymmetry in the information available to the players versus that available to the mechanism. We develop an alternative Instance Oracle model which reduces this asymmetry by allowing the mechanism to access some computational capabilities of the players. By building assumptions about player computation into the model, a more realistic study of mechanism design can be undertaken.

Finally, we give VCG-based mechanisms for some problems in the Instance Oracle model which achieve provably better approximations than the best VCG-based mechanism in the standard model. However, for other problems we give reductions in the Instance Oracle model which prove inapproximability results as strong as those shown in the standard model. These provide more robust hardness results that are not simply artifacts of the asymmetry in the standard model.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:algorithmic game theory, mechanism design, combinatorial auctions, combinatorial public projects, complexity, submodular, VCG
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Computer Science
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Umans, Christopher M.
Thesis Committee:
  • Umans, Christopher M. (chair)
  • Schulman, Leonard J.
  • Wierman, Adam C.
  • Ledyard, John O.
Defense Date:20 May 2011
Record Number:CaltechTHESIS:05242011-112814785
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:6424
Deposited By: David Buchfuhrer
Deposited On:27 May 2011 20:36
Last Modified:09 Oct 2019 17:09

Thesis Files

PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page