From Nash to Cournot–Nash equilibria via the Monge–Kantorovich problem

1. Introduction

Since the seminal work of Nash [1], the notion of Nash equilibrium for N-person games has become the key concept to analyse strategic interaction situations and plays a major role not only in economics, but also in biology, computer science, etc. The existence of Nash equilibria generally relies on a non-constructive fixed-point argument as in the original work of Nash. They are therefore generally hard to compute, especially for a large number of players. A traditional question in game theory and theoretical economics is whether the analysis of equilibria simplifies as the number N of players becomes so large that one can use models with a continuum of agents. Indeed, since Aumann's seminal works [2,3] models with a continuum of agents have occupied a distinguished position in economics and game theory. The challenging new theory of mean-field games of Lasry & Lions [4–6] sheds some new light on this issue and has renewed interest in the rigorous derivation of continuum models as the limit of models with N players, letting N tend to infinity. Mean-field games theory addresses complex dynamic situations (stochastic differential games with a large number of players), and in the sequel we consider only simpler static situations.

Schmeidler [7] introduced a notion of non-cooperative equilibrium in games with a continuum of agents, having in mind such diverse applications as elections, many small buyers from a few competing firms and drivers that can choose among several roads. Mas-Colell [8] reformulated Schmeidler's analysis in a framework that presents great analogies with the Monge–Kantorovich optimal transport problem. Indeed, in Mas-Colell's formulation, players are characterized by some type (productivity, tastes, wealth, geographical position, etc.), whose probability distribution μ is given. Each agent has to choose a strategy so as to minimize a cost that not only depends on her type, but also on the probability distribution of strategies resulting from the behaviour of the rest of the population. A Cournot–Nash equilibrium then is a joint probability distribution of types and strategies with first marginal μ (given) and second marginal ν (unknown) that is concentrated on cost-minimizing strategies. The difficulty of the problem lies in the fact that the cost depends on ν. For relevant applications, this dependence can be quite complex, because there may be both attractive (mimetism) and repulsive (congestion) effects in the cost.

Another situation where one looks for joint probabilities (or couplings) is the optimal transport problem of Monge–Kantorovich. In the Monge–Kantorovich problem, one is given two probability spaces (Θ,μ) and (X,ν), and a transport cost c, and one looks for the cheapest way to transport μ to ν for the cost c. In Monge's original formulation, one looks for a transport T between μ and ν, i.e. a measurable map from Θ to X such that T_#μ=ν, where T_#μ denotes the image of μ by T, i.e.

that minimizes the total transport cost Because there may exist no transport map between μ and ν, and the mass conservation constraint, T_#μ=ν is highly nonlinear, Kantorovich relaxed Monge's formulation in the 1940s by considering the notion of transport plan (that allows mass splitting and therefore convexifies Monge's problem). A transport plan between μ and ν is by definition a joint probability measure on Θ×X having μ and ν as marginals. Denoting by Π(μ,ν) the set of transport plan between μ and ν, the least cost of transporting μ to ν for the cost c then is the value of the Monge–Kantorovich optimal transport problem: In the case where we have as same source and target space a compact metric space X with distance d_X, the previous definition defines the usual 1-Wasserstein metric, : which is well-known to metrize the weak-* topology. We refer the reader to the textbooks of Villani [9,10] for a detailed exposition of optimal transport theory.

The purpose of the present article is twofold:

	— emphasize the role of optimal transport theory as a simple but powerful tool to obtain rigorous passage from Nash to Cournot–Nash as the number of players tends to infinity (see theorem 4.2),
	— give an account of [11,12] which identifies some classes of games with a continuum of players for which Cournot–Nash equilibria can be characterized, thanks to optimal transport and actually computed numerically in some non-trivial situations.

The paper is organized as follows. Section 2 recalls the classical results of Nash regarding equilibria for N-person games. In §3, we define Cournot–Nash equilibria in the framework of games with a continuum of agents. In §4, we give asymptotic results concerning the convergence of Nash equilibria to Cournot–Nash equilibria as the number of players tends to infinity. In §5, we give an account on recent results from [11,12] which enable one to find Cournot–Nash equilibria using tools from optimal transport and perform numerical simulations.

2. Nash equilibria

An N-person game, consists of a set of N players i∈{1,…,N}, each player i has a strategy space X_i, setting

