  The existence of incentive-compatible computationally-efficient protocols for
combinatorial auctions with decent approximation ratios is the paradigmatic
problem in computational mechanism design. It is believed that in many cases
good approximations for combinatorial auctions may be unattainable due to an
inherent clash between truthfulness and computational efficiency. However, to
date, researchers lack the machinery to prove such results. In this paper, we
present a new approach that we believe holds great promise for making progress
on this important problem. We take the first steps towards the development of
new technologies for lower bounding the VC dimension of k-tuples of disjoint
sets. We apply this machinery to prove the first computational-complexity
inapproximability results for incentive-compatible mechanisms for combinatorial
auctions. These results hold for the important class of VCG-based mechanisms,
and are based on the complexity assumption that NP has no polynomial-size
circuits.
