Graphon mean field games and the GMFG equations
Caines, Peter E.
Very large networks linking dynamical agents are now ubiquitous and there is significant interest in their analysis, design and control. The emergence of the graphon theory of large networks and their infinite limits has recently enabled the formulation of a theory of the centralized control of dynamical systems distributed on asymptotically infinite networks. Furthermore, the study of the decentralized control of such systems has been initiated in where Graphon Mean Field Games (GMFG) and the GMFG equations are formulated for the analysis of non-cooperative dynamical games on unbounded networks. In this talk the GMFG framework will be first be presented followed by the basic existence and uniqueness results for the GMFG equations, together with an epsilon-Nash theorem relating the infinite population equilibria on infinite networks to that of finite population equilibria on finite networks.
 So indeed, my title today is Meafield Games on Unbounded Networks and the Graphon MSG Equations. This is work with Xuan-Gal, my current post doctoral research fellow and former student and Min Yi Wang, professor at Carlton University in Ottawa and former student of Roland Malamé who's in the audience and myself. So the program is some propaganda as if you need it for Meafield Games which have been beautifully presented in the PDE context in several talks at this meeting. Just a slightly different perspective and to introduce a key feature and then we're going to introduce the motivation for considering what is effectively a new mathematical theory, effectively, of complex networks which I hope in modesty might be relevant to the study of crowds and for which we are developing a control theory. So then we're going to specifically present our initial results. This is initial because we're starting in all of this on control graph on control systems, graph on Meafield Games and we finish off with a linear-credit Gaussian example. So there are essentially four parts of this talk and I'll try to step through them efficiently. So where Min Yi, Roland and myself started with these stochastic models for the many player game setup is given here. I hope these slides are not too faint for you to see. The images don't look as vivid here as they do on my laptop screen. The notion is that one has got a large number of agents as you've heard in the talks up until now in the meeting and with states here denoted z i and that the dynamics of each agent are given by a averaged deterministic drift part and the stochastic term, the diffusion term, where one has here an average of influences over the other agents. And what I want to draw your attention to right at the start is the fact here that one has a flat average 1 over n. So that once averaging over the influences of all the other agents, notice here the indices for this is the ith agent, its state appears in each of these five functions as they are averaged over the states of the other agents and here one has the state of a major agent which stays as a order one entity as the number of agents goes to infinity of what we call minor agents. In your notice here the ones that the ith state appears in the intensity term on the Brownian increments and we're averaging again over the states of the other agents. Similarly in the last function are the performance functions for each agent. This is what makes it a game of course that the individuals have performance functions attached to themselves so they have their individual interests. Here we have for the order one major agent its performance function which is this expectation of the integral of the average of the cost rate functions of the influences of the other agents and here we have the minor agents, the agents who are asymptotically negligible, whose cost functions depend upon the major agent and of course are averaged over the other agents. So now the underlying we have a complete filtered probability space which is generated by the mutually independent initial conditions and the independent of the independent Brownian motions on each of the agents. Right now the way that we go to the limit here is to consider a McKean-Vlasov equation where the trajectory of a generic particle is governed by so we're going to what's happening here is we're going to the limit we're averaging over the other generic agents, along the generic paths of the system and so the average turns into here an integral in the limit against the measure governing the generic path of an agent. So what we have here is a extended Markov process in the sense that a solution is not a single trajectory but it's a pair namely we have the trajectory of an agent of a generic agent, a typical agent and the measure governing the agent. So now I'll make a remark at this point that it's because we come in with a formulation like this that it appears that we join up with the formulation that Guillaume Masanti presented earlier in the earlier in the conference. So then similarly the infinite population limit costs are written in this form of an integral against the measure of a generic agent. So there are one of the key features of Meanfield games is that the strategies of the individual agents depend only on their local information. So this is highly motivated from the point of view of large-scale systems but it means that not only is it the case that each agent you'll see, not only is it the case that each agent is restricted in its information pattern to its own state and deterministic quantities which it can compute but it's of no value for it to do anything else. This is a key feature. So this simply spells out the fact that the local information is a trajectory of the individual agent and that there is indeed also a global population information set. Now the notion of equilibrium which we're using which is basic to again all of the previous Meanfield game presentations and which I don't want to overlap with those because they were complete and elegant in the partial differential equation framework which was being presented and used. Here we've got the notion of a Nash equilibrium is as I'm sure you're familiar with that a unilateral move by a single agent yields no gain when everybody is using those strategies. So formally a set of controls are adapted to the local information set generates a Nash equilibrium with respect to the individual performance functions when the loss incurred to the ith agent cannot be reduced if it makes a unilateral move away from the prescribed set of control. Notice here that this is actually in a strong form because we're not just allowing the delinquent agent or the unilateral agent to move generally with respect to its own information set but we actually here allow it to make any move with respect to all of the possible information which is available. Right so now so this is the famous picture of the of a zero-sum equilibrium between in a zero-sum game equilibrium between two players which adds nothing technically to this talk except to give you the famous image of a Nash equilibrium. So what we actually do with because we're very interested in approximations is the is an epsilon Nash equilibrium which is essentially as it says that given an epsilon and then the strategies that the that the Nash equilibrium holds up to epsilon. Namely if you make a unilateral move you can gain up to epsilon's worth improvement of your performance. Okay so the fundamental partial differential equations which you which as I've said before you've seen in this meeting is that going to the limit so assuming all the limits exist assuming all the limits exist then then the the generic agents best best response strategy is generated by the solution to a McKean-Vlasov Hamilton-Jackabee-Belman equation displayed here where the measure for the generic agent is generated by a Fokker-Planck McKean-Vlasov Fokker-Planck equation Fokker-Planck-Komogorov equation displayed here and as was clearly emphasized by Martino Bardi this the the Hamilton-Jackabee-Belman equation is propagated backwards in time and the Fokker-Planck equation is generated forwards in time and this is equivalent to the stochastic differential equation describing the behavior of an individual agent subject to the controls. Now the the key point here again which has been mentioned before but these ideas are definitely worth saying more than twice is that a large-scale game problem which is intractable game theory problems are intractable when you've got three agents or four agents so that's what large-scale means there but the game theory problems that we're thinking over the order of 200,000, 300,000 or millions of players then that's turned into a stochastic control problem because at the equilibrium which of course we haven't yet proved exists the individual agent is playing against the mass what it sees is going to be this deterministic measure propagating and it plays against that so it's just a cat so the the way that the sort of the magic circle is entered the equilibrium is that it turns a game-threat problem into a stochastic control problem and of course the question is does the equilibrium exist now then the answer is yes and in particular in the that subject to technical conditions now I attempted to spell them out a little bit in a little bit of detail here because it's not really satisfying when somebody flaps their arms and says subject to technical conditions which I won't make completely explicit today so I'll make them semi explicit it's that for the for all the functions concerned so this is a general sort of high generalization not the full details once assuming uniform continuity and boundedness on all the functions and their derivatives and Lipschitz continuity with respect to controls okay so we can supply the details but I don't want to go into the into those here now the then so the that then there doesn't indeed exist so a a unique Nash equilibrium which is generated by the the state dependent control of a generic agent and it will depend on the solution equilibrium measure so furthermore we have the epsilon Nash property for every epsilon there will exist a population size and epsilon such of all population size is greater than that if one plays the infinite population strategy in the finite population setting you're within epsilon of an equilibrium okay now the reason that we think that we consider this to be very important is that it is that the application of MFG theory in a practical in a quote practical situation or on a problem with a large number of agents is hugely simplified by this fact so this one's got 300,000 players instead of trying to solve a 300,000 player game problem one goes to infinity one solves the let's say it's a big if it's a mechanical situation one might have two pairs of six entry PDE's and so one's going to be solving 12 PDE's as against 300,000 PDA PDE's assuming that an equilibrium even existed so this short circuits this runs around the complexity so that of course it's a part of the limit theory of mean field games but it's also the crucial feature of its application so the outline of the proof some of such time here is that how does it work where you restrict the Lipschitz constant so that a banach contraction argument functions so the key ideas here are that and I'll rely on the chair to give me the famous 10 minutes 5 minutes and 3 minutes flash okay so the key ideas is that we have a Nash equilibrium so to a stochastic control which is generated by a solution to a stochastic control problem we have dynamic regeneration namely that equilibrium is dynamically pushed forwards and there's a drastic simplification in terms of complexity okay now now the point is that that for many reasons one wants to apply now this is the most exciting part whether this ah the simulation works so we're through the hardest part of the talk okay so the so here we have one of these familiar schooling pictures where we've got a school of interrelating actually there's sardines so they're interacting with each other there's some sort of equilibrium and here comes a major player okay that's coming through that you don't mess with him or it right now the point is I don't really that I don't think that MFG theory straight off applies in the situation because firstly the the sardines relating to their neighbors they're not taking a one over in average you can't imagine that they're seeing a flat large law of large numbers average taking place and also also I don't think that there's one measure for which a single kernel it can be seen to be integrating to get the behavior now this rather cheesy picture here brings us to networks which are ubiquitous so the point is how are we going to deal with local effects in large-scale systems how can we apply mean field games in for do when we have local effects but they ripple out from each agent so locally you see your neighboring agents but in fact you're interacting with everybody through this can we apply mean for games with this challenge comes up obviously in networks which are everywhere today power grids epidemic models brain networks social networks okay and conceivably crowds so we're going to consider networks with large numbers of nodes in principle millions of billions complex connections which are asymptotically dense this is a technical point but locally in the theory we're using at this point you're going to have an arbitrarily large number of neighbors but those connections do not stretch necessarily over the whole network but the locally locally finite problem will it will be tackled depending upon the our current the advances in the theory by those who are working on it and our capacity to understand that right now what's a graph one so a graph one is a startlingly simple idea for for dealing with complex graphs so and when I say startlingly simple this is the image you have a graph you have a sujegency matrix and you turn that into its pixel picture in the obvious way so here we've got one over n of course partitions along the along the axes so we've had the pixel picture for a given indexing of the nodes now take this to the limit you see as we fill in more and more elements as we run along a sequence of graphs which could be growing they could be nested or may not be then in the limit you see you might conceive that you have some kind of dense image some kind of function at the end so now technically a graph one is simply a bounded symmetric Lebesgue measurable function displayed here and in the simplest case that we deal with the values are between zero and one corresponding to intensities okay so you could imagine it being only zero and one but if the strength of the connection varies as in many problems of interest then you take very zero one or even between minus one and one now the this the theory of graph once was developed basically by a combinatorics group centered on Budapest and the Microsoft research group in Seattle and there's a marvelous exposition it by one of the architects of the subject Lasso Lovic large networks and graph limits published by the American Math Society reporting the state of the subject in 2012 the idea now the point is that the space is given a norm which is the called the cut norm which is given by this definition that you're integrating over the unit square you've got the modulus here on the outside and once then taking the supremum over subsets m and t the measurable subsets of course are of the unit interval then the cut metric is that one then infimizes this you here's you've got a supremum then you infimize over the indexing of the nodes now this infimum makes things difficult to handle but in fact we can in many situations there's an there's a settled indexing of nodes which means we don't have to worry about that which is a great relief then the there's a relationship now I should mention that the cut metric is a generalized a direct generalization the notion of a cut metric in regular normal graph theory and it has some amazing properties for instance if you want to get like the density of triangles which might be important in crowds if three if groups of three were important you simply integrate the the graphon function in this way this triple integral over the unit square and then here I should have finished with an with an x an error which I'll correct next time I'm near the board so the now the point is that in this metric which is related subject which is bounded above by the little two metric and bounded below subject to mild conditions by L two metric as well that that the space is compact so this means that with any infinite sequence of graphs mapped maps into the unit square in this way using the using the cut metric one has convergent sub sequences and on well-defined situations these will actually be unique so now suddenly the world of complex networks is suddenly mathematically under control is turned into a part of functional analysis so that now so then off we go we can now actually put we've got here actually we go from the norm to a metric the properties which I've just described and now we have an operator you see we have an operator from L2 to L2 we can convolve we can we've got an infinite estimate generator we can now define differential equations where the states are going to be L2 functions on the unit interval so so this so now we what I'm going to do how much time do I have exactly left okay so now so then we'll be we try to five minutes for control theory and five for let me field games so to step through perhaps the control theory we can actually take linear control problems here's the picture you see here's the finite dimensional system here's a halfway infinity you see you've got functions on the pixel elements and then you go to the well-defined L2 limits and then one can actually solve linear control problems in the sense of now it now it's just turned into classical infinite dimensional linear control theory so we've taken problems on our three on sequences of arbitrary complex networks and turn it into linear control theory you see so then we consult and I'm going to step through this now quickly we we have here the notion of controllability if you can steer from any state to any state and we can define a Gramian in an analogy with the finite dimensional situation here we require uniform positive definiteness for state-to-state controllability again classical linear infinite dimensional linear control theory and then in fact we get our control methodology this is clearly mean field games driven because you start with something very complicated you step to its limiting smooth infinity object you can you solve your problem there and then you apply the infinite so to speak the infinite limit simple controller in your complex finite situation and it works in the sense that we can prove and I'm going to have to step through this you can actually prove the convergence that the country that if you go to if you've got a control or designed for the infinite system then and if you sample it and apply it to the finite system then you have approximations which of course will get better this is the terminal state approximation which will get better as n goes to infinity namely as the network converges on the limit graph on okay so now I'm going to step through this and I apologize for doing this quickly so that the that these are simulations where a smooth graph on is used to sampled you generate a network and then for using a control which is generated analytically on the graph on limit and applied to the sample and applied to the complex network then in fact one can steer the states of the nodes in a very precise way and of course this gets more precise as the number of nodes increases okay let's get through to and this works for LQG theory as well so you see here's the smooth graph on and here's a network of 160 nodes which is converging to the graph on in the cut metric sense which I've described before right and the control laws have computed for the smooth limiting object not for the complicated sample object of the networks see when you've got 500,000 nodes here obviously this is the simple it's simpler thing to use now let's go to mean field games now the point is as I said that that I don't think that the that the motivation here is that the flat one over n averaging which appears throughout mean field games and the single measure the single generic agent measure which appears doesn't describe a situation where for instance in this picture of airport densities you've got a different characteristics at the different clusters of nodes which are then interacting with each other over a very complex network so the idea and so here is a diagrammatic representation where you have a sequence of clusters which some which contain a very large number of agents where that there's a large number of agents are communicating with each other over a complex network see so we've now got those two we have now these two infinities running okay the infinity locally and the infinity of the network or in the limit so the that we can now go to a direct generalization of the part of the mean field game partial differential equation pair that you saw earlier and which are familiar with from in this meeting so now you see the dynamics at each the dynamics and the costs the dynamics here at the generic the node alpha in its cluster will in fact be a function now averaged over the graph on so the picture here is you're sitting at the at the agent alpha in its in its cluster which is now turned into a point so you've now got an infinite number of agents at a point and those and those are communicating with the infinite a number of agents at every other node and so here you see if you strip away the zero one integral over the graph on with the graph on waiting here then we've just simply got our old McKeen flasso of integral we're integrating we just be integrating here this is our because it's scalar states for simplicity you see if I had x alpha the control you alpha and then x beta x beta here would be integrated would then be be integrating with respect to the measure at now just set beta equals to alpha so there's just one node see that if I have here new alpha DX alpha and then I'm integrating over this free variable then I've got the McKeen flasso of integral that gave us the limit population before but now I have another integral which is that I do that I do that McKeen flasso of integration at each node at each node beta over the network which and the waiting between the alpha node and the beta node is given by the graph on function g alpha beta so I wonder if I dare try to just use the chalk and so the picture what it comes down to is that so here here we've got our unit square here we've got our graph on function a point here being the intensity of the connections between the alpha and the beta node if I'm sitting here at the alpha node then what I'm doing is and I've got here my graph on intensity is that at each of the points here there'll be sitting a measure which describes the popular the behavior of the generic agents at the beta node in the infinite network so then and then I integrate that at alpha integrate over those measures which are going to be distinct in general at each node so this this integration here gives me the dynamics similarly for the cost now for the lqg example oh okay then we have an existence theory okay and which is a generalization of the methods that give us the existence and uniqueness in the classic in the classical mfg case and we've almost got a complete we've almost got me to go the right way we've almost got a full epsilon Nash equilibrium results so this is work with our mini Wang the existence and uniqueness as presented the CDC last year the Nash equilibrium we hope will be accepted for the CDC this year and we're working on the overall paper right so the theorems read the same you see it's like declaring Lyapunov stability or declaring optimality see there's no exciting new information here except there is this earth for me exciting new setting but it's a direct generalization and it's worth mentioning that you retrieve you retrieve the classical case by taking a flat graph on what's happened the classical case we just set the graph equal to a flat level okay and then you retrieve the classical case right so now if for the here we have any more minutes including questions okay so in order to get a question I'll say that you see here's the lqg problem here's the lqg case here is the finite averaging okay here we have the individuals costs incidentally this business are following the crowd was the original problem that a mini a roll on I considered in the our first lqg mfg paper so now let's couple these the clusters by the by the uniform attachment graph whose graph on is given by 1-max alpha beta okay so then we have the individual agents cost you see it looks the same as before except that the now then the last two slides of the talk are here here's the individual agents dynamics here's the class function looks the same as before but but each agent is dealing with z alpha okay it's tracking z alpha which in fact you see is going to be a weighted mean of the other agents over the network so here the z alpha here is the graph on weighted means of all the other agents at the other over the network then the the control equations I look the same as they did in the classical case except that the s alpha equation is driven by v alpha which is the graph on mean over the whole network not just the mean with respect to one measure but is a mean with respect to all of the measures of the agents to which it's connected over the network with intensity given by the graph on and so that's the mean state process okay so that's it so what we've done here is meanfield games the introduction of the notion of a graph on indicated meanfield graph on control and then given the like to think it's a natural generalization of classical meanfield game theory to meanfield game theory on graphons and that's the lqg example to prove it works thank you
 So indeed, my title today is Meafield Games on Unbounded Networks and the Graphon MSG  Equations. This is work with Xuan-Gal, my current post doctoral research fellow and  former student and Min Yi Wang, professor at Carlton University in Ottawa and  former student of Roland Malamé who's in the audience and myself. So the program  is some propaganda as if you need it for Meafield Games which have been  beautifully presented in the PDE context in several talks at this meeting. Just a  slightly different perspective and to introduce a key feature and then we're  going to introduce the motivation for considering what is effectively a new  mathematical theory, effectively, of complex networks which I hope in  modesty might be relevant to the study of crowds and for which we are  developing a control theory. So then we're going to specifically present  our initial results. This is initial because we're starting in all of this on  control graph on control systems, graph on Meafield Games and we finish off with  a linear-credit Gaussian example. So there are essentially four  parts of this talk and I'll try to step through them efficiently. So where  Min Yi, Roland and myself started with these stochastic models for the many  player game setup is given here. I hope these slides are not too faint for  you to see. The images don't look as vivid here as they do on my laptop screen.  The notion is that one has got a large number of agents as you've heard in  the talks up until now in the meeting and with states here denoted z i and that  the dynamics of each agent are given by a averaged deterministic drift part and  the stochastic term, the diffusion term, where one has here an average of  influences over the other agents. And what I want to draw your attention to right at  the start is the fact here that one has a flat average 1 over n. So that  once averaging over the influences of all the other agents, notice here the  indices for this is the ith agent, its state appears in each of these five  functions as they are averaged over the states of the other agents and here one  has the state of a major agent which stays as a order one entity as the  number of agents goes to infinity of what we call minor agents. In your  notice here the ones that the ith state appears in the intensity term on the  Brownian increments and we're averaging again over the states of the other  agents. Similarly in the last function are the performance functions for each  agent. This is what makes it a game of course that the individuals have  performance functions attached to themselves so they have their individual  interests. Here we have for the order one major agent its performance function  which is this expectation of the integral of the average of the  cost rate functions of the influences of the other agents and here we have the  minor agents, the agents who are asymptotically negligible, whose cost  functions depend upon the major agent and of course are averaged over the other  agents. So now the underlying we have a complete filtered probability space  which is generated by the mutually independent initial conditions and the  independent of the independent Brownian motions on each of the agents. Right now  the way that we go to the limit here is to consider a McKean-Vlasov equation  where the trajectory of a generic particle is governed by so we're going to  what's happening here is we're going to the limit we're averaging over the other  generic agents, along the generic paths of the system and so the average turns  into here an integral in the limit against the measure governing the generic  path of an agent. So what we have here is a extended Markov process in the sense  that a solution is not a single trajectory but it's a pair namely we have  the trajectory of an agent of a generic agent, a typical agent and the measure  governing the agent. So now I'll make a remark at this point that it's because we  come in with a formulation like this that it appears that we join up with the  formulation that Guillaume Masanti presented earlier in the  earlier in the conference. So then similarly the infinite population limit  costs are written in this form of an integral against the measure of a  generic agent. So there are one of the key features of  Meanfield games is that the strategies of the individual agents  depend only on their local information. So this is highly  motivated from the point of view of large-scale systems but it means that not  only is it the case that each agent you'll see, not only is it the case that  each agent is restricted in its information pattern to its own state  and deterministic quantities which it can compute but it's of no value for it  to do anything else. This is a key feature. So this simply spells out the  fact that the local information is a trajectory of the individual agent and  that there is indeed also a global population information set. Now the  notion of equilibrium which we're using which is basic to again all of the  previous Meanfield game presentations and which I don't want to overlap with  those because they were complete and elegant in the partial differential  equation framework which was being presented and used. Here we've got the  notion of a Nash equilibrium is as I'm sure you're familiar with that a  unilateral move by a single agent yields no gain when everybody is using those  strategies. So formally a set of controls are adapted to the local  information set generates a Nash equilibrium with respect to the  individual performance functions when the loss incurred to the  ith agent cannot be reduced if it makes a unilateral move away from the prescribed  set of control. Notice here that this is actually in a strong form because we're  not just allowing the delinquent agent or the unilateral agent to move  generally with respect to its own information set but we actually here  allow it to make any move with respect to all of the possible information which  is available. Right so now so this is the famous picture of the of a zero-sum  equilibrium between in a zero-sum game equilibrium between two players which  adds nothing technically to this talk except to give you the famous image of  a Nash equilibrium. So what we actually do with because we're very interested in  approximations is the is an epsilon Nash equilibrium which is essentially as  it says that given an epsilon and then the strategies that the that the Nash  equilibrium holds up to epsilon. Namely if you make a unilateral move you can  gain up to epsilon's worth improvement of your performance. Okay so the  fundamental partial differential equations which you which as I've said  before you've seen in this meeting is that going to the limit so assuming all  the limits exist assuming all the limits exist then then the the generic  agents best best response strategy is generated by the solution to a  McKean-Vlasov Hamilton-Jackabee-Belman equation displayed here where the measure  for the generic agent is generated by a Fokker-Planck McKean-Vlasov Fokker-Planck  equation Fokker-Planck-Komogorov equation displayed here and as was clearly  emphasized by Martino Bardi this the the Hamilton-Jackabee-Belman equation is  propagated backwards in time and the Fokker-Planck equation is generated  forwards in time and this is equivalent to the stochastic differential  equation describing the behavior of an individual agent subject to the controls.  Now the the key point here again which has been mentioned before but these ideas  are definitely worth saying more than twice is that a large-scale game problem  which is intractable game theory problems are intractable when you've got  three agents or four agents so that's what large-scale means there but the game  theory problems that we're thinking over the order of 200,000, 300,000 or  millions of players then that's turned into a stochastic control problem  because at the equilibrium which of course we haven't yet proved exists the  individual agent is playing against the mass what it sees is going to be this  deterministic measure propagating and it plays against that so it's just a cat so  the the way that the sort of the magic circle is entered the equilibrium is that  it turns a game-threat problem into a stochastic control problem and of course  the question is does the equilibrium exist now then the answer is yes and in  particular in the that subject to technical conditions now I attempted to  spell them out a little bit in a little bit of detail here because it's not  really satisfying when somebody flaps their arms and says subject to technical  conditions which I won't make completely explicit today so I'll make them semi  explicit it's that for the for all the functions concerned so this is a general  sort of high generalization not the full details once assuming uniform  continuity and boundedness on all the functions and their derivatives and  Lipschitz continuity with respect to controls okay so we can supply the  details but I don't want to go into the into those here now the then so the  that then there doesn't indeed exist so a a unique Nash equilibrium which is  generated by the the state dependent control of a generic agent and it will  depend on the solution equilibrium measure so furthermore we have the  epsilon Nash property for every epsilon there will exist a population size and  epsilon such of all population size is greater than that if one plays the  infinite population strategy in the finite population setting you're within  epsilon of an equilibrium okay now the reason that we think that we consider  this to be very important is that it is that the application of MFG theory in a  practical in a quote practical situation or on a problem with a large number of  agents is hugely simplified by this fact so this one's got 300,000 players  instead of trying to solve a 300,000 player game problem one goes to  infinity one solves the let's say it's a big if it's a mechanical situation one  might have two pairs of six entry PDE's and so one's going to be solving 12  PDE's as against 300,000 PDA PDE's assuming that an equilibrium even existed  so this short circuits this runs around the complexity so that of course it's a  part of the limit theory of mean field games but it's also the crucial feature  of its application so the outline of the proof some of such time here is that  how does it work where you restrict the Lipschitz constant so that a banach  contraction argument functions so the key ideas here are that and I'll rely on  the chair to give me the famous 10 minutes 5 minutes and 3 minutes flash  okay so the key ideas is that we have a Nash equilibrium so to a stochastic  control which is generated by a solution to a stochastic control problem we have  dynamic regeneration namely that equilibrium is dynamically pushed  forwards and there's a drastic simplification in terms of complexity  okay now now the point is that that for many reasons one wants to apply now  this is the most exciting part whether this ah the simulation works so we're  through the hardest part of the talk okay so the so here we have one of these  familiar schooling pictures where we've got a school of interrelating actually  there's sardines so they're interacting with each other there's some sort of  equilibrium and here comes a major player okay that's coming through that  you don't mess with him or it right now the point is I don't really that I don't  think that MFG theory straight off applies in the situation because firstly the  the sardines relating to their neighbors they're not taking a one over in  average you can't imagine that they're seeing a flat large law of large numbers  average taking place and also also I don't think that there's one measure for  which a single kernel it can be seen to be integrating to get the behavior now  this rather cheesy picture here brings us to networks which are ubiquitous so the  point is how are we going to deal with local effects in large-scale systems how  can we apply mean field games in for do when we have local effects but they  ripple out from each agent so locally you see your neighboring agents but in  fact you're interacting with everybody through this can we apply mean for games  with this challenge comes up obviously in networks which are everywhere today  power grids epidemic models brain networks social networks okay and  conceivably crowds so we're going to consider networks with large numbers of  nodes in principle millions of billions complex connections which are  asymptotically dense this is a technical point but locally in the theory we're  using at this point you're going to have an arbitrarily large number of  neighbors but those connections do not stretch necessarily over the whole  network but the locally locally finite problem will it will be tackled depending  upon the our current the advances in the theory by those who are working on it  and our capacity to understand that right now what's a graph one so a graph one is  a startlingly simple idea for for dealing with complex graphs so and when I  say startlingly simple this is the image you have a graph you have a  sujegency matrix and you turn that into its pixel picture in the obvious way so  here we've got one over n of course partitions along the along the axes so  we've had the pixel picture for a given indexing of the nodes now take this to  the limit you see as we fill in more and more elements as we run along a  sequence of graphs which could be growing they could be nested or may not be  then in the limit you see you might conceive that you have some kind of  dense image some kind of function at the end so now technically a graph one is  simply a bounded symmetric Lebesgue measurable function displayed here and  in the simplest case that we deal with the values are between zero and one  corresponding to intensities okay so you could imagine it being only zero and one  but if the strength of the connection varies as in many problems of interest  then you take very zero one or even between minus one and one now the this  the theory of graph once was developed basically by a combinatorics group  centered on Budapest and the Microsoft research group in Seattle and there's a  marvelous exposition it by one of the architects of the subject Lasso Lovic  large networks and graph limits published by the American Math Society  reporting the state of the subject in 2012 the idea now the point is that the  space is given a norm which is the called the cut norm which is given by  this definition that you're integrating over the unit square you've got the  modulus here on the outside and once then taking the supremum over subsets  m and t the measurable subsets of course are of the unit interval then the cut  metric is that one then infimizes this you here's you've got a supremum then  you infimize over the indexing of the nodes now this infimum makes things  difficult to handle but in fact we can in many situations there's an there's a  settled indexing of nodes which means we don't have to worry about that which is  a great relief then the there's a relationship now I should mention that  the cut metric is a generalized a direct generalization the notion of a cut  metric in regular normal graph theory and it has some amazing properties for  instance if you want to get like the density of triangles which might be  important in crowds if three if groups of three were important you simply  integrate the the graphon function in this way this triple integral over the  unit square and then here I should have finished with an with an x an error  which I'll correct next time I'm near the board so the now the point is that in  this metric which is related subject which is bounded above by the little  two metric and bounded below subject to mild conditions by L two metric as well  that that the space is compact so this means that with any infinite sequence  of graphs mapped maps into the unit square in this way using the using the  cut metric one has convergent sub sequences and on well-defined situations  these will actually be unique so now suddenly the world of complex networks  is suddenly mathematically under control is turned into a part of functional  analysis so that now so then off we go we can now actually put we've got here  actually we go from the norm to a metric the properties which I've just  described and now we have an operator you see we have an operator from L2 to L2  we can convolve we can we've got an infinite estimate generator we can now  define differential equations where the states are going to be L2 functions on  the unit interval so so this so now we what I'm going to do how much time do I  have exactly left okay so now so then we'll be we try to five minutes for  control theory and five for let me field games so to step through perhaps the  control theory we can actually take linear control problems here's the  picture you see here's the finite dimensional system here's a halfway  infinity you see you've got functions on the pixel elements and then you go to  the well-defined L2 limits and then one can actually solve linear control  problems in the sense of now it now it's just turned into classical infinite  dimensional linear control theory so we've taken problems on our three on  sequences of arbitrary complex networks and turn it into linear control theory  you see so then we consult and I'm going to step through this now quickly we we  have here the notion of controllability if you can steer from any state to any  state and we can define a Gramian in an analogy with the finite dimensional  situation here we require uniform positive definiteness for state-to-state  controllability again classical linear infinite dimensional linear control  theory and then in fact we get our control methodology this is clearly  mean field games driven because you start with something very complicated you  step to its limiting smooth infinity object you can you solve your problem  there and then you apply the infinite so to speak the infinite limit simple  controller in your complex finite situation and it works in the sense  that we can prove and I'm going to have to step through this you can actually  prove the convergence that the country that if you go to if you've got a  control or designed for the infinite system then and if you sample it and  apply it to the finite system then you have approximations which of course  will get better this is the terminal state approximation which will get  better as n goes to infinity namely as the network converges on the limit  graph on okay so now I'm going to step through this and I apologize for doing  this quickly so that the that these are simulations where a smooth graph on is  used to sampled you generate a network and then for using a control which is  generated analytically on the graph on limit and applied to the sample and  applied to the complex network then in fact one can steer the states of the  nodes in a very precise way and of course this gets more precise as the  number of nodes increases okay let's get through to and this works for LQG  theory as well so you see here's the smooth graph on and here's a network of  160 nodes which is converging to the graph on in the cut metric sense which  I've described before right and the control laws have computed for the  smooth limiting object not for the complicated sample object of the  networks see when you've got 500,000 nodes here obviously this is the simple  it's simpler thing to use now let's go to mean field games now the point is as I  said that that I don't think that the that the motivation here is that the flat  one over n averaging which appears throughout mean field games and the  single measure the single generic agent measure which appears doesn't describe a  situation where for instance in this picture of airport densities you've  got a different characteristics at the different clusters of nodes  which are then interacting with each other over a very complex network so  the idea and so here is a diagrammatic representation where you have a sequence  of clusters which some which contain a very large number of agents where that  there's a large number of agents are communicating with each other over a  complex network see so we've now got those two we have now these two  infinities running okay the infinity locally and the infinity of the network  or in the limit so the that we can now go to a direct generalization of the  part of the mean field game partial differential equation pair that you saw  earlier and which are familiar with from in this meeting so now you see the  dynamics at each the dynamics and the costs the dynamics here at the generic  the node alpha in its cluster will in fact be a function now averaged over the  graph on so the picture here is you're sitting at the at the agent alpha in  its in its cluster which is now turned into a point so you've now got an  infinite number of agents at a point and those and those are communicating with  the infinite a number of agents at every other node and so here you see if you  strip away the zero one integral over the graph on with the graph on waiting  here then we've just simply got our old McKeen flasso of integral we're  integrating we just be integrating here this is our because it's scalar states  for simplicity you see if I had x alpha the control you alpha and then x beta  x beta here would be integrated would then be be integrating with respect to  the measure at now just set beta equals to alpha so there's just one node see  that if I have here new alpha DX alpha and then I'm integrating over this free  variable then I've got the McKeen flasso of integral that gave us the limit  population before but now I have another integral which is that I do that I do  that McKeen flasso of integration at each node at each node beta over the  network which and the waiting between the alpha node and the beta node is given  by the graph on function g alpha beta so I wonder if I dare try to just use the  chalk and so the picture what it comes down to is that so here here we've got  our unit square here we've got our graph on function a point here being the  intensity of the connections between the alpha and the beta node if I'm sitting  here at the alpha node then what I'm doing is and I've got here my graph on  intensity is that at each of the points here there'll be sitting a measure which  describes the popular the behavior of the generic agents at the beta node in  the infinite network so then and then I integrate that at alpha integrate over  those measures which are going to be distinct in general at each node so this  this integration here gives me the dynamics similarly for the cost now for  the lqg example oh okay then we have an existence theory okay and which is a  generalization of the methods that give us the existence and uniqueness in the  classic in the classical mfg case and we've almost got a complete we've almost  got me to go the right way we've almost got a full epsilon Nash equilibrium  results so this is work with our mini Wang the existence and uniqueness as  presented the CDC last year the Nash equilibrium we hope will be accepted for  the CDC this year and we're working on the overall paper right so the theorems  read the same you see it's like declaring Lyapunov stability or declaring  optimality see there's no exciting new information here except there is this  earth for me exciting new setting but it's a direct generalization and it's  worth mentioning that you retrieve you retrieve the classical case by taking a  flat graph on what's happened the classical case we just set the graph  equal to a flat level okay and then you retrieve the classical case right so now  if for the here we have any more minutes including questions okay so in order to  get a question I'll say that you see here's the lqg problem here's the lqg  case here is the finite averaging okay here we have the individuals costs  incidentally this business are following the crowd was the original problem that  a mini a roll on I considered in the our first lqg mfg paper so now let's  couple these the clusters by the by the uniform attachment graph whose graph on  is given by 1-max alpha beta okay so then we have the individual agents cost  you see it looks the same as before except that the now then the last two  slides of the talk are here here's the individual agents dynamics here's the  class function looks the same as before but but each agent is dealing with z  alpha okay it's tracking z alpha which in fact you see is going to be a weighted  mean of the other agents over the network so here the z alpha here is the  graph on weighted means of all the other agents at the other over the network  then the the control equations I look the same as they did in the classical case  except that the s alpha equation is driven by v alpha which is the graph on  mean over the whole network not just the mean with respect to one measure but is  a mean with respect to all of the measures of the agents to which it's  connected over the network with intensity given by the graph on and so  that's the mean state process okay so that's it so what we've done here is  meanfield games the introduction of the notion of a graph on indicated meanfield  graph on control and then given the like to think it's a natural generalization  of classical meanfield game theory to meanfield game theory on graphons and  that's the lqg example to prove it works thank you
