Stochastic Dynamics in Game Theory: comments on some papers by Matteo Marsili and Yi-Cheng Zhang

Margarita Ifti

- Starting point: a theory for economic equilibria. Game Theory.
- Dealing with economics, not with finance. Finance is a dynamical system out of equilibrium, where players speculate on future market's fluctuations.
- Rational behaviour, but deviations from rationality are present. Infinite precision is impossible, if not at infinite cost.
- Similarity with Stat Mech: minimalization of energy-maximization of utility, Nash equilibria-ground states, deviations from rationality-temperature. Leads to a natural definition of stochastic dynamics in Game Theory.
- Use Langevin approach: fluctuations around Nash equilibria in specific games with a large number of players.
Each of the n players can control a continuous variable or "strategy" x_i. His utility function ui depends on his own strategy as well as on others'. Each player continuously adjusts his variable in order to maximize his utility. He also faces stochastic shocks and so his variable becomes a continuous time stochastic process.
Analogy with Statistical Mechanics: - negative utility plays the role of an energy; - stochastic force on a player like that arising from a heat bath; - effects of fluctuations similar to effects of entropy;
Main difference: - In Stat Mech each degree of freedom evolves to minimize a global variable (energy), in Game Theory each degree of freedom maximizes its own (partial) utility.
We focus on a particular class of games with global interaction.
Nash equilibria are stationary points of the dynamics. Two main equilibria exist: i) non-competitive equilibria, where each player's equilibrium strategy is determined by its interactions with the rules of the game, and ii) competitive equilibria, which result from the aggressive competition of each player with all the others.

Game Theory and Evolution

Large number of interacting agents. Each agent has a spectrum of strategies and a utility or payoff function, which depends on the strategy. Game Theory assumes that payoff functions are common knowledge and that each player behaves rationally. Stable states of the system are called Nash Equilibria. A strategy x_i^* is a NE if each player's utility for fixed opponents' strategies, is a maximum for x_i=x_i^*. The NE strategies are then such that no player has incentives to change them, since any change would result in utility loss. Nash showed that each game has at least one such equilibrium.

Cournot Game and Tragedy of the Commons

2 firms produce quantities x₁ and x₂ of a product
Price depends on total quantity produced: P(X)=a-bX
Cost is proportional to x: C=cx_i
Payoff function then: u_i=x_i[P(x₁+x₂)-c]=x_i[a-c-b(x₁+x₂)]
Best response is obtained by maximizing u₁(x₁,x₂) w.r.t. x₁ for fixed x₂.
Leads to $x_1^*=x_2^*\frac{(a-c)}{3b}$.
For n firms, $x_i=x_0=\frac{n}{(n + 1)}$ with payoff $u_i=\frac{n}{(n+1)^2}$
Known as the Tragedy of the Commons: the common resource is almost depleted, and the payoff per player is very small.

Repeated Games and Evolutionary Game Theory

A strategy describes the action each player has to do at each stage. Also, the single stage utility is replaced by a utility which accounts for many stages, usually a discount factor (i.e. an exponential weight function for future utility).
- Replicator dynamics model: in its simplest form, it assumes that the individuals playing a given strategy reproduce at a rate proportional to their utility. Its applications have been limited to two player games, generalisation is very complex. Rationality is not assumed: players keep playing the game the way their ancestors did. Rational NE results from the selective evolution of replicator dynamics.
A simple realistic dynamics with almost rational players is studied.

Langevin dynamics: Langevin equation:

$$\frac {\partial x_i}{\partial t} = \Gamma_i \frac {\partial u_i}{\partial x_i} + \eta_i$$ (1)

where the stochastic term models deviation from perfect rationality.
The first part (deterministic) assumes "local rationality": each agent knows in which direction his utility increases, i.e. they know u_i in a small neighbourhood of x_i. Weakens perfect rationality assumption.
The stochastic term has a part that represents the individual "problems" (e.g. illness) and the global ones (e.g. earthquake). Hence the correlation of the stochastic terms is taken:

$$\Delta_{i,j} = D_i \delta_{i,j} + D_0$$ (2)

The Langevin approach includes "thermal" fluctuations, allowing to analyse the stability of NE. Also, it gives a "free energy" measure, which enables us to distinguish the real "ground state" from "metastable" states. Curiously, in an ideally slow cooling down only the state with the smallest "free energy" is selected, independently of the initial conditions! (in the evolutionary approach the final state is uniquely determined by the initial conditions).

The Model

Always focusing on global interactions, consider situations where the payoff function for player i is: u_i(x_i,x_-i)=-B(x_i,<x>) with $<x>=\frac{x_1+...x_n}{n}$
Because of the symmetry of the interaction, the NE are symmetric: x_i^* = x^* for all i, and x^* satisfies the equation

