Fairness and Optimality in Routing

We study the existence of almost fair and near-optimal solutions to a routing problem as defined in the seminal work of Rosenthal [41]. We focus on the setting where multiple alternative routes are available for each potential request (which corresponds to a potential user of the network). This model captures a collection of diverse applications such as packet routing in communication networks, routing in road networks with multiple alternative routes, and the economics of transportation of goods. Our proposed centralized routes have provable guarantees in terms of both the total cost and fairness concepts such as approximate envy-freeness. We employ and appropriately combine tools from algorithmic game theory and fair division. Our results apply on two distinct models: the splittable case where the request is split among the selected paths (e. g. , routing a fleet of trucks) and the unsplittable case where the request is assigned to one of its designated paths (e. g. , a single user request). Finally, we conduct an empirical analysis to test the performance of our approach against simpler baselines using the real world road network of New York City.

Authors

• Sreenivas Gollapudi Google Research
• Kostas Kollias Google Research
• Alkmini Sgouritsa Athens University of Economics and Business
• Ali Kemal Sinop Google Research

Keywords

• Congestion Games
• Nash equilibrium
• Envy-freeness