Probably Approximately Correct Nash Equilibrium Learning

• 成果类型: Article
• 署名作者: Fele, Filiberto; Margellos, Kostas
• 署名单位: University of Oxford
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2020.3030754
• 发表日期: 2021
• 页码: 4238-4245
• 关键词: games; uncertainty; Nash equilibrium; Probabilistic logic; linear programming; Picture archiving and communication systems; sensitivity; Electric vehicles (EVs); Nash equilibria; robust game theory; scenario approach; Variational inequalities

摘要

We consider a multiagent 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 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-which is at the core of scenario-based optimization-can be directly obtained as a byproduct of the proposed methodology. We demonstrate the efficacy of our approach on an electric vehicle charging control problem.