Olivier Guéant
email: olivier.gueant@ann.jussieu.fr

Charles-Albert Lehalle
email: clehalle@cheuvreux.com

Joaquin Fernandez Tapia

Dealing with the Inventory Risk

come

Introduction

The optimization of the intra-day trading process on electronic markets was born with the need to split large trades to make the balance between trading too fast (and possibly degrade the obtained price via "market impact") and trading too slow (and suffer from a too long exposure to "market risk"). This "trade scheduling" viewpoint has been mainly formalized in the late nineties by Bertsimas and Lo [START_REF] Bertsimas | Optimal control of execution costs[END_REF] and Almgren and Chriss [START_REF] Almgren | Optimal execution of portfolio transactions[END_REF]. More sophisticated approaches involving the use of stochastic and impulse control have been proposed since then (see for instance [START_REF] Bouchard | Optimal control of trading algorithms: a general impulse control approach[END_REF]). Another branch of proposals goes in the direction of modeling the effect of the "aggressive" (i.e. liquidity consuming) orders at the finest level, for instance via a martingale model of the behavior market depth and of its resilience (see [START_REF] Alfonsi | Optimal Execution and Absence of Price Manipulations in Limit Order Book Models[END_REF]).

From a quantitative viewpoint, market microstructure is a sequence of auction games between market participants. It implements the balance between supply and demand, forming an equilibrium traded price to be used as reference for valuation of the listed assets. The rule of each auction game (fixing auction, continuous auction, etc), are fixed by the firm operating each trading venue. Nevertheless, most of all trading mechanisms on electronic markets rely on market participants sending orders to a "queuing system" where their open interests are consolidated as "liquidity provision" or form transactions [START_REF] Amihud | Dealership Market. Market-Making with Inventory[END_REF]. The efficiency of such a process relies on an adequate timing between buyers and sellers, to avoid too many non-informative oscillations of the transaction price (for more details and modeling, see for example [START_REF] Lehalle | High Frequency Simulations of an Order Book: a Two-Scales Approach[END_REF]).