and for x∈X, setting x=(x_i,x_−i)∈X=X_i×Π_j≠iX_j, the cost function of player i is a function In this classical setting, a Nash equilibrium is defined as follows:

Definition 2.1 (Nash equilibrium)

A Nash equilibrium is a collection of strategies such that, for every i∈{1,…,N} and every x_i∈X_i, one has

The fundamental theorem of Nash states the following existence result for Nash equilibria:

Theorem 2.2 (Existence of Nash equilibria)

If

	— Xi is a convex compact subset of some locally convex Hausdorff topological vector space,
	— for every i∈{1,…,N}, Ji is continuous on and for every x−i∈X−i, Ji(.,x−i) is quasi-convex on Xi,

then there exists at least one Nash equilibrium.

Because the convexity assumptions in the theorem above are quite demanding (and rule out the case of finite games, i.e. the case of finite strategy spaces X_i), Nash also introduced the mixed strategy extension. A mixed strategy for player i is by definition probability measure and given a profile of mixed strategies , the cost for player i reads

A Nash equilibrium in mixed strategies then is a Nash equilibrium for the mixed strategy extension of the game. Because, as soon as the strategy spaces are metric compact spaces, this extension satisfies the continuity and convexity assumptions of theorem 2.2, Nash's second fundamental result states the following.

Theorem 2.3 (Existence of Nash equilibria in mixed strategies).

Any game with compact metric strategy spaces and continuous costs has at least one Nash equilibrium in mixed strategies. In particular, finite games admit Nash equilibria in mixed strategies.

3. Cournot–Nash equilibria

Since the seminal work of Aumann [2,3], games with a continuum of players have received a lot of attention in game theory and economics. The setting is the following: agents are characterized by a type θ belonging to some compact metric space Θ. The type space Θ is also endowed with a Borel probability measure which gives the distribution of types in the agents population. Each agent has to choose a strategy x from some strategy space, X, again a compact metric space. The cost of one agent does not depend only on her type and the strategy she chooses, but also on the other agents' choice through the probability distribution resulting from the whole population strategy choice. In other words, the cost is given by some function where is endowed with the weak-* topology (equivalently, the 1-Wasserstein metric ). In this framework, an equilibrium can conveniently be described by a joint probability measure on Θ×X which gives the joint distribution of types and strategies and which is consistent with the cost-minimizing behaviour of agents, this leads to the following definition:

Definition 3.1 (Cournot–Nash equilibrium).

A Cournot–Nash equilibrium for F and μ is a such that A Cournot–Nash equilibrium γ is called pure if it is of the form γ=(id,T)_#μ for some Borel map T : Θ→X (i.e. agents with the same type use the same strategy).

	— the first marginal of γ is μ: ΠΘ#γ=μ,
	— γ gives full mass to cost-minimizing strategies: where ν denotes the second marginal of γ: ΠX#γ=ν.

By a standard fixed-point argument, see Schmeidler [7] or Mas-Colell [8], one obtains the following

Theorem 3.2 (Existence of Cournot–Nash equilibria)

Ifwhereis endowed with the weak-* topology, there exists at least one Cournot–Nash equilibrium.

The above-mentioned continuity assumption is actually rather demanding and the aim of §5 is to present some results of [11,12] for existence and sometimes uniqueness under less demanding regularity assumptions.

4. From Nash to Cournot–Nash

Our aim now is to explain how Cournot–Nash equilibria can be obtained as limits of Nash equilibria as the number of players tends to infinity. What follows is very much inspired by results from the mean-field games theory of Lasry and Lions, see in particular the notes of Cardaliaguet [13], following Lions' lectures at Collège de France. The main improvement with respect to [13] is that we deal with a situation with heterogeneous players and therefore cannot reduce the analysis to symmetric equilibria.

Let X and Θ be compact and metric spaces with respective distance d_X and d_Θ and let Θ_N:={θ₁,…,θ_N} be a finite subset of the type space Θ. Consider an N-person game where all the agents have the same strategy space X. We assume that the cost of player i, depends on her type θ_i∈Θ_N, her strategy x_i and is symmetric with respect to the other players strategies x_−i:

