Johanne Cohen
Abstract
Stabilizing distributed systems expect all the component processes to run predefined programs that are externally mandated. In Internet scale systems, this is unrealistic, since each process may have selfish interests and motives related to maximizing its own payoff. This article formulates the problem of selfish stabilization to show how competition blends with cooperation in a stabilizing environment.
- Arora, A. and Gouda, M. G. 1993. Closure and convergence: a foundation of fault-tolerant computing. IEEE Trans. Softw. Eng. 19, 11, 1015--1027. Google Scholar
Digital Library
- Aumann, R. 1959. Acceptable points in general cooperative n-person games. In Contributions to the Theory of Games IV. Annals of Math. Study.Google Scholar
- Cao, H., Ertin, E., Kulathumani, V., Sridharan, M., and Arora, A. 2006. Differential games in large-scale sensor-actuator networks. In Proceedings of the 5th International Conference on Information Processing in Sensor Networks (IPSN), J. A. Stankovic, P. B. Gibbons, S. B. Wicker, and J. A. Paradiso, Eds. ACM, New York, NY, 77--84. Google ScholarDigital Library
- Cobb, J. A., Gouda, M. G., and Musunuri, R. 2003. A stabilizing solution to the stable path problem. In Self-Stabilizing Systems, S.-T. Huang and T. Herman, Eds. Lecture Notes in Computer Science, vol. 2704. Springer, Berlin, Heidelberg, Germany. 169--183. Google ScholarDigital Library
- Dijkstra, E. W. 1974. Self-stabilizing systems in spite of distributed control. Comm. ACM 17, 11, 643--644. Google ScholarDigital Library
- Dolev, S. 2000. Self-Stabilization. MIT Press. Google ScholarDigital Library
- Dolev, S., Schiller, E., and Spirakis, P. 2006. Game authority: for robust distributed selfish-computer systems. Tech. rep., DELIS. http://delis.upb.de/docs/.Google Scholar
- Griffin, T., Shepherd, F. B., and Wilfong, G. T. 2002. The stable paths problem and interdomain routing. IEEE/ACM Trans. Netw. 10, 2, 232--243. Google ScholarDigital Library
- Halpern, J. 2000. A computer scientist looks at game theory. In Proceedings of the 1st World Congress of the Game Theory Society (GAMES).Google Scholar
- Hoefer, M. 2006. Non-cooperative tree creation. In Proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science (MFCS), R. Kralovic and P. Urzyczyn, Eds. Lecture Notes in Computer Science, vol. 4162. Springer, Berlin, Germany. 517--527. Google ScholarDigital Library
- Huang, S.-T. and Chen, N.-S. 1992. A self-stabilizing algorithm for constructing breadth-first trees. Inf. Process. Lett. 41, 2, 109--117. Google ScholarDigital Library
- Keidar, I., Melamed, R., and Orda, A. 2006. Equicast: scalable multicast with selfish users. In Proceedings of the 25th Annual ACM Symposium on Principles of Distributed Computing (PODC). ACM, New York, NY, 63--71. Google ScholarDigital Library
- Mavronicolas, M., Papadopoulou, V. G., Philippou, A., and Spirakis, P. G. 2005. A graph-theoretic network security game. In Proceedings of the 1st International Workshop on Internet and Network Economics (WINE), X. Deng and Y. Ye, Eds. Lecture Notes in Computer Science, vol. 3828. Springer, Berlin, Germany. 969--978. Google ScholarDigital Library
- Milchtaich, I. 1996. Congestion games with player-specific payoff functions. Games Eco. Behav. 13, 1 (March), 111--124.Google Scholar
- Moscibroda, T., Schmid, S., and Wattenhofer, R. 2006a. On the topologies formed by selfish peers. In Proceedings of the 25th Annual ACM Symposium on Principles of Distributed Computing (PODC). ACM, New York, NY, 133--142. Google ScholarDigital Library
- Moscibroda, T., Schmid, S., and Wattenhofer, R. 2006b. When selfish meets evil: byzantine players in a virus inoculation game. In Proceedings of the 25th Annual ACM Symposium on Principles of Distributed Computing (PODC). ACM, New York, NY, 35--44. Google ScholarDigital Library
- Nash, J. 1950. Equilibrium points in n-person games. In Proceedings of the National Academy of Sciences USA 36, 48--49.Google ScholarCross Ref
- Simon, H. 1982. Models of Bounded Rationality: Vols. 1 and 2. MIT Press.Google Scholar
Index Terms
- An exercise in selfish stabilization
Recommendations
Altruism and Its Impact on the Price of Anarchy
We study the inefficiency of equilibria for congestion games when players are (partially) altruistic. We model altruistic behavior by assuming that player i's perceived cost is a convex combination of αi times his direct cost and αi times the social ...
When selfish meets evil: byzantine players in a virus inoculation game
PODC '06: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computingOver the last years, game theory has provided great insights into the behavior of distributed systems by modeling the players as utility-maximizing agents. In particular, it has been shown that selfishness causes many systems to perform in a globally ...
Efficiency of Non-Truthful Auctions in Auto-bidding: The Power of Randomization
WWW '23: Proceedings of the ACM Web Conference 2023Auto-bidding is now widely adopted as an interface between advertisers and internet advertising as it allows advertisers to specify high-level goals, such as maximizing value subject to a value-per-spend constraint. Prior research has mainly focused on ...
Comments