To take profit of these oscillations, it is possible to provide liquidity to an impatient buyer (respectively seller) and maintain an inventory until the arrival of the next impatient seller (respectively buyer). Market participants focused on this kind of liquidity-providing activity are called "market makers". On one hand they are buying at the bid price and selling at the ask price they chose, taking profit of this "bid-ask spread". On the other hand, their inventory is exposed to price fluctuations mainly driven by the volatility of the market (see [START_REF] Amihud | Asset pricing and the bid-ask spread[END_REF][START_REF] Robert | Determinants of bid-asked spreads in the over-thecounter market[END_REF][START_REF] Cohen | Transaction Costs, Order Placement Strategy, and Existence of the Bid-Ask Spread[END_REF][START_REF] Garman | Market microstructure[END_REF][START_REF] Ho | Dealer bid-ask quotes and transaction prices: An empirical study of some AMEX options[END_REF][START_REF] O'hara | The microeconomics of market making[END_REF]).

The usual "market making problem" comes from the optimality of the quotes (i.e. the bid and ask prices) that such agents provide to other market participants with respect to the constraints on their inventory and their utility function as a proxy to their risk (see [START_REF] Cohen | Market makers and the market spread: A review of recent literature[END_REF][START_REF] Hendershott | Price pressures[END_REF][START_REF] Ho | The dynamics of dealer markets under competition[END_REF][START_REF] Madhavan | An analysis of changes in specialist inventories and quotations[END_REF][START_REF] Mildenstein | The optimal pricing policy of a monopolistic marketmaker in the equity market[END_REF][START_REF] Roll | A simple implicit measure of the effective bid-ask spread in an efficient market[END_REF]).

The recent evolution of market microstructure and the financial crisis reshaped the nature of the interactions of the market participants during electronic auctions, one consequence being the emergence of "high-frequency market makers" who are said to be part of 70% of the electronic trades and have a massively passive (i.e. liquidity providing) behavior. A typical balance between passive and aggressive orders for such market participants is around 80% of passive interactions (see [START_REF] Menkveld | High Frequency Trading and The New-Market Makers[END_REF]).

Avellaneda and Stoïkov proposed in [START_REF] Avellaneda | High-frequency trading in a limit order book[END_REF] an innovative framework for "market making in an order book" and studied it using different approximations. In such an approach, the "fair price" S t is modeled via a Brownian motion with volatility σ, and the arrival of a buy or sell liquidity-consuming order at a distance δ of S t follows a Poisson process with intensity A exp(-k δ). Our paper extends their proposal and provides results in two main directions:

• An explicit solution to the Hamilton-Jacobi-Bellman equation coming from the optimal market making problem thanks to a non trivial change of variables and the resulting expressions for the optimal quotes:

Main Result 1 (Proposition 2 -Theorem 4). The optimal bid and ask quotes can be expressed as:

s b * (t, q, s) = s - ( 1 k ln ( v q (t) v q+1 (t) ) + 1 γ ln ( 1 + γ k
) )

s a * (t, q, s) = s +

( 1 k ln ( v q (t) v q-1 (t) ) + 1 γ ln ( 1 + γ k ) )
where γ is the risk aversion of the agent and where v is a family of strictly positive functions (v q ) |q|≤Q solution of the linear system of ODEs that follows:

∀q ∈ {-Q + 1, . . . , Q -1}, vq (t) = αq 2 v q (t) -η (v q-1 (t) + v q+1 (t)) vQ (t) = αQ 2 v Q (t) -ηv Q-1 (t) v-Q (t) = αQ 2 v -Q (t) -ηv -Q+1 (t)
with ∀q ∈ {-Q, . . . , Q}, v q (T ) = 1, α = k 2 γσ 2 and η = A(1

+ γ k ) -(1+ k γ )
, T being the time horizon and Q a bound we impose on the inventory of the market marker, be it short or long.

It means that to find an exact solution to the generic high-frequency market making problem, it is enough to solve on the fly the companion ODEs in v q (t) provided by our change of variables, and to plug the result in the upper equalities to obtain the optimal quotes with respect to a given inventory and market state.

• Asymptotics of the solution that are numerically attained fast enough in most realistic cases:

Main Result 2 (Theorem 5 (asymptotics) and the associated approximation equations). lim

T →∞ s -s b * (0, q, s) = δ b * ∞ (q) ≃ 1 γ ln ( 1 + γ k ) + 2q + 1 2 √ σ 2 γ 2kA ( 1 + γ k ) 1+ k γ lim T →∞ s a * (0, q, s) -s = δ a * ∞ (q) ≃ 1 γ ln ( 1 + γ k ) - 2q -1 2 √ σ 2 γ 2kA ( 1 + γ k ) 1+ k γ
These results open doors to new directions of research involving the modeling and control of passive interactions with electronic order books. If some attempts have been made that did not rely on stochastic control but on forward optimization (see for instance [START_REF] Pagès | Optimal split of orders across liquidity pools: a stochatic algorithm approach[END_REF] for a stochastic algorithmic approach for optimal split of passive orders across competing electronic order books), they should be complemented by backward ones.

This paper starts in section 1 with the description of the model choices that had to be made. Section 2 is dedicated to the presentation of the ideas underlying the results of this paper. These ideas are developed in the framework of the initial Avellaneda and Stoïkov setting. Section 3 then goes back to our model with bounds on the inventory and, after having found the optimal quotes, exposes the asymptotics of the obtained dynamics along with applications of the approximations developed in section 2. Section 4 carries out the comparative statics. Section 5 extends the framework to trends in prices and costly terminal liquidation. We finally discuss some issues with the hypotheses of the model in section 6 and end with an application to real data in section 7. Adaptations of our results are already in use at Crédit Agricole Cheuvreux to optimize the brokerage trading flow.

In our framework, we follow Avellaneda and Stoïkov in using a Poisson process model pegged on a "fair price" diffusion (see section 1). As it is discussed in section 6, it is an arguable choice since it does not capture "resistances" that can be built by huge passive (i.e. liquidity-providing) orders preventing the market price to cross their prices. Our results cannot be used as such for large orders, but are perfectly suited for high-frequency market making as it is currently implemented in the market, using orders of small size (close to the average trade size, see [START_REF] Menkveld | High Frequency Trading and The New-Market Makers[END_REF]).

Moreover, to our knowledge, no quantitative model of "implicit market impact" of such small passive orders has never been proposed in the literature, despite very promising studies linking updates of quantities in the order books to price changes (see [START_REF] Cont | The Price Impact of Order Book Events[END_REF]). Its combination with recent applications of more general point processes to capture the process of arrival of orders (like Hawkes models, see [START_REF] Bacry | Modeling microstructure noise with mutually exciting point processes[END_REF]) should give birth to such implicit market impact models, specifying dependencies between the trend, the volatility and possible jumps in the "fair price" semi-martingale process with the parameters of the multi-dimensional point process of the market maker fill rate. At this stage, the explicit injection of such pathdependent approach (once they will be proposed in the literature) into our equations are too complex to be handled, but numerical explorations around our explicit formulas will be feasible. The outcomes of applications of our results to real data (section 7) show that they are realistic enough so that no more that small perturbations should be needed.

Setup of the model 1.Prices, orders and objective function

We consider a small high-frequency market maker operating on a single stock 1 . For the sake of simplicity and since we will basically only consider short horizon problems we suppose that a fair price 2 of the stock moves as an arithmetic brownian motion:

dS t = σdW t
The market maker under consideration will continuously propose bid and ask quotes denoted respectively S b t and S a t and will hence buy and sell shares according to the rate of arrival of aggressive orders at the quoted prices. His inventory q, that is the (signed) quantity of shares he holds, is given by q

t = N b t -N a t
where N b and N a are the jump processes giving the number of shares the market maker respectively bought and sold. These jump processes are supposed to be Poisson processes and to simplify the exposition (although this may be important, see the discussion part) we consider that jumps are of constant size, scaled to 1. Arrival rates obviously depend on the prices S b t = S t -δ b t and S a t = S t + δ a t quoted by the market maker and we assume, in accordance with most datasets 3 , that intensities λ b and λ a associated to N b and N a are of the following form 4 :

λ b (δ b ) = Ae -kδ b = A exp(-k(s -s b )) λ a (δ a ) = Ae -kδ a = A exp(-k(s a -s))
This means for positive δ b and δ a that the closer to the fair price an order is quoted, the faster it will be executed.

As a consequence of his trades, the market maker has an amount of cash whose dynamics is given by:

dX t = (S t + δ a t )dN a t -(S t -δ b t )dN b t
To this original setting introduced by Avellaneda and Stoikov (itself following Ho and Stoll [START_REF] Ho | Optimal dealer pricing under transactions and return uncertainty[END_REF]) we add a bound Q on the inventory that a market maker is authorized to have. In other words, we assume that a market maker with inventory Q (Q depending in practice on risk limits) will never set a bid quote and symmetrically that a market maker with inventory -Q, that is a short position of Q shares in the stock under consideration, will never set an ask quote. Now, coming to the objective function and as we said above, the market maker has a time horizon T and his goal is to optimize the expected utility of his P&L at time T . In line with [START_REF] Avellaneda | High-frequency trading in a limit order book[END_REF], we will focus on CARA utility functions and we suppose that the market maker optimizes: sup

(δ a t )t,(δ b t )t∈A E [-exp (-γ(X T + q T S T ))]
where A is the set of predictable processes bounded from below, where γ is the absolute risk aversion characterizing the market maker, where X T is the amount of cash at time T and where q T S T is the evaluation of the (signed) remaining quantity of shares in the inventory at time T (liquidation at the fair price S T 5 ).

The (HJB) equation and the original Avellaneda-Stoikov (AS-HJB) equation

∀q ∈ {-Q + 1, . . . , Q -1}, ∂ t u(t, x, q, s) + 1 2 σ 2 ∂ 2 ss u(t, x, q, s) + sup δ b λ b (δ b ) [ u(t, x -s + δ b , q + 1, s) -u(t, x, q, s) ] + sup δ a λ a (δ a ) [u(t, x + s + δ a , q -1, s) -u(t, x, q, s)] = 0 ∂ t u(t, x, Q, s) + 1 2 σ 2 ∂ 2 ss u(t, x, Q, s) + sup δ a λ a (δ a ) [u(t, x + s + δ a , Q -1, s) -u(t, x, Q, s)] = 0 ∂ t u(t, x, -Q, s) + 1 2 σ 2 ∂ 2 ss u(t, x, -Q, s) + sup δ b λ b (δ b ) [ u(t, x -s + δ b , -Q + 1, s) -u(t, x, -Q, s) ] = 0
with the final condition:

∀q ∈ {-Q, . . . , Q}, u(T, x, q, s) = -exp (-γ(x + qs))
This system differs from the initial equation introduced by Avellaneda and Stoikov because of the bounds we imposed on the inventory. The original equation was indeed

(AS -HJB) 0 = ∂ t u(t, x, q, s) + 1 2 σ 2 ∂ 2 ss u(t, x, q, s) + sup δ b λ b (δ b ) [ u(t, x -s + δ b , q + 1, s) -u(t, x, q, s) ] + sup δ a λ a (δ a ) [u(t, x + s + δ a , q -1, s) -u(t, x, q, s)]
with the final condition: u(T, x, q, s) = -exp (-γ(x + qs))

and we are going to solve this equation before solving our problem because the arguments underlying our closed-form results are rooted to this equation on an unbounded domain and can then be mutatis mutandis applied to our problem.

Solving the (AS-HJB) equation

The equation (AS-HJB) we introduced in the preceding section is not a simple 4-variable PDE. Rather, because the variable q is discrete, it is an infinite system of 3-variable PDEs. To solve it, we will use a rather non-intuitive change of variables that is different from the one used in [START_REF] Avellaneda | High-frequency trading in a limit order book[END_REF] and transform the system of PDEs in a system of linear ODEs. Proposition 1 (A system of linear ODEs). Let us consider a family of strictly positive functions (v q ) q∈Z solution of the linear system of ODEs (S) that follows:

∀q ∈ Z, vq (t) = αq 2 v q (t) -η (v q-1 (t) + v q+1 (t)) with v q (T ) = 1, where α = k 2 γσ 2 and η = A(1 + γ k ) -(1+ k γ ) .
Then u(t, x, q, s) = -exp(-γ(x + qs))v q (t) -γ k is solution of (AS-HJB).

Theorem 1 (Well-posedness of the system (S)). There exists a unique solution of (S) in C ∞ ([0, T ), ℓ 2 (Z)) and this solution consists in strictly positive functions.

Theorem 2 (Expression of the maximizers). Let us consider the solution v of the system (S) as in Theorem 1. Let u(t, x, q, s) = -exp(-γ(x + qs))v q (t) -γ k as above. Then, λ b (δ b ) [ u(t, x -s + δ b , q + 1, s) -u(t, x, q, s) ] and λ a (δ a ) [u(t, x + s + δ a , q -1, s) -u(t, x, q, s)] are maximal for δ b * and δ a * given by:

δ b * (t, q) = 1 k ln ( v q (t) v q+1 (t) ) + 1 γ ln ( 1 + γ k ) δ a * (t, q) = 1 k ln ( v q (t) v q-1 (t) ) + 1 γ ln ( 1 + γ k )
Now, in addition to these new results on the (AS-HJB) equation, we will provide an approximation of δ b * (t, q) and δ a * (t, q) in two steps. The first step is to notice that the above maximizers have an asymptotic behavior that can easily be characterized in a spectral way. Then, using this spectral characterization, we provide in a second step a closed-form approximation for these maximizers that will turn out to be quite accurate approximations for the optimal quotes in our initial control problem.

The asymptotic behavior of the maximizers is the following -asymptotic meaning here a time horizon T going to infinity: Theorem 3 (Asymptotic behavior of the maximizers).

∀q ∈ Z, lim T →∞ δ b * (0, q) = δ b * ∞ (q) ∀q ∈ Z, lim T →∞ δ a * (0, q) = δ a * ∞ (q) with δ b * ∞ (q) = 1 γ ln ( 1 + γ k ) + 1 k ln ( f 0 q f 0 q+1 ) δ a * ∞ (q) = 1 γ ln ( 1 + γ k ) + 1 k ln ( f 0 q f 0 q-1 )
where f 0 ∈ ℓ 2 (Z) is characterized by:

f 0 ∈ argmin ∥f ∥ ℓ 2 (Z) =1 ∑ q∈Z αq 2 f 2 q + η ∑ q∈Z (f q+1 -f q ) 2
The challenge is now to provide an approximation for f 0 that happens to fit the actual figures and the approximation we propose is based on the continuous counterpart of f 0 , namely f 0 ∈ L 2 (R), a function that verifies:

f 0 ∈ argmin ∥ f ∥ L 2 (R) =1 ∫ ∞ -∞ ( αx 2 f (x) 2 + η f ′ (x) 2
) dx

It can be proved 6 that such a function f 0 must be proportional to the probability distribution function of a normal variable with mean 0 and variance √ η α . Hence, we expect f 0 q 6 To prove this we need to proceed as in the proof of Theorems 1 and 3. In a few words, we introduce the positive, compact and self-adjoint operator

L c defined for f ∈ L 2 (R) as the unique weak solution v of αx 2 v -ηv ′′ = f with ∫ ∞ -∞ ( αx 2 v(x) 2 + ηv ′ (x) 2 )
dx < +∞. L c can be diagonalized and largest eigenvalue of L c can be shown to be associated to the eigenvector f (x) = exp

( -1 2 √ α η x 2
) .

to behave as exp

( -1 2 √ α η q 2
) .

This heuristic viewpoint induces an approximation for the maximizers if we replace f 0 q by exp

( -1 2 √ α η q 2
) :

δ b * ∞ (q) ≃ 1 γ ln ( 1 + γ k ) + 1 2k √ α η (2q + 1) ≃ 1 γ ln ( 1 + γ k ) + 2q + 1 2 √ σ 2 γ 2kA ( 1 + γ k ) 1+ k γ δ a * ∞ (q) ≃ 1 γ ln ( 1 + γ k ) - 1 2k √ α η (2q -1) ≃ 1 γ ln ( 1 + γ k ) - 2q -1 2 √ σ 2 γ 2kA ( 1 + γ k ) 1+ k γ 3 A

solution to our control problem

As for the resolution of the (AS-HJB) equation, we can reduce the Hamilton-Jacobi-Bellman (HJB) associated to our control problem to a linear system of ODEs. However the linear system associated to this model will be simpler since it involves 2Q + 1 equations only and can be solved using linear algebra. Then, using a verification argument, we can prove that our solution to (HJB) is indeed the value function of our control problem and find the optimal quotes.

Proposition 2 (Resolution of (HJB)). Let us consider a family (v q ) |q|≤Q of strictly positive functions solution of:

∀q ∈ {-Q + 1, . . . , Q -1}, vq (t) = αq 2 v q (t) -η (v q-1 (t) + v q+1 (t)) vQ (t) = αQ 2 v Q (t) -ηv Q-1 (t) v-Q (t) = αQ 2 v -Q (t) -ηv -Q+1 (t) with ∀q ∈ {-Q, . . . , Q}, v q (T ) = 1, where α = k 2 γσ 2 and η = A(1 + γ k ) -(1+ k γ ) . Then, u(t, x, q, s) = -exp(-γ(x + qs))v q (t) -γ k is solution of (HJB).
Theorem 4 (Resolution of the control problem). Let us introduce the matrix M defined by:

M =                αQ 2 -η 0 • • • • • • • • • 0 -η α(Q -1)
. . . . . . 0 -η α(Q -1) 2 -η 0 • • • • • • • • • 0 -η αQ 2                where α = k 2 γσ 2 and η = A(1 + γ k ) -(1+ k γ ) .
Then, if

v(t) = (v -Q (t), v -Q+1 (t), . . . , v 0 (t), . . . , v Q-1 (t), v Q (t)) ′ = exp(-M (T -t)) × (1, . . . , 1) ′ u(t, x, q, s) = -exp(-γ(x + qs))v q (t) -γ k
is the value function of the control problem and the optimal quotes are given by:

∀q ∈ {-Q, . . . , 0, . . . , Q -1}, s -s b * (t, q, s) = δ b * (t, q) = 1 k ln ( v q (t) v q+1 (t) ) + 1 γ ln ( 1 + γ k ) ∀q ∈ {-(Q -1), . . . , 0, . . . , Q}, s a * (t, q, s) -s = δ a * (t, q) = 1 k ln ( v q (t) v q-1 (t) ) + 1 γ ln ( 1 + γ k
) and the bid-ask spread quoted by the market maker is given by:

∀q ∈ {-(Q -1), . . . , 0, . . . , Q -1}, ψ * (t, q) = - 1 k ln ( v q+1 (t)v q-1 (t) v q (t) 2 ) + 2 γ ln ( 1 + γ k )
To exemplify our findings and in order to justify the asymptotic approximation we shall provide, let us present some graphs to understand the behavior in time and inventory of the optimal quotes.

= 0. σ = 0.3 Tick•s -1/2 , A = 0.9 s -1 , k = 0.3 Tick -1 , γ = 0.01 Tick -1 , T = 600 s.
We clearly see that the optimal quotes are, after a few minutes, very close to their asymptotic values and this justifies the approximation of the optimal quotes by their asymptotic limits obtained in the following theorem: Theorem 5 (Asymptotics for the optimal quotes). The optimal quotes have asymptotic limits

lim T →∞ δ b * (0, q) = δ b * ∞ (q) lim T →∞ δ a * (0, q) = δ a * ∞ (q)
that can be expressed as:

δ b * ∞ (q) = 1 γ ln ( 1 + γ k ) + 1 k ln ( f 0 q f 0 q+1 ) δ a * ∞ (q) = 1 γ ln ( 1 + γ k ) + 1 k ln ( f 0 q f 0 q-1
)

where f 0 ∈ R 2Q+1 is an eigenvector corresponding to the smallest eigenvalue of the matrix M introduced in the preceding theorem.

The resulting bid-ask spread quoted by the market maker is asymptotically:

ψ * ∞ (q) = - 1 k ln ( f 0 q+1 f 0 q-1 f 0 q 2 ) + 2 γ ln ( 1 + γ k )
Now, these expressions for the limits depend on the spectral decomposition of the matrix M introduced earlier. In fact, and this is the very reason why we first solved the (AS-HJB) equation instead of heading directly to the Hamilton-Jacobi-Bellman equation of our problem, we are going to use the "gaussian" approximations introduced in the preceding section and this approximation will turn out to be quite accurate except when q (or Q) is very large 7 .

We exhibit below the values of the optimal quotes, along with their associated approximations 8 . Empirically, these approximations for the quotes are satisfactory in most cases and are always very good for small values of the inventory q. The apparent difficulty to approximate the bid-ask spread comes from the chosen scale (the bid-ask spread being almost uniform across values of the inventory). 7 In fact, even though f 0 is certainly well approximated by the gaussian approximation, we cannot expect a very good fit for the quotes when q is large because we are approximating an expression that depends on ratios of the form

f 0 q f 0 q+1 or f 0 q f 0 q-1
. 8 For the bid-ask spread the approximation is

ψ * ∞ (q) ≃ 2 γ ln ( 1 + γ k ) + √ σ 2 γ 2kA ( 1 + γ k ) 1+ k γ -30
σ = 0.4 Tick • s -1/2 , A = 0.9 s -1 , k = 0.3 Tick -1 , γ = 0.01 Tick -1 , T = 600 s. Right: σ = 1.0 Tick • s -1/2 , A = 0.2 s -1 , k = 0.3 Tick -1 , γ = 0.01 Tick -1 , T = 600 s.

Comparative statics

Before starting with the comparative statics, we rewrite the approximations used in the previous section to be able to have some intuition about the behavior of the optimal quotes and bid-ask spread with respect to the parameters:

δ b * ∞ (q) ≃ 1 γ ln ( 1 + γ k ) + 2q + 1 2 √ σ 2 γ 2kA ( 1 + γ k ) 1+ k γ δ a * ∞ (q) ≃ 1 γ ln ( 1 + γ k ) - 2q -1 2 √ σ 2 γ 2kA ( 1 + γ k ) 1+ k γ ψ * ∞ (q) ≃ 2 γ ln ( 1 + γ k ) + √ σ 2 γ 2kA ( 1 + γ k ) 1+ k γ
Now, from these approximations, we can "deduce" the behavior of the optimal quotes and the bid-ask spread with respect to price volatility, trading intensity and risk aversion.

Dependence on σ 2

From the above approximations we expect the dependence of optimal quotes on σ 2 to be a function of the inventory. More precisely, we expect:

     ∂δ b * ∞ ∂σ 2 < 0, ∂δ a * ∞ ∂σ 2 > 0, if q < 0 ∂δ b * ∞ ∂σ 2 > 0, ∂δ a * ∞ ∂σ 2 > 0, if q = 0 ∂δ b * ∞ ∂σ 2 > 0, ∂δ a * ∞ ∂σ 2 < 0, if q > 0
For the bid-ask spread we expect it to be increasing with respect to σ 2 :

∂ψ * ∞ ∂σ 2 > 0
The rationale behind this is that a rise in σ 2 increases the inventory risk. Hence, to reduce this risk, a market maker that has a long position will try to reduce his exposure and hence ask less for his stocks (to get rid of some of them) and accept to buy at a cheaper price (to avoid buying new stocks). Similarly, a market maker with a short position tries to buy stocks, and hence increases its bid quote, while avoiding short selling new stocks, and he increases its ask quote to that purpose. Overall, due to the increase in risk, the bid-ask spread widens as it is well instanced in the case of a market maker with a flat position (this one wants indeed to earn more per trade to compensate the increase in inventory risk.

These intuitions can be verified numerically on Figure 3.

Dependence on A

Because of the above approximations, and in accordance with the form of the system (S), we expect the dependence on A to be the exact opposite of the dependence on σ 2 , namely

     ∂δ b * ∞ ∂A > 0, ∂δ a * ∞ ∂A < 0, if q < 0; ∂δ b * ∞ ∂A < 0, ∂δ a * ∞ ∂A < 0, if q = 0 ∂δ b * ∞ ∂A < 0, ∂δ a * ∞ ∂A > 0, if q > 0
For the same reason, we expect the bid-ask spread to be decreasing with respect to A.

∂ψ * ∞ ∂A < 0
The rationale behind these expectations is that an increase in A reduces the inventory risk. An increase in A indeed increases the frequency of trades and hence reduces the risk of being stuck with a large inventory (either positive or negative). For this reason, a rise in A should have the same effect as a decrease in σ 2 . These intuitions can be verified numerically on Figure 4.

Dependence on k

From the above approximations we expect δ b * ∞ to be decreasing in k for q greater than some negative threshold. Below this threshold we expect it to be increasing. Similarly we expect δ a * ∞ to be decreasing in k for q smaller than some positive threshold. Above this threshold we expect it to be increasing.

Eventually, as far as the bid-ask spread is concerned, the above approximation indicates that the bid-ask spread should be a decreasing function of k. ∂ψ * ∞ ∂k < 0

In fact several effects are in interaction. On one hand, there is a "no-volatility" effect that is completely orthogonal to any reasoning on the inventory risk: when k increases, in a situation where δ b and δ a are positive, trades occur closer to the price S t . For this reason, and in absence of inventory risk, the optimal bid-ask spread has to shrink. However, an increase in k also affects the inventory risk since it decreases the probability to be executed (for δ b , δ a > 0). Hence, an increase in k is also, in some aspects, similar to a decrease in A. These two effects explain the expected behavior.

Numerically, one of two effects dominates for the values of the inventory under consideration:

Dependence on γ

Using the above approximations, we see that the dependence on γ is ambiguous. The market maker faces two different risks that contribute to the inventory risk: (i) trades occur at random times and (ii) the fair price is stochastic. But if risk aversion increases, the market maker will mitigate the two risks: (i) he may set his quotes closer to one another to reduce the randomness in execution and (ii) he may enlarge his spread to reduce price risk. The tension between these two roles played by γ explains the different behaviors we may observe, as in the figures below:

σ = 0.3 Tick • s -1/2 , A = 0.9 s -1 , k = 0.3 Tick -1 , T = 600 s. Right: σ = 0.6 Tick • s -1/2
, A = 0.9 s -1 , k = 0.9 Tick -1 , T = 600 s

Different settings

In what follows we provide the settings of several variants of the initial model. We will alternatively consider a model with a trend in prices and a model with a penalization term for not having cleared one's inventory.

For each model, we enounce the associated results and the general proofs are not repeated since they can easily be derived from adaptations of the proofs of the initial model.

Trend in prices

In the preceding setting, we supposed that the fair price of the stock followed a brownian motion. However, we can also build a model in presence of a trend:

dS t = µdt + σdW t
In that case we have the following proposition:

Proposition 3 (Resolution with drift). Let us consider a family of functions (v q ) |q|≤Q solution of the linear system of ODEs that follows:

∀q ∈ {-Q + 1, . . . , Q -1}, vq (t) = (αq 2 -βq)v q (t) -η (v q-1 (t) + v q+1 (t)) vQ (t) = (αQ 2 -βQ)v Q (t) -ηv Q-1 (t) v-Q (t) = (αQ 2 + βQ)v -Q (t) -ηv -Q+1 (t) with ∀q ∈ {-Q, . . . , Q}, v q (T ) = 1, where α = k 2 γσ 2 , β = kµ and η = A(1 + γ k ) -(1+ k γ ) .
Then, optimal quotes are given by:

s -s b * (t, q, s) = δ b * (t, q) = 1 k ln ( v q (t) v q+1 (t) ) + 1 γ ln ( 1 + γ k ) s a * (t, q, s) -s = δ a * (t, q) = 1 k ln ( v q (t) v q-1 (t) ) + 1 γ ln ( 1 + γ k
) and the bid-ask spread quoted by the market maker is :

ψ * (t, q) = - 1 k ln ( v q+1 (t)v q-1 (t) v q (t) 2 ) + 2 γ ln ( 1 + γ k ) Moreover, lim T →∞ δ b * (0, q) = 1 γ ln ( 1 + γ k ) + 1 k ln ( f 0 q f 0 q+1 ) lim T →∞ δ a * (0, q) = 1 γ ln ( 1 + γ k ) + 1 k ln ( f 0 q f 0 q-1 ) lim T →∞ ψ * (0, q) = - 1 k ln ( f 0 q+1 f 0 q-1 f 0 q 2 ) + 2 γ ln ( 1 + γ k )
where f 0 is an eigenvector corresponding to the smallest eigenvalue of:

               αQ 2 -βQ -η 0 • • • • • • • • • 0 -η α(Q -1) 2 -β(Q -1)
(Q -1) 2 -β(Q -1) -η 0 • • • • • • • • • 0 -η αQ 2 -βQ               
Using the same continuous approximation as in the initial model we find the following approximations for the optimal quotes and the bid-ask spread:

δ b * ∞ (q) ≃ 1 γ ln ( 1 + γ k ) + [ - µ γσ 2 + 2q + 1 2 ] √ σ 2 γ 2kA ( 1 + γ k ) 1+ k γ δ a * ∞ (q) ≃ 1 γ ln ( 1 + γ k ) + [ µ γσ 2 - 2q -1 2 ] √ σ 2 γ 2kA ( 1 + γ k ) 1+ k γ ψ * ∞ (q) ≃ 2 γ ln ( 1 + γ k ) + √ σ 2 γ 2kA ( 1 + γ k ) 1+ k γ

Costly inventory liquidation

In the initial model we imposed a terminal condition based on the assumption that the market maker liquidates his inventory at the fair price at time t = T . This hypothesis is questionable and we propose to introduce an additional term to model liquidation cost that can also be interpreted as a penalization term for having a non-zero inventory at time T .

From a mathematical perspective it means that the control problem is now:

sup (δ a t )t,(δ b t )t∈A E [-exp (-γ(X T + q T S T -c|q T |))]
where c|q| represents the penalization term modeling the incurred cost at the end of the period for not having cleared the inventory 9 .

The analysis can then be done in the same way as in the initial model and we get the following result: Proposition 4 (Resolution with inventory liquidation cost). Let us consider a family of functions (v q ) |q|≤Q solution of the linear system of ODEs that follows:

∀q ∈ {-Q + 1, . . . , Q -1}, vq (t) = αq 2 v q (t) -η (v q-1 (t) + v q+1 (t)) vQ (t) = αQ 2 v Q (t) -ηv Q-1 (t) v-Q (t) = αQ 2 v -Q (t) -ηv -Q+1 (t)
with ∀q ∈ {-Q, . . . , Q}, v q (T ) = e -kc|q| , where α = k 2 γσ 2 and η = A(1

+ γ k ) -(1+ k γ ) .
Then, optimal quotes are given by:

s -s b * (t, q, s) = δ b * (t, q) = 1 k ln ( v q (t) v q+1 (t) ) + 1 γ ln ( 1 + γ k ) s a * (t, q, s) -s = δ a * (t, q) = 1 k ln ( v q (t) v q-1 (t) ) + 1 γ ln ( 1 + γ k
) and the bid-ask spread quoted by the market maker is :

ψ * (t, q) = - 1 k ln ( v q+1 (t)v q-1 (t) v q (t) 2 ) + 2 γ ln ( 1 + γ k )
Moreover, the asymptotic behavior of the optimal quotes and the bid-ask spread does not depend on the liquidation cost coefficient c and is the same as in the initial model.

6 Discussion on the model

Exogenous nature of prices

In our model, a fair price is introduced and modeled by a brownian motion independent of the behavior of the agent. Since we are modeling a single market maker who operates through limit orders, it seems natural to consider the price process exogenous in the medium run. However, even if we neglect the impact of our market maker on the market, the very notion of fair price must be clarified. The fair price we consider may be thought of as a smoothed version of the current mid-price of the market. It is not the current mid-price because it would in that case depend on the actions of the market maker. It is neither a medium-run fair value for the stock (or fondamental value). The only important characteristic, that in fact somehow defines S, is that the execution probabilities must be well described as depending on the distance to the fair price we consider.

Another issue linked to the exogenous nature of prices is the absence of market impact or more generally the independence between the Poisson processes and the brownian motion. This issue is a deep one and, for a part of it, it points out the lack of market impact models for passive orders in the financial literature.

Constant parameters

A related issue is that the parameters σ, A and k are constant. While models can be developed to take account of deterministic or stochastic variations of the parameters, the most important point is to take account of the links between the different parameters. σ, A and k should not indeed be considered independent of one another since, for instance, an increase in A should induce an increase in the number of trades and hence an increase in price volatility. Some attempts have been made in this direction to model the link between volatility and trades intensity. Hawkes processes (see [START_REF] Bacry | Modeling microstructure noise with mutually exciting point processes[END_REF]) for instance may provide good modeling perspectives to link the parameters but this has been left aside for future work.

Constant size of orders

Another apparent issue of the model is that market makers set orders of size 1 at all times. A first remark is that, if this is an issue, it is only limited to the fact that orders are of constant size since we can consider that the unitary orders stand for orders of constant size δq or equivalently, though more abstractly, orders of size 1 on a bunch of δq stocks.

If all the orders are of size δq then the stochastic process representing cash is:

d Xt = δq(S a t dN a t -S b t dN b t ) = δq × dX t
where the jump processes model the event of being hit by an aggressive order (of size δq).

Then, if we consider that an order of size δq is a unitary order on a bunch of δq stocks, we can write qt = δq × q t and the optimization criterion becomes:

sup

(δ a t )t,(δ b t )t∈A E [ -exp ( -γ( XT + qT S T ) )] = sup (δ a t )t,(δ b t )t∈A E [-exp (-γδq(X T + q T S T ))]
Hence, we can solve the problem for orders of size δq using a modified risk aversion, namely solving the problem for unitary orders, with γ multiplied by δq.

However, if we can transform the problem with orders of constant size δq into the initial problem where δq = 1, the parameters must be adjusted in accordance with the fact that orders are of size δq. As such, it must be noticed that A has to be estimated to take account of the expected proportion of an order of size δq filled by a single trade and approximations must be made to take account of market making with orders of constant size. In fact, we can consider that, after each trade that partially filled the order, the market maker sends a new order so that the total size of his orders is δq, using a convex combination of the model recommendations for the price 10 , since in that case the inventory is not a multiple of δq.

In our view, this issue is important but it should not be considered a problem to describe qualitative market maker's behavior and appropriate approximation on A allows us to believe that the error made, as far as quantitative modeling results are concerned, is relatively small.

Applications

In spite of the limitations discussed above we used this model to backtest the strategy on real data. We rapidly discuss the change that had to be made to the model to use it in reality and the way backtests have been carried out. Then we present an instance of the results on the French stock AXA.

Empirical use

Before using the above model in reality, we need to discuss some features of the model that need to be adapted before any backtest is possible. First of all, the model is continuous in both time and space while the real control problem under scrutiny is intrinsically discrete in space, because of the tick size, and in time, because orders have a certain priority and changing position too often reduces the actual chance to be reached by a market order. Hence, the model has to be reinterpreted in a discrete way. In terms of prices, quotes must not be between two ticks and we decided to ceil or floor the optimal quotes with probabilities that depend on the respective proximity to the neighboring quotes. In terms of time, an order is sent to the market and is not canceled nor modified for a given period ∆t (say 20 or 60 seconds), unless a trade occurs and, though perhaps partially, fills one of the market maker's orders. Now, when a trade occurs and changes the inventory or when an order stayed in the order book for longer than ∆t, then the optimal quotes on both sides are updated and, if necessary, new orders are inserted. Now, concerning the parameters, σ, A and k can be calibrated on trade-by-trade limit order book data while γ has to be chosen. However, it is well known by practitioners that A and k have to depend at least on the actual market bid-ask spread. Since we do not explicitly take into account the underlying market, there is no market bid-ask spread in the model. Thus, we simply chose to calibrate k and A as functions of the market bid-ask spread, making then an off-model hypothesis.

Turning to the backtests, they were carried out with trade-by-trade data and we assumed that our orders were entirely filled when a trade occurred above (resp. below) the ask (resp. bid) price quoted by the market maker.

Results

To present the results, we chose to illustrate the case of the French stock AXA on November 2 nd 2010. We first show the evolution of the inventory and we see that this inventory mean-reverts around 0. Now, to better understand the very nature of the strategy, we focused on a subperiod of 20 minutes and we plotted the state of the market both with the quotes of the market maker. Trades occurrences involving the market maker are signalled by a dot.

Conclusion

In this paper we presented a model for the optimal quotes of a market maker. Starting from a model in line with Avellaneda ans Stoikov [START_REF] Avellaneda | High-frequency trading in a limit order book[END_REF] and rooted to Ho and Stoll [START_REF] Ho | Optimal dealer pricing under transactions and return uncertainty[END_REF], we introduced a change of variables11 that allows to find exact expressions for the quotes. Then, we exhibited the asymptotic value of the optimal quotes and argued that the asymptotic values were very good approximations for the quotes even for rather small times. Closed-form approximations were then obtained using spectral arguments. The model is finally backtested on real data and the results are promising.

Appendix

Proof of Proposition 1 and Theorem 2:

Let us consider a strictly positive solution (v q ) q of (S) and introduce u(t, x, q, s) = -exp (-γ(x + qs)) v q (t) -γ k .

Then:

∂ t u + 1 2 σ 2 ∂ 2 ss u = - γ k vq (t) v q (t) u + γ 2 σ 2 2 q 2 u
Now, concerning the first part of the hamiltonian, we have:

sup δ b λ b (δ b ) [ u(t, x -s + δ b , q + 1, s) -u(t, x, q, s) ] = sup δ b Ae -kδ b u(t, x, q, s) [ exp ( -γδ b ) ( v q+1 (t) v q (t) ) -γ k -1 ]
The first order condition of this problem corresponds to a maximum (because u is negative) and writes:

(k + γ) exp ( -γδ b * ) ( v q+1 (t) v q (t) ) -γ k = k
Hence:

δ b * = 1 k ln ( v q (t) v q+1 (t) ) + 1 γ ln ( 1 + γ k ) and sup δ b λ b (δ b ) [ u(t, x -s + δ b , q + 1, s) -u(t, x, q, s) ] = - γ k + γ A exp(-kδ b * )u(t, x, q, s) = - γA k + γ ( 1 + γ k ) -k γ v q+1 (t) v q (t) u(t, x, q, s)
Similarly, the maximizer for the second part of the hamiltonian is:

δ a * = 1 k ln ( v q (t) v q-1 (t) ) + 1 γ ln ( 1 + γ k ) and sup δ a λ a (δ a ) [u(t, x + s + δ a , q -1, s) -u(t, x, q, s)] = - γ k + γ A exp(-kδ a * )u(t, x, q, s) = - γA k + γ ( 1 + γ k ) -k γ v q-1 (t) v q (t) u(t, x, q, s)
Hence, putting the three terms together we get:

∂ t u(t, x, q, s) + 1 2 σ 2 ∂ 2 ss u(t, x, q, s) + sup δ b λ b (δ b ) [ u(t, x -s + δ b , q + 1, s) -u(t, x, q, s) ] + sup δ a λ a (δ a ) [u(t, x + s + δ a , q -1, s) -u(t, x, q, s)] = - γ k vq (t) v q (t) u + γ 2 σ 2 2 q 2 u - γA k + γ ( 1 + γ k ) k γ [ v q+1 (t) v q (t) + v q-1 (t) v q (t) ] u = - γ k u v q (t) [ vq (t) - kγσ 2 2 q 2 v q (t) + A ( 1 + γ k ) - ( 1+ k γ ) (v q+1 (t) + v q-1 (t)) ] = 0
Now, noticing that the terminal condition for v q is consistent with the terminal condition for u, we get that u verifies (HJB).

Proof of Theorem 1 and Theorem 3:

Before starting the very proof, let us introduce the necessary functional framework.

Let us introduce H

= { u ∈ ℓ 2 (Z), ∑ q∈Z αq 2 u 2 q + η(u q+1 -u q ) 2 < +∞ } .
H is a Hilbert space equipped with the scalar product:

⟨v, w⟩ H = ∑ q∈Z αq 2 v q w q + η(v q+1 -v q )(w q+1 -w q ), ∀v, w ∈ H
The first preliminary lemma indicates that the ℓ 2 (Z)-norm can be controlled by the Hnorm.

Lemma 1. ∃C > 0, ∀w ∈ H, ∥w∥ ℓ 2 (Z) ≤ C∥w∥ H Proof: ∀w ∈ H, ∥w∥ 2 ℓ 2 (Z) = |w 0 | 2 + ∑ q∈Z * |w q | 2 ≤ |w 0 | 2 + 1 α ∥w∥ 2 H ≤ (|w 1 | + |w 0 -w 1 |) 2 + 1 α ∥w∥ 2 H ≤   ( √ 1 α + √ 1 η ) 2 + 1 α   ∥w∥ 2 H
A second result that is central in the proof of our results is that H is compactly embedded in ℓ 2 (Z).

Lemma 2. H is compactly embedded in ℓ 2 (Z)

Proof:

To prove the result we consider a bounded sequence (s k ) k∈N in H N . For each k ∈ N we introduce ŝk defined by: ŝk 0 = s k 0 , ∀q ∈ Z * , ŝk q = qs k q For (s k ) k∈N is a bounded sequence in H N , (ŝ k ) k∈N is a bounded sequence in ℓ 2 (Z) N . Hence, we can find ŝ∞ ∈ ℓ 2 (Z) so that there exists a subsequence indexed by (k j ) j∈N such that (ŝ k j ) j∈N weakly converges toward ŝ∞ in ℓ 2 (Z). Now, we can define s ∞ ∈ H by the inverse transformation:

s ∞ 0 = ŝ∞ 0 , ∀q ∈ Z * , s ∞ q = 1 q ŝ∞ q
and it is easy to check that (s k j ) N converges in the ℓ 2 (Z) sense toward s ∞ . Indeed,

∥s k j -s ∞ ∥ 2 ℓ 2 (Z) ≤ |s k j 0 -s ∞ 0 | 2 + ∑ q∈Z * 1 q 2 |ŝ k j q -ŝ∞ q | 2 = |ŝ k j 0 -ŝ∞ 0 | 2 + ∑ q̸ =0,|q|≤N 1 q 2 |ŝ k j q -ŝ∞ q | 2 + ∑ |q|>N 1 q 2 |ŝ k j q -ŝ∞ q | 2
The first two terms tend to 0 because (ŝ k j ) N weakly converges in ℓ 2 (Z) towards ŝ∞ . The last one can be made smaller than any ϵ > 0 as N becomes large because ∑ |q|>N 1 q 2 tends to zero as N tends to infinity and (∥ŝ k j -ŝ∞ ∥ ℓ 2 (N) ) j∈N is a bounded sequence. Now, we are going to consider a linear operator L that is linked to the system (S). L is defined by

L : f ∈ ℓ 2 (Z) → v ∈ H ⊂ ℓ 2 (Z)
where ∀q ∈ Z, αq 2 v q -η(v q+1 -2v q + v q-1 ) = f q

We need to prove that L is well-defined and we use the weak formulation of the equation.

f q w q = ∑ q∈Z αq 2 v q w q + η(v q+1 -v q )(w q+1 -w q ) = α ∑ q∈Z q 2 v q w q + η ∑ q∈Z (v q+1 -v q )w q+1 -η ∑ q∈Z (v q+1 -v q )w q = α ∑ q∈Z q 2 v q w q + η ∑ q∈Z (v q -v q-1 )w q -η ∑ q∈Z (v q+1 -v q )w q
This proves ∀q ∈ Z, αq 2 v q -η(v q+1 -2v q + v q-1 ) = f q . Conversely, if ∀q ∈ Z, αq 2 v q -η(v q+1 -2v q + v q-1 ) = f q , then we have by the same manipulations as before that:

∀w ∈ H, ⟨v, w⟩ H = ⟨f, w⟩ ℓ 2 (Z)
Hence L is well-defined, obviously linear and Lf ∈ H. Now, if we take w = Lf we get

⟨Lf, Lf ⟩ H = ⟨f, Lf ⟩ ℓ 2 (Z) ≤ ∥f ∥ ℓ 2 (Z) ∥Lf ∥ ℓ 2 (Z) ≤ C∥f ∥ ℓ 2 (Z) ∥Lf ∥ H so that ∥Lf ∥ H ≤ C∥f ∥ ℓ 2 (Z)
and L is hence continuous. Now, we are able to prove important properties about L. As far as the positiveness of the operator is concerned we just need to notice that, by definition:

∀f ∈ ℓ 2 (Z), ⟨Lf, f ⟩ ℓ 2 (Z) = ∥Lf ∥ 2 H ≥ 0 For compactness, we know that ∥Lf ∥ H ≤ C∥f ∥ ℓ 2 (Z) and Lemma 2 allows to conclude. Now, we prove that the operator L is self-adjoint.

Consider f 1 , f 2 ∈ ℓ 2 (Z), we have:

⟨f 1 , Lf 2 ⟩ ℓ 2 (Z) = ⟨Lf 1 , Lf 2 ⟩ H = ⟨Lf 2 , Lf 1 ⟩ H = ⟨f 2 , Lf 1 ⟩ ℓ 2 (Z) = ⟨Lf 1 , f 2 ⟩ ℓ 2 (Z)
Now, we can go to the very proof of Theorem 1 and Theorem 3.

Step 1: Spectral decomposition and building of a solution when the terminal condition is in ℓ 2 (Z).

We know that there exists an orthogonal basis (f k ) k∈N of ℓ 2 (Z) made of eigenvectors of L (that in fact belongs to H and we can take for instance ||f k || H = 1) and we denote λ k > 0 the eigenvalue12 associated to f k (we suppose that the eigenvalues are ordered, λ 0 being the largest one). We have:

αq 2 f k q -η(f k q+1 -2f k q + f k q-1 ) = 1 λ k f k q
Hence, if we want to solve (S ′ ) that is similar to (S) but with a terminal condition v(T ) ∈ ℓ 2 (Z) instead of v(T ) = 1 (where 1 stands for the sequence equal to 1 for all indices), classical argument shows that we can search for a solution of the form

v(t) = ∑ k∈N µ k (t)f k . Since ∀q ∈ Z vq (t) = αq 2 v q (t) -η (v q-1 (t) + v q+1 (t)) = αq 2 v q (t) -η (v q+1 (t) -2v q (t) + v q-1 (t)) -2ηv q (t) We must have dµ k dt (t) = ( 1 λ k -2η)µ k (t)
and hence, since λ k → 0 we can easily define a solution of (S ′ ) by:

v(t) = ∑ k∈N ⟨v(T ), f k ⟩ ℓ 2 (Z) exp (( 2η - 1 λ k ) (T -t) ) f k and the solution is in fact in C ∞ ([0, T ], ℓ 2 (Z))
Step 2: Building of a solution when v(T ) = 1

The first thing to notice is that H ⊂ ℓ 1 (Z) (indeed, w ∈ H ⇒ (qw q ) q ∈ ℓ 2 (Z) ⇒ (w q ) q ∈ ℓ 1 (Z) by Cauchy-Schwarz inequality). Hence, the sequence v(T ) that equals 1 at each index is in H ′ , the dual of H. As a consequence, to build a solution of (S), we can consider a similar formula:

v(t) = ∑ k∈N ⟨1, f k ⟩ H ′ ,H exp (( 2η - 1 λ k ) (T -t) ) f k
Step 3: Uniqueness Uniqueness follows easily from the ℓ 2 (Z) analysis. If indeed v(T ) = 0 we see that we must have that

∀k ∈ Z, ⟨f k , v(t)⟩ ℓ 2 (Z) = d⟨f k , v(t)⟩ ℓ 2 (Z) dt = ( 1 λ k -2η)⟨f k , v(t)⟩ ℓ 2 (Z) Hence, ∀k ∈ Z, ⟨f k , v(T )⟩ ℓ 2 (Z) = 0 =⇒ ∀k ∈ Z, ∀t ∈ [0, T ], ⟨f k , v(t)⟩ ℓ 2 (Z) = 0 and v = 0.
Step 4: Asymptotics

To prove Theorem 3, we will show that the largest eigenvalue λ 0 of L is simple and that the associated eigenvector f 0 can be chosen so as to be a strictly positive sequence.

If this is true then we have ∀q ∈ Z, v q (0)

∼ T →∞ ⟨1, f 0 ⟩ H ′ ,H f 0 q exp ( (2η -1 λ 0 )T ) so that the result is proved with δ b * ∞ (q) = 1 γ ln ( 1 + γ k ) + 1 k ln ( f 0 q f 0 q+1 ) δ a * ∞ (q) = 1 γ ln ( 1 + γ k ) + 1 k ln ( f 0 q f 0 q-1
)

Hence we just need to prove the following lemma:

Lemma 5. The eigenvalue λ 0 is simple and any associated eigenvector is of constant sign (in a strict sense).

Proof:

Let us consider the following characterization of λ 0 and ofthe associated eigenvectors (this characterization follows from the spectral decomposition):

1 λ 0 = inf f ∈ℓ 2 (Z) ∥f ∥ 2 H ∥f ∥ 2 ℓ 2 (Z) = inf ∥f ∥ ℓ 2 (Z) =1 ∥f ∥ 2 H = inf ∥f ∥ ℓ 2 (Z) =1 ∑ q∈Z αq 2 f 2 q + η(f q+1 -f q ) 2
Let us consider f an eigenvector associated to λ 0 . We have that:

∑ q∈Z αq 2 |f q | 2 + η(|f q+1 | -|f q |) 2 ≤ ∑ q∈Z αq 2 f 2 q + η(f q+1 -f q ) 2
Hence, since |f | has the same ℓ 2 (Z)-norm as f , we know that |f | is an eigenvector associated to λ 0 . This proves that there exists a strictly positive eigenvector associated to λ 0 . Now, if the eigenvalue λ 0 were not simple, there would exist an eigenvector g associated to λ 0 with ⟨|f |, g⟩ ℓ 2 (Z) = 0. Hence, there would exist both positive and negative values in the sequence g. But, in that case, since |g| must also be an eigenvector associated to λ 0 , we must have equality in the following inequality:

Now, since αq

2 |f q | -η(|f q+1 | -2|f q | + |f q-1 |) = 1 λ 0 |f q |, if |f q | = 0 at some point q, we have -η(|f q+1 | + |f q-1 |) = 0
∑ q∈Z αq 2 |g q | 2 + η(|g q+1 | -|g q |) 2 ≤ ∑ q∈Z αq 2 g 2 q + η(g q+1 -g q ) 2
In particular, we must have that ||g q+1 | -|g q || = |g q+1 -g q |, ∀q. This implies that ∀q, either g q and g q+1 are of the same sign or at least one of the two terms is equal to 0. Thus, since g cannot be of constant sign, there must exist q so that g q = 0. But then, because |g| is also an eigenvector associated to λ 0 we have by immediate induction, as above, that g = 0. This proves that there is no such g and that the eigenvalue is simple.

Step 5: Positiveness So far, we did not prove that v, the solution of (S) was strictly positive. A rapid way to prove that point is to use a Feynman-Kac-like representation of v. If (q s ) s is a continuous Markov chain on Z with intensities η to jump to immediate neighbors, then we have the following representation for v:

v q (t) = E [ exp ( - ∫ T t (αq 2 s -2η)ds ) q t = q ]
This representation guarantees that v > 0.

This ends the proof of Theorems 1 and 3

Proof of Proposition 2:

The same computations as for Proposition 1 lead to the result.

Proof of Theorem 4:

Using Proposition 2, because the functions v q s are strictly positive as above, we see that u is a solution of (HJB). Then, we are going to use a verification argument to prove that u is the value function of the optimal control problem under consideration and prove subsequently that the optimal controls are as given in the Theorem.

Let us consider processes (ν b ) and (ν a ) ∈ A. Let t ∈ [0, T ) and let us consider the following processes for τ ∈ [t, T ]:

dS t,s τ = σdW τ , S t,s t = s dX t,x,ν τ = (S τ + ν a τ )dN a τ -(S τ -ν b τ )dN b τ , X t,x,ν t = x dq t,q,ν τ = dN b τ -dN a τ , q t,q,ν t = q
where the point process N b has stochastic intensity (λ b τ ) τ with λ b τ = Ae -kν b τ 1 q τ -<Q and where the point process N a has stochastic intensity (λ a τ ) τ with λ a τ = Ae -kν a τ 1 q τ ->-Q 13 .

13 These intensities are bounded since ν b and ν a are bounded from below. Now, since u is smooth, let us write Itô's formula for u, between t and t n where

t n = T ∧ inf{τ > t, |S τ -s| ≥ n or |N a τ -N a t | ≥ n or |N b τ -N b t | ≥ n} (n
being a strictly positive integer): u(t n , X t,x,ν tn-, q t,q,ν tn-, S t,s tn ) = u(t, x, q, s) + ∫ tn t ( ∂ τ u(τ, X t,x,ν τ -, q t,q,ν τ -, S t,s τ ) + σ 2 2 ∂ 2 ss u(τ, X t,x,ν τ -, q t,q,ν τ -, S t,s τ )

) dτ + ∫ tn t ( u(τ, X t,x,ν τ -+ S t,s τ + ν a τ , q t,q,ν τ --1, S t,s τ ) -u(τ, X t,x,ν τ -, q t,q,ν τ -, S t,s τ )

) λ a τ dτ + ∫ tn t ( u(τ, X t,x,ν τ --S t,s τ + ν b τ , q t,q,ν τ -+ 1, S t,s τ ) -u(τ, X t,x,ν τ -, q t,q,ν τ -, S t,s τ )

) λ b τ dτ + ∫ tn t σ∂ s u(τ, X t,x,ν τ -, q t,q,ν τ -, S t,s τ )dW τ + ∫ tn t ( u(τ, X t,x,ν τ -+ S t,s τ + ν a τ , q t,q,ν τ --1, S t,s τ ) -u(τ, X t,x,ν τ -, q t,q,ν τ -, S t,s τ )

) dM a τ + ∫ tn t ( u(τ, X t,x,ν τ --S t,s τ + ν b τ , q t,q,ν τ -+ 1, S t,s τ ) -u(τ, X t,x,ν τ -, q t,q,ν τ -, S t,s τ )

) dM b τ
where M b and M a are compensated processes associated respectively to N b and N a for the intensity processes (λ b τ ) τ and (λ a τ ) τ . Now, because v is strictly positive on a compact set, it has a strictly positive lower bound and v qτ (τ ) -γ k is bounded along the trajectory, independently of the trajectory. Also, because ν b and ν a are bounded from below, and because of the definition of t n , all the terms in the stochastic integrals are bounded and, local martingales being in fact martingales, we have: E [ u(t n , X t,x,ν tn-, q t,q,ν tn-, S t,s tn ) ] = u(t, x, q, s)

+E

[∫ tn t ( ∂ τ u(τ, X t,x,ν τ -, q t,q,ν τ -, S t,s τ ) + σ 2 2 ∂ 2 ss u(τ, X t,x,ν τ -, q t,q,ν τ -, S t,s τ )

) dτ + ∫ tn t ( u(τ, X t,x,ν τ -+ S t,s τ + ν a τ , q t,q,ν τ --1, S t,s τ ) -u(τ, X t,x,ν τ -, q t,q,ν τ -, S t,s τ )

) λ a τ dτ + ∫ tn t ( u(τ, X t,x,ν τ --S t,s τ + ν b τ , q t,q,ν τ -+ 1, S t,s τ ) -u(τ, X t,x,ν τ -, q t,q,ν τ -, S t,s τ )

) λ b τ dτ ]
Using the fact that u solves (HJB), we have that E [ u(t n , X t,x,ν tn-, q t,q,ν tn-, S t,s tn )

] ≤ u(t, x, q, s)

with equality when the controls are taken equal the maximizers of the hamiltonians (these controls being in A because v is bounded and has a strictly positive lower bounded).

Now, if we prove that lim n→∞ E [ u(t n , X t,x,ν tn-, q t,q,ν tn-, S t,s tn )

] = E [ u(T, X t,x,ν T , q t,q,ν T , S t,s T )

] ,

we will have that for all controls ν b and ν a in A:

E [ -exp
( -γ(X t,x,ν T + q t,q,ν T S t,s T )

)] = E
[ u(T, X t,x,ν T , q t,q,ν T , S t,s T )

] ≤ u(t, x, q, s)

with equality for ν b t = δ b * (t, q t-) and ν a t = δ a * (t, q t-).

Hence: sup (ν a t )t,(ν b t )t∈A E [ -exp ( -γ(X t,x,ν T + q t,q,ν T S t,s T )

)] = E [ -exp
( -γ(X t,x,δ * T + q t,q,δ * T S t,s T )

)] and this will give the result.

It remains to prove that lim n→∞ E [ u(t n , X t,x,ν tn-, q t,q,ν tn-, S t,s tn )

] = E
[ u(T, X t,x,ν T , q t,q,ν T , S t,s T )

] .

First, we have, almost surely, that u(t n , X t,x,ν tn-, q t,q,ν tn-, S t,s tn ) tends to u(T, X t,x,ν T -, q t,q,ν T -, S t,s T ). Then, in order to prove that the sequence is uniformly integrable we will bound it in L 2 . However, because of the uniform lower bound on v already used early, it is sufficient to bound exp ( -γ ( X t,x,ν tn-+ q t,q,ν tn-S t,s tn

)) in L 2 .
But, X t,x,ν tn-+ q t,q,ν tn-S t,s tn = x + qs +

∫ tn t ν a τ dN a τ + ∫ tn t ν b τ dN b τ + σ ∫ tn t q t,q,ν τ dW τ ≥ x + qs -∥ν a -∥ ∞ N a T -∥ν b -∥ ∞ N b T + +σ ∫ tn t q t,q,ν τ dW τ
Hence E [ exp(-2γ(X t,x,ν tn-+ q t,q,ν tn-S t,s tn ))

]

≤ e -2γ(x+qs) E [ exp ( 2γ∥ν a -∥ ∞ N a T ) exp ( 2γ∥ν a -∥ ∞ N b T ) exp ( -2γσ ∫ tn t q t,q,ν τ dW τ )] ≤ e -2γ(x+qs) E [ exp ( 6γ∥ν a -∥ ∞ N a T )] 1 3 E[exp(6γ∥ν b -∥ ∞ N b T )] 1 3 E [ exp ( -6γσ
∫ tn t q t,q,ν τ dW τ )] 1 3

Now, since the intensity of each point process is bounded, the point processes have a Laplace transform and the first three terms of the product are finite (and independent of n). Concerning the last term, because |q t,q,ν τ | is bounded by Q, we know (for instance applying Girsanov's theorem and Hölder's inequality) that:

E [ exp ( -6γσ ∫ tn t q t,q,ν τ dW τ )] ≤ exp ( 3γ 2 σ 2 (t n -t)Q 2 ) ≤ exp ( 3γ 2 σ 2 Q 2 T )
Hence, the sequence is bounded in L 2 , then uniformly integrable, and we have:

lim n→∞ E
[ u(t n , X t,x,ν tn-, q t,q,ν tn-, S t,s tn )

] = E
[ u(T, X t,x,ν T -, q t,q,ν T -, S t,s T )

] = E
[ u(T, X t,x,ν T , q t,q,ν T , S t,s T )

]

We have proved that u is the value function and that δ b * and δ a * are optimal controls.

Proof of Theorem 5:

The demonstration of the result and the characterization of f 0 is the same as in Theorem 3 once it is noticed that the counterpart of L is now (M + 2ηI) -1 .

Figure 1 :

 1 Figure1: Left: Behavior of the optimal quotes with time and inventory. Right: Behavior of the optimal quotes with inventory, at time t = 0. σ = 0.3 Tick•s -1/2 , A = 0.9 s -1 , k = 0.3 Tick -1 , γ = 0.01 Tick -1 , T = 600 s.

Figure 2 :

 2 Figure2: Asymptotic behavior of optimal quotes and the bid-ask spread (bold line). Approximation (dotted line). Left:σ = 0.4 Tick • s -1/2 , A = 0.9 s -1 , k = 0.3 Tick -1 , γ = 0.01 Tick -1 , T = 600 s. Right: σ = 1.0 Tick • s -1/2 , A = 0.2 s -1 , k = 0.3 Tick -1 , γ = 0.01 Tick -1 , T = 600 s.

Figure 3 :

 3 Figure 3: Asymptotic optimal quotes and bid-ask spread for different inventories and different values for the volatility σ. A = 0.9 s -1 , k = 0.3 Tick -1 , γ = 0.01 Tick -1 , T = 600 s.

Figure 4 :

 4 Figure 4: Asymptotic optimal quotes and bid-ask spread for different inventories and different values of A. σ = 0.3 Tick • s -1/2 , k = 0.3 Tick -1 , γ = 0.01 Tick -1 , T = 600 s.

Figure 5 :

 5 Figure 5: Asymptotic optimal quotes and bid-ask spread for different inventories and different values of k. σ = 0.3 Tick • s -1/2 , A = 0.9 s -1 , γ = 0.01 Tick -1 , T = 600 s.

Figure 6 :

 6 Figure6: Asymptotic optimal quotes and bid-ask spread for different inventories and different values for the risk aversion parameter γ. Left: σ = 0.3 Tick • s -1/2 , A = 0.9 s -1 , k = 0.3 Tick -1 , T = 600 s. Right: σ = 0.6 Tick • s -1/2 , A = 0.9 s -1 , k = 0.9 Tick -1 , T = 600 s

Figure 7 :

 7 Figure 7: Inventory when the strategy is used on AXA (02/11/2010) from 10:00 to 16:00 with γ = 0.05 Tick -1

Figure 8 :

 8 Figure 8: Details for the quotes and trades when the strategy is used on AXA (02/11/2010) with γ = 0.05 Tick -1 . Thin lines represent the market while bold lines represent the quotes of the market maker. Dotted lines are associated to the bid side while plain lines are associated to the ask side. Black points represent trades in which the market maker is involved.

Figure 9 :

 9 Figure 9: Details for the inventory when the strategy is used on AXA (02/11/2010) with γ = 0.05 Tick -1

Lemma 4 .

 4 L is a positive, compact, self-adjoint operator Proof:

  and this induces |f q+1 | = |f q-1 | = 0, and |f | = 0 by immediate induction. Since f ̸ = 0, we must have therefore |f | > 0.

  Lemma 3. L is a well-defined linear (continuous) operator.Moreover ∀f ∈ ℓ 2 (Z), ∀w ∈ H, ⟨Lf, w⟩ H = ⟨f, w⟩ ℓ 2 (Z) Let us consider f ∈ ℓ 2 (Z). Because of Lemma 1, w ∈ H → ⟨f, w⟩ ℓ 2 (Z) is continuous. Hence,by Riesz representation Theorem there exists a unique v ∈ H such that ∀w ∈ H, ⟨v, w⟩ H = ⟨f, w⟩ ℓ 2 (Z) .

	Proof:
	This equation writes
	∑
	∀w ∈ H,
	q∈Z

We suppose that this high-frequency market maker does not "make" the price in the sense that he has no market power. In other words, we assume that his size is small enough to consider price dynamics exogenous. Small high-frequency proprietary trader operating on both sides would be another way to describe our agent.

c is a positive number that represents the cost per share in the inventory at time T .

If the optimal quote changed, the remaining part of the order is canceled before a new order is inserted. Otherwise, the market maker may just insert a new order so that the cumulated size of his orders is δq.

In a companion paper (see[START_REF] Guéant | Optimal Execution with Limit Orders[END_REF]) we used a change of variables similar to the one introduced above to solve the Hamilton-Jacobi-Bellman equation associated to an optimal execution problem with passive orders.

0 cannot be an eigenvalue. If indeedλ k = 0 then ∀w ∈ H, ⟨f k , w⟩ ℓ 2 (Z) = ⟨Lf k , w⟩ H = 0. But because H is dense in ℓ 2 (Z), f k = 0.


Olivier Guéant

From infinity to one: The reduction of some mean field games to a global control problem

), from which the MFG equations can be deduced. Then, this Master equation can be reinterpreted using a global control problem inducing the same behaviors as in the non-cooperative initial mean field game.

Introduction

Mean field games have been introduced in 2006 by J.-M. Lasry and P.-L. Lions [START_REF] Lasry | Jeux à champ moyen i. le cas stationnaire[END_REF][START_REF] Lasry | Jeux à champ moyen ii. horizon fini et contrôle optimal[END_REF][START_REF] Lasry | Mean field games[END_REF] to generalize stochastic differential games to games involving a continuum of players. Since 2006, many applications of mean field games have been proposed, particularly in economics (see for instance [START_REF] Guéant | Mean field games and applications to economics[END_REF], [START_REF] Guéant | Mean field games and applications[END_REF], or [START_REF] Lachapelle | Computation of mean field equilibria in economics[END_REF]) and an important effort has been made to solve the partial differential equations associated to mean field games when both time and the state space are continuous (see [START_REF] Achdou | Mean field games: numerical methods for the planning problem[END_REF], [START_REF] Achdou | Mean field games: Numerical methods[END_REF], [START_REF] Guéant | Mean field games equations with quadratic hamiltonian: a specific approach[END_REF], [START_REF] Lachapelle | Computation of mean field equilibria in economics[END_REF], etc). In this paper, we consider a mean field game on a complex discrete state space that is represented by a graph and we explain the discrete counterpart of the MFG equations and of the Master equation formally introduced in [START_REF] Lions | Cours au collège de france : Théorie des jeux à champs moyens[END_REF]. This Master equation, or in our discrete case the Master equations, "contains" the MFG equations and allows for the introduction of random noise (although this question is not tackled here). In addition to these Master equations that can be exposed in a simple way in this discrete context without relying on differential calculus in a space of probability measures, we provide an interpretation of them as the equations solved by the partial differentials of a function that solves a single Hamilton-Jacobi equation in high dimension associated to a global optimization problem on the graph.

In the first section, we introduce the setting of our mean field game on a graph and define what a Nash-MFG equilibrium is. Then, in section 2, we define the MFG equations in the case of a graph, along with the Master equations, and we show how to deduce a Nash-MFG equilibrium from smooth solutions of these equations. In section 3 we define a global optimization problem on the graph and show how the solution of the associated Hamilton-Jacobi equation is related to the Master equations and eventually to the initial mean field game.

The author wishes to acknowledge the helpful conversations with Yves Achdou (Université Paris-Diderot), Guy Barles (Université de Tours), Diogo Gomes (IST Lisboa), Jean-Michel Lasry (Université Paris-Dauphine) and Pierre-Louis Lions (Collège de France). Also, the research presented in this paper benefited from the support of the Conseil Français de l'Energie.

* UFR de Mathématiques, Laboratoire Jacques-Louis Lions, Université Paris-Diderot. 175, rue du Chevaleret, 75013 Paris, France. olivier.gueant@ann.jussieu.fr

Mean field games in a graph

We consider a directed graph G whose nodes are indexed by integers from 1 to N . For each node i ∈ N = {1, . . . , N } we introduce V(i) ⊂ N \ {i} the set of nodes j for which a directed edge exists from i to j. The cardinal of this set is denoted d i and called the out-degree of the node i. Reciprocally, we denote V -1 (i) ⊂ N \ {i} the set of nodes j for which a directed edge exists from j to i. This graph G is going to be the state space of our mean field game and we suppose that there is a continuum of anonymous and identical players of size 1, playing a game on the graph as described in the next paragraphs 1 . Each player's position is represented by a continuous-time Markov chain (X t ) t with values in G and instantaneous transition probabilities at time t described by a collection of functions λ t (i, •) :

V(i) → R + (for each node i ∈ N ).
Each player is able to decide on the values of the transition probabilities at time t and pays an instantaneous cost2 L(i, (λ i,j ) j∈V(i) ) to set the value of λ(i, j) to λ i,j .

The assumptions made on the continuous functions L(i, •) are the following. First, we assume asymptotic super-linearity for each i ∈ N ; ∀i ∈ N , lim

λ∈R d i + ,|λ|→+∞ L(i, λ) |λ| = +∞
Then, we define the Hamiltonians H(i,

•): ∀i ∈ N , p ∈ R d i → H(i, p) = sup λ∈R d i + λ • p -L(i, λ)
and we assume that for each i ∈ N ,

H(i, •) is a C 1 function with 3 ∇H(i, p) = argmax λ∈R d i + λ • p -L(i, λ)
This assumption is satisfied as soon as for each i ∈ N , L(i, •) is a C 2 strongly convex function or if L(i, λ) = j∈V(i) C(i, j, λ i,j ) with each of the functions C(i, j, •) a strictly convex C 2 function.

Now, to define the mean field game, let us introduce a domain Ω ⊂ R N containing

P N = {(x 1 , . . . , x N ) ∈ [0, 1] n , N i=1 x i = 1}
and two functions f and g defined4 on N × Ω such that ∀i ∈ N , f (i, •) and g(i, •) are continuous on Ω. Now, let us also define the set A of admissible controls. We are only considering markovian controls and we define:

A = (λ t (i, j)) t∈[0,T ],i∈N ,j∈V(i) deterministic |∀i ∈ N , ∀j ∈ V(i), t → λ t (i, j) ∈ L ∞ (0, T )
Now, for a given admissible control5 λ ∈ A and a given function m : t ∈ [0, T ] → (m(t, 1), . . . , m(t, N )) ∈ P N we define the payoff function J m : [0, T ] × N × A → R by:

J m (t, i, λ) = E T t (-L(X s , λ s (X s , •)) + f (X s , m(s)))) ds + g (X T , m(T ))
for (X s ) s∈[t,T ] a Markov chain on G, starting from i at time t, with instantaneous transition probabilities given by (λ s ) s∈[t,T ] .

