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.
Answering a question of Erdos, Sauer [4] and independently Perles and Shelah [5] found the maximal cardinality of a collection F of subsets of a set: N of cardinality n such that for every subset M @? N of cardinality m | C @? M: C @e F | < 2^m. Karpovsky and Milman [3] generalised this result. Here we give a short proof of these results and further extensions.  Learnability in Valiant's PAC learning model has been shown to be strongly related to the existence of uniform laws of large numbers. These laws define a distribution-free convergence property of means to expectations uniformly over classes of random variables. Classes of real-valued functions enjoying such a property are also known as uniform Glivenko-Cantelli classes. In this paper, we prove, through a generalization of Sauer's lemma that may be interesting in its own right, a new characterization of uniform Glivenko-Cantelli classes. Our characterization yields Dudley, Gine´, and Zinn's previous characterization as a corollary. Furthermore, it is the first based on a Gine´, and Zinn's previous characterization as a corollary. Furthermore, it is the first based on a simple combinatorial quantity generalizing the Vapnik-Chervonenkis dimension. We apply this result to obtain the weakest combinatorial condition known to imply PAC learnability in the statistical regression (or “agnostic”) framework. Furthermore, we find a characterization of learnability in the probabilistic concept model, solving an open problem posed by Kearns and Schapire. These results show that the accuracy parameter plays a crucial role in determining the effective complexity of the learner's hypothesis class. In this article we introduce a new combinatorial parameter which generalizes the VC dimension and the fat-shattering dimension, and extends beyond the function-class setup. Using this parameter we establish entropy bounds for subsets of the n-dimensional unit cube, and in particular, we present new bounds on the empirical covering numbers and gaussian averages associated with classes of functions in terms of the fat-shattering dimension.