Weighted Stackelberg Algorithms for Road Traffic Optimization

We study the problem faced by an online navigation platform that wishes to improve the total cost experienced by drivers in the road network, i.e., minimize the total travel time of vehicles on the streets. The platform has access to a fixed fraction of the traffic and needs to route it in a manner that improves the overall conditions in the network, both for platform users and non-users. This setting has been studied in the context of designing {\em Stackelberg strategies} for selfish routing games. An additional consideration for a routing platform in this setting is that it should ensure a positive experience for its users. The reasons for this are twofold: (a) the platform has a customer-service provider relationship with its users and (b) the users will opt out of following the platform's recommendations if they are systematically poor and the overall routing optimization effort will fail. This aspect is not explicitly addressed in standard Stackelberg algorithms and, in particular, some of them (e.g., Largest Latency First) move in the opposite direction of assigning user traffic to the most expensive paths so that the (selfish) non-user traffic can utilize the better part of the network. To address this challenge we formulate a weighted version of the Stackelberg routing problem in which the delay experienced by non-users of the platform is discounted by some parameter $\beta < 1$. We study natural algorithms for this problem and provide provable guarantees in the form of constant approximation ratios for various settings. In simulations with real graphs, data-induced delay functions, and realistic demands, we exhibit that such strategies improve the experience of both platform users and independent traffic in the road network and extract the trade-off between providing high quality service to the platform's users and improving the overall total cost.

• Algorithms and Theory

• Networking