Abstract:

The Internet is a unique modern artifact given its sheer size and the number of its users. Given its continuing distributed and ad-hoc evolution, there have been growing concerns about the effectiveness of its current routing protocols in finding good routes and ensuring quality of service. Imposing congestion-based and QoS-based prices on traffic has been suggested as a way of combating the ills of this distributed growth and selfish use of resources. Unfortunately, the effectiveness of such approaches relies on the cooperation of the multiple entities implementing them, namely the ISPs or Internet service providers. The goals of the ISPs do not necessarily align with the social objectives of efficiency and quality of service; their primary objective is to maximize their own profit. It is therefore imperative to study the following question: given a large combinatorial market such as the Internet, suppose that the owners of resources selfishly price their product to maximize their own profit, and consumers selfishly purchase resources to maximize their own utility, how does this effect the functioning of the market as a whole?

We study this problem in the context of a simple network pricing game, and analyze the performance of equilibria arising in this game as a function of the degree of competition in the game, the network topology, and the demand structure. Economists have traditionally studied such questions in single-item markets. It is well known, for example, that monopolies cause inefficiency in a market by charging high prices, whereas competition has the effect of driving prices down and operating efficiently. Our work extends the classical Bertrand model of competition from economics to the network setting. For example, we ask: is competition in a network enough to ensure efficient operation? does performance worsen as the number of monopolies grows? does the answer depend in an interesting way on the network topology and/or demand distribution? We provide tight bounds on the performance (efficiency) of the network.

This is joint work with Tim Roughgarden.