Probably Approximately Correct Nash Equilibrium Learning

Abstract

We consider a multi-agent noncooperative game with agents' objective functions being affected by uncertainty. Following a data driven paradigm, we represent uncertainty by means of scenarios and seek a robust Nash equilibrium solution. We treat the Nash equilibrium computation problem within the realm of probably approximately correct (PAC) learning. Building upon recent developments in scenario-based optimization, we accompany the computed Nash equilibrium with a priori and a posteriori probabilistic robustness certificates, providing confidence that the computed equilibrium remains unaffected (in probabilistic terms) when a new uncertainty realization is encountered. For a wide class of games, we also show that the computation of the so called compression set - a key concept in scenario-based optimization - can be directly obtained as a byproduct of the proposed solution methodology. Finally, we illustrate how to overcome differentiability issues, arising due to the introduction of scenarios, and compute a Nash equilibrium solution in a decentralized manner. We demonstrate the efficacy of the proposed approach on an electric vehicle charging control problem.

arXiv commentPreprint submitted to IEEE Transactions on Automatic Control

References in corpus (8)

• Dynamic control of agents playing aggregative games with coupling constraints
• Real and Complex Monotone Communication Games
• Randomized Solutions to Convex Programs with Multiple Chance Constraints
• Nash and Wardrop equilibria in aggregative games with coupling constraints
• Distributed generalized Nash equilibria computation of monotone games via a preconditioned proximal point algorithm
• The scenario approach meets uncertain variational inequalities and game theory
• Robust Worst-Case Analysis of Demand-Side Management in Smart Grids
• A framework for receding-horizon control in infinite-horizon aggregative games

Cited by in corpus (4)

• Tracking-based distributed equilibrium seeking for aggregative games
• Probabilistic feasibility guarantees for solution sets to uncertain variational inequalities
• Distributed equilibrium seeking in aggregative games: linear convergence under singular perturbations lens
• A priori data-driven robustness guarantees on strategic deviations from generalised Nash equilibria