From this we can adapt the definition of a (symmetric) Nash-MFG equilibrium to our context: Definition 1 (Nash-MFG symmetric equilibrium). A differentiable function m : t ∈ [0, T ] → (m(t, 1), . . . , m(t, N )) ∈ P N is said to be a Nash-MFG equilibrium, if there exists an admissible control λ ∈ A such that:

∀ λ ∈ A, ∀i ∈ N , J m (0, i, λ) ≥ J m (0, i, λ) and ∀i ∈ N , d dt m(t, i) = j∈V -1 (i) λ t (j, i)m(t, j) - j∈V(i) λ t (i, j)m(t, i)
In that case, λ is called an optimal control.

In this definition, m stands implicitly for the distribution of the players across the different nodes.

As for all mean field games, the problem is a fixed point problem since, starting from a (guessed) trajectory m, the control problem in Definition 1 induces trajectories for the players and to obtain a Nash-MFG equilibrium these individual trajectories must generate the right macroscopic trajectory m for the distribution of the players in G.

In the next section we are going to write the MFG equations associated to our problem, which we call the decentralized problem as it involves all the players, and see that these equations can be extracted from a set of equations called the Master equations, as introduced by J.-M. Lasry and P.-L. Lions and presented in [START_REF] Lions | Cours au collège de france : Théorie des jeux à champs moyens[END_REF] in a different framework.

