BIG Hype: Best Intervention in Games via Distributed Hypergradient Descent

作     者：Grontas, Panagiotis D. Belgioioso, Giuseppe Cenedese, Carlo Fochesato, Marta Lygeros, John Dorfler, Florian 

作者机构：Swiss Fed Inst Technol Dept Elect Engn & Informat Technol Automat Control Lab CH-8092 Zurich Switzerland 

出 版 物：《IEEE TRANSACTIONS ON AUTOMATIC CONTROL》 (IEEE Trans Autom Control)

年 卷 期：2024年第69卷第12期

页      面：8338-8353页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0811[工学-控制科学与工程] 

基　　金：NCCR Automation, National Centre of Competence in Research Swiss National Science Foundation Onassis Foundation [F ZQ 019-1/2020-2021] 

主　　题：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.