We first explain how to use concepts from learning theory to make optimal auction theory more operational, replacing the common prior assumption with a data-driven approach. We then expand on this idea, taking a PAC learning approach to the selection of application-specific algorithms. Our work shows that dimension notions from statistical learning theory, historically used to measure the complexity of classes of binary- and real-valued functions, are relevant in a much broader algorithmic context.
Includes joint work with Rishi Gupta and Jamie Morgenstern.
Tim Roughgarden is an Associate Professor of Computer Science and (by courtesy) Management Science and Engineering at Stanford University. He received a BS in Applied Mathematics from Stanford in 1997, and a PhD in Computer Science from Cornell in 2002. His research interests include the many connections between computer science and economics, as well as the design, analysis, and applications of algorithms. For his research, he has been awarded the ACM Grace Murray Hopper Award, the Presidential Early Career Award for Scientists and Engineers (PECASE), the Shapley Lectureship of the Game Theory Society, the Social Choice and Welfare Prize, INFORM’s Optimization Prize for Young Researchers, the Mathematical Programming Society’s Tucker Prize, and the EATCS-SIGACT Gödel Prize.
Faculty Host: Nina Balcan