On the Limitations of Greedy Mechanism Design for Truthful Combinatorial Auctions

We study the combinatorial auction (CA) problem, in which m objects are sold to rational agents and the goal is to maximize social welfare. Of particular interest is the special case in which agents are interested in sets of size at most s (s-CAs), where a simple greedy algorithm obtains an s+1 approximation but no truthful algorithm is known to perform better than O(m/logm). As partial work towards resolving this gap, we ask: what is the power of truthful greedy algorithms for CA problems? The notion of greediness is associated with a broad class of algorithms, known as priority algorithms, which encapsulates many natural auction methods. We show that no truthful greedy priority algorithm can obtain an approximation to the CA problem that is sublinear in m, even for s-CAs with s>=2.