Internet systems perform suboptimally because of selfish user behavior; examples include email spam, freeloading, link spam, and packet flooding. How should a multi-user system such as a computer network be designed such that it operates well in the presence of selfish user behavior? The field of mechanism design lays the economic foundations for the design and analysis of protocols, services, and applications in computer networks where users may act selfishly in their own best interest. With varying degrees of clarity, the classical mechanism design literature gives rigorous mathematical tools from which optimal mechanisms can be derived. Unfortunately, except for a few cases, optimal mechanisms are complex, highly dependent on the details of the setting, and impractical. Dr. Hartline addresses each these critiques in detail, and his project includes a well connected research agenda for developing a theory of mechanism design that is relevant to computer systems.
This project will develop a theory for the design of mechanisms that are universal, simple, and practical. Mechanisms for computer systems must be universal -- indeed the success of the Internet is owed in part to the fact that most Internet protocols function under a wide range of workloads. Mechanisms for the Internet must be simple, if they are parameterized by more than a few dimensions, they are too difficult to optimize. Note in contrast that the classical economic theory gives complicated mechanisms that are inextricably dependent on the the setting. Finally, mechanisms for the Internet must be practical; this project addresses the disconnect between theory and practice in the computer science literature on mechanism design.
