Journal of Convex Analysis 20 (2013), No. 2, 395--438
Copyright Heldermann Verlag 2013
Learning how to Play Nash, Potential Games and Alternating Minimization Method for Structured Nonconvex Problems on Riemannian Manifolds
João Xavier Cruz Neto
Dept. of Mathematics, Federal University of Piauí, Teresina, Brazil
jxavier@ufpi.edu.br
Paulo Roberto Oliveira
PESC/COPPE, Programa de Engenharia de Sistemas e Computação, Rio de Janeiro, Brazil
poliveir@cos.ufrj.br
Pedro A. Soares Jr
PESC/COPPE, Programa de Engenharia de Sistemas e Computação, Rio de Janeiro, Brazil
pedroasoaresjr@gmail.com
Antoine Soubeyran
GREQAM-AMSE, Université d'Aix-Marseille II, France
antoine.soubeyran@gmail.com
We consider minimization problems with constraints. We show that if the set of constraints is a Riemannian manifold of non positive curvature and the objective function is lower semicontinuous and satisfies the Kurdyka-Lojasiewicz property, then the alternating proximal algorithm in Euclidean space is naturally extended to solve that class of problems. We prove that the sequence generated by our algorithm is well defined and converges to an inertial Nash equilibrium under mild assumptions about the objective function. As an application, we give a welcome result on the difficult problem of "learning how to play Nash" (convergence, convergence in finite time, speed of convergence, constraints in action spaces in the context of "alternating potential games" with inertia).
Keywords: Nash equilibrium, convergence, finite time, proximal algorithm, alternation, learning in games, inertia, Riemannian manifold, Kurdyka-Lojasiewicz property.
MSC: 65K10, 49J52, 49M27 , 90C26, 91B50, 91B06; 53B20
[ Fulltext-pdf (311 KB)] for subscribers only.