$$\frac {\partial u_i}{\partial x_i}(eq) = -B_{0,1}(x^*,x^*)- \frac {1}{n} B_{0,1}(x^*,x^*)=0$$ (3)

where for convenience we have defined

$$B_{j,k}(x,y)= \frac{\partial^j}{\partial x^j} \frac{\partial^k}{\partial y^k} B(x,y)$$ (4)

and B_0,0(x,y)=B(x,y).
Also, a NE must be a maximum w.r.t x_i, i.e.

$$\frac {\partial^2 u_i}{\partial x_i^2} (eq) = -B_{2,0}(x^*,x^... ...}{n^2} B_{1,1} (x^*,x^*) - \frac{1}{n^2} B_{0,2}(x^*,x^*) < 0$$ (5)

We can always choose x^*=0 (if not, a linear transformation will do). Also choose B(0,0)=0. Expanding the deterministic part to the leading order, we arrive to the equation:

$$\frac {\partial x}{\partial t} = - \Gamma_i \sum {(g \delta_{i,j} + \frac {h}{n}) x_j} + \eta_i$$ (6)

where

$$g=B_{2,0}(0,0)+\frac{1}{n}B_{1,1}(0,0)$$ (7)

and

$$h=B_{1,1}(0,0) + \frac {1}{n}B_{0,2}(0,0)$$ (8)

Stability requires that all the eigenvalues of the matrix

$$G_{i,j}= \Gamma_i ( g \delta_{i,j} + \frac {h}{n})$$ (9)

be positive. These are given by the equation:

$$\frac {1}{n} = \frac {1}{h} \sum\frac{\Gamma_k}{\lambda - g \Gamma_k}$$ (10)

But if g > 0, and h + g > 0, all the eigenvalues are positive.
The equation above is a multivariate Ornstein-Uhlenbeck process. Fluctuations around the NE are described by the matrix of correlations. The correlation functions decay exponentially, with correlation time given by the minimum eigenvalue.
After some algebra, we find that the average utility is:

$$<u>=- \frac {1}{2} <\sigma> B_{2,0} - \frac {<v>}{n} B_{1,1} - \frac {<v>}{2n} B_{0,2}$$ (11)

with

$$<v>= \frac {<D> + n D_0}{g + h}$$ (12)

The last term is the average utility at the NE in presence of fluctuations. This would be the utility of a player who maintains the NE strategy x_i=0 even in presence of fluctuations. It is interesting to note that it is possible to get an average utility larger than those for NE strategy. Loosely speaking, it means that in a game with random deviations from rationality, player who are affected by the randomness may happen to receive a higher payoff (in average) than those who behave rationally (x_i=0). It pays to be stupid sometimes! The condition for this to happen is

$$\frac {1}{2} < \sigma > B_{2,0} + \frac {<v>}{n} B_{1,1} < 0$$ (13)

As expected, the fluctuations grow with D_i and D₀. There are three qualitatively different cases, as shown in figure 2: a) when B_2,0, B_1,1 and B_0,2 are all finite and positive. We have a normal behaviour with small fluctuations. Fluctuations increase the average utility and a rational behaviour is generally more rewarding. b) $B_{2,0} \approx 0$, B_1,1 and B_0,2 are finite and positive. Then g is small and the fluctuations are proportional to n. Generally B_2,0 = 0 is typical of competitive equilibria. Indeed it means that each player does not feel the effects of change in their x_i directly. Rather they are transmitted through the change on the global variable <x>. Large fluctuations come together with large relaxation times. Finally, the average utility is decreased. c) $B_{2,0} + B_{1,1} \approx 0$ . Also in this case large fluctuations occur, since g + h << 1. The smallest eigenvalue is small, and this means large correlation time. Only one eigenvalue is small in this case, unlike case b). Also, x_i fluctuate in phase, thus yielding a large fluctuation of their sum. Finally, the fluctuations may decrease the average utility in this case. Furthermore, a player who behaves rationally receives a smaller payoff for sure! Expansion to higher order shows that the fluctuations experienced by a player are smaller the faster his dynamics (acceptable intuitively).

Conclusions

- Competitive Nash equilibria are usually affected by very large fluctuations, which increase with the number of players. Competition leads to broad distributions and large inequalities in an economic system. This is reminiscent of Pareto Law of distribution of incomes. Inequalities increase with the number of players. - Competitive equilibria are also characterized by large relaxation times, which are proportional to n, and by a negative correlation between players' strategies. This means that two players tend to have opposite fluctuations around Nash Equilibrium. - At odd with Stat Mech, where fluctuations always increase the energy of the system, in a game theoretical system, under particular conditions, fluctuations increase the utility (i.e. decrease the energy). - Fluctuations, in general displace NE, and in some cases, for strong randomness, a NE can disappear. Return to title page.