Buchfuhrer, David I. (2011) Limits on computationally efficient VCG-based mechanisms for combinatorial auctions and public projects. Dissertation (Ph.D.), California Institute of Technology. http://resolver.caltech.edu/CaltechTHESIS:05242011-112814785
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)|
|Defense Date:||20 May 2011|
|Default Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||David Buchfuhrer|
|Deposited On:||27 May 2011 20:36|
|Last Modified:||26 Dec 2012 04:36|
- Final Version
See Usage Policy.
Repository Staff Only: item control page