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 resources 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 to induce each user to truth-fully 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 the optimal) allocations and an agent could misreport his/her information so 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 o