Computationally Feasible VCG Mechanisms

Details Computationally Feasible VCG Mechanisms Computationally Feasible VCG Mechanisms

2011-09-30

arxiv.org/abs/1110.0025v1

Journal Of Artificial Intelligence Research, Volume 29, pages 19-47, 2007

Computer Science

Computer Science and Game Theory

Scientific paper

10.1613/jair.2046

A major achievement of mechanism design theory is a general method for the construction of truthful mechanisms called VCG (Vickrey, Clarke, Groves). When applying this method to complex problems such as combinatorial auctions, a difficulty arises: VCG mechanisms are required to compute optimal outcomes and are, therefore, computationally infeasible. However, if the optimal outcome is replaced by the results of a sub-optimal algorithm, the resulting mechanism (termed VCG-based) is no longer necessarily truthful. The first part of this paper studies this phenomenon in depth and shows that it is near universal. Specifically, we prove that essentially all reasonable approximations or heuristics for combinatorial auctions as well as a wide class of cost minimization problems yield non-truthful VCG-based mechanisms. We generalize these results for affine maximizers. The second part of this paper proposes a general method for circumventing the above problem. We introduce a modification of VCG-based mechanisms in which the agents are given a chance to improve the output of the underlying algorithm. When the agents behave truthfully, the welfare obtained by the mechanism is at least as good as the one obtained by the algorithms output. We provide a strong rationale for truth-telling behavior. Our method satisfies individual rationality as well.

Affiliated with

Also associated with

No associations

Rating

Computationally Feasible VCG Mechanisms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Computationally Feasible VCG Mechanisms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computationally Feasible VCG Mechanisms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-236433