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.
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.
Accepted:
Published online:
Mots-clés : Jeux stochastiques, Graphe, Équations aux dérivées partielles, EDPs locales et non locales sur graphes, Interpolation sur graphes
Abderrahim Elmoataz 1; Pierre Buyssens 1
@article{CRMECA_2017__345_3_177_0, author = {Abderrahim Elmoataz and Pierre Buyssens}, title = {On the connection between tug-of-war games and nonlocal {PDEs} on graphs}, journal = {Comptes Rendus. M\'ecanique}, pages = {177--183}, publisher = {Elsevier}, volume = {345}, number = {3}, year = {2017}, doi = {10.1016/j.crme.2016.12.001}, language = {en}, }
Abderrahim Elmoataz; Pierre Buyssens. On the connection between tug-of-war games and nonlocal PDEs on graphs. Comptes Rendus. Mécanique, Volume 345 (2017) no. 3, pp. 177-183. doi : 10.1016/j.crme.2016.12.001. https://comptes-rendus.academie-sciences.fr/mecanique/articles/10.1016/j.crme.2016.12.001/
[1] Tug-of-war with noise: a game-theoretic view of the p-Laplacian, Duke Math. J., Volume 145 (2008) no. 1, pp. 91-120
[2] Tug-of-war and the infinity Laplacian, J. Amer. Math. Soc., Volume 22 (2009) no. 1, pp. 167-210
[3] Local regularity results for value functions of tug-of-war with noise and running payoff, Adv. Calc. Var., Volume 9 (2016) no. 1, pp. 1-17
[4] The emerging field of signal processing on graphs: extending high-dimensional data analysis to networks and other irregular domains, IEEE Signal Process. Mag., Volume 30 (2013) no. 3, pp. 83-98
[5] Nonlocal infinity Laplacian equation on graphs with applications in image processing and machine learning, Math. Comput. Simul., Volume 102 (2014), pp. 153-163
[6] Diffuse interface models on graphs for classification of high dimensional data, Multiscale Model. Simul., Volume 10 (2012) no. 3, pp. 1090-1118
[7] Nonlocal discrete regularization on weighted graphs: a framework for image and manifold processing, IEEE Trans. Image Process., Volume 17 (2008) no. 7, pp. 1047-1060
[8] Nonlocal operators with applications to image processing, Multiscale Model. Simul., Volume 7 (2008) no. 3, pp. 1005-1028
[9] Dynamic programming principle for tug-of-war games with noise, ESAIM Control Optim. Calc. Var., Volume 18 (2012) no. 1, pp. 81-90
[10] On the definition and properties of p-harmonious functions, Ann. Sc. Norm. Super. Pisa, Cl. Sci. (5), Volume 11 (2012) no. 2, p. 215
[11] Game theoretical methods in PDEs, Boll. Unione Mat. Ital., Volume 7 (2014) no. 3, pp. 211-216
[12] A game-tree approach to discrete infinity Laplacian with running costs (arXiv preprint) | arXiv
[13] p-Harmonious functions with drift on graphs via games, Electron. J. Differ. Equ., Volume 2011 (2011) no. 114, pp. 1-11
[14] Nonlinear elliptic partial differential equations and p-harmonic functions on graphs, Differ. Integral Equ., Volume 28 (2015) no. 1–2, pp. 79-102
[15] Nonlocal PDEs on graphs: from tug-of-war games to unified interpolation on images and point clouds, J. Math. Imaging Vis. (2016), pp. 1-21
[16] A Hölder infinity Laplacian, ESAIM Control Optim. Calc. Var., Volume 18 (2012), pp. 799-835
[17] Nonlocal Diffusion Problems, Mathematical Surveys and Monographs, vol. 165, American Mathematical Society, 2010
[18] Partial difference operators on weighted graphs for image processing on surfaces and point clouds, IEEE Trans. Image Process., Volume 23 (2014) no. 9, pp. 3896-3909
Cited by Sources:
Comments - Policy