Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension

Amit Daniely, Michael Schapira, Gal Shahaf

Algorithmic mechanism design (AMD) studies the delicate interplay between computational efficiency, truthfulness, and optimality. We focus on AMD's paradigmatic problem: combinator…