MFG equations and the Master equation

As for any control problem we can associate, when m is fixed, a Hamilton-Jacobi equation to the above control problem. More exactly, since there are N states, we need to write down N Hamilton-Jacobi equations, one for each state. However, these backward equations need to be coupled with a system of forward transport equations that describe the resulting evolution of the distribution of players.

The graph counterpart of the two partial differential equations of classical mean field games (see [START_REF] Lasry | Jeux à champ moyen i. le cas stationnaire[END_REF][START_REF] Lasry | Jeux à champ moyen ii. horizon fini et contrôle optimal[END_REF][START_REF] Lasry | Mean field games[END_REF]) are the following:

Definition 2 (The G-MFG equations). The G-MFG equations consist in a system of 2N equations, the unknown being t ∈ [0, T ] → (u(t, 1), . . . , u(t, N ), m(t, 1), . . . , m(t, N )).

The first half of these equations are the Hamilton-Jacobi equations associated to the above problem and consist in the following system:

∀i ∈ N , d dt u(t, i) + H i, (u(t, j) -u(t, i)) j∈V(i) + f (i, m(t, 1), . . . , m(t, N )) = 0 with u(T, i) = g(i, m(t, 1), . . . , m(t, N )).
The second half of these equations are forward transport equations:

∀i ∈ N , d dt m(t, i) = j∈V -1 (i) ∂H(j, •) ∂p i (u(t, k) -u(t, j)) k∈V(j) m(t, j) - j∈V(i) ∂H(i, •) ∂p j (u(t, k) -u(t, i)) k∈V(i) m(t, i)
with (m(0, 1), . . . , m(0, N )) = m 0 ∈ P N given.

