Abstract

This chapter studies the inefficiency of equilibria in noncooperative routing games, in which self-interested players route traffic through a congested network. Our goals are threefold: to introduce the most important models and examples of routing games; to survey optimal bounds on the price of anarchy in these models; and to develop proof techniques that are useful for bounding the inefficiency of equilibria in a range of applications.

Introduction

A majority of the current literature on the inefficiency of equilibria concerns routing games. One reason for this popularity is that routing games shed light on an important practical problem: how to route traffic in a large communication network, such as the Internet, that has no central authority. The routing games studied in this chapter are relevant for networks with “source routing,” in which each end user chooses a full route for its traffic, and also for networks in which traffic is routed in a distributed, congestion-sensitive manner. Section 18.6 contains further details on these applications.

This chapter focuses on two different models of routing games, although the inefficiency of equilibria has been successfully quantified in a range of others (see Section 18.6). The first model, nonatomic selfish routing, is a natural generalization of Pigou's example (Example 17.1) to more complex networks. The modifier “nonatomic” refers to the assumption that there are a very large number of players, each controlling a negligible fraction of the overall traffic.