Evolutionary Stackelberg Routing for Social Cost Reduction in Traffic Networks

An evolutionary Stackelberg framework for a two-population routing game is proposed, in which a boundedly rational central controller manages a fleet of vehicles sharing the network with selfish drivers. The controller assigns routes to minimize social cost by managing her fleet via the E-Aloof strategy, a low-information, adaptive rule that requires only the observation of the instantaneous traffic distribution and no memory of past states; E-Aloof is an evolutionary extension of the greedy, static Aloof strategy. The drivers of the remaining vehicles behave selfishly and myopically, adapting routes according to the Stackelberg Replicator Dynamic by comparing their travel costs with those of randomly sampled vehicles. The work formulates the problem as a nonatomic routing game on a two-parallel-link network. It establishes the existence of asymptotically stable equilibria under standard assumptions of continuously differentiable, nondecreasing, convex cost functions. The conditions under which centralization improves performance are derived, showing that while Aloof is beneficial when at least half of the vehicles are centralized, E-Aloof requires fewer centralized vehicles depending on the cost functions. For linear costs, conditions are found under which the equilibria coincide with those of a full-information Stackelberg game.