Now, we enounce a result saying that a C 1 solution of the G-MFG equations provides a Nash-MFG equilibrium and an optimal control: Proposition 1 (The G-MFG equations as a sufficient condition). Let m 0 ∈ P N and let us consider a C 1 solution (u(t, 1), . . . , u(t, N ), m(t, 1), . . . , m(t, N )) of the G-MFG equations with (m(0, 1), . . . , m(0, N )) = m 0 .

Then t → m(t) = (m(t, 1), . . . , m(t, N )) is a Nash-MFG equilibrium and the relations

λ t (i, j) = ∂H(i,•) ∂p j (u(t, k) -u(t, i)) k∈V(i) define an optimal control.

Proof:

Let us consider an admissible control λ ∈ A. Let us then consider an initial position i ∈ N and a Markov chain (X 0,i, λ t ) t starting in i at time 0, with instantaneous transition probabilities given by λ. Since the values taken by λ are bounded, there is almost surely a finite number Q of moves in the time interval [0, T ) and we can write (almost surely):

u T, X 0,i, λ T - = u(0, i)+   Q q=1 u t q , X 0,i, λ tq -u t q-1 , X 0,i, λ t q-1   +u T, X 0,i, λ T - -u t Q , X 0,i, λ t Q
where t 0 = 0 and the other t i s are the time of jumps.

