BIG Hype: Best Intervention in Games via Distributed Hypergradient Descent
OPEN ACCESS
Loading...
Author / Producer
Date
2024-12
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
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 objective, 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.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
69 (12)
Pages / Article No.
8338 - 8353
Publisher
IEEE
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Game theory; Optimization algorithms; Network analysis and control; Stackelberg games
Organisational unit
03751 - Lygeros, John / Lygeros, John
09478 - Dörfler, Florian / Dörfler, Florian
02650 - Institut für Automatik / Automatic Control Laboratory
Notes
Funding
180545 - NCCR Automation (phase I) (SNF)