Computer Science

Colloquium Details

Selfish Routing and Sybil-Proof reputations

Abstract

This talk will cover two topics in computer science in which it is important to consider self interested behavior. The first concerns the efficiency losses that arise when users can choose their own routing on a network. In the worst case, the losses due to such nonoptimal routing can be quite large; however, we provide two reasons one might expect them to be small in practice. One relies on the concept of genericity and shows that for "most" sets of data rates, the losses are small, while the other shows that if the network is using congestion control then the losses are also small. The second topic concerns the rigorous analysis of reputation systems (such as google or those for P2P). First we show that most well-knows reputation systems are not robust against sybils and then construct a class of robust "flow-like" reputation systems.

Biography

Eric Friedman is currently an associate professor of Operations Research at Cornell University, where he is in the faculty of Information Science and the field of Computer Science. Previously he was an associate professor at Rutgers University. He received his PhD from U.C. Berkeley in 1993. His current research concerns the applications of tools from game theory to computer science, including reputations on the Internet and in P2P systems, wireless networks and selfish routing. Most recently he has begun working in AI, developing new approaches for combinatorial games.