Probably Approximately Correct Nash Equilibrium Learning

DOI10.1109/TAC.2020.3030754MaRDI QIDQ4957715zbMATH OpenOpenAlexWikidataFDO

Authors Filiberto Fele, Kostas Margellos

Publication date 9 September 2021

Published in IEEE Transactions on Automatic Control (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1903.10387

zbMATH Keywords

electric vehiclesNash equilibriarobust game theoryscenario approachvariational inequalities

Mathematics Subject Classification ID

Noncooperative games (91A10) Applications of game theory (91A80) Multi-agent systems (93A16) Application models in control theory (93C95)

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.

Cited in

(10)

• Probabilistic feasibility guarantees for solution sets to uncertain variational inequalities
• On the probabilistic feasibility of solutions in multi-agent optimization problems under uncertainty
• Steady State Learning and Nash Equilibrium
• A priori data-driven robustness guarantees on strategic deviations from generalised Nash equilibria
• Adaptive generalized Nash equilibrium seeking algorithm for nonsmooth aggregative game under dynamic event-triggered mechanism
• Non-convex scenario optimization
• Distributed local-constraint-satisfied strategy for noncooperative games of autonomous general linear players and its application to smart grids
• Finite sample learning of moving targets
• On distributionally robust generalized Nash games defined over the Wasserstein ball
• Distributed online path-length-independent algorithm for noncooperative games over unbalanced digraphs

This page was built for publication: Probably Approximately Correct Nash Equilibrium Learning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4957715)