A Characterization of n-Player Strongly Monotone Scheduling Mechanisms

Our work deals with the important problem of globally characterizing truthful mechanisms where players have multi-parameter, additive valuations, like scheduling unrelated machines or additive combinatorial auctions. Very few mechanisms are known for these settings and the question is: Can we prove that no other truthful mechanisms exist? We characterize truthful mechanisms for n players and 2 tasks or items, as either task-independent, or a player-grouping minimizer, a new class of mechanisms we discover, which generalizes affine minimizers. We assume decisiveness, strong monotonicity and that the truthful payments1 are continuous functions of players’ bids.