ColloquiaTalk by Tim Roughgarden on Monday, February 24

[Margery Ishmael]

----------------------------------------------------------------------------

DEPARTMENT OF COMPUTER SCIENCE - TALK

Monday, February 24, 2003 at 2:30 pm, Ryerson 251

----------------------------------------------------------------------------

Speaker: Tim Roughgarden, Cornell University
http://www.cs.cornell.edu/timr/

Title: "Selfish Routing and the Price of Anarchy"

Abstract:
A central and well-studied problem arising in the management of a
large network is that of routing traffic to achieve the best possible
network performance. In large networks, it can be difficult or even
impossible to impose optimal routing strategies on network traffic.
On the other hand, permitting network users to act according to their
own independent and conflicting interests precludes any type of global
optimality, and therefore carries the cost of decreased network
performance. This inefficiency of noncooperative behavior is well
known, and is most (in)famously illustrated in classical game theory
by ``The Prisoner's Dilemma'' and in network routing by the
counterintuitive ``Braess's Paradox''.

In this talk, I will discuss methods for quantifying the worst-possible
loss in network performance arising from such noncooperative behavior
--- the ``price of anarchy''. In general networks, the price of anarchy
can be arbitrarily large. This negative fact motivates the following
two positive results that bound the consequences of noncooperative
behavior:
(1) The inefficiency of selfish routing can always be offset by a
moderate investment in network hardware.
(2) If network performance does not degrade arbitrarily quickly as
network congestion increases, then the price of anarchy is
bounded. Moreover, very simple networks furnish worst-case
examples for selfish routing.

I will also briefly touch on methods for improving the noncooperative
solution, such as network design and edge pricing; en route to
understanding the power of these methods, I will describe the first
generalization of Braess's Paradox to an infinite family of networks.

Portions of this work are joint with Eva Tardos.

*Refreshments will follow the talk in Ryerson 255*

Hosts: Laci Babai & Eric Vigoda
If you need any assistance, please call 773-834-8977


=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Margery Ishmael
Secretary to the Chairman, Department of Computer Science
The University of Chicago
1100 E. 58th Street, Chicago, IL. 60637-1581
tel. 773.834.8977 fax. 773.702.8487
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-