where S_N−1 denotes the set of permutations of {1,…,N}∖{i}. We moreover assume that there is a modulus of continuity ω such that for every for every N, every (θ_i,θ_j)∈Θ_N×Θ_N, every (x_i,x_−i) and (y_i,y_−i) in X^N, one has For further reference, let us observe, following [13], that the distance above is nothing but the quotient (by permutations) distance As in [13, theorem 2.1], under (4.1), one can extend J^N to by the classical Mc Shane construction, i.e. by defining for every , the cost F^N(θ,x,ν) by the formula The previous assumptions are therefore equivalent to the fact that player is cost is given by with F^N a sequence of uniformly equicontinuous functions on .

Theorem 4.1 (Pure Nash equilibria converge to Cournot–Nash equilibria).

Letbe a Nash equilibrium for the game above, and define

Assume that, up to the extraction of subsequences,then γ is a Cournot–Nash equilibrium for F and μ in the sense of definition 3.1.

Proof.

First set

Because is a Nash equilibrium we have Hence, using , we obtain where ε_N:=2ω(diam(X)/N) tends to 0 as N goes to . Summing over i and dividing by N gives Because F^N(.,.,ν^N) converges in to F(.,.,ν), letting N tend to in the previous inequality, we obtain Because γ obviously has marginals μ and ν, we readily deduce that γ is a Cournot–Nash equilibrium for F and μ. ▪

As already discussed above, not all the games have a pure Nash equilibrium. So that the previous result might be of limited interest. This is why we now consider the mixed strategy extension that always has Nash equilibria as recalled in §2.

Theorem 4.2 (Nash equilibria in mixed strategies converge to Cournot–Nash equilibria)

If assumption (4.1) holds for ω(t)=Kt, then the conclusions of theorem 4.1 applies to the extension in mixed strategies with the extended cost

This theorem is a direct consequence of the fact that for uniformly Lipschitz J^N, the extension in mixed strategies still satisfies (4.1).

Lemma 4.3

Under the assumptions of theorem 4.2, the extended costsatisfies

for every (π_i,π_−i) and (η_i,η_−i) in.

Proof.

The inequality

is obvious by integration. Let Γ∈Π(π_i,η_i) be such that We have Let σ_∈S_N−1 and for j≠i, let then Γ_j∈Π(π_j,η_σ(j)) be such that Then, define by We then have by symmetry, definition of Γ and (4.1) and because σ is arbitrary, we have which ends the proof. ▪

5. Solving Cournot–Nash via the Monge–Kantorovich problem

Here, we give a brief and informal account of our recent works [11,12] and the computation of Cournot–Nash equilibria in the separable case, i.e. the case where, using the notations of §3

All the strategic interactions are then captured by the term V (ν,x). Typical effects that have to be taken into account are

	— congestion (or repulsive) effects: frequently played strategies are costly. This can be captured by a term of the form x↦f(x,ν(x)), where slightly abusing notations ν are identified with its density with respect to some reference measure m0 according to which congestion is measured. The congestion effect leads to dispersion in the strategy distribution ν,
	— positive interactions (or attractive effects) such as mimetism: such effects can be captured by a term like with ϕ minimal when x=y. The positive interaction effect leads to the concentration of the strategy distribution.

In the sequel, we shall therefore consider a term V (ν,x) which reflects both effects. Cournot–Nash equilibria have to balance the attractive and repulsive effects in some sense, but their structure is not easy to guess when these two opposite effects are present. As a benchmark, one can think of ν being absolutely continuous with respect to some reference measure m₀ and a potential of the form

where f(x,.) is increasing and ϕ is some continuous interaction kernel. Note that congestion terms, though natural in applications, pose important mathematical difficulties because they are not regular. In particular, in the presence of such terms, one cannot use the existence result stated in theorem 3.2.

In [11], we emphasized that the structure of equilibria, which we take pure to simplify the exposition, i.e. we look for a strategy map T from Θ to X, is as follows:

	— players of type θ choose a cost-minimizing strategy T(θ), i.e. T is called best-reply map,
	— ν is the image of μ by T: ν:=T#μ. This is a mass conservation condition.

The aim is to compute ν and T from the previous two conditions. In general, these two highly nonlinear conditions are difficult to handle, but in [11,12] we identified some cases in which they can be greatly simplified. We then obtained some uniqueness results and/or numerical methods to compute equilibria. Roughly speaking, in a Euclidean setting; for instance, the best-reply condition leads to an optimality condition relating ν and T, whereas the mass conservation condition leads to a Jacobian equation. Combining the two conditions therefore leads to a certain nonlinear partial differential equation of Monge–Ampère type.

