Routing Selfish Unsplittable Traffic

We consider general resource assignment games involving selfish users/agents in which users compete for resources and try to be assigned to those which maximize their own benefits (e.g., try to route their traffic through links which minimize the latency of their own traffic). We propose and study a mechanism design approach in which an allocation mechanism assigns users to resources and charges the users for using the resources so as to induce each user to truthfully report a private piece of information he/she holds (e.g., how much traffic he/she needs to transmit). This information is crucial for computing optimal (or close to optimal) allocations and an agent could misreport his/her information to induce the underlying allocation algorithm to output a solution which he/she likes more (e.g., which assigns better resources to him/her). For our resource allocation problems, we give an algorithmic characterization of the solutions for which truth-telling is a Nash equilibrium. A natural application of these results is to a scheduling/routing problem which is the mechanism design counterpart of the selfish routing game of Koutsoupias and Papadimitriou [1999]: Each selfish user wants to route a piece of unsplittable traffic using one of m links of different speeds so as to minimize his/her own latency. Our mechanism design counterpart can be seen as the problem of scheduling selfish jobs on parallel related machines and is the dual of the problem of scheduling (unselfish) jobs on parallel selfish machines studied by Archer and Tardos [2001]. Koutsoupias and Papadimitriou studied an “anarchic” scenario in which each user chooses his/her own link, and this may produce Nash equilibria of cost Ω(log m/log log m) times the optimum. Our mechanism design counterpart is a possible way of reducing the effect of selfish behavior via suitable incentives to the agents (i.e., taxes for using the links). We indeed show that in the resulting game, it is possible to guarantee an approximation factor of 8 for any number of links/machines (this solution also works for online settings). However, it remains impossible to guarantee arbitrarily good approximate solutions, even for 2 links/machines and even if the allocation algorithm is allowed superpolynomial time. This result shows that our scheduling problem with selfish jobs is more difficult than the scheduling problem with selfish machines by Archer and Tardos (which admits exact solutions). We also study some generalizations of this basic problem.