We consider incentive compatible mechanisms for a domain that is very close to the domain of scheduling @math unrelated machines: the single exception is that the valuation of just one machine is submodular. For the scheduling problem with such cost functions, we give a lower bound of @math on the approximation ratio of incentive compatible deterministic mechanisms. This is a strong information-theoretic impossibility result on the approximation ratio of mechanisms on relatively simple domains. The lower bound of the current work assumes no restriction on the mechanism side, but an expanded class of valuations, in contrast to previous general results on the Nisan-Ronen conjecture that hold for only special classes of mechanisms such as local, strongly monotone, and anonymous mechanisms. Our approach is based on a novel characterization of appropriately selected smaller instances that allows us to focus on particular type of algorithms (linear mechanisms), from which we extract a locality property that gives the lower bound.
@cite_12: A long-standing open question in algorithmic mechanism design is whether there exist computationally efficient truthful mechanisms for combinatorial auctions, with performance guarantees close to those possible without considerations of truthfulness. In this article, we answer this question negatively: the requirement of truthfulness can impact dramatically the ability of a mechanism to achieve a good approximation ratio for combinatorial auctions. More precisely, we show that every universally truthful randomized mechanism for combinatorial auctions with submodular valuations that approximates optimal social welfare within a factor of m1 2−e must use exponentially many value queries, where m is the number of items. Furthermore, we show that there exists a class of succinctly represented submodular valuation functions, for which the existence of a universally truthful polynomial-time mechanism that provides an m1 2−e-approximation would imply NP e RP. In contrast, ignoring truthfulness, there exist constant-factor approximation algorithms for this problem, and ignoring computational efficiency, the VCG mechanism is truthful and provides optimal social welfare. These are the first hardness results for truthful polynomial-time mechanisms for any type of combinatorial auctions, even for deterministic mechanisms. Our approach is based on a novel direct hardness technique that completely skips the notoriously hard step of characterizing truthful mechanisms. The characterization step was the main obstacle for proving impossibility results in algorithmic mechanism design so far.
Scheduling is related to combinatorial auctions, where multiple items need to be assigned to a set of buyers. This is a broad and successful area, and the setting shares both aforementioned features of multi-dimensionality and lack of externalities, therefore insights and techniques can be transferred from the one problem to the other. However the difference is that the objective for combinatorial auctions is social welfare maximization , and this is known to be achieved by the VCG mechanism, albeit in exponential time. Hence the focus on this rich area is on what can be achieved by computationally efficient mechanisms (see for example @cite_12 ). But in the case of the scheduling with the min-max objective, the flavor is more information theoretic, as we know that not even exponential time mechanisms can achieve the optimal makespan.