Then:

u T, X 0,i, λ T - = u(0, i) + T 0 ∂u ∂t (t, X t-)dt + Q q=1 u t q , X 0,i, λ tq -u t q , X 0,i, λ tq- = u(0, i) + T 0 ∂u ∂t (t, X t-)dt + T 0 j∈V(X t-) u (t, j) -u t, X 0,i, λ t- λt (X t-, j)dt + M T
where (M t ) t is a local martingale starting from 0 that happens to be a martingale since u is bounded.

Hence:

E g(X 0,i, λ T , m(T )) = E g(X 0,i, λ T -, m(T -)) = u(0, i) +E   T 0   ∂u ∂t (t, X t-) + j∈V(X t-) u (t, j) -u t, X 0,i, λ t- λt (X t-, j)   dt   =⇒ E g(X 0,i, λ T , m(T )) - T 0 L(X t-, λ t (X t-, •))dt = u(0, i) +E   T 0   ∂u ∂t (t, X t-) -L(X t-, λ t (X t-, •)) + j∈V(X t-) u (t, j) -u t, X 0,i, λ t- λt (X t-, j)   dt  
By definition of u, we have that:

E g(X 0,i, λ T , m(T )) + T 0 (-L(X t-, λ t (X t-, •))) dt ≤ u(0, i) -E T 0 f (X 0,i, λ t-, m(t-))dt =⇒ E T 0 -L(X t , λ t (X t , •)) + f (X 0,i, λ t , m(t)) dt + g(X 0,i, λ T , m(T )) ≤ u(0, i)
with equality when λ is taken to be the control λ as described in the statement of the result (because of our assumption on the hamiltonians), this control being indeed admissible since the function u is bounded and since each

