On the discretization of some nonlinear Fokker-Planck-Kolmogorov equations and applications
CC Attribution - NonCommercial - NoDerivatives 2.0 Generic:
You are free to use, copy, distribute and transmit the work or content in unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Silva Álvarez, Francisco José
In this work, we consider the discretization of some nonlinear Fokker-Planck-Kolmogorov equations. The scheme we propose preserves the non-negativity of the solution, conserves the mass and, as the discretization parameters tend to zero, has limit measure-valued trajectories which are shown to solve the equation. This convergence result is proved by assuming only that the coefficients are continuous and satisfy a suitable linear growth property with respect to the space variable. In particular, under these assumptions, we obtain a new proof of existence of solutions for such equations. We apply our results to several examples, including Mean Field Games systems and variations of the Hughes model for pedestrian dynamics.
 Thank you very much for the invitation to give this talk. So this is a joint work with Elisabeth Carlini from the University of La Sabienza. So the aim of this talk is to describe some numerical methods in order to discretize the well-known Fokker Planck-Kolmogorov equation. And in a rather general nonlinear case. And so please if you have any questions, something is not clear, tell me. We have time. So let's go. So here is the plan of the talk. I will give a small introduction to the PDE that we will study. Then we will discuss about the numerical scheme and its properties. And then we will end with applications in midfield games. And also in problems that come from pedestrian dynamics that are known as the huge model. So this is important. So this is the question that we will consider in the whole talk, in the entire talk. So is that working? That is strange because it doesn't matter. So here you see that you have this equation. The equation that you have there is the Fokker Planck-Kolmogorov equation. So you have the derivative with respect to M. So you have the second order term whose coefficients A, I, G depends on M. And then you have plus the transport term, the divergence of B that depends on M, also times M. And the important factor is the dependence of the nonlinearities, the coefficients on M. So B, the drift that is there, as a function of M, is a function of the whole path of the trajectories. So M, you have to see it as a function of time taking values in the space of probability measures. So in fact, this is a question that is rather general because it's not local also in time. Times the space are D and times zero T. So this is B. A, G is the square of sigma, where sigma is as B. So it's a function of the whole path of the M times R D times the time. So this is a rather general equation. We will see later, Miffel games is a very particular case of this equation. It's very easy to see. And the definition of the solution of this, you multiply, you integrate by part formally, and you give a definition in a weak sense that is given by this expression here. So M will solve this Fogger-Planck equation. If and only if for each test function phi, you have that equality. So you have to see that here I put D M zero and D M S, meaning that I'm not looking for necessarily absolutely continuous measure. Okay? This is equation for measures. Is clear now? Okay. So what is the idea is that formally a solution of this equation will be given by the law of the solution M is a measure, it's a trajectory in the space of probability measure, will satisfy formally that M of t at time t will be the law of X t, where X t, where capital X is the solution of this Stoke-Gaston differential equation. This is in some sense the Makin-Blassov equation, but the coefficients again depends on M in the whole history and also in the future. Okay? So DX solves that. So this is formal because we have to establish the existence of solution and all that. But anyway, this gives an idea of the link between the PDE and the Stoke-Gaston differential equation behind. Okay? Good. So let me give some reference, important reference in the case of linear equations where B and sigma do not depend on M. So in that case, if you take sigma equal to zero, so you are in the first order case and B is not regular, then you have several results, one result by the Bernoulli-Leon's and then by Ambrosio, et cetera, about the existence and uniqueness of this equation. And when sigma is not zero, so you are in the second order case and B is still not regular, you have also results by Le Brie and Lyons and by Figalli, et cetera. And also there is this people that are interested in the Fogger Plan equation. I advise to read that paper, to look at that book that I recently discovered that is very important. So this is what they do by Bogachev, Krilov, Röknöf and Schapofnikov, where they do like a detailed account of this equation. Well in the non-linear case, in the generality that I presented before, there are also some results but there are also some interesting results by Bogachev, Röknöf and Schapofnikov when sigma is equal to zero and in the stochastic case by Manita and Schapofnikov in the 2012 and 13. So this is important papers, I think, in this subject. Good. So nothing works anymore. And with this, I will go with the, I don't know who it is. Okay, so now that I presented the equation, now we will discuss about the scheme. So in order to present the scheme, for pedagogical reasons, I will start with the most simplest case that will be with sigma equal to zero, so it will be in a deterministic framework. And also with B, so there is no sigma, but there is B. And I will take B independent of M. Okay? So I will take that case and then we will go forward. Okay? So in that case, under suitable assumptions on B here, I won't discuss the technical assumptions on B and sigma yet because I can suppose that they are very smooth, they have good properties in order to derive the scheme, but then the scheme will apply to more general coefficients. Okay? So I suppose that everything is regular in order to motivate the scheme. Okay? So it's B's regular leap cheats. So you have a solution of the, so you have a solution of this equation, x dot equals to B of x. And when you have this equation, you can define a flow. The flow, it means that as you associate at each initial condition, you associate at time t the value of the solution at time t. Okay? So that is what I call capital phi. So phi of s t x, okay, will be the solution of the equation at time t when I take initial time as small s and initial condition as small x, okay? So I can define this flow. So this is a function of three variables, the two times, the initial times and the time where I look at the solution and initial condition, okay? And then once you have this solution of this equation, this flow, I'm sorry, then in fact you can prove that the solution of the Fokker-Planck equation is given as the E measure, measure also called in English the push forward measure, of the initial measure M0 under this flow, okay? So this is a function of the initial condition, okay? So you want to compute M at time t, you put initial time 0 because you will move M0, okay? And then you compute the flow up to time t. So this gives you a function of the initial condition. And then you transport the initial measure with this flow. I will recall this notation for people that are not aware. So you take this, the function, for a function F, you take the push forward of M0 of a set, this is a new measure, you define the border set, for example, this would be M0 of F minus one of A, okay? So this is this notation. It's like the E-match measure, okay? Good. So this is very important because once you have a, you have a trajectory, a trajectory interpretation of the solution of the Fokker-Planck equation, okay? In terms of that ODE. So once you understand that, you say, okay, in order to discretize the Fokker-Planck equation, instead of discretizing the Fokker-Planck equation, I can discretize the flow, okay? So how do you do that? Well, you take an Euler scheme, for example. So you take a time step delta t, you divide capital T by capital N, N is a natural number, and then you set tk as k times delta t. So you have agreed in time. Good. So that's normal. And once you have that, you can define your discrete flow with the Euler scheme. So, in fact, you can define the small phi at time k. The small k there, in fact, is like you will do only one step, okay, from k to time k plus 1. So you do an Euler scheme. So you have your flow at time k when your starting point is small x. It will be x plus delta t B of x tk, okay? So then you define recursively this flow, okay? And so the natural discretization in time of that equation is that you will say the measure at time k plus 1 will be the measure at time k transported with the flow phi k, because you do only one step. It's clear, right? The idea? Okay. Good. But then you don't have a computable method because you only discretize in time. So now we can decide to choose to discretize also in space to have something that is implementable. So we discretize in space now, okay? So the space discretization is that you take a space step delta x, okay? And you define your space grid here. I am working in Rd. So I am taking all the grid in the whole space, okay? So I define g delta x as the point xi where i is in zd times delta x, okay? So you have a grid in Rd of length delta x. And then you consider p1 basis. So this is a function that I think at each element. So you have to construct, using this grid, you can construct a triangulation, for example, and then you can take this p1 function. But I don't want to make it just complicated. So let's think only in dimension one to make it simple, okay? So in dimension one, my function beta i will be this function like that. So it's a function here you have xi, here you have xi plus delta x, so it's xi plus one, and here you have xi minus delta x, xi minus one. So the function beta i associated to that node will be the function that values one in the node, and it's zero here, zero there, and zero everywhere else, and inside is affine, okay? It's affine here and there. So that's the function beta i. Okay, so good. Now we will use this function beta i to do the discretization in space. So how we will discretize? Now I do the same before, so I have my discrete flow, but now I have discrete space. So I already find my trajectories only starting at the points on the grid. So that's phi i k is the discrete characteristic starting at point xa. Okay? And then I will define my measure at time k, my discretization, as the sum of delta measures, of delta of direct measures, weighted by some weight that I have to compute, so I have to compute the weights. So the weights, so you have weights in each point on the grid in the space, but you also have time, okay? Okay? So how do I compute these weights? So at time zero, at time zero I only, at time zero I will do a picture here. So this is xi, this is xi plus one, and this is xi minus one. Okay? So at time zero, so I have half, so this will be ai, so this will be xi plus delta x over two. Okay, so this will be this small interval delta, we'll call it ai, and so my initial measure, the mass that I will put at time t, at time k equals zero in this point, the weight that I will put in this point, will be the measure m zero of that interval. Okay? So this will be at time zero, this will be the measure m zero that is given of the interval ei. Okay? Okay, so that's how I define my measures. Then I have, then I have, I will use another blackboard, then I have to compute the measures, the weights in the next times. How do I do that? How do I do that? So the idea here, so you have this formula with the beta i that is complicated, but I will try to explain it with a picture, okay? So the idea is that here you have point xi, so I want to compute, I am looking at the second line, I want to compute the weight at that point at time k plus one. So this is time k plus one. Okay? And so here I have my function, so here I have my function like that, this is beta i, sorry it's not very, this is beta i. So I have to compute, I want to compute the mass, the weight at this point. Okay? And so in order to do that, I will look at the past time, so at time k, and I will see all the characteristics, this phi i k that arrive into this support of my beta i. And then I will multiply the weight of the mass that arrives to that point with the inverse to the distance to the point xa. So that's the idea. So if I have point, I have here time kk. For example, if I have here xj, here I have a mass mjk, okay? Then if I want to see how much mass at point xj will be transferred to point xi, I will see if my disc is characteristic, so I have phi jk. So imagine that this is phi jk. Imagine that this is phi jk. So if that's phi jk, so if I compute the characteristic and it arrives to the support of beta i, I will put mass from xj into xi. And how much? It will be proportional to the distance. For example, if this guy, the characteristic, arrives at the midpoint between xi and xi plus one, I will put half of the mass of mj to xi and the other half to xi plus one. Okay? If phi jk arrives exactly to the point xi, I will put all the mass mj in the mass mi. So this will be the contribution of this term. But then I have to see all the other points on the grid. And I have to see where the disc characteristic goes, and so that's why you have the sum of beta i. Okay? So that's the idea. So if this is clear, it's the basis of the schema. Okay. So that's the schema, and well, you can prove that it works. And everything will be the convergence of all the schemes. All that will be a consequence of the general result in the nonlinear case. So I'm only showing the scheme. Good. Now, what happens in the stochastic case? In the stochastic case, we don't have these deterministic characteristics because you have a second order term. This second order term will be linked to a diffusion. Okay? So what is important is, as I said before, is the representation formula. So in the stochastic case, you have that your characteristics will be given by what? I am considering the stochastic case, but linear yet. Okay? So B and sigma do not depend on M. So in the stochastic case, you have that your characteristic will be, your flow will be defined as X at S will be the solution of B of X, X, S. And here I will put S prime, for example. This will be S prime, S prime, the S prime, plus the sigma term, X, X at point S prime, and the Bromley motion, W. And so you have X at time S will be X. So this will be the analogous characteristic, but now it's stochastic. Okay? But in fact, you have the same kind of representation formula. MT at the measure, the solution of the Fokker Planck is a measure. So at time T, I compute it, it will be a measure. So if I want to compute that measure on a set A, what do I do? I solve this equation. So this gives me an stochastic flow. And this, so it depends on omega on the alia. So for each omega, I will have like a deterministic flow in some sense. And then I will transport the initial measure with this deterministic flow that depends on omega. And this gives me a measure that will be stochastic because it will be the transport of the initial measure with this stochastic flow. And then you compute that set A and then you take that mean. Okay? So this is the solution of the Fokker Planck in the case where you have a second order term. So it's exactly as before, a set that, from the fact that you have to take a mean over the alia of these flows. Okay? Good. So this is that phi 0 t omega. This would be the stochastic flow. Okay? That is the final term. So then as before, we saw that we have to discretize the flow. Okay? So here is the same idea. So I will discretize the stochastic differential equation. So here I consider, I also, I am skipping the part where I discretized first time and then space. I will do all in one step because you know how does it work. So I have to compute the characteristics starting from the points on the grid. Okay? And so the idea is that you define, you will discretize your Brony motion from time k up to time k plus 1. You will discretize it with the most simplest thing that will be a random work. So you will have your point x a and your Brony motion can go up with probability one-half and go down with probability one-half. And so you will discretize that with a random work in that step. Okay? So you will define that discrete flow now that have two possibilities with the plus and the minus. So it would be phi jk plus minus dL, I will discuss it now. It would be xj plus delta tb, so this is the earlier scheme, plus a minus or minus, you have to decide. Okay? The square root, that's natural scaling for the Brony motion as you know, times the sigma, the sigma term. So dL here is this because you have R or you have several Brony motion. You have R Brony motion. So you have two possibilities for each Brony motion. Okay? To each Brony motion, you have associated a column of the matrix sigma. So sigma L is the L column of sigma. So for that column, you will move with probability one-half up or probability one-half down. So you have this discrete flow. Okay? So that's very natural. And then you do the same. So the representation formula gives you that m at time k should be equal to the sum of Dirac masses times some weights, and you have to compute the weights, and I would use those discrete characteristics. Okay? So at the beginning I do as before, and then to go from time k up to time k plus one, I do the same, forget R, take R equals to one, so you have only one Brony motion to simplify the discussion. So here you don't have this sum and you have R equals to one. So you have this similar formula than before, but you have to evaluate two characteristics because you have these two possibilities for the random walk. Okay? And you have these two possibilities, and this possibility has probability one-half. Okay? Good. So that's the scheme in the second order case. So it is important from the theoretical point of view to prove the convergence of the schemes. It is important to notice that these schemes, it corresponds to the transition probabilities of a Markov chain. Okay? So the transition probability that is described by exactly the transition probability that I want. So you have a Markov chain behind that is somehow discretizing this diffusion. Okay? So the initial law, so it's a Markov chain that is discretized in space and discretized in time, and the initial law of this Markov chain, it would be this initial distribution, and then the transition probabilities are computed via that formula, and when you define those transition probabilities, if you compute the marginal laws of the Markov chains, you will have that the marginal will be given by this formula. Okay? So if you define those transition probabilities, you will have that. Okay. So that's the point. Now in the nonlinear case, well, in the nonlinear case, you have a problem because all this idea that you are doing this stuff recursively is linked with the Markov property in some sense. Okay? But in the nonlinear case, you lose the Markov properties in those machine class of equations, so you don't have the Markov property, but if you fix a measure on the coefficients, then you will have a regular diffusion for which you have the Markov property and all these schemes I presented before make sense. So the decision in very natural, I freeze the measure, I do my scheme, and then I have to compute a fixed point. Okay? So that's exactly the scheme that at the end, it corresponds to put the measures M's in the nonlinearity in the discrete characteristics. So the scheme is exactly the same, but you have that M also is inside the nonlinearities. Okay. Then you can prove under only the continuity assumption of the coefficients, you can prove that this scheme has a, I admit a solution. This solution is in the linear case was trivial. Of course you have only one, in that case you have only one solution in the linear case because you construct the scheme iteratively. Okay? So here it will be exactly the same if my, so this is important. If my coefficients, as I recall that my coefficient depends on M on the whole interval of time. So if I compute BM at time XT, but what is important here is time, if I compute BM at time T, and if this BM at time T depends only on the past trajectory of the measure, then the scheme will be explicit. Okay? And then you will have only one solution of the scheme. On the other hand, if my scheme might be at time, might be as a function of M at time T, it depends on the value of M in the future, then the scheme will be implicit. And then in that case the solution, the existence of a solution of that scheme comes from the, from a fixed point argument. Okay? And so we will see exactly that this case of an implicit scheme is exactly the case of M in field games. So the convergent result. So the assumption is that, this is the only assumption that you have that your maps are continuous as a function of the measure times an X, so you don't have leap this assumption, you have any assumption, only continuity. Okay? And you have linear growth with respect to X, that is uniform with respect to the other variables. Yeah? I'm sorry? What's the question? Are you using the direction of measure? In M? Yes. Yeah, I'm so sorry, yes, that's an important question, because I will write an, I will write, so I will write then, and then we continue the property that makes use of the distance. So I'm working with the space, the space of zero T, so in P1 of Rd. So well, I have to only to measure side this space because you have to, here you take the sweep. So here you take the, this is the probability space with the one versus side distance. So you have this, so P1, you have P1 Rd, and you endow it with a metric that we call d1, that is the metric of optimal transport, that d1 of measure M1 and M2 will be the infimum over all the measured gammas in the product. There are probabilities in Rd times Rd of the integral in Rd times Rd of the distance between x minus y, the gamma of x and y, and I take the infimum over gamma, so the first margin I have to go response to the measure M1, so I write this as the projection on x. So I take the image measure of gamma under the projection on the x coordinate, it will be M1 and the same with x2, the projection on y of gamma will be M2. So this is the optimal transport, excuse me, the versus time, one versus time, this is by, in fact in this case there is an important probability also for the prudent system of x-point, is that this, it does this space, in fact with this point because you can put here a P, you have the distance of P here, you will put P here and you take the square, the P root, so this is the P distance, but in the case P equals to 1 in this case, this also has an alternative formula, that will be that's the super over the set of leashes function of the integral in Rd now, you are not in the product of Fd, here you will have M1 minus M2 and you take the super over the normal Fr leptis or 1 leptis, so you take the gradient of F less than 1. So you have that formula, it's not exactly the dual of leashes function, but it's somehow like that, but what is important is that here you can embed this metric space of P1, that's a metric space, you can embed it like in a vector space, and like that you can use shorter fixed point theory and stuff like that, well that's the distance, what is important is the distance 1, okay? Good, any other question? Okay, so now we have these two assumptions, continuity and linear growth, and under this assumption the skin has at least one solution, okay? But now the solution, remember I have weights in space, so I have dirai masses in space, and in time I have to extend them, because I will work with this space, this will be the space that I will work with, because this is the space where the solution lives, so I have to work with this space, so I have to extend my measure in time, so I do that with a simple interpolation in time, okay? So now we have to make the parameters go to zero, so the important here, there is the condition for the convergence, the condition is that delta x, delta n, the bad notation, delta n x is a sequence of space steps that are going to zero, and delta tn is a sequence of time steps that are going to zero, but if they satisfy that relation, that delta t is small with respect to the square, no, excuse me, the square of delta x is small with respect to delta t, then you will have convergence, so this is a nice property of this scheme, because you can think or you can use another Markov chain to discretize your diffusion, because the Markov chain that you took is strange, but the Markov chain that we took has this good property that you will get conversion under that condition, so this means that time can be bigger with respect to space, that is contrary to the finite difference scheme when you implement it in explicit form, where you have that time has to be small with respect to space, so that's the CPL condition in numerical analysis, so this scheme has the other, in the other sense, time can be bigger with respect to space, so this is interesting if you want to compute the solution in times, long time horizons, because you cannot take very small time steps, okay, and so here in this interpretation in terms of Markov chains, in fact, gives you this nice property, so you have that the distance, you have the inequity continuity of the sequence of measures in this space, so you have a whole there continuity here with that metric, and you also have that second moments are bounded uniformly, so this is an important property of that space of P1, so if you have a family C, so you have a family C subset of P1 of RD such that you have that the integral of x square d mu is bounded, that is bounded for a uniform constant K is bounded for all mu in C, okay, so you are in the case in the distance, in the one distance, that you bound the second moments uniformly, then that set will be relatively compact, okay, in P1, in P1, not in P2, in P1 it will be relative, so to get compactness in P1 you have to bond higher moments, okay, so here in P2, so here if you see the second line gives me that my oldest trajectory takes values in a relatively bounded set of P1, and I have a continuity because of the first line, so by Arsela's colleague I have a limit measure in C0, T, P1, okay, but then I have to prove that that measure is the solution of the Fokker Planck equation, okay, but I won't do that because it's constant but that's the answer, so under this assumption you have limit points, you always have a limit point, okay, because of this continuity, this Arsela's colleague theory, in particular, so here this is a convergence result, so all the schemes that are constructed have limits point, and each limit point is a solution of the Fokker Planck, Kolmogorov equation, the general equation, okay, and in particular this gives also an existence result for the equation, okay, so in some sense it's like a piano result, remember piano in the ODE's that you only ask for continuity of the coefficients, you have existence, so in that sense this is exactly the analogous of piano theory but for Fokker Planck equation, so I was convinced that this result was somehow new, the existence also, but in fact no, there is this paper that I cited before by Manita and Shapov-Fligov, that is 2012 and 13, where they prove existence of these general equations but also under more general assumptions than the one that I put, okay, so in fact our contribution is more in the numerical part, but anyway, but this gives another proof of the existence in any case, okay, so this is now, this is important, so I will see later, I don't have access always to B and sigma, so I cannot compute the solutions of the scheme, okay, so what do we do in that case? We have to approximate the coefficients B and sigma in order to get an implementable scheme, so that is the second result, so what happens if I take an approximation, if I take B and sigma n, have linear growth independent of n, okay, they have to be continuous only on x in that case, but the important property is that this converges, so there are good approximation of the coefficients, good approximation means that if I take mu n converging to mu in P1 and the C0 t P1, so remember that these are trajectories, then as a function of x and t, this function Bn of mu n, they converge uniformly to B in the same for sigma over compact sets of rd times 0 t, so if you have that property, everything works, so you can construct the same scheme as before, but now with Bn and with sigma n, there are computable things, and then you can take the limit and you recover the solution again, okay, so that's important, good, so now, how much time do I have? Okay, so now let's go to the applications, so me feel games, so here I will consider a particular instance about full course, it can be generalized, but I consider a particular instance of me feel games, so here I have a Hamilton-Jacoby-Bellman equation, co-applet with a Fokker-Plank equation, the Hamilton-Jacoby-Bellman equation has a Hamiltonian that is quadratic, and in the Fokker-Plank equation you have this velocity field that is minus the gradient of the value function V, okay, so the important thing is that here I consider sigma not positive because I have this square, sigma not equal to 0, there's a typo there, sigma is not 0, so this is what people call like non-degenerate me feel game system, okay, and you can prove under good assumption of capital F and G, I will discuss later, and under good assumption of capital F and G that are those these coupling terms, you have existence of a solution, okay, of the me feel game, good, but I don't know if you know the more or less this theory, you have been in the course, so I don't have to remember to recall what was the meaning of that system, but anyway you will see right now with the rewriting as only one Fokker-Plank equation, because here you have Hamilton-Jacoby-Bellman equation, couplet with a Fokker-Plank equation, but you can put everything else on only one equation, so the key point is that you can write all that system and only that equation, the second one, but the gradient of V depends on M, okay, and depends on M trajectorially, because so to compute the velocity field, I have to take the gradient of V of M, but who is V of M, it will be the solution of that optimal control property, where in the coefficients you see appear M in the future, because I want to compute the value of function at time x at time t as a function of M, but then you see appear M at any time, so it's exactly a particular case of the equation that we considered before, okay, but with a time dependence that's only in the future, and you don't have any past here, good, so it's clear or not? Okay, so this is the technical assumptions that you have to take very nice function f and capital F and capital G with bounded, with second bounded derivative, everything with what you want, because this is only technical matters, because you are working on RD in the whole space, you are working a bounded domain, then you have to put boundary conditions, it becomes complicated, but otherwise you can work on the torus, you forget boundary conditions, you unbounded domain, then you can relax those, so how those assumptions, so those assumptions are important because of the unbounded of the space, anyway, they are also important to get convergence also, but I mean that in a bounded domain, I think that they can be relaxed, I think, well under these assumptions you have this very important property that as a function of the three variables, so this is somehow a tonician, as a function of the three variables m, x and t, the gradient of v, m, x and t is continuous, okay, and it's bounded, bounded is not as a surprise because the function b you can prove that it's glitches because everything is bounded, everything is glitches thanks to the first assumption, so that's no problem, but so I have this, so it is continuous, so this is my b, sigma is a constant, so I can apply my preview and it's bounded, so I have in particular has linear growth, so I can apply my theory, so in particular I have existence of a solution, okay, that may be a system and I can approximate it, but now there is a problem that we don't know this vector field, v, because I don't have an explicit formula for v, because it's the value function of an optimal control problem, so then you have to approximate v, the value function v, in fact you have to approximate the gradient of the value function v, so then in order to compute the gradient, we compute first an approximation of v and this we do it with what is called, you can choose any method that you want here, this is not important, you can choose more or less any method to approximate your value function v, here I choose, we choose the semi-lagrangian scheme, so you have this function b that is computed recursively backward, and well anyway, so this here you have a function that is defined on the grid and on the grid points of the, in the north of the grid, okay, and then you have to interpolate in a space to have a function, but it will not be differentiable in the grid points, because you will have a piece y affine function that will not be differentiable, but cannot compute the gradient, so I want to, to approximate the gradient, so then you have this affine functions, so you have to regularize them, you know, and then you compute the gradient, so then is what it, when it enters, like, so the first line is only interpolation in space, it doesn't matter, but the second, the second display here, it only means that I have this affine function that is not differentiable, so I regularize with a modifier, okay, so then, but then I have another parameter that is epsilon, that is the modifier, so then I have to make sure that when I do all the three stuff, delta x, delta t, and epsilon go to zero, it will get convergence again, okay, well, in this case, as you can prove that this, this, this value function regularize value functions satisfy like a key inequality that is related with what is called the semiconcavity of the value function in the, in the continuous case, but in the discrete case, so if you don't have this term here, the second term there, with delta x squared divided by epsilon, if you don't have that term, this will mean that this function is semiconcave, so this means that if you subtract a parabola with an adequate coefficient, you will get a complicated function, okay, so it's almost concave if you want, and once you have that, you, you, you, you, this is the key of the, of the approximation result because you see that if now I may disappear that guy at the end, at the limit, I will get the semiconcavity, so I have to make it disappear, so epsilon, the regularization terms of the modifier has to be bigger with respect to delta x, and the first condition is the first, the same as before, okay, so in that case, I can, we can prove that's an important result that those gradients using this semiconcavity property, those approximated gradients converge to the true gradient, okay, uniformly over compact sets, and so I can apply the approximation result that I put before, okay, and that's good, and so, and then we have the convergence of the scheme, in general dimension, space dimension, so these are related, these are not new techniques, this part, this, this is more or less an, a difference thing that we, what we have done already with Elisabetta in 2014 and 15, but where we prove the convergence only in dimension d equals to one, and the space dimension d equals to one, because we consider the generate meaningful games, we consider the games where you, you don't have sigma, because to have that property there, the, this convergence of the gradient, we only can prove it when, when you have sigma, okay, so if you don't have sigma, you cannot do that, and the scheme is not the same, because then you have to work, you cannot work with Dirac masses, you have to work with densities, so it's more complicated in those papers, okay, so now I will end with another, so then we have a, a, a convergence scheme for meaningful games in general dimension, now I will end with another application, that is SOHA, where it's called huge model, but what we propose here is a modification, that we can prove that it's well-posed, so the idea is the same equation as before, exactly the same, but the V as a function of M is the, is the value function of the same stochastic optimal control problem, except for the fact that if I compute that time t, my, the, the dependence in, the, does not depend on M on the future, but I look only M at time t, I am at time t, I see the population, and I will suppose that all the population remain like that in the future, and I will optimize there, because I don't have time to do computations, so imagine that you have like more to, to modelize, to model a panic situation, there is a fire, so you have to escape, you are not going to compute an equilibrium to see what people will do then, and then you will optimize, you will see the situation right, or now, you will try to escape, so then that means that you fix M at this time, at this moment, and then you compute, okay? So in, well, you have with this new velocity field, you have again that, or assumptions are satisfied, but you have to, again, to use the approximation result, because you have to approximate V again, because of value function, and then we also have convergence of the scheme, so this, you cannot write it as a mean field game system, because you have the Fokker-Plan equation, but at each time t, you solve a different Hamilton-Jagoby-Belman equation, so you have like a Fokker-Plan equation with an infinite number of Hamilton-Jagoby-Belman equations, each one corresponds to the optimal control problem when you fix M at that point, okay? But anyway, the system is, we prove with this thing, either the system is well-posed, and we have convergence also. What do we have to, and what is important is that, in some sense, it is easier than mean field games, in some sense, numerically, because numerically, you have to solve like, you will disk a tight time, so you have to solve N, Hamilton-Jagoby-Belman equation, so you have a lot to solve, but what is important is that at each point, it's more, it's easier, because this is an explicit scheme, it's an explicit situation, because I don't look the future, I look my measure now, so it's an explicit problem. So these are the numerical simulations, so I don't explain the details on people, these one D because it was amplified, so here people, these are the initial distribution of people, they want to reach these doors, okay, and these are, these are charts of the, of the evolution, so this is a time, 30 times h, h I don't remember, I don't remember how much is h, h is the time step, so this is an intermediate time, and this is the final time, so you, these people in the second model, in this model of evacuation, that people will more or less distribute like that at the end, okay, so people rather go, because they're like somehow blind, they rather go rather quickly to the doors, they concentrate in the red parts on the doors, rather quickly, so within the same data, the same data, for me field games, and you see the difference, because here you have the same nature population, and at the intermediate time there are people that remains, you have this peak at the middle, that people that remains, that do not, that wait there, so they forecast somehow the behavior of the crowd, and then they will move, and you have a very, a different distribution, the final distribution is the red one, so then you see this rational behavior, I think, so okay, so I will skip that, so this is the real huge model, but the problem with the real huge model that is there, so you have a stationary, excuse me, you have a stationary, having to Jacobi-Berman equation, but the problem of that, of that system is that it's not well-posed in general, instead that the one that we propose is well-posed, so perspective, all the talk is, was based on a particular Markov chain approximation of the diffusion, by saying that we can do the same with a general Markov chain approximation of the diffusion, so then for a particular problem you choose the Markov chain that you want, and you implement it, okay, now for the implicit scheme, as an example the Miffel game, when you had the discrete system, you have existence of a solution, but it's not clear how to compute it, because another fixed point of Banach, so you cannot do this sucessively iterate, so we have to, and then we solve the discrete system in the Miffel game system, we solve it with a learning procedure, but it's only realistic that people use in game theory, so for the implicit scheme it's not clear how to provide, for the discrete system, how to provide a conversion algorithm, and then there is all this point about the boundary condition, and of course there goes this case that we didn't consider, so in the long time we're here, so these are the reference, so the first, the old, the old I gave today is based on a, when I preprinted that we, so it's available in archive, and the other papers are more ancient about Miffel games, so thank you for your attention. So just if I understood correctly, to solve the Miffel game, first you fix a distribution, you plug it in V, and you solve V by a semi Lagrangian, and then you apply your method for, that you've described before, exactly, but you could do that for another system of optimality, right, I mean it could be, doesn't have to be Miffel game, it can be some Fogger plan coupled with some AJB, and you do the same trick. Like a Miffel time control program. For example, yeah. Yeah, yeah, I think so, yeah, of course, of course, yeah, I think that, yeah, I only put one example, but of course I think, yeah, I think it should work, I have to think about it, but I think it should work, but then I repeat, I took a simple example where I have a nice property, I think that this should be checked in case by case, in fact, but you're right, what idea? Question? If not, let's thank Francisco again.
 Thank you very much for the invitation to give this talk.  So this is a joint work with Elisabeth Carlini from the University of La Sabienza.  So the aim of this talk is to describe some numerical methods in order to discretize the  well-known Fokker Planck-Kolmogorov equation.  And in a rather general nonlinear case.  And so please if you have any questions, something is not clear, tell me.  We have time.  So let's go.  So here is the plan of the talk.  I will give a small introduction to the PDE that we will study.  Then we will discuss about the numerical scheme and its properties.  And then we will end with applications in midfield games.  And also in problems that come from pedestrian dynamics that are known as the huge model.  So this is important.  So this is the question that we will consider in the whole talk, in the entire talk.  So is that working?  That is strange because it doesn't matter.  So here you see that you have this equation.  The equation that you have there is the Fokker Planck-Kolmogorov equation.  So you have the derivative with respect to M.  So you have the second order term whose coefficients A, I, G depends on M.  And then you have plus the transport term, the divergence of B that depends on M, also  times M.  And the important factor is the dependence of the nonlinearities, the coefficients on  M.  So B, the drift that is there, as a function of M, is a function of the whole path of the  trajectories.  So M, you have to see it as a function of time taking values in the space of probability  measures.  So in fact, this is a question that is rather general because it's not local also in time.  Times the space are D and times zero T. So this is B. A, G is the square of sigma, where  sigma is as B. So it's a function of the whole path of the M times R D times the time.  So this is a rather general equation.  We will see later, Miffel games is a very particular case of this equation.  It's very easy to see.  And the definition of the solution of this, you multiply, you integrate by part formally,  and you give a definition in a weak sense that is given by this expression here.  So M will solve this Fogger-Planck equation.  If and only if for each test function phi, you have that equality.  So you have to see that here I put D M zero and D M S, meaning that I'm not looking for  necessarily absolutely continuous measure.  Okay?  This is equation for measures.  Is clear now?  Okay.  So what is the idea is that formally a solution of this equation will be given by the law  of the solution M is a measure, it's a trajectory in the space of probability measure, will  satisfy formally that M of t at time t will be the law of X t, where X t, where capital  X is the solution of this Stoke-Gaston differential equation.  This is in some sense the Makin-Blassov equation, but the coefficients again depends on M in  the whole history and also in the future.  Okay?  So DX solves that.  So this is formal because we have to establish the existence of solution and all that.  But anyway, this gives an idea of the link between the PDE and the Stoke-Gaston differential  equation behind.  Okay?  Good.  So let me give some reference, important reference in the case of linear equations where B and  sigma do not depend on M.  So in that case, if you take sigma equal to zero, so you are in the first order case and  B is not regular, then you have several results, one result by the Bernoulli-Leon's and then  by Ambrosio, et cetera, about the existence and uniqueness of this equation.  And when sigma is not zero, so you are in the second order case and B is still not regular,  you have also results by Le Brie and Lyons and by Figalli, et cetera.  And also there is this people that are interested in the Fogger Plan equation.  I advise to read that paper, to look at that book that I recently discovered that is very  important.  So this is what they do by Bogachev, Krilov, Röknöf and Schapofnikov, where they do like  a detailed account of this equation.  Well in the non-linear case, in the generality that I presented before, there are also some  results but there are also some interesting results by Bogachev, Röknöf and Schapofnikov  when sigma is equal to zero and in the stochastic case by Manita and Schapofnikov in the 2012  and 13.  So this is important papers, I think, in this subject.  Good.  So nothing works anymore.  And with this, I will go with the, I don't know who it is.  Okay, so now that I presented the equation, now we will discuss about the scheme.  So in order to present the scheme, for pedagogical reasons, I will start with the most simplest  case that will be with sigma equal to zero, so it will be in a deterministic framework.  And also with B, so there is no sigma, but there is B. And I will take B independent  of M. Okay?  So I will take that case and then we will go forward.  Okay?  So in that case, under suitable assumptions on B here, I won't discuss the technical assumptions  on B and sigma yet because I can suppose that they are very smooth, they have good properties  in order to derive the scheme, but then the scheme will apply to more general coefficients.  Okay?  So I suppose that everything is regular in order to motivate the scheme.  Okay?  So it's B's regular leap cheats.  So you have a solution of the, so you have a solution of this equation, x dot equals  to B of x.  And when you have this equation, you can define a flow.  The flow, it means that as you associate at each initial condition, you associate at  time t the value of the solution at time t.  Okay?  So that is what I call capital phi.  So phi of s t x, okay, will be the solution of the equation at time t when I take initial  time as small s and initial condition as small x, okay?  So I can define this flow.  So this is a function of three variables, the two times, the initial times and the time  where I look at the solution and initial condition, okay?  And then once you have this solution of this equation, this flow, I'm sorry, then in fact  you can prove that the solution of the Fokker-Planck equation is given as the E measure, measure  also called in English the push forward measure, of the initial measure M0 under this flow,  okay?  So this is a function of the initial condition, okay?  So you want to compute M at time t, you put initial time 0 because you will move M0, okay?  And then you compute the flow up to time t.  So this gives you a function of the initial condition.  And then you transport the initial measure with this flow.  I will recall this notation for people that are not aware.  So you take this, the function, for a function F, you take the push forward of M0 of a set,  this is a new measure, you define the border set, for example, this would be M0 of F minus  one of A, okay?  So this is this notation.  It's like the E-match measure, okay?  Good.  So this is very important because once you have a, you have a trajectory, a trajectory  interpretation of the solution of the Fokker-Planck equation, okay?  In terms of that ODE.  So once you understand that, you say, okay, in order to discretize the Fokker-Planck equation,  instead of discretizing the Fokker-Planck equation, I can discretize the flow, okay?  So how do you do that?  Well, you take an Euler scheme, for example.  So you take a time step delta t, you divide capital T by capital N, N is a natural number,  and then you set tk as k times delta t.  So you have agreed in time.  Good.  So that's normal.  And once you have that, you can define your discrete flow with the Euler scheme.  So, in fact, you can define the small phi at time k.  The small k there, in fact, is like you will do only one step, okay, from k to time k plus  1.  So you do an Euler scheme.  So you have your flow at time k when your starting point is small x.  It will be x plus delta t B of x tk, okay?  So then you define recursively this flow, okay?  And so the natural discretization in time of that equation is that you will say the  measure at time k plus 1 will be the measure at time k transported with the flow phi k,  because you do only one step.  It's clear, right?  The idea?  Okay.  Good.  But then you don't have a computable method because you only discretize in time.  So now we can decide to choose to discretize also in space to have something that is implementable.  So we discretize in space now, okay?  So the space discretization is that you take a space step delta x, okay?  And you define your space grid here.  I am working in Rd.  So I am taking all the grid in the whole space, okay?  So I define g delta x as the point xi where i is in zd times delta x, okay?  So you have a grid in Rd of length delta x.  And then you consider p1 basis.  So this is a function that I think at each element.  So you have to construct, using this grid, you can construct a triangulation, for example,  and then you can take this p1 function.  But I don't want to make it just complicated.  So let's think only in dimension one to make it simple, okay?  So in dimension one, my function beta i will be this function like that.  So it's a function here you have xi, here you have xi plus delta x, so it's xi plus  one, and here you have xi minus delta x, xi minus one.  So the function beta i associated to that node will be the function that values one  in the node, and it's zero here, zero there, and zero everywhere else, and inside is affine,  okay?  It's affine here and there.  So that's the function beta i.  Okay, so good.  Now we will use this function beta i to do the discretization in space.  So how we will discretize?  Now I do the same before, so I have my discrete flow, but now I have discrete space.  So I already find my trajectories only starting at the points on the grid.  So that's phi i k is the discrete characteristic starting at point xa.  Okay?  And then I will define my measure at time k, my discretization, as the sum of delta measures,  of delta of direct measures, weighted by some weight that I have to compute, so I have to  compute the weights.  So the weights, so you have weights in each point on the grid in the space, but you also  have time, okay?  Okay?  So how do I compute these weights?  So at time zero, at time zero I only, at time zero I will do a picture here.  So this is xi, this is xi plus one, and this is xi minus one.  Okay?  So at time zero, so I have half, so this will be ai, so this will be xi plus delta x over  two.  Okay, so this will be this small interval delta, we'll call it ai, and so my initial measure,  the mass that I will put at time t, at time k equals zero in this point, the weight that  I will put in this point, will be the measure m zero of that interval.  Okay?  So this will be at time zero, this will be the measure m zero that is given of the interval  ei.  Okay?  Okay, so that's how I define my measures.  Then I have, then I have, I will use another blackboard, then I have to compute the measures,  the weights in the next times.  How do I do that?  How do I do that?  So the idea here, so you have this formula with the beta i that is complicated, but I  will try to explain it with a picture, okay?  So the idea is that here you have point xi, so I want to compute, I am looking at the  second line, I want to compute the weight at that point at time k plus one.  So this is time k plus one.  Okay?  And so here I have my function, so here I have my function like that, this is beta i,  sorry it's not very, this is beta i.  So I have to compute, I want to compute the mass, the weight at this point.  Okay?  And so in order to do that, I will look at the past time, so at time k, and I will see  all the characteristics, this phi i k that arrive into this support of my beta i.  And then I will multiply the weight of the mass that arrives to that point with the inverse  to the distance to the point xa.  So that's the idea.  So if I have point, I have here time kk.  For example, if I have here xj, here I have a mass mjk, okay?  Then if I want to see how much mass at point xj will be transferred to point xi, I will  see if my disc is characteristic, so I have phi jk.  So imagine that this is phi jk.  Imagine that this is phi jk.  So if that's phi jk, so if I compute the characteristic and it arrives to the support  of beta i, I will put mass from xj into xi.  And how much?  It will be proportional to the distance.  For example, if this guy, the characteristic, arrives at the midpoint between xi and xi plus  one, I will put half of the mass of mj to xi and the other half to xi plus one.  Okay?  If phi jk arrives exactly to the point xi, I will put all the mass mj in the mass mi.  So this will be the contribution of this term.  But then I have to see all the other points on the grid.  And I have to see where the disc characteristic goes, and so that's why you have the sum of  beta i.  Okay?  So that's the idea.  So if this is clear, it's the basis of the schema.  Okay.  So that's the schema, and well, you can prove that it works.  And everything will be the convergence of all the schemes.  All that will be a consequence of the general result in the nonlinear case.  So I'm only showing the scheme.  Good.  Now, what happens in the stochastic case?  In the stochastic case, we don't have these deterministic characteristics because you  have a second order term.  This second order term will be linked to a diffusion.  Okay?  So what is important is, as I said before, is the representation formula.  So in the stochastic case, you have that your characteristics will be given by what?  I am considering the stochastic case, but linear yet.  Okay?  So B and sigma do not depend on M.  So in the stochastic case, you have that your characteristic will be, your flow will be  defined as X at S will be the solution of B of X, X, S.  And here I will put S prime, for example.  This will be S prime, S prime, the S prime, plus the sigma term, X, X at point S prime,  and the Bromley motion, W. And so you have X at time S will be X.  So this will be the analogous characteristic, but now it's stochastic.  Okay?  But in fact, you have the same kind of representation formula.  MT at the measure, the solution of the Fokker Planck is a measure.  So at time T, I compute it, it will be a measure.  So if I want to compute that measure on a set A, what do I do?  I solve this equation.  So this gives me an stochastic flow.  And this, so it depends on omega on the alia.  So for each omega, I will have like a deterministic flow in some sense.  And then I will transport the initial measure with this deterministic flow that depends  on omega.  And this gives me a measure that will be stochastic because it will be the transport of the initial  measure with this stochastic flow.  And then you compute that set A and then you take that mean.  Okay?  So this is the solution of the Fokker Planck in the case where you have a second order  term.  So it's exactly as before, a set that, from the fact that you have to take a mean over  the alia of these flows.  Okay?  Good.  So this is that phi 0 t omega.  This would be the stochastic flow.  Okay?  That is the final term.  So then as before, we saw that we have to discretize the flow.  Okay?  So here is the same idea.  So I will discretize the stochastic differential equation.  So here I consider, I also, I am skipping the part where I discretized first time and  then space.  I will do all in one step because you know how does it work.  So I have to compute the characteristics starting from the points on the grid.  Okay?  And so the idea is that you define, you will discretize your Brony motion from time k up  to time k plus 1.  You will discretize it with the most simplest thing that will be a random work.  So you will have your point x a and your Brony motion can go up with probability one-half  and go down with probability one-half.  And so you will discretize that with a random work in that step.  Okay?  So you will define that discrete flow now that have two possibilities with the plus and  the minus.  So it would be phi jk plus minus dL, I will discuss it now.  It would be xj plus delta tb, so this is the earlier scheme, plus a minus or minus, you  have to decide.  Okay?  The square root, that's natural scaling for the Brony motion as you know, times the sigma,  the sigma term.  So dL here is this because you have R or you have several Brony motion.  You have R Brony motion.  So you have two possibilities for each Brony motion.  Okay?  To each Brony motion, you have associated a column of the matrix sigma.  So sigma L is the L column of sigma.  So for that column, you will move with probability one-half up or probability one-half down.  So you have this discrete flow.  Okay?  So that's very natural.  And then you do the same.  So the representation formula gives you that m at time k should be equal to the sum of  Dirac masses times some weights, and you have to compute the weights, and I would use those  discrete characteristics.  Okay?  So at the beginning I do as before, and then to go from time k up to time k plus one, I  do the same, forget R, take R equals to one, so you have only one Brony motion to simplify  the discussion.  So here you don't have this sum and you have R equals to one.  So you have this similar formula than before, but you have to evaluate two characteristics  because you have these two possibilities for the random walk.  Okay?  And you have these two possibilities, and this possibility has probability one-half.  Okay?  Good.  So that's the scheme in the second order case.  So it is important from the theoretical point of view to prove the convergence of the schemes.  It is important to notice that these schemes, it corresponds to the transition probabilities  of a Markov chain.  Okay?  So the transition probability that is described by exactly the transition probability that  I want.  So you have a Markov chain behind that is somehow discretizing this diffusion.  Okay?  So the initial law, so it's a Markov chain that is discretized in space and discretized  in time, and the initial law of this Markov chain, it would be this initial distribution,  and then the transition probabilities are computed via that formula, and when you define  those transition probabilities, if you compute the marginal laws of the Markov chains, you  will have that the marginal will be given by this formula.  Okay?  So if you define those transition probabilities, you will have that.  Okay.  So that's the point.  Now in the nonlinear case, well, in the nonlinear case, you have a problem because all this idea  that you are doing this stuff recursively is linked with the Markov property in some  sense.  Okay?  But in the nonlinear case, you lose the Markov properties in those machine class of equations,  so you don't have the Markov property, but if you fix a measure on the coefficients,  then you will have a regular diffusion for which you have the Markov property and all  these schemes I presented before make sense.  So the decision in very natural, I freeze the measure, I do my scheme, and then I have  to compute a fixed point.  Okay?  So that's exactly the scheme that at the end, it corresponds to put the measures M's in  the nonlinearity in the discrete characteristics.  So the scheme is exactly the same, but you have that M also is inside the nonlinearities.  Okay.  Then you can prove under only the continuity assumption of the coefficients, you can prove  that this scheme has a, I admit a solution.  This solution is in the linear case was trivial.  Of course you have only one, in that case you have only one solution in the linear case  because you construct the scheme iteratively.  Okay?  So here it will be exactly the same if my, so this is important.  If my coefficients, as I recall that my coefficient depends on M on the whole interval of time.  So if I compute BM at time XT, but what is important here is time, if I compute BM at  time T, and if this BM at time T depends only on the past trajectory of the measure, then  the scheme will be explicit.  Okay?  And then you will have only one solution of the scheme.  On the other hand, if my scheme might be at time, might be as a function of M at time  T, it depends on the value of M in the future, then the scheme will be implicit.  And then in that case the solution, the existence of a solution of that scheme comes from the,  from a fixed point argument.  Okay?  And so we will see exactly that this case of an implicit scheme is exactly the case of  M in field games.  So the convergent result.  So the assumption is that, this is the only assumption that you have that your maps are  continuous as a function of the measure times an X, so you don't have leap this assumption,  you have any assumption, only continuity.  Okay?  And you have linear growth with respect to X, that is uniform with respect to the other  variables.  Yeah?  I'm sorry?  What's the question?  Are you using the direction of measure?  In M?  Yes.  Yeah, I'm so sorry, yes, that's an important question, because I will write an, I will  write, so I will write then, and then we continue the property that makes use of the distance.  So I'm working with the space, the space of zero T, so in P1 of Rd.  So well, I have to only to measure side this space because you have to, here you take the  sweep.  So here you take the, this is the probability space with the one versus side distance.  So you have this, so P1, you have P1 Rd, and you endow it with a metric that we call d1,  that is the metric of optimal transport, that d1 of measure M1 and M2 will be the infimum  over all the measured gammas in the product.  There are probabilities in Rd times Rd of the integral in Rd times Rd of the distance between  x minus y, the gamma of x and y, and I take the infimum over gamma, so the first margin  I have to go response to the measure M1, so I write this as the projection on x.  So I take the image measure of gamma under the projection on the x coordinate, it will  be M1 and the same with x2, the projection on y of gamma will be M2.  So this is the optimal transport, excuse me, the versus time, one versus time, this is  by, in fact in this case there is an important probability also for the prudent system of  x-point, is that this, it does this space, in fact with this point because you can put  here a P, you have the distance of P here, you will put P here and you take the square,  the P root, so this is the P distance, but in the case P equals to 1 in this case, this  also has an alternative formula, that will be that's the super over the set of leashes  function of the integral in Rd now, you are not in the product of Fd, here you will have  M1 minus M2 and you take the super over the normal Fr leptis or 1 leptis, so you take  the gradient of F less than 1.  So you have that formula, it's not exactly the dual of leashes function, but it's somehow  like that, but what is important is that here you can embed this metric space of P1, that's  a metric space, you can embed it like in a vector space, and like that you can use shorter  fixed point theory and stuff like that, well that's the distance, what is important is  the distance 1, okay?  Good, any other question?  Okay, so now we have these two assumptions, continuity and linear growth, and under this  assumption the skin has at least one solution, okay?  But now the solution, remember I have weights in space, so I have dirai masses in space,  and in time I have to extend them, because I will work with this space, this will be  the space that I will work with, because this is the space where the solution lives, so  I have to work with this space, so I have to extend my measure in time, so I do that  with a simple interpolation in time, okay?  So now we have to make the parameters go to zero, so the important here, there is the  condition for the convergence, the condition is that delta x, delta n, the bad notation,  delta n x is a sequence of space steps that are going to zero, and delta tn is a sequence  of time steps that are going to zero, but if they satisfy that relation, that delta  t is small with respect to the square, no, excuse me, the square of delta x is small  with respect to delta t, then you will have convergence, so this is a nice property of  this scheme, because you can think or you can use another Markov chain to discretize  your diffusion, because the Markov chain that you took is strange, but the Markov chain  that we took has this good property that you will get conversion under that condition,  so this means that time can be bigger with respect to space, that is contrary to the  finite difference scheme when you implement it in explicit form, where you have that time  has to be small with respect to space, so that's the CPL condition in numerical analysis,  so this scheme has the other, in the other sense, time can be bigger with respect to  space, so this is interesting if you want to compute the solution in times, long time  horizons, because you cannot take very small time steps, okay, and so here in this interpretation  in terms of Markov chains, in fact, gives you this nice property, so you have that the  distance, you have the inequity continuity of the sequence of measures in this space,  so you have a whole there continuity here with that metric, and you also have that second  moments are bounded uniformly, so this is an important property of that space of P1,  so if you have a family C, so you have a family C subset of P1 of RD such that you have that  the integral of x square d mu is bounded, that is bounded for a uniform constant K is  bounded for all mu in C, okay, so you are in the case in the distance, in the one distance,  that you bound the second moments uniformly, then that set will be relatively compact,  okay, in P1, in P1, not in P2, in P1 it will be relative, so to get compactness in P1 you  have to bond higher moments, okay, so here in P2, so here if you see the second line  gives me that my oldest trajectory takes values in a relatively bounded set of P1, and I have  a continuity because of the first line, so by Arsela's colleague I have a limit measure in C0,  T, P1, okay, but then I have to prove that that measure is the solution of the Fokker  Planck equation, okay, but I won't do that because it's constant but that's the answer, so under  this assumption you have limit points, you always have a limit point, okay, because of this  continuity, this Arsela's colleague theory, in particular, so here this is a convergence result,  so all the schemes that are constructed have limits point, and each limit point is a solution of  the Fokker Planck, Kolmogorov equation, the general equation, okay, and in particular this gives also  an existence result for the equation, okay, so in some sense it's like a piano result, remember  piano in the ODE's that you only ask for continuity of the coefficients, you have existence, so in  that sense this is exactly the analogous of piano theory but for Fokker Planck equation, so I was  convinced that this result was somehow new, the existence also, but in fact no, there is this  paper that I cited before by Manita and Shapov-Fligov, that is 2012 and 13, where they prove  existence of these general equations but also under more general assumptions than the one that I put,  okay, so in fact our contribution is more in the numerical part, but anyway, but this gives  another proof of the existence in any case, okay, so this is now, this is important, so I will see  later, I don't have access always to B and sigma, so I cannot compute the solutions of the scheme,  okay, so what do we do in that case? We have to approximate the coefficients B and sigma in order  to get an implementable scheme, so that is the second result, so what happens if I take an  approximation, if I take B and sigma n, have linear growth independent of n, okay, they have to be  continuous only on x in that case, but the important property is that this converges, so there are good  approximation of the coefficients, good approximation means that if I take mu n converging to mu in  P1 and the C0 t P1, so remember that these are trajectories, then as a function of x and t, this  function Bn of mu n, they converge uniformly to B in the same for sigma over compact sets of rd times  0 t, so if you have that property, everything works, so you can construct the same scheme as  before, but now with Bn and with sigma n, there are computable things, and then you can take the limit  and you recover the solution again, okay, so that's important, good, so now, how much time do I have?  Okay, so now let's go to the applications, so me feel games, so here I will consider a particular  instance about full course, it can be generalized, but I consider a particular instance of me feel  games, so here I have a Hamilton-Jacoby-Bellman equation, co-applet with a Fokker-Plank equation,  the Hamilton-Jacoby-Bellman equation has a Hamiltonian that is quadratic, and in the Fokker-Plank  equation you have this velocity field that is minus the gradient of the value function V, okay,  so the important thing is that here I consider sigma not positive because I have this square,  sigma not equal to 0, there's a typo there, sigma is not 0, so this is what people call like  non-degenerate me feel game system, okay, and you can prove under good assumption of capital F and  G, I will discuss later, and under good assumption of capital F and G that are those  these coupling terms, you have existence of a solution, okay, of the me feel game, good,  but I don't know if you know the more or less this theory, you have been in the course, so I don't  have to remember to recall what was the meaning of that system, but anyway you will see right now  with the rewriting as only one Fokker-Plank equation, because here you have Hamilton-Jacoby-Bellman  equation, couplet with a Fokker-Plank equation, but you can put everything else on only one equation,  so the key point is that you can write all that system and only that equation, the second one,  but the gradient of V depends on M, okay, and depends on M trajectorially, because so to compute  the velocity field, I have to take the gradient of V of M, but who is V of M, it will be the solution  of that optimal control property, where in the coefficients you see appear M in the future,  because I want to compute the value of function at time x at time t as a function of M, but then  you see appear M at any time, so it's exactly a particular case of the equation that we considered  before, okay, but with a time dependence that's only in the future, and you don't have any past here,  good, so it's clear or not? Okay, so this is the technical assumptions that you have to take very  nice function f and capital F and capital G with bounded, with second bounded derivative, everything  with what you want, because this is only technical matters, because you are working on RD in the  whole space, you are working a bounded domain, then you have to put boundary conditions, it  becomes complicated, but otherwise you can work on the torus, you forget boundary conditions,  you unbounded domain, then you can relax those, so how those assumptions, so those assumptions  are important because of the unbounded of the space, anyway, they are also important to get  convergence also, but I mean that in a bounded domain, I think that they can be relaxed, I think,  well under these assumptions you have this very important property that as a function of the  three variables, so this is somehow a tonician, as a function of the three variables m, x and t,  the gradient of v, m, x and t is continuous, okay, and it's bounded, bounded is not as a  surprise because the function b you can prove that it's glitches because everything is bounded,  everything is glitches thanks to the first assumption, so that's no problem, but so I have this,  so it is continuous, so this is my b, sigma is a constant, so I can apply my preview and it's  bounded, so I have in particular has linear growth, so I can apply my theory, so in particular I have  existence of a solution, okay, that may be a system and I can approximate it, but now there is a  problem that we don't know this vector field, v, because I don't have an explicit formula for v,  because it's the value function of an optimal control problem, so then you have to approximate v,  the value function v, in fact you have to approximate the gradient of the value function v,  so then in order to compute the gradient, we compute first an approximation of v and this  we do it with what is called, you can choose any method that you want here, this is not important,  you can choose more or less any method to approximate your value function v, here I choose,  we choose the semi-lagrangian scheme, so you have this function b that is computed recursively  backward, and well anyway, so this here you have a function that is defined on the grid  and on the grid points of the, in the north of the grid, okay, and then you have to interpolate  in a space to have a function, but it will not be differentiable in the grid points, because you will  have a piece y affine function that will not be differentiable, but cannot compute the gradient,  so I want to, to approximate the gradient, so then you have this affine functions, so you have to  regularize them, you know, and then you compute the gradient, so then is what it, when it enters,  like, so the first line is only interpolation in space, it doesn't matter, but the second,  the second display here, it only means that I have this affine function that is not differentiable,  so I regularize with a modifier, okay, so then, but then I have another parameter that is epsilon,  that is the modifier, so then I have to make sure that when I do all the three stuff, delta x, delta  t, and epsilon go to zero, it will get convergence again, okay, well, in this case, as you can prove  that this, this, this value function regularize value functions satisfy like a key inequality  that is related with what is called the semiconcavity of the value function in the, in the continuous  case, but in the discrete case, so if you don't have this term here, the second term there,  with delta x squared divided by epsilon, if you don't have that term, this will mean that this  function is semiconcave, so this means that if you subtract a parabola with an adequate coefficient,  you will get a complicated function, okay, so it's almost concave if you want, and once you have that,  you, you, you, you, this is the key of the, of the approximation result because you see that if now  I may disappear that guy at the end, at the limit, I will get the semiconcavity, so I have to make it  disappear, so epsilon, the regularization terms of the modifier has to be bigger with respect to delta x,  and the first condition is the first, the same as before, okay, so in that case, I can, we can prove  that's an important result that those gradients using this semiconcavity property, those approximated  gradients converge to the true gradient, okay, uniformly over compact sets, and so I can apply  the approximation result that I put before, okay, and that's good, and so, and then we have the  convergence of the scheme, in general dimension, space dimension, so these are related, these are  not new techniques, this part, this, this is more or less an, a difference thing that we, what we  have done already with Elisabetta in 2014 and 15, but where we prove the convergence only in dimension  d equals to one, and the space dimension d equals to one, because we consider the generate  meaningful games, we consider the games where you, you don't have sigma, because to have that property  there, the, this convergence of the gradient, we only can prove it when, when you have sigma, okay,  so if you don't have sigma, you cannot do that, and the scheme is not the same, because then you  have to work, you cannot work with Dirac masses, you have to work with densities, so it's more  complicated in those papers, okay, so now I will end with another, so then we have a, a, a convergence  scheme for meaningful games in general dimension, now I will end with another application, that is  SOHA, where it's called huge model, but what we propose here is a modification, that we can prove  that it's well-posed, so the idea is the same equation as before, exactly the same, but the V  as a function of M is the, is the value function of the same stochastic optimal control problem,  except for the fact that if I compute that time t, my, the, the dependence in, the,  does not depend on M on the future, but I look only M at time t, I am at time t, I see the  population, and I will suppose that all the population remain like that in the future,  and I will optimize there, because I don't have time to do computations, so imagine that you  have like more to, to modelize, to model a panic situation, there is a fire, so you have to escape,  you are not going to compute an equilibrium to see what people will do then, and then you will  optimize, you will see the situation right, or now, you will try to escape, so then that means  that you fix M at this time, at this moment, and then you compute, okay? So in, well, you have  with this new velocity field, you have again that, or assumptions are satisfied,  but you have to, again, to use the approximation result, because you have to approximate V again,  because of value function, and then we also have convergence of the scheme, so this, you cannot write  it as a mean field game system, because you have the Fokker-Plan equation, but at each time t,  you solve a different Hamilton-Jagoby-Belman equation, so you have like a Fokker-Plan equation  with an infinite number of Hamilton-Jagoby-Belman equations, each one corresponds to the  optimal control problem when you fix M at that point, okay? But anyway, the system is, we prove  with this thing, either the system is well-posed, and we have convergence also.  What do we have to, and what is important is that, in some sense, it is easier than  mean field games, in some sense, numerically, because numerically, you have to solve like,  you will disk a tight time, so you have to solve N, Hamilton-Jagoby-Belman equation,  so you have a lot to solve, but what is important is that at each point, it's more,  it's easier, because this is an explicit scheme, it's an explicit situation,  because I don't look the future, I look my measure now, so it's an explicit problem.  So these are the numerical simulations, so I don't explain the details on people,  these one D because it was amplified, so here people, these are the initial distribution of  people, they want to reach these doors, okay, and these are, these are charts of the, of the  evolution, so this is a time, 30 times h, h I don't remember, I don't remember how much is h,  h is the time step, so this is an intermediate time, and this is the final time, so you,  these people in the second model, in this model of evacuation, that people will more or less  distribute like that at the end, okay, so people rather go, because they're like somehow blind,  they rather go rather quickly to the doors, they concentrate in the red parts on the doors,  rather quickly, so within the same data, the same data, for me field games,  and you see the difference, because here you have the same nature population, and at the intermediate  time there are people that remains, you have this peak at the middle, that people that remains,  that do not, that wait there, so they forecast somehow the behavior of the crowd, and then they  will move, and you have a very, a different distribution, the final distribution is the red  one, so then you see this rational behavior, I think, so okay, so I will skip that, so this is  the real huge model, but the problem with the real huge model that is there, so you have a  stationary, excuse me, you have a stationary, having to Jacobi-Berman equation, but the problem of that,  of that system is that it's not well-posed in general, instead that the one that we propose  is well-posed, so perspective, all the talk is, was based on a particular Markov chain  approximation of the diffusion, by saying that we can do the same with a general Markov chain  approximation of the diffusion, so then for a particular problem you choose the Markov chain  that you want, and you implement it, okay, now for the implicit scheme, as an example the Miffel  game, when you had the discrete system, you have existence of a solution, but it's not clear how to  compute it, because another fixed point of Banach, so you cannot do this sucessively iterate,  so we have to, and then we solve the discrete system in the Miffel game system, we solve it  with a learning procedure, but it's only realistic that people use in game theory, so for the implicit  scheme it's not clear how to provide, for the discrete system, how to provide a conversion algorithm,  and then there is all this point about the boundary condition, and of course there goes  this case that we didn't consider, so in the long time we're here, so these are the reference,  so the first, the old, the old I gave today is based on a, when I preprinted that we,  so it's available in archive, and the other papers are more ancient about Miffel games,  so thank you for your attention. So just if I understood correctly, to solve the Miffel game,  first you fix a distribution, you plug it in V, and you solve V by a semi Lagrangian,  and then you apply your method for, that you've described before, exactly, but you could do that  for another system of optimality, right, I mean it could be, doesn't have to be Miffel game,  it can be some Fogger plan coupled with some AJB, and you do the same trick.  Like a Miffel time control program. For example, yeah.  Yeah, yeah, I think so, yeah, of course, of course, yeah, I think that, yeah, I only put one example,  but of course I think, yeah, I think it should work, I have to think about it, but I think it  should work, but then I repeat, I took a simple example where I have a nice property, I think  that this should be checked in case by case, in fact, but you're right, what idea?  Question?  If not, let's thank Francisco again.
