In this paper, we develop an approximation scheme for solving bilevel programs with equilibrium constraints, which are generally difficult to solve. Among other things, calculating the first-order derivative in such a problem requires differentiation across the hierarchy, which is computationally intensive, if not prohibitive. To bypass the hierarchy, we propose to bound such bilevel programs, equivalent to multiple-followers Stackelberg games, with two new hierarchy-free problems: a $T$-step Cournot game and a $T$-step monopoly model. Since they are standard equilibrium or optimization problems, both can be efficiently solved via first-order methods. Importantly, we show that the bounds provided by these problems — the upper bound by the $T$-step Cournot game and the lower bound by the $T$-step monopoly model — can be made arbitrarily tight by increasing the step parameter $T$ for a wide range of problems. We prove that a small $T$ usually suffices under appropriate conditions to reach an approximation acceptable for most practical purposes. Eventually, the analytical insights are highlighted through numerical examples.

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 payoffs 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.

In the urban traffic research field, taxi detour behavior analysis can be regarded as one of the most crucial and challenging topics accounting for real-world routing network dynamics with complicated external inducement such as “avoiding congestion sections”, “unfamiliarity with road maps” or just “earning more fee under a longer travel path”. We carried out an interdisciplinary research framework to build a more holistic and profound view of the spatio-temporal distribution of the taxi detour behavior at directional road segment (DRS) level. First, a map matching based detour clustering method was proposed to deal with one week of taxi GPS tracing (divided into 3.4 million occupied trips). Then we employed an established multi-layer road index system in Shenzhen, China, to illustrate the spatio-temporal distribution variation of taxi detour features and statistics. Furthermore, three categories of DRS factors related to road structural attributes, traffic dynamics and point-of-interests (POIs) were defined to fit a selected-sample-based binary logit model. Some remarkable findings include: (i) in Shenzhen on average, 23.5 percent of taxi trips made a detour larger than 2.1 kilometers, which could be astonishingly high considering that only a very few trips yielded formal complaints for fraudulent detouring; (ii) both the level of detour intensity and ratio are affected by road features and dynamics in different spatio-temporal interaction patterns.

In a social system, the self-interest of agents can be detrimental to the collective good, sometimes leading to social dilemmas. To resolve such a conflict, a central designer may intervene by either redesigning the system or incentivizing the agents to change their behaviors. To be effective, the designer must anticipate how the agents react to the intervention, which is dictated by their often unknown payoff functions. Therefore, learning about the agents is a prerequisite for intervention. In this paper, we provide a unified framework for learning and intervention in games. We cast the equilibria of games as individual layers and integrate them into an end-to-end optimization framework. To enable the backward propagation through the equilibria of games, we propose two approaches, respectively based on explicit and implicit differentiation. Specifically, we cast the equilibria as the solutions to variational inequalities (VIs). The explicit approach unrolls the projection method for solving VIs, while the implicit approach exploits the sensitivity of the solutions to VIs. At the core of both approaches is the differentiation through a projection operator. Moreover, we establish the correctness of both approaches and identify the conditions under which one approach is more desirable than the other. The analytical results are validated using several real-world problems.