Time Heals Unfairness: Efficient Dynamic Routing at an Autonomous Society

With the continuous advances in AI, the vision of fully automated driving is not far away. However, it remains a key challenge to understand what kind of multi-agent systems will these intelligent cars shape, when being deployed on the road. This paper examines a key question of societal importance along this line. That is, will each self-driving car’s intelligent/selfish behavior lead to unfair societal outcomes and, if so, how could we mitigate such unfairness. Specifically, we envision the future with a highly automated traffic network where all cars are automated and scheduled by a central planner. We start by observing that in single-round routing, the objective of social cost minimization may be inherently incompatible with fairness—that is, any truly fair routing has been unfortunately far from social optimum which can be achieved only by “sacrificing” a portion of the population to significantly profit the other. To address this fundamental challenge, we extend the scope of the mode to multi-round repeated routing. We develop two methods to compute the social cost minimizing routing with fairness considerations: (i) an integer program optimization approach, which we show can be approximately solved via continuous relaxation, (ii) travel probability approximation, which can be complicated into a more generalized solution. Numerical experiments show that we are able to achieve socially optimal routing while restoring fairness.