CS Colloquia: Bertrand Competition in Networks

Title: Bertrand Competition in NetworksSpeaker: Prof. Shuchi Chawla (Wisconsin)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.BIO:
Shuchi Chawla is an assistant professor of Computer Science at
University of Wisconsin - Madison. She received her PhD in 2005 from
Carnegie Mellon University and her Bachelor of Technology degree from
the Indian Institute of Technology, Delhi, India in 2000. Her research
interests lie in theoretical computer science, with emphasis towards
approximation algorithms, combinatorial optimization, and game theory.
Shuchi is the recepient of an NSF CAREER award and an IBM Ph.D.
fellowship.

Location: Hughes Aircraft Electrical Engineering Center (EEB) - 248

Audiences: Everyone Is Invited

Contact: CS Colloquia