Chaos in learning a simple two-person game

Most work in game theory and economics involves the assumption of perfect rationality. In this case, it is natural to characterize a game in terms of its Nash equilibria, at which neither player can achieve better performance by modifying her/his strategy. Under the more realistic assumption that the players are only boundedly rational and must learn their strategies, everything becomes more complicated. Under-learning the strategies may fail to converge to a Nash equilibrium (1) or may even be chaotic (2). Thus, understanding the learning dynamics is essential (3). Here we give an example of an elementary two-person game in which a standard learning procedure leads to Hamiltonian chaos. This example extends earlier work finding chaotic attractors in dissipative game dynamics (4). We argue that chaos is a necessary condition for intelligent adaptive players to fail to converge to a Nash equilibrium (for some related work, see ref. 5).

A good example is the game of rock–paper–scissors: rock beats scissors, paper beats rock, scissors beats paper. With possible relabelings of the three possible moves, such as “earwig–man–elephant,” this ancient game is played throughout the world (6). To allow players to use their “skill,” it is often played repeatedly. In contrast, two-game theorists who practice what they preach would play with the skill-free Nash equilibrium mixed strategy, which is to choose the three possible moves randomly with equal probability. (In game theory, a mixed strategy is a random combination of the pure strategies—here, rock, paper, and scissors.) On average, the Nash equilibrium mixed strategy for rock–paper–scissors has the advantage that no strategy can beat it but it also has the disadvantage that there is no strategy that it can beat. An inspection of the World Rock–Paper–Scissors Society web site (http://www.worldrps.com/gbasics.html) suggests that members of this society do not play the Nash equilibrium strategy. Instead, they use psychology to try to anticipate the moves of the other player or particular sequences of moves to try to induce responses in the other player. At least for this game, it seems that real people do not learn to act like the rational agents studied in standard game theory.

A failure to converge to a Nash equilibrium under learning can happen, for example, because the dynamics of the trajectories of the evolving strategies in the space of possibilities are chaotic. Chaos has been observed in games with spatial interactions (7) or in games based on the single-population replicator equation (4, 8). In the latter examples, players are drawn from a single population and the game is repeated only in a statistical sense, i.e., the players' identities change in repeated trials of the game.

The example we present here demonstrates Hamiltonian chaos in a two-person game, in which each player learns her/his own strategy. We observe this for a zero-sum game, i.e., one in which one player's win is always the other's loss. The observation of chaos is particularly striking because of the simplicity of the game. Because of the zero-sum condition the learning dynamics have a conserved quantity with a Hamiltonian structure (9) similar to that of physical problems, such as celestial mechanics. There are no attractors, and trajectories do not approach the Nash equilibrium. Because of the Hamiltonian structure, the chaos is particularly complex, with chaotic orbits finely interwoven between regular orbits; for an arbitrary initial condition it is impossible to say a priori which type of behavior will result. When the zero-sum condition is violated we observe other complicated dynamical behaviors, such as heteroclinic orbits with chaotic transients. As discussed in the conclusions, the presence of chaos is important because it implies that it is not trivial to anticipate the behavior of the other player. Thus, under chaotic learning dynamics even intelligent adaptive agents may fail to converge to a Nash equilibrium.

We investigate a game involving two players. At each move the first player chooses from one of m possible pure strategies (moves) with frequency x = (x₁, x₂, …, x_n), and similarly the second player chooses from one of n possible pure strategies with frequency y = (y₁, y₂, …, y_m). The players update x and y based on past experience by using reinforcement learning. Behaviors that have been successful are reinforced, and those that have been unsuccessful are repressed. In the continuous time limit where the change in x and y on any given time step goes to zero under some plausible assumptions, it is possible to show (11) that reinforcement learning dynamics are described by the coupled replicator equations (see Notes) of the formwhere A and B are the payoff matrices for the first and second players, respectively.

The relation of these equations to reinforcement learning is very intuitive. Consider the first equation, which describes the updating of the strategies of the first player: The frequency of strategy i increases proportional to [current frequency (x_i)] times [average performance relative to the mean]. (Ay)_i is the performance of strategy i (averaged over the second player's possible moves), and xAy is the performance averaged over all m strategies of the first player. The second equation is similar.

We investigate the dynamics of a generalized rock–paper–scissors game whose payoff matrices arewhere −1 < ɛ_x < 1 and −1 < ɛ_y < 1 are the payoffs when there is a tie. We place these bounds on ɛ because when they are violated, the behavior under ties dominates, and this more closely resembles a matching-pennies-type game with three strategies. We have placed the columns in the order “rock,” “paper,” and “scissors.” For example, reading down the first column of A, in the case that the opponent plays “rock,” we see that the payoff for using the pure strategy “rock” is ɛ_x, “paper” is 1, and “scissors” is −1.

The rock–paper–scissors game exemplifies a class of games where no strategy is dominant and no pure-strategy Nash equilibrium exists (any pure strategy is vulnerable to another). An example of a possible application is two broadcasting companies competing for the same time slot when preferences of the audience are context-dependent. Suppose, for example, that the audience prefers sports to news, news to drama, and drama to sports. If each broadcasting company must commit to their schedule without knowing that of their competitor, then the resulting game is of this type.

We consider the general case that a tie is not equivalent for both players, i.e., ɛ_x ≠ ɛ_y. In the example above, this symmetry would be true if the audience believes that within any given category one company's programming is superior to the other. If the size of the audience is fixed, so that one company's gain is the other's loss, this is a zero-sum game corresponding to the condition ɛ_x = −ɛ_y = ɛ. In general, Eqs. 1 and 2 form a conservative system, which cannot have an attractor. If in addition A = −B^t, it is known that the dynamics are Hamiltonian (9). This is a stronger condition, as it implies the full dynamical structure of classical mechanics, with pairwise conjugate coordinates obeying Liouville's theorem.

To visualize the behavior of this system, in Fig. 1 we show Poincaré sections of Eqs. 1 and 2 with the initial conditions (x₁, x₂, x₃, y₁, y₂, y₃) = (0.5, 0.01k, 0.5 − 0.01k, 0.5, 0.25, 0.25) with k = 1, 2, … , 25. This is a sample of points where the trajectories intersect the hyperplane x₂ − x₁ + y₂ − y₁ = 0. When ɛ = 0, our simulation indicates that the system is integrable, and trajectories are confined to quasi-periodic tori. When ɛ > 0, however, this is no longer guaranteed. As we vary ɛ from 0 to 0.5 without changing initial conditions, some tori collapse and become chaotic, and the trajectories cover a larger region of the strategy space. Regular and chaotic trajectories are finely interwoven; for typical behavior of this type, there is a regular orbit arbitrarily close to any chaotic orbit (12).

To demonstrate that these trajectories are indeed chaotic, we numerically compute Lyapunov exponents, which can be viewed as generalizations of eigenvalues that remain well defined for chaotic dynamics. Positive values indicate directions of average local exponential expansion, and negative values indicate local exponential contraction. Some examples are given in Table 1. The largest Lyapunov exponents are clearly positive for the first three initial conditions when ɛ = 0.25 and for the first four initial conditions when ɛ = 0.5. An indication of the accuracy of these computations can be obtained by comparing to known cases: because of the conservation condition the four exponents always sum to zero; because of the special nature of motion along trajectories plus the Hamiltonian condition the second and third are always zero; and when ɛ = 0, because the motion is integrable, all Lyapunov exponents are exactly zero.

As mentioned already, this game has a unique Nash equilibrium when all responses are equally likely, i.e., x \begin{equation*}{\mathrm{_{1}^{^{*}}}}\end{equation*} = x \begin{equation*}{\mathrm{_{2}^{^{*}}}}\end{equation*} = x \begin{equation*}{\mathrm{_{3}^{^{*}}}}\end{equation*} = y \begin{equation*}{\mathrm{_{1}^{^{*}}}}\end{equation*} = y \begin{equation*}{\mathrm{_{2}^{^{*}}}}\end{equation*} = y \begin{equation*}{\mathrm{_{3}^{^{*}}}}\end{equation*} = 1/3. It is possible to show that all trajectories have the same payoff as the Nash equilibrium on average (13). However, there are significant deviations from this payoff on any given step, which are larger than those of the Nash equilibrium. Thus, a risk averse agent would prefer the Nash equilibrium to a chaotic orbit.

The behavior of the non-zero sum game is also interesting and unusual. When ɛ_x + ɛ_y < 0 (e.g., ɛ_x = −0.1, ɛ_y = 0.05), the motion approaches a heteroclinic cycle, as shown in Fig. 2.

Players switch between pure strategies in the order rock → paper → scissors. The time spent near each pure strategy increases linearly with time. This dynamics is in contrast to analogous behavior in the standard single-population replicator model, which increases exponentially with time. When ɛ_x + ɛ_y > 0 (e.g., ɛ_x = 0.1, ɛ_y = −0.05), as shown in Fig. 3, the behavior is similar, except that the time spent near each pure strategy varies irregularly. The orbit is an infinitely persistent chaotic transient (14).

The emergence of chaos in learning in such a simple game illustrates that rationality may be an unrealistic approximation even in elementary settings. Chaos provides an important self-consistency condition. When the learning of her/his opponent is regular, any agent with even a crude ability to extrapolate can exploit this to improve performance. Nonchaotic learning trajectories are symptomatic that the learning algorithm is too crude to represent the behavior of a human agent. When the behavior is chaotic, however, extrapolation is difficult, even for intelligent humans. Hamiltonian chaos is particularly complex, because of the lack of attractors and the fine interweaving of regular and irregular motion. This situation is compounded for high dimensional chaotic behavior, because of the “curse of dimensionality” (15). In dimensions greater than about five, the amount of data an “econometric” agent would need to collect to build a reasonable model to extrapolate the learning behavior of her/his opponent becomes enormous. For games with more players it is possible to extend the replicator framework to systems of arbitrary dimension (Y.S. and J. P. Crutchfield, unpublished observations). It is striking that low dimensional chaos can occur even in a game as simple as the one we study here. The phase space of this game is four dimensional, which is the lowest dimension in which continuous dynamics can give rise to Hamiltonian chaos. In more complicated games in higher dimensional-state spaces we expect that chaos becomes even more common.

Many economists have noted the lack of any compelling account of how agents might learn to play a Nash equilibrium (16). Our results strongly reinforce this concern (see Notes), in a game simple enough for children to play. That chaos can occur in learning such a simple game indicates that one should use caution in assuming that real people will learn to play a game according to a Nash equilibrium strategy.

We thank Sam Bowles, Jim Crutchfield, Mamoru Kaneko, Paolo Patelli, Cosma Shalizi, Spyros Skouras, Isa Spoonheim, Jun Tani, and Eduardo Boolean of the World Rock–Paper–Scissors Society for useful discussions. This work was supported by the Special Postdoctoral Researchers Program at The Institute of Physical and Chemical Research (Japan); and by grants from the McKinsey Corporation, Bob Maxfield, Credit Suisse, and Bill Miller.