An Optimal Distributed Algorithm with Operator Extrapolation for Stochastic Aggregative Games

This work studies Nash equilibrium seeking for a class of stochastic aggregative games, where each player has an expectation-valued objective function depending on its local strategy and the aggregate of all players' strategies. We propose a distributed algorithm with operator extrapolation, in...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2022-05
Main Authors: Wang, Tongyu, Peng, Yi, Chen, Jie
Format: Article
Language:English
Subjects:
Algorithms
Convergence
Extrapolation
Game theory
Games
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This work studies Nash equilibrium seeking for a class of stochastic aggregative games, where each player has an expectation-valued objective function depending on its local strategy and the aggregate of all players' strategies. We propose a distributed algorithm with operator extrapolation, in which each player maintains an estimate of this aggregate by exchanging this information with its neighbors over a time-varying network, and updates its decision through the mirror descent method. An operator extrapolation at the search direction is applied such that the two step historical gradient samples are utilized to accelerate the convergence. Under the strongly monotone assumption on the pseudo-gradient mapping, we prove that the proposed algorithm can achieve the optimal convergence rate of \(\mathcal{O}(1/k)\) for Nash equilibrium seeking of stochastic games. Finally, the algorithm performance is demonstrated via numerical simulations.
ISSN:2331-8422