H(i, •) is C 1 . Hence: J m (0, i, λ) ≤ u(0, i) = J m (0, i, λ)
and this proves the result.

Existence and uniqueness of solutions to the G-MFG equations are now tackled. We first start with existence and our proof is based on a Schauder fixed-point argument and a priori estimates to obtain compactness. Then we will present a criterion to ensure uniqueness of m for C 1 solutions.

For the existence result, we first start with a Lemma stating that, for a fixed m, the N Hamilton-Jacobi equations amongst the G-MFG equations obey a maximum principle: Lemma 1 (Maximum principle). Let m : [0, T ] → P N be a continuous function. Let u : t ∈ [0, T ] → (u(t, 1), . . . , u(t, N )) be a C 1 function that verifies:

∀i ∈ N , - d dt u(t, i) -H i, (u(t, j) -u(t, i)) j∈V(i) -f (i, m(t, 1), . . . , m(t, N )) ≤ 0 with u(T, i) ≤ g(i, m(t, 1), . . . , m(t, N )). Let v : t ∈ [0, T ] → (v(t, 1), . . . , v(t, N )) be a C 1 function that verifies: ∀i ∈ N , - d dt v(t, i) -H i, (v(t, j) -v(t, i)) j∈V(i) -f (i, m(t, 1), . . . , m(t, N )) ≥ 0 with v(T, i) ≥ g(i, m(t, 1), . . . , m(t, N )). Then, ∀i ∈ N , ∀t ∈ [0, T ], v(t, i) ≥ u(t, i).
Proof:

Let us consider for a given ǫ > 0, a point (t

* , i * ) ∈ [0, T ] × N such that u(t * , i * ) -v(t * , i * ) -ǫ(T -t * ) = max (t,i)∈[0,T ]×N u(t, i) -v(t, i) -ǫ(T -t) If t ∈ [0, T ), then d dt (u(t * , i * ) -v(t * , i * ) -ǫ(T -t * )) ≤ 0. Also, by definition of (t * , i * ), ∀j ∈ V(i * ), u(t * , i * ) -v(t * , i * ) ≥ u(t * , j) -v(t * , j
) and hence, by definition of H(i * , •):

H i * , (v(t * , j) -v(t * , i * )) j∈V(i * ) ≥ H i * , (u(t * , j) -u(t * , i * )) j∈V(i * )
Combining these inequalities we get:

- d dt u(t * , i * )-H i * , (u(t * , j) -u(t * , i * )) j∈V(i * ) ≥ - d dt v(t * , i * )-H i * , (v(t * , j) -v(t * , i * )) j∈V(i * ) +ǫ
But this is in contradiction with the hypotheses on u and v.

Hence t * = T and max (t,i)∈[0,T ]×N u(t, i)-v(t, i)-ǫ(T -t) ≤ 0 because of the assumptions on u(T, i) and v(T, i).

This being true for any ǫ > 0, we have that max (t,i)∈[0,T ]×N u(t, i)v(t, i) ≤ 0. This lemma allows to provide a bound to any solution u of the N Hamilton-Jacobi equations and this bound is then used to obtain compactness in order to apply Schauder's fixed point theorem.

Proposition 2 (Existence of a solution to the G-MFG equations). Let m 0 ∈ P N . Under the assumptions made in section 1, there exists a C 1 solution (u, m) of the G-MFG equations such that m(0) = m 0 .

Proof:

Let m : [0, T ] → P N be a continuous function.

Let then consider the solution u : t ∈ [0, T ] → (u 1 (t), . . . , u N (t)) to the Hamilton-Jacobi equations:

∀i ∈ N , d dt u(t, i) + H i, (u(t, j) -u(t, i)) j∈V(i) + f (i, m(t, 1), . . . , m(t, N )) = 0 with u(T, i) = g(i, m(t, 1), . . . , m(t, N )).
This function u is a well defined C 1 function with the following bound coming from the above lemma:

sup i∈N u(•, i) ∞ ≤ sup i∈N g(i, •) ∞ + sup i∈N f (i, •) ∞ + sup i∈N |H(i, 0)| T
Using this bound and the fact that the functions H(i, •) are assumed to be C 1 , we can define a function m : [0, T ] → P N by:

∀i ∈ N , d dt m(t, i) = j∈V -1 (i) ∂H(j, •) ∂p i (u(t, k) -u(t, j)) k∈V(j) m(t, j) - j∈V(i) ∂H(i, •) ∂p j (u(t, k) -u(t, i)) k∈V(i) m(t, i) with ( m(0, 1), . . . , m(0, N )) = m 0 ∈ P N .
This function m is bounded and d m dt is also bounded, the bounds depending only on the functions f (i, •), g(i, •) and H(i, •), i ∈ N .

