BIG Hype: Best Intervention in Games via Distributed Hypergradient Descent

• 成果类型: Article
• 署名作者: Grontas, Panagiotis D.; Belgioioso, Giuseppe; Cenedese, Carlo; Fochesato, Marta; Lygeros, John; Dorfler, Florian
• 署名单位: Swiss Federal Institutes of Technology Domain; ETH Zurich
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2024.3410890
• 发表日期: 2024
• 页码: 8338-8353
• 关键词: games; Jacobian matrices; CONVERGENCE; STANDARDS; scalability; Numerical models; COSTS; game theory; network analysis and control; optimization algorithms; Stackelberg games

摘要

Hierarchical decision making problems, such as bilevel programs and Stackelberg games, are attracting increasing interest in both the engineering and machine learning communities. Yet, existing solution methods lack either convergence guarantees or computational efficiency, due to the absence of smoothness and convexity. In this work, we bridge this gap by designing a first-order hypergradient-based algorithm for Stackelberg games and mathematically establishing its convergence using tools from nonsmooth analysis. To evaluate the hypergradient, namely, the gradient of the upper-level objectve, we develop an online scheme that simultaneously computes the lower level equilibrium and its Jacobian. Crucially, this scheme exploits and preserves the original hierarchical and distributed structure of the problem, which renders it scalable and privacy-preserving. We numerically verify the computational efficiency and scalability of our algorithm on a large-scale hierarchical demand-response model.