The Impact of Oligopolistic Competition in Networks

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 i