  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.

Computer Science and Game Theory;Machine Learning