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.

We study the problem of routing plug-in electric and conventional fuel vehicles on a city scale using incentives. In our model, commuters selfishly aim to minimize a local cost that combines travel time and the financial expenses of using city facilities, i.e., parking and service stations. The traffic authority can influence the commuters' routing choice via personalized discounts on parking tickets and on the energy price at service stations. We formalize the problem of optimally designing these monetary incentives to induce traffic decongestion as a large-scale bilevel game, where constraints arise at both levels due to the finite capacities of city facilities and incentives budget. Then, we develop an efficient scalable solution scheme with convergence guarantees based on BIG Hype, a recently-proposed hypergradient-based algorithm for bilevel games. Finally, we validate our approach via numerical simulations over the Anaheim's traffic network, showcasing its advantages in terms of traffic decongestion and scalability.

In modern buildings renewable energy generators and storage devices are spreading, and consequently the role of the users in the power grid is shifting from passive to active. We design a demand response scheme that exploits the prosumers' flexibility to provide ancillary services to the main grid. We propose a hierarchical scheme to coordinate the interactions between the distribution system operator and a community of smart prosumers. The framework inherits characteristics from price-based and incentive-based schemes and it retains the advantages of both. We cast the problem as a Stackelberg game with the prosumers as followers and the distribution system operator as leader. We solve the resulting bilevel optimization program via a KKT reformulation, proving the existence and the convergence to a local Stackelberg equilibrium.