How to Route and Tax Selfish Unsplittable Traffic

We study the problem of assigning unsplittable traffic to a set of $m$ links so to minimize the maximum link congestion (i.e., the makespan). We consider the case of *selfish agents* owning pieces of the traffic. In particular, we introduce a variant of the model by Koutsoupias and Papadimitriou [1999] in which owners of the traffic cannot directly choose which link to use; instead, the assignment is performed by a *scheduler*. The agents can manipulate the scheduler by reporting false information regarding the size of each piece of unsplittable traffic. We provide upper and lower bounds on the approximation achievable by *mechanisms* that induce a Nash equilibrium when all agents report their true values. For the case of each agent owning one job, our positive results for $m$ identical links show the effectiveness of introducing such a scheduler since, in this case, (1+\epsilon)-approximate solutions are guaranteed in polynomial time. In contrast, the result by Koutsoupias and Papadimitriou [1999] shows that, without payments and allowing selfish routing, Nash equilibria yield (in the worst case) $\Omega(\frac{\log m}{\log \log m})$-approximate solutions, even for unitary weighted traffic. When links have different speeds we prove lower and upper bounds on the approximation achievable by a mechanism inducing a Nash equilibrium. For the case of agents owning more than one job, we give mechanisms that achieve constant approximation and prove lower bounds on the approximation ratio that can be achieved by a mechanism