A sufficient condition for truthfulness with single parameter agents.

ABSTRACTWe consider the task of designing truthful mechanisms for single parameter agents. We prove a general sufficient condition for truthfulness when each agent's valuation function for each possible outcome is a one-dimensional function of its type, continuous everywhere and differentiable almost everywhere. For certain types of natural valuation functions, our condition is also necessary. Our condition extends both the Mirrlees-Spence condition [25, 17], applicable only for differentiable real allocations, and Archer and Tardos' single parameter characterization [4], which assumes an agent's valuation is linear in its type.We demonstrate the simplicity of testing our condition by showing that classical criteria for truthfulness in combinatorial problems such as auctions and machine scheduling can be derived from our condition. In addition, we use our condition to derive results for new single parameter problems, which have not been previously analyzed.We also consider combinatorial problems where the true types of agents affect the valuation of each other, such as in machine scheduling with selfish jobs. In such cases there are only degenerate dominant strategy mechanisms. We show that the same condition can be used to design mechanisms which are ex-post truthful, meaning that the outcome where all agents cooperate and report their true type is a Nash equilibrium. We demonstrate the power of this condition by applying it on the problem of machine scheduling with strategic job owners, previously presented in [5]. We give a constant approximation ratio algorithms for the original problem and to the double setting where both jobs and machines are strategic.