Approximate Nash Equilibria in Large Nonconvex Aggregative Games

• 成果类型: Article
• 署名作者: Liu, Kang; Oudjane, Nadia; Wan, Cheng
• 署名单位: Institut Polytechnique de Paris; ENSTA Paris; Ecole Polytechnique; Institut Polytechnique de Paris; ENSTA Paris
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2022.1321
• 发表日期: 2023
• 页码: 1791-1809
• 关键词: duality gap; optimization

摘要

This paper shows the existence of O(1/n(gamma))-Nash equilibria in n-player noncooperative sum-aggregative games in which the players' cost functions, depending only on their own action and the average of all players' actions, are lower semicontinuous in the former, whereas gamma-Holder continuous in the latter. Neither the action sets nor the cost functions need to be convex. For an important class of sum-aggregative games, which includes congestion games with gamma equal to one, a gradient-proximal algorithm is used to construct O(1/n)-Nash equilibria with at most O(n(3)) iterations. These results are applied to a numerical example concerning the demand-side management of an electricity system. The asymptotic performance of the algorithm when n tends to infinity is illustrated.