Scenario-Game ADMM

Scenario-Game ADMM: A Parallelized Scenario-Based Solver for Stochastic Noncooperative Games

Li, Jingqi (University of California)
Chiu, Chih Yuan (University of California)
Peters, L. (TU Delft Learning & Autonomous Control)
Palafox, Fernando (University of California)
Karabag, Mustafa (The University of Texas at Austin)
Alonso-Mora, J. (TU Delft Learning & Autonomous Control)
Sojoudi, Somayeh (University of California)
Tomlin, Claire (University of California)
Fridovich-Keil, David (The University of Texas at Austin)

2023

Decision-making in multi-player games can be extremely challenging, particularly under uncertainty. In this work, we propose a new sample-based approximation to a class of stochastic, general-sum, pure Nash games, where each player has an expected-value objective and a set of chance constraints. This new approximation scheme inherits the accuracy of objective approximation from the established sample average approximation (SAA) method and enjoys a feasibility guarantee derived from the scenario optimization literature. We characterize the sample complexity of this new game-theoretic approximation scheme, and observe that high accuracy usually requires a large number of samples, which results in a large number of sampled constraints. To accommodate this, we decompose the approximated game into a set of smaller games with few constraints for each sampled scenario, and propose a decentralized, consensus-based ADMM algorithm to efficiently compute a generalized Nash equilibrium (GNE) of the approximated game. We prove the convergence of our algorithm to a GNE and empirically demonstrate superior performance relative to a recent baseline algorithm based on ADMM and interior point method.

http://resolver.tudelft.nl/uuid:fb6b9ce4-9b73-417b-a05c-ac9c91736c5d

https://doi.org/10.1109/CDC49753.2023.10383423

IEEE

2024-07-19

979-8-3503-0124-3

Proceedings of the 62nd IEEE Conference on Decision and Control (CDC 2023)

62nd IEEE Conference on Decision and Control, CDC 2023, 2023-12-13 → 2023-12-15, Singapore, Singapore

Proceedings of the IEEE Conference on Decision and Control, 0743-1546

Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

Institutional Repository

conference paper

© 2023 Jingqi Li, Chih Yuan Chiu, L. Peters, Fernando Palafox, Mustafa Karabag, J. Alonso-Mora, Somayeh Sojoudi, Claire Tomlin, David Fridovich-Keil