Routing selfish unsplittable traffic

ABSTRACT

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.

REFERENCES

• 1: A. Archer , É. Tardos, Truthful Mechanisms for One-Parameter Agents, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.482, October 14-17, 2001
• 2: James Aspnes , Yossi Azar , Amos Fiat , Serge Plotkin , Orli Waarts, On-line routing of virtual circuits with applications to load balancing and machine scheduling, Journal of the ACM (JACM), v.44 n.3, p.486-504, May 1997 [doi>10.1145/258128.258201]
• 3: Auletta, V., De Prisco, R., Penna, P., and Persiano, G. 2005. On designing truthful mechanisms for online scheduling. In Proceedings of the 12th International Colloquium on Structural Information and Communication Complexity (SIROCCO), Mont Saint-Michel, France, May 24--26. Lecture Notes in Computer Science, vol. 3499. Springer, 3--17.
• 4: Christodoulou, G., Koutsoupias, E., and Nanavati, A. 2004. Coordination mechanisms. In Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP), Turku, Finland, Jul. 12--16. Lecture Notes in Computer Science, vol. 3142. Springer, 345-- 357.
• 5: Clarke, E. H. 1971. Multipart pricing of public goods. Public Choice 11, 1 (Sept.), 17--33.
• 6: Cominetti, R., Correa, J. R., and Stier-Moses, N. 2006. Network games with atomic players. In Proceedings of the 33rd International Colloquium on Automata, Languages and Programming (ICALP), Venice, Jul. 10--14. Lecture Notes in Computer Science, vol. 4052. Springer, 525--536.
• 7: Artur Czumaj , Berthold Vöcking, Tight bounds for worst-case equilibria, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.413-420, January 06-08, 2002, San Francisco, California
• 8: Even-Dar, E., Kesselman, A., and Mansour, Y. 2003. Convergence time to Nash equilibria. In Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP), Eindhoven, The Netherlands, Jun. 30--Jul. 4. Lecture Notes in Computer Science, vol. 2719. Springer, 502--513.
• 9: Feldmann, R., Gairing, M., Luecking, T., Monien, B., and Rode, M. 2003. Nashification and the coordination ratio for a selfish routing game. In Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP), Eindhoven, The Netherlands, Jun. 30--Jul. 4. Lecture Notes in Computer Science, vol. 2719. Springer, 514--526.
• 10: Ferrante, A., and Parente, M. 2004. Existence of Nash equilibria in selfish routing problems. In Proceedings of the 11th International Colloquium on Structural Information and Communication Complexity (SIROCCO), Smolenice Castle, Slowakia, Jun. 21--23. Lecture Notes in Computer Science, vol. 3104. Springer, 149--160.
• 11: Dimitris Fotakis , Spyros C. Kontogiannis , Elias Koutsoupias , Marios Mavronicolas , Paul G. Spirakis, The Structure and Complexity of Nash Equilibria for a Selfish Routing Game, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.123-134, July 08-13, 2002
• 12: Fotakis, D., Kontongiannis, S., and Spirakis, P. 2006. Atomic congestion games among coalitions. In Proceedings of the 33rd International Colloquium on Automata, Languages and Programming (ICALP), Venice, Jul. 10--14. Lecture Notes in Computer Science, vol. 4052. Springer, 572--583.
• 13: Graham, R. 1969. Bound on multiprocessor timing anomalies. SIAM J. Appl. Math. 17, 416--429.
• 14: Groves, T. 1973. Incentive in teams. Econometrica 41, 617--631.
• 15: Ara Hayrapetyan , Éva Tardos , Tom Wexler, The effect of collusion in congestion games, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132529]
• 16: Dorit S. Hochbaum , David B. Shmoys, Using dual approximation algorithms for scheduling problems theoretical and practical results, Journal of the ACM (JACM), v.34 n.1, p.144-162, Jan. 1987 [doi>10.1145/7531.7535]
• 17: Koutsoupias, E., Mavronicolas, M., and Spirakis, P. 2003. Approximate equilibria and ball fusion. TOCS 36, 683--693.
• 18: Koutsoupias, E., and Papadimitriou, C. 1999. Worst-Case equilibria. In Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science (Trier, Germany, Mar. 4--6). Lecture Notes in Computer Science, vol. 1563. Springer, 404--413.
• 19: Marios Mavronicolas , Paul Spirakis, The price of selfish routing, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.510-519, July 2001, Hersonissos, Greece [doi>10.1145/380752.380846]
• 20: Myerson, R. 1981. Optimal auction design. Math. Oper. Res. 6, 58--73.
• 21: Noam Nisan , Amir Ronen, Algorithmic mechanism design (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.129-140, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301287]
• 22: Noam Nisan , Amir Ronen, Computationally feasible VCG mechanisms, Proceedings of the 2nd ACM conference on Electronic commerce, p.242-252, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352898]
• 23: Osborne, M., and Rubinstein, A. 1994. A Course in Game Theory. MIT Press, Cambridge, MA.
• 24: T. Roughgarden, Designing Networks for Selfish Users is Hard, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.472, October 14-17, 2001
• 25: Tim Roughgarden, Selfish routing with atomic players, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 26: T. Roughgarden , E. Tardos, How bad is selfish routing?, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.93, November 12-14, 2000
• 27: Vickrey, W. 1961. Counterspeculation, auctions and competitive sealed tenders. J. Finance, 8--37.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms

Keywords:
Algorithmic mechanism design, Nash equilibrium, scheduling, selfish routing