Traditional treatments of distributed computation typically assume nodes to be either cooperative (i.e., they execute the prescribed algorithm) or Byzantine (i.e., they can act in an arbitrary fashion). However, to properly model the Internet, in which distributed computation and autonomous agents prevail, one must also consider selfish agents that maximize their own utility. To cope with selfish agents, system designers must develop mechanisms in which cooperation is in each agent's self-interest; we call such mechanisms incentive-compatible. This tutorial will first introduce the computer-science audience to the economic theory that forms the basis for the design and analysis of incentive-compatible Internet algorithms. It will then review previous results in this area, including those on interdomain routing and multicast cost sharing. Finally, it will present several promising research directions and pose some specific open problems.
Joan Feigenbaum is a Professor in the Computer Science Department at Yale University. She received a BA in Mathematics from Harvard and a Ph.D. in Computer Science from Stanford. Between finishing her Ph.D. in 1986 and starting at Yale in 2000, she was with AT&T, most recently in the Information Sciences Research Center of the AT&T Shannon Laboratory in Florham Park, NJ. Her research interests are in security and cryptology, computational complexity, digital copyright, and Internet algorithms. Her current and recent professional service activities include Editor-in-Chief of the Journal of Cryptology, Editorial-Board Member for SIAM Journal on Computing, Member of the Computer Science and Telecommunications Board, Program Committee Chair for the 2002 ACM Workshop on Digital Rights Management, and Tutorial Chair for the 2003 ACM Conference on Electronic Commerce. Professor Feigenbaum is a Fellow of the ACM.
Scott Shenker is Group Leader of Networking at the International Computer Science Institute (ICSI) and an adjunct professor in the computer science division at U. C. Berkeley. He received his degrees, in theoretical physics, from Brown University (Sc. B.) and the University of Chicago (Ph. D.). After a postdoctoral year at Cornell's physics department in 1983, he joined Xerox's Palo Alto Research Center. He left PARC in 1999 to head up a newly established Internet research group at ICSI. Dr. Shenker's research over the past 15 years has spanned the range from computer performance modeling and computer networks to game theory and economics. Most of his recent work has focused on the Internet architecture and related issues. He received the ACM Sigcomm award in 2002.