Abstract
In the traffic assignment problem, commuters select the shortest available path to travel from a given origin to a given destination. This system has been studied for over 50 years since Wardrop's seminal work (1952). Motivated by freight companies, which need to ship goods across the network, we study a generalization of the traffic assignment problem in which some competitors control a non-negligible fraction of the total flow. This type of games, usually referred to as atomic games, readily applies to situations in which some competitors have market power. Other applications include telecommunication network service providers, intelligent transportation systems, and scheduling with flexible machines.
Our goal is to determine whether these systems can benefit from some form of coordination or regulation. We measure the quality of the outcome of the game when there is no centralized control by computing the worst-case inefficiency of Nash equilibria. The main conclusion is that although self-interested competitors will not achieve a fully efficient solution from the system's point of view, the loss is not too severe. We show how to compute several bounds for the worst-case inefficiency, which depend on the characteristics of cost functions and the market structure in the game. In addition, building upon the work of Catoni and Pallotino (1991), we show examples in which market aggregation (or collusion) can adversely impact the aggregated competitors, even though their market power increases. For example, all Nash equilibria of an atomic network game may be less efficient than the corresponding Wardrop equilibrium. When the market structure is simple enough, we give an optimization formulation of the Nash equilibrium and prove that this counter-intuitive phenomenon does not arise. Finally, we offer a pricing mechanism that elicits more coordination from the players by reducing the worst-case inefficiency of Nash equilibria.