Comptes Rendus
no. 3
On the connection between tug-of-war games and nonlocal PDEs on graphs
[Sur la connexion entre certains jeux stochastiques et les EDP sur graphes]
Abderrahim Elmoataz1  ; Pierre Buyssens1
1 Université de Caen Normandie, GREYC Laboratory, Image Team, 6, boulevard du Maréchal-Juin, 14050 Caen cedex, France
Comptes Rendus. Mécanique, Volume 345 (2017) no. 3, pp. 177-183.

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.

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.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/j.crme.2016.12.001
Keywords: Tug-of-war games, Graph, Partial differential equations, Local and non-local PDE on graphs, Interpolation on graphs
Mot 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

1 Université de Caen Normandie, GREYC Laboratory, Image Team, 6, boulevard du Maréchal-Juin, 14050 Caen cedex, France 
@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},
}
TY  - JOUR
AU  - Abderrahim Elmoataz
AU  - Pierre Buyssens
TI  - On the connection between tug-of-war games and nonlocal PDEs on graphs
JO  - Comptes Rendus. Mécanique
PY  - 2017
SP  - 177
EP  - 183
VL  - 345
IS  - 3
PB  - Elsevier
DO  - 10.1016/j.crme.2016.12.001
LA  - en
ID  - CRMECA_2017__345_3_177_0
ER  - 
%0 Journal Article
%A Abderrahim Elmoataz
%A Pierre Buyssens
%T On the connection between tug-of-war games and nonlocal PDEs on graphs
%J Comptes Rendus. Mécanique
%D 2017
%P 177-183
%V 345
%N 3
%I Elsevier
%R 10.1016/j.crme.2016.12.001
%G en
%F CRMECA_2017__345_3_177_0
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] Y. Peres; S. Sheffield 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] Y. Peres; O. Schramm; S. Sheffield; D. Wilson Tug-of-war and the infinity Laplacian, J. Amer. Math. Soc., Volume 22 (2009) no. 1, pp. 167-210

[3] E. Ruosteenoja 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] D.I. Shuman; S.K. Narang; P. Frossard; A. Ortega; P. Vandergheynst 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] A. Elmoataz; X. Desquesnes; Z. Lakhdari; O. Lézoray Nonlocal infinity Laplacian equation on graphs with applications in image processing and machine learning, Math. Comput. Simul., Volume 102 (2014), pp. 153-163

[6] A.L. Bertozzi; A. Flenner Diffuse interface models on graphs for classification of high dimensional data, Multiscale Model. Simul., Volume 10 (2012) no. 3, pp. 1090-1118

[7] A. Elmoataz; O. Lezoray; S. Bougleux 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] G. Gilboa; S. Osher Nonlocal operators with applications to image processing, Multiscale Model. Simul., Volume 7 (2008) no. 3, pp. 1005-1028

[9] J.J. Manfredi; M. Parviainen; J.D. Rossi Dynamic programming principle for tug-of-war games with noise, ESAIM Control Optim. Calc. Var., Volume 18 (2012) no. 1, pp. 81-90

[10] J.J. Manfredi; M. Parviainen; J.D. Rossi 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] M. Lewicka; J.J. Manfredi Game theoretical methods in PDEs, Boll. Unione Mat. Ital., Volume 7 (2014) no. 3, pp. 211-216

[12] Q. Liu; A. Schikorra A game-tree approach to discrete infinity Laplacian with running costs (arXiv preprint) | arXiv

[13] A.P. Sviridov p-Harmonious functions with drift on graphs via games, Electron. J. Differ. Equ., Volume 2011 (2011) no. 114, pp. 1-11

[14] J.J. Manfredi; A.M. Oberman; A.P. Sviridov Nonlinear elliptic partial differential equations and p-harmonic functions on graphs, Differ. Integral Equ., Volume 28 (2015) no. 1–2, pp. 79-102

[15] A. Elmoataz; F. Lozes; M. Toutain 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. Chambolle; E. Lindgren; R. Monneau A Hölder infinity Laplacian, ESAIM Control Optim. Calc. Var., Volume 18 (2012), pp. 799-835

[17] F. Andreu-Vaillo; J.M. Mazón; J.D. Rossi; J.J. Toledo-Melero Nonlocal Diffusion Problems, Mathematical Surveys and Monographs, vol. 165, American Mathematical Society, 2010

[18] F. Lozes; A. Elmoataz; O. Lézoray 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

Cité par Sources :

Commentaires - Politique

Ces articles pourraient vous intéresser

A policy iteration algorithm for zero-sum stochastic games with mean payoff

Jean Cochet-Terrasson; Stéphane Gaubert

C. R. Math (2006)

Strategic advantages in mean field games with a major player

Charles Bertucci; Jean-Michel Lasry; Pierre-Louis Lions

C. R. Math (2020)

Équations d'Hamilton–Jacobi liées aux jeux différentiels avec coût de type supremum

Oana-Silvia Serea

C. R. Math (2007)