A network pricing game for selfish traffic

The success of the Internet is remarkable in light of the decentralized manner in which it is designed and operated. Unlike small scale networks, the Internet is built and controlled by a large number of disparate service providers who are not interested in any global optimization. Instead, providers simply seek to maximize their own profit by charging users for access to their service. Users themselves also behave selfishly, optimizing over price and quality of service. Game theory provides a natural framework for the study of such a situation. However, recent work in this area tends to focus on either the service providers or the network users, but not both. This paper introduces a new model for exploring the interaction of these two elements, in which network managers compete for users via prices and the quality of service provided. We study the extent to which competition between service providers hurts the overall social utility of the system. A preliminary version of this paper appeared in the proceedings of 24th annual ACM SIGACT-SIGOPS symposium on principles of distributed computing, July 17–20, 2005, Las Vegas, Nevada, USA. The work of Ara Hayrapetyan was supported in part by NSF ITR grant CCR-0325453. The work of éva Tardos was supported in part by NSF grant CCR-0311333, ITR grant CCR-0325453, and ONR grant N00014-98-1-0589. The work of Tom Wexler was supported in part by NSF ITR grant CCR-0325453.