We shall review some tractable examples in the next paragraphs, but wish to observe that in the separable setting Cournot–Nash equilibria are very much related to optimal transport. More precisely, for , let Π(μ,ν) denote the set of probability measures on Θ×X having μ and ν as marginals and let be the least cost of transporting μ to ν for the cost c, i.e. the value of the Monge–Kantorovich optimal transport problem

It is obvious that the optimal transport problem above admits solutions, because the admissible set is convex and weakly-* compact. Let us then denote by Π_o(μ,ν) the set of optimal transport plans, i.e.

The link between Cournot–Nash equilibria and optimal transport is then based on the following straightforward observation: if γ is a Cournot–Nash equilibrium and ν denotes its second marginal then γ∈Π_o(μ,ν), see [11], lemma 2.2 for details. Hence, if γ is pure then it is induced by an optimal transport. Optimal transport theory has developed extremely quickly in the past decades, and one can therefore naturally take advantage of this powerful theory, for which we refer to the books of Villani [9,10], to study Cournot–Nash equilibria.

(a) Dimension one

Assume that both Θ and X are intervals of the real line, say [0,1]. The two equations of cost minimization and mass conservation can be simplified to characterize Cournot–Nash equilibria. This is why under quite general assumptions on c, f and ϕ we prove in [12], section 6.3 that the optimal transport map T associated with a Cournot–Nash equilibrium satisfies a certain nonlinear and non-local differential equation. For instance when , the map T corresponding to an equilibrium solves

supplemented with the boundary conditions T(0)=0 and T(1)=1. The case of a power congestion function f(ν)=ν^α with α>0 is more involved, because, in this case, equilibrium densities may vanish. In this case, one cannot really write a differential equation for the transport map but working with the generalized inverse of the transport map still gives a tractable equation for equilibria. Hence, equilibria can be computed numerically, see [12], as shown in figure 1.

• Download figure
• Open in new tab
• Download PowerPoint

Let us mention that in higher dimensions, for a quadratic c and a logarithmic f, finding an equilibrium amounts to solve the following Monge–Ampère equation, see [11, section 4.3]:

(b) Variational approach

In [11], we observe that whenever V takes the form (5.2) with a symmetric kernel ϕ then it is the first variation of the energy

We can thus prove that the condition defining equilibria is in fact the Euler–Lagrange equation for the variational problem More precisely, if ν solves (5.5) and γ∈Π_o(μ,ν), then γ actually is a Cournot–Nash equilibrium. Not only this approach gives new existence results, but also, and more surprisingly, uniqueness in some cases, because the functional above may have hidden convexity properties. It is worth noting that in the quadratic cost case variational problems of the form (5.5) play a key role in the theory of gradient flows in the Wasserstein space of probability measures, see [14] for a detailed exposition of this powerful theory, in which it appears as one step of the celebrated Jordan–Kinderleherer–Otto [15] scheme. This theory has been extremely fruitful in recent years to study a variety of evolution equations with nonlinear, non-local (attractive/repulsive) effects (see in particular [16,17] and the references therein). In dimension one, under suitable convexity assumptions, the variational problem above can be solved numerically in an efficient way as illustrated by figure 2.

• Download figure
• Open in new tab
• Download PowerPoint

(c) A two-dimensional case by best-reply iteration

For some specific forms in (5.1) where c and the potential V have strong convexity properties with respect to x, one can look for equilibria directly by best-reply iteration. For a fixed strategy distribution ν, each type θ has a unique optimal strategy T(ν,θ), transporting μ by this best-reply map then gives a new measure T(ν,.)_#μ, an equilibrium corresponds to a fixed-point, i.e. a solution of T(ν,.)_#μ=ν. For a quadratic c, the previous equation simplifies a lot and, in [12], we obtained conditions under which the best-reply map is a contraction for the Wasserstein metric which guarantees uniqueness of the equilibrium and convergence of best-reply iterations. See figure 3 for a two-dimensional example. A dynamical extension of this best-reply scheme was recently developed in [18].

• Download figure
• Open in new tab
• Download PowerPoint

Footnotes

One contribution of 13 to a Theme Issue ‘Partial differential equation models in the socio-economic sciences’.