Incentive Analysis of Approximately Efficient Allocation Algorithms

We present a series of results providing evidence that the incentive problem with approximate VCG-based mechanismsis often not very severe. Our first result uses average-caseanalysis to show that if an algorithm can solve the allocationproblem well for a large proportion of instances, incentivesto lie essentially disappear. We next show that even if suchincentives exist, a simple enhancement of the mechanismmakes it unlikely that any player will find an improving deviation. Additionally, we offer a simulation-based techniqueto verify empirically the incentive properties of an arbitraryapproximation algorithm and demonstrate it in a specificinstance using combinatorial auction data.

Authors

• Yevgeniy Vorobeychik Washington University, St. Louis
• Yagil Engel Microsoft Research

Keywords

• Algorithmic mechanism design
• combinatorial auctions
• VCG