Abstract
We consider the problem of dynamically reallocating (or re-routing) m weighted tasks among a set of n uniform resources (one may think of the tasks as selfish players). We assume an arbitrary initial placement of tasks, and we study the performance of distributed, natural reallocation algorithms. We are interested in the time it takes the system to converge to an equilibrium (or get close to an equilibrium).
Our main contributions are (i) a modification of the protocol in 2006 that yields faster convergence to equilibrium, together with a matching lower bound, and (ii) a non-trivial extension to weighted tasks.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ackermann, H., Röglin, H., Vöcking, B.: On the impact of combinatorial structure on congestion games. In: FOCS, pp. 613–622 (2006)
Berenbrink, P., Friedetzky, T., Goldberg, L.A., Goldberg, P., Hu, Z., Martin, R.: Distributed selfish load balancing. In: Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), pp. 354–363. ACM SIAM, New York (2006)
Berenbrink, P., Friedetzky, T., Hu, Z.: A new analytical method for parallel, diffusion-type load balancing. In: Proceedings of the 20th IEEE International Parallel and Distributed Processing Symposium (IPDPS06), April 2006, pp. 1–10. IEEE, New York (2006)
Chien, S., Sinclair, A.: Convergence to approximate Nash equilibria in congestion games. In: Proc. of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), New Orleans, Louisiana, pp. 169–178 (2007)
Even-Dar, E., Kesselman, A., Mansour, Y.: Convergence time to Nash equilibria. In: Proc. of the 30th International Colloquium on Automata, Languages and Programming (ICALP), Eindhoven, Netherlands, pp. 502–513 (2003)
Even-Dar, E., Mansour, Y.: Fast convergence of selfish rerouting. In: Proc. of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA), Vancouver, British Columbia, pp. 772–781 (2005)
Fabricant, A., Papadimitriou, C.H., Talwar, K.: The complexity of pure Nash equilibria. In: Proc. of the 36th Annual Symposium on Theory of Computing (STOC), pp. 604–612 (2004)
Fischer, S., Räcke, H., Vöcking, B.: Fast convergence to wardrop equilibria by adaptive sampling methods. In: Proc. of the 38th Annual Symposium on Theory of Computing (STOC), Seattle, WA, pp. 53–662 (2006)
Goldberg, P.: Bounds for the convergence rate of randomized local search in a multiplayer load-balancing game. In: Proc. of the 23rd Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), St. John’s, Newfoundland, pp. 131–140 (2004)
Ieong, S., McGrew, R., Nudelman, E., Shoham, Y., Sun, Q.: Fast and compact: a simple class of congestion games. In: AAAI(2005)
Luby, M., Randall, D., Sinclair, A.J.: Markov chain algorithms for planar lattice structures. SIAM J. Comput. 31, 167–192 (2001)
Mirrokni, V.S., Vetta, A.: Convergence issues in competitive games. In: Proc. of APPROX-RANDOM. LNCS, vol. 3122, pp. 183–194 (2004)
Rosenthal, R.W.: A class of games possessing pure-strategy Nash equilibria. Int. J. Game Theory 2, 65–67 (1973)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Berenbrink, P., Friedetzky, T., Hajirasouliha, I. et al. Convergence to Equilibria in Distributed, Selfish Reallocation Processes with Weighted Tasks. Algorithmica 62, 767–786 (2012). https://doi.org/10.1007/s00453-010-9482-1
Received:
Accepted:
Published:
Issue date:
DOI: https://doi.org/10.1007/s00453-010-9482-1