Impact of Asynchrony on the Behavior of Rational Selfish Agents

• Autorzy: Ilcinkas D. , Pelc A.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

selfish agent; Nash equilibrium; asynchronous game

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 82, nr 1-2
• Strony: 113--125
• Opis fizyczny: bibliogr. 14 poz., tab.

Twórcy

autor

Ilcinkas D.

autor

Pelc A.

• Department d'Informatique, Université du Quebec en outaouais, Gatineau, Quebec J8X 3X7, Canada,

Bibliografia

• [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., Vő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.
• [9] Moscibroda T., Schmid S.,Wattenhofer R.: When selfish 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.
• [11] Osborne M.J.: An introduction to game theory, Oxford University Press, 2004.
• [12] Osborne M.J., Rubinstein A.: A Course in Game Theory, MIT Press, 2000.
• [13] Papadimitriou C.: Algorithms, games and the Internet, Proc. 33rd ACM Symposium on Theory of Computing (STOC), 2001, 749-753.
• [14] von Neumann J., Morgenstern O.: Theory of games and economic behavior, Princeton University Press, 1944.