Roughgarden, Tim

views updated

Roughgarden, Tim

PERSONAL:

Education: Cornell University, Ph.D., 2002.

ADDRESSES:

Office—Stanford University, Computer Science Department, 462 Gates Bldg., 353 Serra Mall, Stanford, CA 94305. E-mail—[email protected].

CAREER:

Stanford University, Stanford, CA, assistant professor of computer science; has also worked as a DJ on radio station KZSU.

AWARDS, HONORS:

Stanford Firestone Award for Outstanding Undergraduate Thesis, 1997; Cornell University Fellow, 1998-2002; National Science Foundation Graduate Fellow, 1998-2002; Danny Lewin Best Student Paper Award, 2002; Tucker Prize, Mathematical Programming Society, 2003; Optimization Prize for Young Researchers, INFORM, 2003; National Science Foundation Postdoctoral Fellow, 2003-04; National Science Foundation CAREER Award, 2005; Alfred P. Sloan Fellow, 2006; ONR Young Investigator Award, 2007.

WRITINGS:

Selfish Routing and the Price of Anarchy, MIT Press (Cambridge, MA), 2005.

SIDELIGHTS:

Computer scientist Tim Roughgarden conducts research in areas related to game theory, algorithms, and network and combinatorial optimization. He is particularly interested in the application of game theory concepts to networking, and in the areas where game theory and combinatorial optimization combine and intersect. In his Selfish Routing and the Price of Anarchy, Roughgarden offers a technical examination of selfish routing, a concept that has implications not only in the real world of travel and moving people and objects from place to place, but also on the electronic traffic found online and within the complex pathways of computer and communication networks. "‘Selfish routing’ is the process of choosing a path based strictly on one's own interests, without regard for how that choice may affect anyone else; ‘the price of anarchy’ is the penalty that may have to be paid for this oblivious individualism," commented reviewer Brian Hayes in the American Scientist. Roughgarden applies detailed mathematics and theoretical computer science to the study of selfish routing.

In his review, Hayes offers a conceptualization of the selfish routing problem couched in terms of a commute from one's workplace to home. Two routes, one along Main Street and the other along the freeway, offer commuters a choice. Main Street is not crowded, but stop lights and other distractions mean the trip will take an hour. The freeway provides a higher speed limit and, if traffic is light, the prospect of a half-hour commute. Heavy traffic on the freeway, however, means that the commute will take an hour as well. Travel on the freeway appears to be the best option, since it could result in a shorter trip and, at worst, will take as long as the trip home via Main Street. In the selfish routing model, everyone will apply this reasoning and choose to take the freeway. The freeway may have had the potential to offer a shorter trip, but the reasoning behind selfish routing ensures that it will lose that potential and become a congested route. Meanwhile, Main Street remains deserted and the better choice in this travel scenario. "The problems and paradoxes of selfish routing have been known for decades; Roughgarden's contribution is to work out careful, quantitative estimates of just how much we may have to pay for the privilege of choosing our routes without regard for the commonweal," Hayes observed. In his book, Roughgarden looks for solutions to these problems, considering various paradoxes that arise through attempts to ease the congested routing, seeking practical results that can apply to both transportation and networking, and looking at solutions through the behavior of simple, single agents acting collectively.