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.

本文分两部分，第一部分研究了将 VCG (Vickrey, Clarke, Groves) 机制应用于复杂问题如组合拍卖时的计算难度，第二部分提出了修改后的 VCG 机制，使得机制更加高效且诚实。