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

**Authors:** Jingqi Li, Chih-Yuan Chiu, Lasse Peters, Fernando Palafox, Mustafa Karabag, Javier Alonso-Mora, Somayeh Sojoudi, Claire Tomlin, David Fridovich-Keil  
**arXiv:** [2304.01945](https://arxiv.org/abs/2304.01945)  
**Date:** 2023-04-04  
**Summary page:** https://www.summarizepaper.com/en/paper/2304.01945v2/

## Key points

- Multi-agent games involve complex decision-making, especially with uncertainty.
- Researchers proposed a new sample-based approximation scheme for stochastic general-sum pure Nash games.
- The proposed method 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.
- High accuracy usually requires a large number of samples resulting in many sampled constraints. To overcome this challenge, they decomposed the approximated game into smaller games with fewer constraints for each sampled scenario.
- They also proposed a decentralized consensus ADMM algorithm to efficiently compute a generalized Nash equilibrium of the approximated game.
- The team proved the convergence of their algorithm and demonstrated its superior performance relative to recent baselines through empirical testing.
- This research presents an innovative approach to solving noncooperative games under uncertainty by leveraging sample-based techniques and scenario optimization literature.
- This could have significant implications for various fields where decision-making under uncertainty is prevalent.

## Summary

In the field of multi-agent games, decision-making can be a complex task, especially when dealing with uncertainty. To address this challenge, a team of researchers comprising Jingqi Li, Chih-Yuan Chiu, Lasse Peters, Fernando Palafox, Mustafa Karabag, Javier Alonso-Mora, Somayeh Sojoudi, Claire Tomlin and David Fridovich-Keil have proposed a new sample-based approximation scheme for stochastic general-sum pure Nash games. In such games, each player has an expected-value objective and a set of chance constraints. The proposed method 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. The researchers characterized the sample complexity of their game-theoretic approximation scheme and observed that high accuracy usually requires a large number of samples resulting in many sampled constraints. To overcome this challenge, they decomposed the approximated game into smaller games with fewer constraints for each sampled scenario. They also proposed a decentralized consensus ADMM algorithm to efficiently compute a generalized Nash equilibrium of the approximated game. The team proved the convergence of their algorithm and demonstrated its superior performance relative to recent baselines through empirical testing. Their work presents an innovative approach to solving noncooperative games under uncertainty by leveraging sample-based techniques and scenario optimization literature. This research could have significant implications for various fields where decision-making under uncertainty is prevalent.