Inducing Equilibria via Incentives: Simultaneous Design-and-Play Ensures Global Convergence
This addresses the incentive design problem in social systems, offering a more efficient solution for regulators or designers, though it is incremental as it builds on existing bilevel optimization methods.
The paper tackles the computational inefficiency of designing economic incentives to regulate self-interested agents in a bilevel optimization framework by proposing a single-loop method where the designer and agents update simultaneously, ensuring global convergence and optimality with a proven convergence rate for a broad class of games.
To regulate a social system comprised of self-interested agents, economic incentives are often required to induce a desirable outcome. This incentive design problem naturally possesses a bilevel structure, in which a designer modifies the rewards of the agents with incentives while anticipating the response of the agents, who play a non-cooperative game that converges to an equilibrium. The existing bilevel optimization algorithms raise a dilemma when applied to this problem: anticipating how incentives affect the agents at equilibrium requires solving the equilibrium problem repeatedly, which is computationally inefficient; bypassing the time-consuming step of equilibrium-finding can reduce the computational cost, but may lead the designer to a sub-optimal solution. To address such a dilemma, we propose a method that tackles the designer's and agents' problems simultaneously in a single loop. Specifically, at each iteration, both the designer and the agents only move one step. Nevertheless, we allow the designer to gradually learn the overall influence of the incentives on the agents, which guarantees optimality after convergence. The convergence rate of the proposed scheme is also established for a broad class of games.