Abstract
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.
Original language | English |
---|---|
Title of host publication | Proceedings of the 62nd IEEE Conference on Decision and Control (CDC 2023) |
Publisher | IEEE |
Pages | 8093-8099 |
Number of pages | 7 |
ISBN (Electronic) | 979-8-3503-0124-3 |
DOIs | |
Publication status | Published - 2023 |
Event | 62nd IEEE Conference on Decision and Control, CDC 2023 - Singapore, Singapore Duration: 13 Dec 2023 → 15 Dec 2023 |
Publication series
Name | Proceedings of the IEEE Conference on Decision and Control |
---|---|
ISSN (Print) | 0743-1546 |
ISSN (Electronic) | 2576-2370 |
Conference
Conference | 62nd IEEE Conference on Decision and Control, CDC 2023 |
---|---|
Country/Territory | Singapore |
City | Singapore |
Period | 13/12/23 → 15/12/23 |
Bibliographical note
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-careOtherwise 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.