An Operator Theoretic Approach to Distributed GNE Computation in Games
View this talk here: https://www.youtube.com/watch?v=98diS-M-BPQ
We consider continuous-kernel games with shared coupled constraints and the problem of how to compute an equilibrium solution, namely a variational generalized Nash equilibrium (GNE). Based on a variational inequality characterization and the KKT conditions, we show that the problem can be reformulated as that of finding zeros of a sum of monotone operators. Based on this, GNE seeking algorithms can be developed via a operator-splitting methods, guaranteed to globally converge with fixed step-sizes under perfect information on the other players. We consider how to distribute such algorithms in partial-information settings, when players can only communicate with their neighbours over an arbitrary undirected graph. To distribute the problem, we augment variables, so that each player has local decision estimates and local copies of Lagrangian multipliers. We then show how the problem can be reframed as one of finding the zeros for a sum of augmented monotone operators, with a special preconditioning matrix. Proper selection of parameters can ensure that these augmented operators have desired monotonicity/cocoercivity properties, thus guaranteeing convergence to a variational GNE.