Games, dynamics and optimization

Abstract: This talk aims to survey the triple-point interface between optimization, game theory, and dynamical systems. In the first part of the talk, we will discuss how the ordinary differential equation (ODE) method of stochastic approximation can be used to analyze the trajectories of stochastic first-order algorithms in non-convex programs – both in terms of convergence to the problem's critical set as well as the avoidance of non-minimizing critical manifolds. Subsequently, we will examine the behavior of these algorithms in a game-theoretic context involving \emph{several} optimizing agents, each with their individual objective. In this multi-agent setting, the situation is considerably more involved: On the one hand, if the game being played satisfies a monotonicity condition known as "diagonal strict convexity" (Rosen, Econometrica, 1965), the induced sequence of play converges to Nash equilibrium with probability $1$. On the other hand, in non-monotone games, the sequence of play may converge with arbitrarily high probability to spurious attractors that are in no way unilaterally stable (or even stationary). "Traps" of this type can arise even in simple two-player zero-sum games with one-dimensional action sets and polynomial payoffs, a fact which highlights the fundamental gap between min-min and min-max problems.

We will discuss both classical and recent results – but not the proofs thereof.

game theoryoptimization and control

Audience: researchers in the topic

Comments: [joint talk with the One World Mathematical Game Theory Seminar]

the address and password of the zoom room of the seminar are sent by e-mail on the mailinglist of the seminar one day before each talk

---

One World Optimization seminar

Series comments: Description: Online seminar on optimization and related areas

The address and password of the zoom room of the seminar are sent by e-mail on the mailinglist of the seminar one day before each talk

---