The already extended literature in combinatorial auctions, public projects and scheduling demands a more systematic classification of the domains and a clear comparison of the results known. Connecting characterization results for different settings and providing a characterization proof using another characterization result as a black box without having to repeat a tediously similar proof is not only elegant and desirable, but also greatly enhances our intuition and provides a classification of different results and a unified and deeper understanding. Characterizing the mechanisms for the domains of combinatorial auctions and scheduling unrelated machines are two outstanding problems in mechanism design. Since the scheduling domain is essentially the subdomain of combinatorial auc- tions with additive valuations, we consider whether one can extend a characterization of a subdomain to a domain. This is possible for two players (and for n-player mechanisms that satisfy stabilty) if the only truthful mechanisms for the sub-domain are the affine maximizers. Although this is not true for scheduling because besides the affine maximizers there are other truthful mechanisms (the threshold mechanisms), we still show that the truthful mechanisms that allocate all goods of practi- cally any domain which is strictly superdomain of additive combinatorial auctions are only the affine maximizers.

Top