2019-06-05_Caines_0_47.png 2019-06-05_Caines_48_95.png 2019-06-05_Caines_96_155.png 2019-06-05_Caines_156_203.png 2019-06-05_Caines_204_275.png 2019-06-05_Caines_276_527.png 2019-06-05_Caines_528_1223.png 2019-06-05_Caines_1224_1631.png 2019-06-05_Caines_1632_3155.png 2019-06-05_Caines_3156_7559.png 2019-06-05_Caines_7560_10739.png 2019-06-05_Caines_10740_13439.png 2019-06-05_Caines_13440_14279.png 2019-06-05_Caines_14280_14831.png 2019-06-05_Caines_14832_24347.png 2019-06-05_Caines_24348_24551.png 2019-06-05_Caines_24552_24755.png 2019-06-05_Caines_24756_25535.png 2019-06-05_Caines_25536_25727.png 2019-06-05_Caines_25728_29219.png 2019-06-05_Caines_29220_32771.png 2019-06-05_Caines_32772_34883.png 2019-06-05_Caines_34884_35267.png 2019-06-05_Caines_35268_35939.png 2019-06-05_Caines_35940_36659.png 2019-06-05_Caines_36660_36755.png 2019-06-05_Caines_36756_36815.png 2019-06-05_Caines_36816_38363.png 2019-06-05_Caines_38364_39299.png 2019-06-05_Caines_39300_43643.png 2019-06-05_Caines_43644_44615.png 2019-06-05_Caines_44616_46271.png 2019-06-05_Caines_46272_50063.png 2019-06-05_Caines_50064_50159.png 2019-06-05_Caines_50160_50219.png 2019-06-05_Caines_50220_50325.png
So indeed, my title today is Meafield Games on Unbounded Networks and the Graphon MSG Equations. This is work with Xuan-Gal, my current post doctoral research fellow and former student and Min Yi Wang, professor at Carlton University in Ottawa and former student of Roland Malamé who's in the audience and myself. So the program is some propaganda as if you need it for Meafield Games which have been beautifully presented in the PDE context in several talks at this meeting. Just a slightly different perspective and to introduce a key feature and then we're going to introduce the motivation for considering what is effectively a new mathematical theory, effectively, of complex networks which I hope in modesty might be relevant to the study of crowds and for which we are developing a control theory. So then we're going to specifically present our initial results. This is initial because we're starting in all of this on control graph on control systems, graph on Meafield Games and we finish off with a linear-credit Gaussian example. So there are essentially four parts of this talk and I'll try to step through them efficiently. So where Min Yi, Roland and myself started with these stochastic models for the many player game setup is given here. I hope these slides are not too faint for you to see. The images don't look as vivid here as they do on my laptop screen. The notion is that one has got a large number of agents as you've heard in the talks up until now in the meeting and with states here denoted z i and that the dynamics of each agent are given by a averaged deterministic drift part and the stochastic term, the diffusion term, where one has here an average of influences over the other agents. And what I want to draw your attention to right at the start is the fact here that one has a flat average 1 over n. So that once averaging over the influences of all the other agents, notice here the indices for this is the ith agent, its state appears in each of these five functions as they are averaged over the states of the other agents and here one has the state of a major agent which stays as a order one entity as the number of agents goes to infinity of what we call minor agents. In your notice here the ones that the ith state appears in the intensity term on the Brownian increments and we're averaging again over the states of the other agents. Similarly in the last function are the performance functions for each agent. This is what makes it a game of course that the individuals have performance functions attached to themselves so they have their individual interests. Here we have for the order one major agent its performance function which is this expectation of the integral of the average of the cost rate functions of the influences of the other agents and here we have the minor agents, the agents who are asymptotically negligible, whose cost functions depend upon the major agent and of course are averaged over the other agents. So now the underlying we have a complete filtered probability space which is generated by the mutually independent initial conditions and the independent of the independent Brownian motions on each of the agents. Right now the way that we go to the limit here is to consider a McKean-Vlasov equation where the trajectory of a generic particle is governed by so we're going to what's happening here is we're going to the limit we're averaging over the other generic agents, along the generic paths of the system and so the average turns into here an integral in the limit against the measure governing the generic path of an agent. So what we have here is a extended Markov process in the sense that a solution is not a single trajectory but it's a pair namely we have the trajectory of an agent of a generic agent, a typical agent and the measure governing the agent. So now I'll make a remark at this point that it's because we come in with a formulation like this that it appears that we join up with the formulation that Guillaume Masanti presented earlier in the earlier in the conference. So then similarly the infinite population limit costs are written in this form of an integral against the measure of a generic agent. So there are one of the key features of Meanfield games is that the strategies of the individual agents depend only on their local information. So this is highly motivated from the point of view of large-scale systems but it means that not only is it the case that each agent you'll see, not only is it the case that each agent is restricted in its information pattern to its own state and deterministic quantities which it can compute but it's of no value for it to do anything else. This is a key feature. So this simply spells out the fact that the local information is a trajectory of the individual agent and that there is indeed also a global population information set. Now the notion of equilibrium which we're using which is basic to again all of the previous Meanfield game presentations and which I don't want to overlap with those because they were complete and elegant in the partial differential equation framework which was being presented and used. Here we've got the notion of a Nash equilibrium is as I'm sure you're familiar with that a unilateral move by a single agent yields no gain when everybody is using those strategies. So formally a set of controls are adapted to the local information set generates a Nash equilibrium with respect to the individual performance functions when the loss incurred to the ith agent cannot be reduced if it makes a unilateral move away from the prescribed set of control. Notice here that this is actually in a strong form because we're not just allowing the delinquent agent or the unilateral agent to move generally with respect to its own information set but we actually here allow it to make any move with respect to all of the possible information which is available. Right so now so this is the famous picture of the of a zero-sum equilibrium between in a zero-sum game equilibrium between two players which adds nothing technically to this talk except to give you the famous image of a Nash equilibrium. So what we actually do with because we're very interested in approximations is the is an epsilon Nash equilibrium which is essentially as it says that given an epsilon and then the strategies that the that the Nash equilibrium holds up to epsilon. Namely if you make a unilateral move you can gain up to epsilon's worth improvement of your performance. Okay so the fundamental partial differential equations which you which as I've said before you've seen in this meeting is that going to the limit so assuming all the limits exist assuming all the limits exist then then the the generic agents best best response strategy is generated by the solution to a McKean-Vlasov Hamilton-Jackabee-Belman equation displayed here where the measure for the generic agent is generated by a Fokker-Planck McKean-Vlasov Fokker-Planck equation Fokker-Planck-Komogorov equation displayed here and as was clearly emphasized by Martino Bardi this the the Hamilton-Jackabee-Belman equation is propagated backwards in time and the Fokker-Planck equation is generated forwards in time and this is equivalent to the stochastic differential equation describing the behavior of an individual agent subject to the controls. Now the the key point here again which has been mentioned before but these ideas are definitely worth saying more than twice is that a large-scale game problem which is intractable game theory problems are intractable when you've got three agents or four agents so that's what large-scale means there but the game theory problems that we're thinking over the order of 200,000, 300,000 or millions of players then that's turned into a stochastic control problem because at the equilibrium which of course we haven't yet proved exists the individual agent is playing against the mass what it sees is going to be this deterministic measure propagating and it plays against that so it's just a cat so the the way that the sort of the magic circle is entered the equilibrium is that it turns a game-threat problem into a stochastic control problem and of course the question is does the equilibrium exist now then the answer is yes and in particular in the that subject to technical conditions now I attempted to spell them out a little bit in a little bit of detail here because it's not really satisfying when somebody flaps their arms and says subject to technical conditions which I won't make completely explicit today so I'll make them semi explicit it's that for the for all the functions concerned so this is a general sort of high generalization not the full details once assuming uniform continuity and boundedness on all the functions and their derivatives and Lipschitz continuity with respect to controls okay so we can supply the details but I don't want to go into the into those here now the then so the that then there doesn't indeed exist so a a unique Nash equilibrium which is generated by the the state dependent control of a generic agent and it will depend on the solution equilibrium measure so furthermore we have the epsilon Nash property for every epsilon there will exist a population size and epsilon such of all population size is greater than that if one plays the infinite population strategy in the finite population setting you're within epsilon of an equilibrium okay now the reason that we think that we consider this to be very important is that it is that the application of MFG theory in a practical in a quote practical situation or on a problem with a large number of agents is hugely simplified by this fact so this one's got 300,000 players instead of trying to solve a 300,000 player game problem one goes to infinity one solves the let's say it's a big if it's a mechanical situation one might have two pairs of six entry PDE's and so one's going to be solving 12 PDE's as against 300,000 PDA PDE's assuming that an equilibrium even existed so this short circuits this runs around the complexity so that of course it's a part of the limit theory of mean field games but it's also the crucial feature of its application so the outline of the proof some of such time here is that how does it work where you restrict the Lipschitz constant so that a banach contraction argument functions so the key ideas here are that and I'll rely on the chair to give me the famous 10 minutes 5 minutes and 3 minutes flash okay so the key ideas is that we have a Nash equilibrium so to a stochastic control which is generated by a solution to a stochastic control problem we have dynamic regeneration namely that equilibrium is dynamically pushed forwards and there's a drastic simplification in terms of complexity okay now now the point is that that for many reasons one wants to apply now this is the most exciting part whether this ah the simulation works so we're through the hardest part of the talk okay so the so here we have one of these familiar schooling pictures where we've got a school of interrelating actually there's sardines so they're interacting with each other there's some sort of equilibrium and here comes a major player okay that's coming through that you don't mess with him or it right now the point is I don't really that I don't think that MFG theory straight off applies in the situation because firstly the the sardines relating to their neighbors they're not taking a one over in average you can't imagine that they're seeing a flat large law of large numbers average taking place and also also I don't think that there's one measure for which a single kernel it can be seen to be integrating to get the behavior now this rather cheesy picture here brings us to networks which are ubiquitous so the point is how are we going to deal with local effects in large-scale systems how can we apply mean field games in for do when we have local effects but they ripple out from each agent so locally you see your neighboring agents but in fact you're interacting with everybody through this can we apply mean for games with this challenge comes up obviously in networks which are everywhere today power grids epidemic models brain networks social networks okay and conceivably crowds so we're going to consider networks with large numbers of nodes in principle millions of billions complex connections which are asymptotically dense this is a technical point but locally in the theory we're using at this point you're going to have an arbitrarily large number of neighbors but those connections do not stretch necessarily over the whole network but the locally locally finite problem will it will be tackled depending upon the our current the advances in the theory by those who are working on it and our capacity to understand that right now what's a graph one so a graph one is a startlingly simple idea for for dealing with complex graphs so and when I say startlingly simple this is the image you have a graph you have a sujegency matrix and you turn that into its pixel picture in the obvious way so here we've got one over n of course partitions along the along the axes so we've had the pixel picture for a given indexing of the nodes now take this to the limit you see as we fill in more and more elements as we run along a sequence of graphs which could be growing they could be nested or may not be then in the limit you see you might conceive that you have some kind of dense image some kind of function at the end so now technically a graph one is simply a bounded symmetric Lebesgue measurable function displayed here and in the simplest case that we deal with the values are between zero and one corresponding to intensities okay so you could imagine it being only zero and one but if the strength of the connection varies as in many problems of interest then you take very zero one or even between minus one and one now the this the theory of graph once was developed basically by a combinatorics group centered on Budapest and the Microsoft research group in Seattle and there's a marvelous exposition it by one of the architects of the subject Lasso Lovic large networks and graph limits published by the American Math Society reporting the state of the subject in 2012 the idea now the point is that the space is given a norm which is the called the cut norm which is given by this definition that you're integrating over the unit square you've got the modulus here on the outside and once then taking the supremum over subsets m and t the measurable subsets of course are of the unit interval then the cut metric is that one then infimizes this you here's you've got a supremum then you infimize over the indexing of the nodes now this infimum makes things difficult to handle but in fact we can in many situations there's an there's a settled indexing of nodes which means we don't have to worry about that which is a great relief then the there's a relationship now I should mention that the cut metric is a generalized a direct generalization the notion of a cut metric in regular normal graph theory and it has some amazing properties for instance if you want to get like the density of triangles which might be important in crowds if three if groups of three were important you simply integrate the the graphon function in this way this triple integral over the unit square and then here I should have finished with an with an x an error which I'll correct next time I'm near the board so the now the point is that in this metric which is related subject which is bounded above by the little two metric and bounded below subject to mild conditions by L two metric as well that that the space is compact so this means that with any infinite sequence of graphs mapped maps into the unit square in this way using the using the cut metric one has convergent sub sequences and on well-defined situations these will actually be unique so now suddenly the world of complex networks is suddenly mathematically under control is turned into a part of functional analysis so that now so then off we go we can now actually put we've got here actually we go from the norm to a metric the properties which I've just described and now we have an operator you see we have an operator from L2 to L2 we can convolve we can we've got an infinite estimate generator we can now define differential equations where the states are going to be L2 functions on the unit interval so so this so now we what I'm going to do how much time do I have exactly left okay so now so then we'll be we try to five minutes for control theory and five for let me field games so to step through perhaps the control theory we can actually take linear control problems here's the picture you see here's the finite dimensional system here's a halfway infinity you see you've got functions on the pixel elements and then you go to the well-defined L2 limits and then one can actually solve linear control problems in the sense of now it now it's just turned into classical infinite dimensional linear control theory so we've taken problems on our three on sequences of arbitrary complex networks and turn it into linear control theory you see so then we consult and I'm going to step through this now quickly we we have here the notion of controllability if you can steer from any state to any state and we can define a Gramian in an analogy with the finite dimensional situation here we require uniform positive definiteness for state-to-state controllability again classical linear infinite dimensional linear control theory and then in fact we get our control methodology this is clearly mean field games driven because you start with something very complicated you step to its limiting smooth infinity object you can you solve your problem there and then you apply the infinite so to speak the infinite limit simple controller in your complex finite situation and it works in the sense that we can prove and I'm going to have to step through this you can actually prove the convergence that the country that if you go to if you've got a control or designed for the infinite system then and if you sample it and apply it to the finite system then you have approximations which of course will get better this is the terminal state approximation which will get better as n goes to infinity namely as the network converges on the limit graph on okay so now I'm going to step through this and I apologize for doing this quickly so that the that these are simulations where a smooth graph on is used to sampled you generate a network and then for using a control which is generated analytically on the graph on limit and applied to the sample and applied to the complex network then in fact one can steer the states of the nodes in a very precise way and of course this gets more precise as the number of nodes increases okay let's get through to and this works for LQG theory as well so you see here's the smooth graph on and here's a network of 160 nodes which is converging to the graph on in the cut metric sense which I've described before right and the control laws have computed for the smooth limiting object not for the complicated sample object of the networks see when you've got 500,000 nodes here obviously this is the simple it's simpler thing to use now let's go to mean field games now the point is as I said that that I don't think that the that the motivation here is that the flat one over n averaging which appears throughout mean field games and the single measure the single generic agent measure which appears doesn't describe a situation where for instance in this picture of airport densities you've got a different characteristics at the different clusters of nodes which are then interacting with each other over a very complex network so the idea and so here is a diagrammatic representation where you have a sequence of clusters which some which contain a very large number of agents where that there's a large number of agents are communicating with each other over a complex network see so we've now got those two we have now these two infinities running okay the infinity locally and the infinity of the network or in the limit so the that we can now go to a direct generalization of the part of the mean field game partial differential equation pair that you saw earlier and which are familiar with from in this meeting so now you see the dynamics at each the dynamics and the costs the dynamics here at the generic the node alpha in its cluster will in fact be a function now averaged over the graph on so the picture here is you're sitting at the at the agent alpha in its in its cluster which is now turned into a point so you've now got an infinite number of agents at a point and those and those are communicating with the infinite a number of agents at every other node and so here you see if you strip away the zero one integral over the graph on with the graph on waiting here then we've just simply got our old McKeen flasso of integral we're integrating we just be integrating here this is our because it's scalar states for simplicity you see if I had x alpha the control you alpha and then x beta x beta here would be integrated would then be be integrating with respect to the measure at now just set beta equals to alpha so there's just one node see that if I have here new alpha DX alpha and then I'm integrating over this free variable then I've got the McKeen flasso of integral that gave us the limit population before but now I have another integral which is that I do that I do that McKeen flasso of integration at each node at each node beta over the network which and the waiting between the alpha node and the beta node is given by the graph on function g alpha beta so I wonder if I dare try to just use the chalk and so the picture what it comes down to is that so here here we've got our unit square here we've got our graph on function a point here being the intensity of the connections between the alpha and the beta node if I'm sitting here at the alpha node then what I'm doing is and I've got here my graph on intensity is that at each of the points here there'll be sitting a measure which describes the popular the behavior of the generic agents at the beta node in the infinite network so then and then I integrate that at alpha integrate over those measures which are going to be distinct in general at each node so this this integration here gives me the dynamics similarly for the cost now for the lqg example oh okay then we have an existence theory okay and which is a generalization of the methods that give us the existence and uniqueness in the classic in the classical mfg case and we've almost got a complete we've almost got me to go the right way we've almost got a full epsilon Nash equilibrium results so this is work with our mini Wang the existence and uniqueness as presented the CDC last year the Nash equilibrium we hope will be accepted for the CDC this year and we're working on the overall paper right so the theorems read the same you see it's like declaring Lyapunov stability or declaring optimality see there's no exciting new information here except there is this earth for me exciting new setting but it's a direct generalization and it's worth mentioning that you retrieve you retrieve the classical case by taking a flat graph on what's happened the classical case we just set the graph equal to a flat level okay and then you retrieve the classical case right so now if for the here we have any more minutes including questions okay so in order to get a question I'll say that you see here's the lqg problem here's the lqg case here is the finite averaging okay here we have the individuals costs incidentally this business are following the crowd was the original problem that a mini a roll on I considered in the our first lqg mfg paper so now let's couple these the clusters by the by the uniform attachment graph whose graph on is given by 1-max alpha beta okay so then we have the individual agents cost you see it looks the same as before except that the now then the last two slides of the talk are here here's the individual agents dynamics here's the class function looks the same as before but but each agent is dealing with z alpha okay it's tracking z alpha which in fact you see is going to be a weighted mean of the other agents over the network so here the z alpha here is the graph on weighted means of all the other agents at the other over the network then the the control equations I look the same as they did in the classical case except that the s alpha equation is driven by v alpha which is the graph on mean over the whole network not just the mean with respect to one measure but is a mean with respect to all of the measures of the agents to which it's connected over the network with intensity given by the graph on and so that's the mean state process okay so that's it so what we've done here is meanfield games the introduction of the notion of a graph on indicated meanfield graph on control and then given the like to think it's a natural generalization of classical meanfield game theory to meanfield game theory on graphons and that's the lqg example to prove it works thank you
Unbounded Networks and the Graphon MSG Equations. modesty might be relevant to the study of crowds control systems, graph on Meafield Games and we So there are essentially four parts of this talk join up with the formulation that Guillaume conference. So then similarly the infinite of an integral against the measure of a generic Meanfield games is that the strategies of the where the measure for the generic agent is point here again which has been mentioned before population strategy in the finite population with a large number of agents is hugely firstly the the sardines relating to their one and one now the this the theory of graph once subject Lasso Lovic large networks and graph limits published by the American Math Society there's a large number of agents are existence and uniqueness as presented the CDC