The Power of Verification for One-Parameter Agents

We study combinatorial optimization problems involving one-parameter selfish agents considered by Archer and Tardos [FOCS 2001]. In particular, we show that, if agents can lie in one direction (that is they either overbid or underbid) then any (polynomial-time) c-approximation algorithm, for the optimization problem without selfish agents, can be turned into a (polynomial-time) c(1 + epsilon)-approximation truthful mechanism, for any epsilon > 0. We then look at the Q||Cmax problem in the case of agents owning machines of different speeds. We consider the model in which payments are given to the agents only after the machines have completed the jobs assigned. This means that for each machine that receives at least one job, the mechanism can verify if the corresponding agent declared a greater speed. For this setting, we characterize the allocation algorithms A that admit a payment function P such that M = (A, P) is a truthful mechanism. In addition, we give a (1+epsilon)-approximation truthful mechanism for Q||Cmax when machine speeds are bounded by a constant. Finally, we consider the classical scheduling problem Q||wjCj which does not admit an exact mechanism if verification is not allowed. By contrast, we show that an exact mechanism for Q||wjCj exists when verification is allowed.