Robert Kleinberg Department of Computer Science, Cornell University Computing and Incentives Friday, February 17 ABSTRACT Fascinating challenges arise when designing platforms for Internet advertising, cloud computing, or any other service that has a multitude of users with potentially conflicting interests. In particular, the system designer must account for the fact that knowing the users' interests is vital to providing effective service, yet self-interested users may misrepresent their preferences if it benefits them to do so. This conflict creates additional "incentive constraints" that must be satisfied by the algorithms in such systems. Do these constraints make algorithm design fundamentally harder? The theory of algorithmic mechanism design addresses this question, borrowing tools from economic theory and incorporating them into computer science. An ideal solution to incentive problems in computer science would be a generic procedures to convert any algorithm into an incentive-compatible mechanism with little or no computational overhead. In this talk I will identify two broad settings in which such generic procedures exist. A recurring theme in this work is the power of randomization and indirect representation: rather than incorporating user's reported preferences directly into an algorithm, the information is used to select a random "surrogate" who participates in the algorithm on the user's behalf. BIOGRAPHY Robert Kleinberg is an Assistant Professor of Computer Science at Cornell University. His research studies the design and analysis of algorithms, and their applications to electronic commerce, networking, information retrieval, and other areas. Prior to receiving his doctorate from MIT in 2005, Kleinberg spent three years at Akamai Technologies, where he assisted in designing the world's largest Internet Content Delivery Network. He is the recipient of a Microsoft Research New Faculty Fellowship, an Alfred P. Sloan Foundation Fellowship, and an NSF CAREER Award.