On the connection between tug-of-war games and nonlocal PDEs on graphs

In this paper, we are interested in the connection between some stochastic games, namely the tug-of-war games, and non-local PDEs on graphs. We consider a general formulation of tug-of-war games related to many continuous PDEs. Using the framework of partial difference equations, we transcribe this formulation on graph, and show that it encompasses several PDEs on graphs such as the ∞-Laplacian, the game p-Laplacian with and without gradient terms, and the eikonal equation. We then interpret these discrete games as non-local tug-of-war games. The proposed framework is illustrated with general interpolation problems on graphs.

RésuméDans cet article, nous nous intéressons à la connexion entre certains jeux stochastiques et certaines équations aux dérivées artielles (EDP) sur graphes. Nous considérons une formulation générale des jeux de type tug of war reliés à de nombreuses EDP continues. En utilisant le cadre des équations aux différences partielles, nous transcrivons cette formulation, et montrons qu'elle inclut de nombreuses EDP sur graphes, telles que l'∞-laplacien, le game p-laplacien avec et sans termes de gradients, ainsi que l'équation eikonale. Nous interprétons ensuite ces jeux discrets comme des jeux de type tug of war non locaux. La méthode proposée est illustrée à travers de nombreux problèmes d'interpolation sur graphe.