CUBO A Mathematical Journal Vol.11, No¯ 02, (7–13). May 2009 N-Person Games with Crossing Externalities Miklos N. Szilagyi Department of Electrical & Computer Engineering, University of Arizona, Tucson, AZ 85721-0104 email: szilagyi@ece.arizona.edu ABSTRACT We report computer simulation experiments based on our agent-based simulation tool to model uniform N -person games with crossing payoff functions for the case when the agents are greedy simpletons who imitate the action of that of their neighbors who received the highest payoff for its previous action. The payoff (reward/penalty) functions are given as two straight lines: one for the cooperators and another for the defectors. The payoff curves are functions of the ratio of cooperators to the total number of agents. Even if the payoff functions are linear, four free parameters determine them. In this investigation only crossing payoff functions are considered. We have investigated the behavior of the agents systematically. The results show that the solutions are non-trivial and in some cases quite irregular. They show drastic changes in case of the Leader Game in the narrow parameter range of 1.72 ≤ P ≤ 1.75. This behavior is similar to that observed by [3] for the N -person Chicken Game. Irregular solutions were also found for the Reversed Stag Hunt Game. 8 Miklos N. Szilagyi CUBO 11, 2 (2009) RESUMEN Nosotros reportamos experimentos de simulación de ordenadores basados en nuestra herramienta de simulación agent-based para el modelo de juegos N -personas uniforme con funciones “crossing payoff” para el caso cuando los agentes son “greedy simpletons” los cuales imitan la acción de que sus vecinos quienes recibieron alto pago por sus acciones previas. Las funciones de pago (recompenza/castigo) son dadas como dos lineas rectas: una para los cooperadores y otra para opositores. Las curvas de pago son funciones del radio de cooperadores para el número total de agentes. Incluso si las funciones de pago son lineales, cuatro parametros libres determinan ellas. En esta investigación son consideradas solamente funciones “crossing payoff”. Investigamos sistematicamente el comportamiento de los agentes. Los resultados mues- tran que las soluciones son no-triviales y en algunos casos muy irregulares. Ellas mues- tran cambios drásticos en el caso de juegos lider en el estrecho rango de parametros 1.72 ≤ P ≤ 1.75. Este comportamento es similar al observado por [3] para juegos de N -persons chicken. Soluciones irregulares fueran encontradas para el juego inverso Stag-Hunt. Key words and phrases: Agent-based simulation, cooperation, N -person games. Math. Subj. Class.: 91A06, 91A25. 1 Introduction Externality is an economic term. It refers to actions that are external to a firm’s interests but within the interests of someone else. In N -person game theory externalities refer to the environment of the participating agents. They are the rewards and penalties they receive for their actions. In binary choice games the externalities are the payoff functions that determine these rewards and penalties [1]. There are an infinite variety of N -person games. In a previous paper [2] we listed the 13 most important characteristics that determine a game. In this short review we restrict ourselves to the investigation of uniform games with linear payoff functions only. The agents are considered to be greedy simpletons who imitate the action of that of their neighbors who received the highest payoff for its previous action. We assume that the individual agents may cooperate with each other for the collective interest or may defect, i.e., pursue their selfish interests. Their decisions to cooperate or defect will accumulate over time to produce a result that will determine the success or failure of the given artificial society. CUBO 11, 2 (2009) N -Person Games with Crossing Externalities 9 Figure 1: Payoff (reward/penalty) functions for defectors (D) and cooperators (C). The horizontal axis (x) represents the ratio of the number of cooperators to the total number of agents in the neighborhood; the vertical axis is the payoff provided by the environment. In this case, D(x) = x and C(x) = 0.6 + 0.14x. The broken lines represent the fact that the values C(0) and D(1) are not possible by definition. The payoffs for both choices are similar to those shown in Figure 1. The horizontal axis represents the number of cooperators related to the total number of agents. We assume that the payoffs are linear functions of this ratio x. Point P corresponds to the punishment when all agents defect, point R is the reward when all agents cooperate, T is the temptation to defect when everybody else cooperates, and S is the sucker’s payoff for cooperating when everyone else defects. C(0) and D(1) are impossible by definition, but we will follow the generally accepted notation by extending both lines for the full range of 0 ≤ x ≤ 1 and denoting C(0) = S and D(1) = T that makes it simpler to define the payoff functions. We connect by straight lines point S with point R (cooperators’ payoff function C) and point P with point T (defectors’ payoff function D). Thus the payoff to each agent depends on its choice and on the distribution of other players among cooperators and defectors. The payoff function C(x) is the same for all cooperators and D(x) is the same for all defectors (uniform game). The two lines cross each other at the point xcross. There are 12 different orderings of the values of P, R, S, and T that lead to crossing payoff lines. Each of them represents a different type of game. For the payoff functions shown in Figure 1, for example, we have T > R > S > P which is the case of the Chicken Game. The Chicken Game is the only N -person game with crossing payoff functions that has been inves- tigated in the literature [3]. It has the following properties: 1. Both payoff functions increase with the increasing number of cooperators. 10 Miklos N. Szilagyi CUBO 11, 2 (2009) 2. In the region of low cooperation the cooperators have a higher reward than the defectors. 3. When the cooperation rate is high, there is a higher payoff for defecting behavior than for cooperating behavior. 4. As a consequence, the slope of the D function is greater than that of the C function and the two payoff functions intersect. 5. All agents receive a lower payoff if all defect than if all cooperate. In this short paper we look at other N -person games with crossing payoff functions. For the greedy simpletons only the relative payoffs count; therefore, a thorough investigation is possible. A more detailed treatment of this subject can be found in [4]. 2 Simulation We used our agent-based model developed for simulated social and economic experiments with a large number of decision-makers operating in a stochastic environment [5]. The simulation environment is a two-dimensional array of the participating agents. Its size is limited only by the computer’s virtual memory. The behavior of a few million interacting agents can easily be observed on the computer’s screen. There are two actions available to each agent, and each agent must choose between them (coop- eration or defection). The cooperators and the defectors are initially distributed randomly over the array. In the iterative game the aggregate cooperation proportion changes in time, i.e., over subsequent iterations. At each iteration, every agent chooses an action according to the rewards to its neighbors. The software tool draws the array of agents in a window on the computer’s screen, with each agent in the array colored according to its most recent action. The updating occurs simultaneously for all agents. After a certain number of iterations the proportion of cooperators stabilizes to either a constant value or oscillates around such a value. The experimenter can view and record the evolution of the society of agents as it changes in time. The outcome of the game strongly depends on the ”personalities” of the agents, i.e., on the type of their responses to the environment. The software tool allows for a number of different personalities and their arbitrary combinations. In this work we assume that all agents are greedy simpletons. Throughout this work the total number of agents is 500 · 500 = 250, 000, the initial ratio of cooperators is 50%, and the neighborhood of each agent is one layer deep, i.e., each agent has exactly eight neighbors except those that are situated at the borders of the array. Our free parameters are the four constants P, R, S, and T . They are chosen in such a way that the CUBO 11, 2 (2009) N -Person Games with Crossing Externalities 11 two lines cross each other. We have performed a systematic investigation of games for hundreds of values of these parameters. The global ratio X(t) of the total number of cooperators in the entire array as a function of time (iterations) was observed for all parameter values. (Note that X is different from x that refers to an agent’s immediate neighbors only.) The final ratio of cooperators Xfinal around which X(t) oscillates represents the solution of the game. If at x < xcross the cooperators get a higher payoff than the defectors and at x > xcross the defectors get a higher payoff than the cooperators, then the intersection point xcross of the two payoff functions is a Nash equilibrium for rational players. Indeed, under these conditions at x < xcross the number of cooperators increases and this number decreases when x > xcross. This is, however, not true for the greedy simpletons because x refers to the immediate neighbors only while the final ratio of cooperators Xfinal represents the ratio of the total number of cooperators in the entire array. Let us first find out how the value of Xfinal changes as a function of xcross. To investigate this dependence, we fix the values of the payoff lines’ slopes at R−S = −1 and T −P = 3 and move the two lines so that xcross changes but the payoff value ycross = 2.2 corresponding to xcross remains constant. We expect a monotonically increasing Xfinal(xcross) dependence. The result is shown in Figure 2. Figure 2: The solution of the game Xfinal as a function of xcross The values of (R − S) = −1, (T − P ) = 3, and ycross = 2.2 are fixed. For xcross < 0.2 the solution is total defection and it is overwhelming cooperation for xcross > 0.85. The transition in between these two limiting values, however, is quite interesting. As wee see, in the region 0.75 < xcross < 0.80 the value of Xfinal even decreases as xcross grows. It is interesting to note the transitions between different games as the value of xcross changes. For 12 Miklos N. Szilagyi CUBO 11, 2 (2009) 0 ≤ xcross0.2 we have the Battle of the Sexes Game, for 0.3 ≤ xcross0.7 it is the Benevolent Chicken Game, and for 0.8 ≤ xcross ≤ 1.0 we have the Leader Game. xcross = 0.25 and xcross = 0.75 are borderline cases in between two games. The transitions between games are relatively smooth. Figure 3: Rotating the D(x) function around the intersection point of the two lines xcross = 0.7, ycross = 2.2. C(x) = 2.9 − x. To investigate the role of the relative angle between the two payoff lines, we fix the C(x) function as C(x) = 2.9 − x, the intersection point of the two lines at xcross = 0.7, ycross = 2.2, and rotate the D(x) function around this point (Figure 3). Under these conditions for −10.0 ≤ P ≤ 0.5 we have the Benevolent Chicken Game, for 0.6 ≤ P ≤ 1.8 it is the Leader Game, for 2.0 ≤ P ≤ 2.1 we have the Reversed Benevolent Chicken Game, and for 2.3 ≤ P ≤ 2.9 it is the Reversed Stag Hunt Game. P = 0.56, P = 1.9, and P = 2.2 are borderline cases in between two games. The transitions between games are quite smooth. We present the result of the simulation Xfinal as a function of P in Figure 4. For the region −10.0 ≤ P ≤ −0.6 the result is nearly constant around the value of Xfinal = 0.82. Therefore, we only show the result for the region −1.0 ≤ P ≤ 2.9. Several remarkable features can be immediately noticed. First, neither the Benevolent Chicken nor the Reversed Benevolent Chicken games are sensitive to the rotation of the D(x) function. However, the Leader and the Reversed Stag Hunt games behave quite strangely. The behavior of the Reversed Stag Hunt Game is quite remarkable. At P = 2.275, Xfinal suddenly jumps from 0.66 to 0.80, then rises to 0.83, then at P = 2.394 it has a dip down to 0.76, rises again to 0.81, then at P = 2.4 jumps down to 0.65, rises again and finally at P = 0.525 suddenly CUBO 11, 2 (2009) N -Person Games with Crossing Externalities 13 changes from 0.63 to 0.23, and at P = 2.65 reaches its final value of 0.11. The character of the X(t) function also drastically changes at these points. The X(t) function for P = 2.24 wildly fluctuates in between 0.40 and 0.91 so that Xfinal = 0.65. For P = 2.41, Xfinal = 0.65 again, but there are practically no fluctuations. The graphics outputs are also quite different. Figure 4: The solution of the game Xfinal as a function of P . The D(x) function is rotated around the fixed intersection point. The Leader Game behaves even more strangely. There are several wild fluctuations in between Xfinal = 0.64 and Xfinal = 0.90 in the narrow region of 1.72 ≤ P ≤ 1.75. We found similar behavior in the N -person Chicken Game [3]. Received: May 3, 2008. Revised: June 14, 2008. References [1] Schelling, T.C., Hockey helmets, concealed weapons, and daylight savings, Journal of Con- flict Resolution, 17(3)(1973), 381–428. [2] Szilagyi, M.N., N -person Prisoners’ Dilemmas, Cubo Mathemática Educacional, 5(3)(2003), 469–499. [3] Szilagyi, M.N., Agent-based simulation of the N -person Chicken Game, Advances in Dynam- ical Games (S. Jorgensen, M. Quincampoix, and T.L. Vincent, eds.) 9(2006), 695–703. [4] Szilagyi, M.N. and Somogyi, I., Agent-based simulation of N-person games with crossing payoff functions, Complex Systems, 17(2008), 427–439. [5] Szilagyi, M.N. and Szilagyi, Z.C., A tool for simulated social experiments, Simulation, 74(1)(2000), 4–10. N02-crossing