BIG Hype: Best Intervention in Games via Distributed Hypergradient Descent

arXiv2303.01101MaRDI QIDQ6509018FDOQ6509018

Authors: Panagiotis D. Grontas, Giuseppe Belgioioso, Carlo Cenedese, Marta Fochesato, John Lygeros, Florian Dörfler 

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 single-leader multi-follower Stackelberg games and mathematically establishing its convergence using technical 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.

Has companion code repository: https://github.com/p-grontas/big_hype_algorithm

This page was built for publication: BIG Hype: Best Intervention in Games via Distributed Hypergradient Descent

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6509018)