Impact of Asynchrony on the Behavior of Rational Selfish Agents
Impact of Asynchrony on the Behavior of Rational Selfish Agents
The behavior of rational selfish agents has been classically studied in the framework of strategic games in which each player has a set of possible actions, players choose actions simultaneously and the payoff for each player is determined by the matrix of the game. However, in many applications, players choose actions asynchronously, and simultaneity of this process is not guaranteed: it is possible that a player learns the action of another player before making its choice. Delays of choices are controled by the adversary and each player can only secure the worst-case payoff over the adversary's decisions. In this paper we consider such asynchronous versions of arbitrary two-person strategic games and we study how the presence of the asynchronous adversary influences the behavior of the players, assumed to be selfish but rational. We concentrate on deterministic (pure) strategies, and in particular, on the existence and characteristics of pure Nash equilibria in such games. It turns out that the rational behavior of players changes significantly if the decision process is asynchronous. We show that pure Nash equilibria often exist in the asynchronous version of the game even if there were no such equilibria in the synchronous game. We also show that a mere threat of asynchrony in the game may make social optimum a rational choice while it was not rational in the synchronous game.
[INFO.INFO-GT] Computer Science [cs]/Computer Science and Game Theory [cs.GT], [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Nash equilibrium, asynchronous game, Selfish agent
[INFO.INFO-GT] Computer Science [cs]/Computer Science and Game Theory [cs.GT], [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Nash equilibrium, asynchronous game, Selfish agent
1412
[1] Albers S., Eilits S., Even-Dar E., Mansour Y., Roditty L.: On Nash equilibria for a network creation game, Proc. 17th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2006.
[2] Lynch N.: Distributed Algorithms, Morgan Kaufmann Publ., Inc., 1996.
[3] Czumaj A., Vo¨cking B.: Tight bounds for worst-case equilibria. Proc. 13th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2002, 413-420.
[4] Friedman E.: Asynchronous Learning in Decentralized Environments: A Game Theoretic Approach (2004), in Collectives and the Design of Complex Systems, edited by K. Tumer and D. Wolpert, Springer-Verlag
[5] Friedman E., Shenker S.: Synchronous and asynchronous learning by responsive learning automata, mimeo, 1996.
[6] Friedman E., Shenker S.: Learning and Implementation on the Internet, manuscript 1997.
[7] Koutsoupias E., Papadimitriou C.: Worst-case equilibria. Proc. 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS), LNCS 1563, 1999, 404-413.
[8] Kun A., Boza G., Scheuring I.: Asynchronous snowdrift game with synergistic effect as a model of cooperation, Behavioral Ecology, 17, 2006, 633-641. [OpenAIRE]
[9] Moscibroda T., Schmid S., Wattenhofer R.: When selfich meets evil: Byzantine players in a virus inoculation game, Proc. 25th Annual ACM Symposium on Principles of Distributed Computing (PODC), 2006, 35-44.
[10] Nash J.F., Jr.: Non-cooperative games, Annals of Mathematics, 54, 1951, 286-295.
- 1
- 2