As a consequence, if we define Θ : m ∈ C([0, T ], P N ) → m ∈ C([0, T ], P N ), Θ is a continuous function (from classical ODEs theory) with Θ(C([0, T ], P N )) a relatively compact set (because of Ascoli's Theorem and the uniform Lipschitz property we just obtained).

Hence, by Schauder's fixed point theorem, there exists a fixed point m to Θ. If we then consider u associated to m by the Hamilton-Jacobi equations as above, (u, m) is a C 1 solution to the G-MFG equations.

Coming now to uniqueness, we deduce from the proof of uniqueness introduced in [START_REF] Lasry | Jeux à champ moyen i. le cas stationnaire[END_REF][START_REF] Lasry | Jeux à champ moyen ii. horizon fini et contrôle optimal[END_REF][START_REF] Lasry | Mean field games[END_REF], a criterion to ensure uniqueness of m for C 1 solutions of the G-MFG equations: Proposition 3 (m-Uniqueness for the G-MFG equations). Assume that f and g are such that:

∀(m 1 , m 2 ) ∈ P N ×P N , N i=1 (f (i, m 1 1 , . . . , m 1 N )-f (i, m 2 1 , . . . , m 2 N ))(m 1 i -m 2 i ) ≥ 0 =⇒ m 1 = m 2 and ∀(m 1 , m 2 ) ∈ P N ×P N , N i=1 (g(i, m 1 1 , . . . , m 1 N )-g(i, m 2 1 , . . . , m 2 N ))(m 1 i -m 2 i ) ≥ 0 =⇒ m 1 = m 2
Then, if (u, m) and (ũ, m) are two C 1 solutions of the G-MFG equations, we have m = m.

Proof:

The proof of this result is a straightforward adaptation of the classical proof of uniqueness for continuous MFG equations.

It consists in computing the value of

I = T 0 N i=1 d dt ((u(t, i) -ũ(t, i))(m(t, i) -m(t, i))) dt in two different ways.
We first know directly that

I = N i=1 (g(i, m(T, 1), . . . , m(T, N )) -g(i, m(T, 1), . . . , m(T, N )))(m(T, i) -m(T, i))
Now, differentiating the product we get, after reordering the terms that:

I = - T 0 N i=1 (f (i, m(t, 1), . . . , m(t, N )) -f (i, m(t, 1), . . . , m(t, N )))(m(t, i) -m(t, i))dt + T 0 N i=1 m(t, i) H(i, (ũ(t, k) -ũ(t, i)) k∈V(i) ) -H(i, (u(t, k) -u(t, i)) k∈V(i) ) - j∈V(i) ((u(t, i) -ũ(t, i)) -(u(t, j) -ũ(t, j))) ∂H(i, •) ∂p j (u(t, k) -u(t, i)) k∈V(i) dt + T 0 N i=1 m(t, i) H(i, (u(t, k) -u(t, i)) k∈V(i) ) -H(i, (ũ(t, k) -ũ(t, i)) k∈V(i) ) - j∈V(i) ((ũ(t, i) -u(t, i)) -(ũ(t, j) -u(t, j))) ∂H(i, •) ∂p j (ũ(t, k) -ũ(t, i)) k∈V(i) dt
Now, using the convexity of the hamiltonian functions, we know that:

T 0 N i=1 (f (i, m(t, 1), . . . , m(t, N )) -f (i, m(t, 1), . . . , m(t, N )))(m(t, i) -m(t, i))dt + N i=1
(g(i, m(T, 1), . . . , m(T, N ))g(i, m(T, 1), . . . , m(T, N )))(m(T, i)m(T, i)) ≥ 0

Hence, using the hypotheses on f and g, m = m.

A simple example of functions f and g satisfying the above criterion consists in taking for f (i, •) and g(i, •) functions of m i only, strictly decreasing in m i . Now we define the graph counterpart of the Master equation proposed by J.-M. Lasry and P.-L. Lions and presented in [START_REF] Lions | Cours au collège de france : Théorie des jeux à champs moyens[END_REF]:

Definition 3 (The G-Master equations). The G-Master equations consist in N equations, the unknown being (t, m 1 , . . . , m N ) ∈ [0, T ] × Ω → (U 1 (t, m 1 , . . . , m N ), . . . , U N (t, m 1 , . . . , m N )). ∀i ∈ N , ∂U i ∂t (t, m 1 , . . . , m N ) + H i, (U j (t, m 1 , . . . , m N ) -U i (t, m 1 , . . . , m N )) j∈V(i) + N l=1 ∂U i ∂m l (t, m 1 , . . . , m N )   j∈V -1 (l) ∂H(j, •) ∂p l (U k (t, m 1 , . . . , m N ) -U j (t, m 1 , . . . , m N )) k∈V(j) m j - j∈V(l) ∂H(l, •) ∂p j (U k (t, m 1 , . . . , m N ) -U l (t, m 1 , . . . , m N )) k∈V(l) m l   +f (i, m 1 , . . . , m N ) = 0 with U i (T, m 1 , . . . , m N ) = g(i, m 1 , . . . , m N ).
This equation is the Hamilton-Jacobi equation associated to the decentralized problem when we consider that the state variable is not only the current position but also the repartition of the players on G. In particular, when there is a common noise affecting for instance the functions f and g, one cannot write the G-MFG equations and one has to rely instead on the G-Master equations (see [START_REF] Lions | Cours au collège de france : Théorie des jeux à champs moyens[END_REF]).

To prove that these G-Master equations are indeed more general than the G-MFG equations we enounce the following proposition:

∀i ∈ N , d dt m(t, i) = j∈V -1 (i) ∂H(j, •) ∂p i (U k (t, m(t, 1), . . . , m(t, N )) -U j (t, m(t, 1), . . . , m(t, N ))) k∈V(j) m(t, j) - j∈V(i) ∂H(i, •) ∂p j (U k (t, m(t, 1), . . . , m(t, N )) -U i (t, m(t, 1), . . . , m(t, N ))) k∈V(i) m(t, i) with (m(0, 1), . . . , m(0, N )) = m 0 ∈ P N . If we define ∀i ∈ N , u(t, i) = U i (t, m(t, 1), . . . , m(t, N ))
then t ∈ [0, T ] → (u(t, 1), . . . , u(t, N ), m(t, 1), . . . , m(t, N )) is a solution of the G-MFG equations with the initial condition m 0 .

Proof:

Differentiating u(t, i) = U i (t, m(t, 1
), . . . , m(t, N )) with respect to t, one obtain the i th Hamilton-Jacobi equation that defines the G-MFG equations. The result is then straightforward.

Potential games and reduction to a planning problem

In this section, we provide a way to deduce the G-Master equations that consist in N equations from a single equation when the functions f and g verify the hypotheses of potential games 6 . We say that the above game is a potential game when there exist two C 1 functions

F : (m 1 , . . . , m N ) ∈ Ω → F (m 1 , . . . , m N ) and G : (m 1 , . . . , m N ) ∈ Ω → G(m 1 , . . . , m N ) such that ∀i ∈ N , ∂F ∂m i = f (i, •) and ∂G ∂m i = g(i, •) in Ω.
To that purpose let us introduce a global optimization problem that we phrase a planning problem 7 . This optimization problem consists in optimizing directly, with a macroscopic viewpoint, the different flows of agents (the preceding players being now controlled by a single agent, often referred to as a planner) between the nodes of the graph.

We introduce for t ∈ [0, T ], m t ∈ P N and a given admissible control (function) λ ∈ A, the payoff function

J (t, m t , λ) = T t F (m(s)) - N i=1 L(i, (λ s (i, j)) j∈V(i) )m(s, i) ds + G(m(T )) where ∀i ∈ N , m(t, i) = m t i and ∀i ∈ N , ∀s ∈ [t, T ], d ds m(s, i) = j∈V -1 (i) λ s (j, i)m(s, j) - j∈V(i) λ s (i, j)m(s, i)
The optimization problem we consider is, for a given m 0 ∈ P N : sup λ∈A J (0, m 0 , λ)

Noteworthy, and contrary to the first optimization problem that was a stochastic control problem, this new problem is a deterministic control problem.

We define the Hamilton-Jacobi equation associated to this deterministic control problem: Definition 4 (The G-planning equation). The G-planning equation consists in a single partial differential equation, the unknown being (t, m) ∈ [0, T ] × Ω → Φ(t, m 1 , . . . , m N ):

∂Φ ∂t (t, m 1 , . . . , m N ) + H(m 1 , . . . , m N , ∇Φ) + F (m 1 , . . . , m N ) = 0
with the terminal conditions Φ(T, m 1 , . . . , m N ) = G(m 1 , . . . , m N ), where the hamiltonian is given by:

H(m 1 , . . . , m N , p) = sup (λ i,j ) i∈N ,j∈V(i) N i=1     j∈V -1 (i) λ j,i m j - j∈V(i) λ i,j m i   p i -L(i, (λ i,j ) j∈V(i) )m i  
Our goal is to link this planning problem to the decentralized problem. The first step is to write the hamiltonian H in another way:

Lemma 2. H(m 1 , . . . , m N , p) = N i=1 m i H i, (p j -p i ) j∈V(i) Proof:
Reordering the terms we can write H(m 1 , . . . , m N , p) as:

N i=1 m i sup (λ i,j ) j∈V(i)   j∈V(i) λ i,j (p j -p i ) -L(i, (λ i,j ) j∈V(i) )  
Then using the definition of the hamiltonians in the decentralized problem, we get the result.

Proposition 5. Let us consider a C 1 function Φ solution of the G-planning equation. Then, Φ restricted to [0, T ] × P N is the value function of the above planning problem, i.e.:

∀(t, m t ) ∈ [0, T ] × P N , Φ(t, m t ) = sup λ∈A J (t, m t , λ) Moreover, if we define ∀i ∈ N , m(t, i) = m t i and ∀i ∈ N , ∀s ∈ [t, T ], d ds m(s, i) = j∈V -1 (i) λ s (j, i)m(s, j) - j∈V(i) λ s (i, j)m(s, i) with λ s (i, j) = ∂H(i, •) ∂p j ∂Φ ∂m k (s, m(s, 1), . . . , m(s, N )) - ∂Φ ∂m i (s, m(s, 1), . . . , m(s, N )) k∈V(i)
then λ is an optimal control for the planning problem.

Proof:

Let us consider an admissible control λ ∈ A and a repartition m t ∈ P N . Then, let us define:

∀i ∈ N , ∀s ∈ [t, T ], d ds m t,m t , λ(s, i) = j∈V -1 (i) λs (j, i)m t,m t , λ(s, j) - j∈V(i) λs (i, j)m t,m t , λ(s, i) with m(t, i) = m t i . We can write Φ T, m t,m t , λ(T ) -Φ t, m t = T t ∂Φ ∂s (s, m t,m t , λ(s))ds + N i=1 ∂Φ ∂m i (s, m t,m t , λ(s))   j∈V -1 (i) λs (j, i)m t,m t , λ(s, j) - j∈V(i) λs (i, j)m t,m t , λ(s, i)  
Hence, using the definition of Φ:

G m t,m t , λ(T ) - T t N i=1 L(i, ( λs (i, j)) j∈V(i) )m t,m t , λ(s, i)ds ≤ Φ t, m t - T t F (m t,m t , λ(s))ds
with equality when λ is equal to λ as defined in the Proposition, thanks to the preceding Lemma (this λ being admissible because of our hypotheses on the hamiltonians, because Φ is C 1 and because P N is compact).

As a consequence:

J (t, m t , λ) ≤ Φ(t, m t ) = J (t, m t , λ)
and this proves the result. Now, we are going to relate the function Φ to the G-Master equations and prove that a solution to the planning problem can provide a solution to the decentralized problem, that is the initial mean field game.

k∈V(i)
then m is a Nash-MFG equilibrium and λ is an optimal control for the initial mean field game (the decentralized problem).

Proof:

We need to prove the first assertion of the Proposition, then the other assertions are consequences of Proposition 3.

Differentiating the G-planning equation with respect to m i , and using the above Lemma, we know since Φ is C 2 that:

∂U i ∂t +H i, (U j -U i ) j∈V(i) + N j=1 m j k∈V(j)
∂U k ∂m i -∂U j ∂m i ∂H(j, •) ∂p k (U l -U j ) l∈V(j) +f (i, •) = 0 Now, using the fact that Φ is C 2 , we have ∀(i, j) ∈ N 2 , ∂U i ∂m j = ∂U j ∂m i . Hence:

∂U i ∂t +H i, (U j -U i ) j∈V(i) + N j=1 m j k∈V(j)
∂U i ∂m k -∂U i ∂m j ∂H(j, •) ∂p k (U l -U j ) l∈V(j) +f (i, •) = 0 and this is exactly the i th equation amongst the G-Master equations, after reordering the terms. Hence, since the two terminal conditions are coherent, U = ∇Φ is indeed solution of the G-Master equations.

Conclusion

In this paper, we presented a way to deduce a solution to the mean field games equations in a graph from a smooth solution of a single equation Hamilton-Jacobi equation associated to a global deterministic control problem on the whole graph. Moreover, and as described on Figure 1 below, the Master equations -that "contain" MFG equations and have to be used in the case of games with common noise -can be reinterpreted as the equations verified by the partial differentials of solutions of this single Hamilton-Jacobi equation. This paper also opens the door to the important challenge of numerical resolution of Hamilton Jacobi equations in very high dimension either to solve the equations presented in this paper or as a numerical approximation to solutions of the Hamilton-Jacobi equations in infinite dimension presented in [START_REF] Lions | Cours au collège de france : Théorie des jeux à champs moyens[END_REF].

Proposition 4 (

 4 From G-Master equations to G-MFG equations). Let us consider a C 1 function (t, m 1 , . . . , m N ) ∈ [0, T ] × Ω → (U 1 (t, m 1 , . . . , m N ), . . . , U N (t, m 1 , . . . , m N )) verifying the G-Master equations. Let us then consider a C 1 function m : t ∈ [0, T ] → (m(t, 1), . . . , m(t, N )) verifying:

Proposition 6 .

 6 Let us consider a C 2 function 8 Φ solution of the G-planning equation. Define ∀i ∈ N , ∀t ∈ [0, T ], ∀m ∈ P N , U i (t, m 1 , . . . , m N ) = ∂Φ ∂m i (t, m 1 , . . . , m N ). Then, ∇Φ = U = (U 1 , . . . , U N ) verifies the G-Master equations. Consequently, if we define ∀i ∈ N , m(0, i) = m 0 i for a given m 0 ∈ P N and ∀i ∈ N , ∀s ∈ [t, T ], d ds m(s, i) = j∈V -1 (i) λ s (j, i)m(s, j) -j∈V(i) λ s (i, j)m(s, i) with λ s (i, j) = ∂H(i, •) ∂p j ∂Φ ∂m k (s, m(s,1), . . . , m(s, N )) -∂Φ ∂m i (s, m(s, 1), . . . , m(s, N ))

While writing this article, we learnt during a conference organized in Rome on Mean Field Games that results on the limit of continuous time and finite state space M -player-games as M → +∞ had been obtained by Diogo Gomes, justifying our direct passage to a continuum of players

There is no additional difficulty when a time dependency is added.

The argmax being well defined because of the asymptotic super-linearity of L.

If one adds a time dependency to f , the following results can be adapted straightforwardly.

We call λ a control although it is an abuse of terminology since the controls consist in the values of λ.

This is for instance the case if ∀i ∈ N , f (i, •) and g(i, •) only depend on m i .

The term "planning problem" must be understood here as the problem of a planner controlling the whole population of players. The planing problem studied in[START_REF] Achdou | Mean field games: numerical methods for the planning problem[END_REF] is of a different nature.

In reality, we do not need to be able to differentiate twice with respect to t