CS 789 THEORY SEMINAR [home]

Speaker:  Eric Friedman     
Affiliation: Computer Science, Cornell University
Date: Monday, February 11, 2002
Title: Selfishness, Learning, and Mechanism Design on the Internet, 
         Part 2: Technical Analysis

Abstract: 

In this paper we consider the foundations of game-theoretic analysis for many problems arising on the Internet. We find that, in general, selfish learning algorithms do not converge to the Nash equilibrium. However, they do converge to the serially unoverwhelmed set, which we define. We then consider the mechanism design problem for the Internet, in which one designs network protocols to achieve good system performance under selfish learning. While such protocols are easy to design if one assumes
convergence to the Nash equilibrium, they are much more difficult to design for the selfish learning case, in which play does not converge to the Nash equilibrium. In fact, we prove that the set of learnable social choice functions (achievable performance levels) is quite restrictive under selfish learning.

joint work with Scott Shenker