Abstract
Let n atomic players be routing their unsplitable flow on m resources. When each player has the option to drop her current resource and select a better one, and this option is exercised sequentially and unilaterally, then a Nash Equilibrium (NE) will be eventually reached. Acting sequentially, however, is unrealistic in large systems. But, allowing concurrency, with an arbitrary number of players updating their resources at each time point, leads to an oscillation away from NE, due to big groups of players moving simultaneously and due to non-smooth resource cost functions. In this work, we validate experimentally simple concurrent protocols that are realistic, distributed and myopic yet are scalable, require only information local at each resource and, still, are experimentally shown to quickly reach a NE for a range of arbitrary cost functions.
The 2nd and 3rd author were partially supported by the IST Program of the European Union under contract number IST-015964 (AEOLUS).
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Babaoglu, O., Canright, G., Deutsch, A., Di Caro, G.A., Ducatelle, F., Gambardella, L.M., Ganguly, N., Jelasity, M., Montemani, R., Urnes, T.: Design Patterns from Biology for Distributed Computing. ACM Transactions on Autonomous and Adaptive Systems 1(1), 26–66 (2006)
Barford, P., Crovella, M.: Generating representative web workloads for network and server performance evaluation. In: SIGMETRICS, pp. 151–160 (1998)
Berenbrink, P., Friedetzky, T., Goldberg, L.A., Goldberg, P., Hu, Z., Martin, R.: Distributed selfish load balancing. In: SODA 2006: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pp. 354–363. ACM Press, New York, NY, USA (2006)
Berenbrink, P., Friedetzky, T., Hu, Z.: A new analytical method for parallel, diffusion-type load balancing. In: Proc. of the 20th International Parallel and Distributed Processing Symposium (IPDPS) (2006)
Chien, S., Sinclair, A.: Convergece to Approximate Nash Equilibria in Congestion Games. In: Proc. of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA 2007) (to appear, 2007)
Christodoulou, G., Mirrokni, V.S., Sidiropoulos, A.: Convergence and approximation in potential games. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol. 3884, pp. 349–360. Springer, Heidelberg (2006)
Cybenko, G.: Dynamic Load Balancing for Distributed Memory Multiprocessors. Journal of Parallel Distributed Computing 7(2), 279–301 (1989)
Even-Dar, E., Kesselman, A., Mansour, Y.: Convergence Time to Nash Equilibria. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 502–513. Springer, Heidelberg (2003)
Even-Dar, E., Mansour, Y.: Fast convergence of selfish rerouting. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pp. 772–781 (2005)
Fabrikant, A., Papadimitriou, C., Talwar, K.: The Complexity of Pure Nash Equilibria. In: Proc. of the 36th ACM Symp. on Theory of Computing (STOC 2004), pp. 604–612 (2004)
Fotakis, D., Kaporis, A.C., Spirakis, P.G.: Atomic congestion games: Fast, myopic and concurrent. In: Proceedings of the 1st International Symposium on Algorithmic Game Theory (SAGT) (to appear, 2008)
Ghosh, B., Muthukrishnan, S.: Dynamic load balancing in parallel and distributed networks by random matchings. In: Proc. of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 220–225 (1994)
Goemans, M.X., Mirrokni, V.S., Vetta, A.: Sink equilibria and convergence. In: FOCS, pp. 142–154 (2005)
Goldberg, P.W.: Bounds for the convergence rate of randomized local search in a multiplayer load-balancing game. In: Proc. of the twenty-third annual ACM symposium on Principles of distributed computing (PODC 2004), pp. 131–140. ACM Press, New York, NY, USA (2004)
Ieong, S., McGrew, R., Nudelman, E., Shoham, Y., Sun, Q.: Fast and compact: A simple class of congestion games. In: AAAI, pp. 489–494 (2005)
Koutsoupias, E., Papadimitriou, C.: Worst-case Equilibria. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 404–413. Springer, Heidelberg (1999)
Libman, L., Orda, A.: Atomic resource sharing in noncooperative networks. Telecommunication Systems 17(4), 385–409 (2001)
Mirrokni, V.S., Vetta, A.: Convergence issues in competitive games. In: APPROX-RANDOM, pp. 183–194 (2004)
Orda, A., Rom, R., Shimkin, N.: Competitive routing in multiuser communication networks. IEEE/ACM Transactions on Networking 1(5), 510–521 (1993)
Rosenthal, R.W.: A Class of Games Possessing Pure-Strategy Nash Equilibria. International Journal of Game Theory 2, 65–67 (1973)
Valiant, G., Roughgarden, T.: Braess’s paradox in large random graphs. In: EC 2006: Proceedings of the 7th ACM conference on Electronic commerce, pp. 296–305. ACM Press, New York, NY, USA (2006)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kalles, D., Kaporis, A.C., Spirakis, P.G. (2008). Myopic Distributed Protocols for Singleton and Independent-Resource Congestion Games. In: McGeoch, C.C. (eds) Experimental Algorithms. WEA 2008. Lecture Notes in Computer Science, vol 5038. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-68552-4_14
Download citation
DOI: https://doi.org/10.1007/978-3-540-68552-4_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-68548-7
Online ISBN: 978-3-540-68552-4
eBook Packages: Computer ScienceComputer Science (R0)