Guardado en:
| Autores principales: | , , , , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2304.01945 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929575299121152 |
|---|---|
| author | Li, Jingqi Chiu, Chih-Yuan Peters, Lasse Palafox, Fernando Karabag, Mustafa Alonso-Mora, Javier Sojoudi, Somayeh Tomlin, Claire Fridovich-Keil, David |
| author_facet | Li, Jingqi Chiu, Chih-Yuan Peters, Lasse Palafox, Fernando Karabag, Mustafa Alonso-Mora, Javier Sojoudi, Somayeh Tomlin, Claire Fridovich-Keil, David |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2304_01945 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Scenario-Game ADMM: A Parallelized Scenario-Based Solver for Stochastic Noncooperative Games Li, Jingqi Chiu, Chih-Yuan Peters, Lasse Palafox, Fernando Karabag, Mustafa Alonso-Mora, Javier Sojoudi, Somayeh Tomlin, Claire Fridovich-Keil, David Systems and Control 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. |
| title | Scenario-Game ADMM: A Parallelized Scenario-Based Solver for Stochastic Noncooperative Games |
| topic | Systems and Control |
| url | https://arxiv.org/abs/2304.01945 |