2017-08-10_Alvarez_0_47.png 2017-08-10_Alvarez_48_95.png 2017-08-10_Alvarez_96_155.png 2017-08-10_Alvarez_156_203.png 2017-08-10_Alvarez_204_275.png 2017-08-10_Alvarez_276_395.png 2017-08-10_Alvarez_396_467.png 2017-08-10_Alvarez_468_911.png 2017-08-10_Alvarez_912_1883.png 2017-08-10_Alvarez_1884_2099.png 2017-08-10_Alvarez_2100_2399.png 2017-08-10_Alvarez_2400_4391.png 2017-08-10_Alvarez_4392_5111.png 2017-08-10_Alvarez_5112_5627.png 2017-08-10_Alvarez_5628_6011.png 2017-08-10_Alvarez_6012_6107.png 2017-08-10_Alvarez_6108_6719.png 2017-08-10_Alvarez_6720_8423.png 2017-08-10_Alvarez_8424_8783.png 2017-08-10_Alvarez_8784_8963.png 2017-08-10_Alvarez_8964_9059.png 2017-08-10_Alvarez_9060_10055.png 2017-08-10_Alvarez_10056_10235.png 2017-08-10_Alvarez_10236_11279.png 2017-08-10_Alvarez_11280_11747.png 2017-08-10_Alvarez_11748_12275.png 2017-08-10_Alvarez_12276_12515.png 2017-08-10_Alvarez_12516_14879.png 2017-08-10_Alvarez_14880_15443.png 2017-08-10_Alvarez_15444_15563.png 2017-08-10_Alvarez_15564_16943.png 2017-08-10_Alvarez_16944_17447.png 2017-08-10_Alvarez_17448_18683.png 2017-08-10_Alvarez_18684_20231.png 2017-08-10_Alvarez_20232_21119.png 2017-08-10_Alvarez_21120_21335.png 2017-08-10_Alvarez_21336_23027.png 2017-08-10_Alvarez_23028_23147.png 2017-08-10_Alvarez_23148_24755.png 2017-08-10_Alvarez_24756_25151.png 2017-08-10_Alvarez_25152_25391.png 2017-08-10_Alvarez_25392_25655.png 2017-08-10_Alvarez_25656_26015.png 2017-08-10_Alvarez_26016_26459.png 2017-08-10_Alvarez_26460_27047.png 2017-08-10_Alvarez_27048_27995.png 2017-08-10_Alvarez_27996_29207.png 2017-08-10_Alvarez_29208_29531.png 2017-08-10_Alvarez_29532_30047.png 2017-08-10_Alvarez_30048_30995.png 2017-08-10_Alvarez_30996_32003.png 2017-08-10_Alvarez_32004_33719.png 2017-08-10_Alvarez_33720_37139.png 2017-08-10_Alvarez_37140_39251.png 2017-08-10_Alvarez_39252_39755.png 2017-08-10_Alvarez_39756_45563.png 2017-08-10_Alvarez_45564_45635.png 2017-08-10_Alvarez_45636_46811.png 2017-08-10_Alvarez_46812_46967.png 2017-08-10_Alvarez_46968_47627.png 2017-08-10_Alvarez_47628_48923.png 2017-08-10_Alvarez_48924_49043.png 2017-08-10_Alvarez_49044_49331.png 2017-08-10_Alvarez_49332_49475.png 2017-08-10_Alvarez_49476_50315.png 2017-08-10_Alvarez_50316_53867.png 2017-08-10_Alvarez_53868_54011.png 2017-08-10_Alvarez_54012_54611.png 2017-08-10_Alvarez_54612_54863.png 2017-08-10_Alvarez_54864_55079.png 2017-08-10_Alvarez_55080_55319.png 2017-08-10_Alvarez_55320_55367.png 2017-08-10_Alvarez_55368_58979.png 2017-08-10_Alvarez_58980_60707.png 2017-08-10_Alvarez_60708_61739.png 2017-08-10_Alvarez_61740_63287.png 2017-08-10_Alvarez_63288_63899.png 2017-08-10_Alvarez_63900_73547.png 2017-08-10_Alvarez_73548_83891.png 2017-08-10_Alvarez_83892_83951.png 2017-08-10_Alvarez_83952_84054.png