- Tim Roughgarden
(Stanford University) - Applications of Learning Theory in Algorithmic Game Theory.
Algorithmic game theory is a field that uses and extends tools from economics and game theory to reason about fundamental computer science problems. The field is important both for its applications, which span the gamut from network routing to online advertising, and for its remarkably diverse and rich connections to other areas of theoretical computer science, including complexity theory and approximation algorithms.In this talk, we survey two ways in which definitions and tools from learning theory have been crucial to recent advances in algorithmic game theory. First, we outline a theory of robust bounds on the “price of anarchy” — meaning approximation guarantees for game-theoretic equilibria — that apply to all outcome sequences generated by no-regret learners playing a multi-player game. Second, we explain how to use concepts from learning theory to make traditional (Bayesian) optimal auction theory operational, replacing the practically problematic “common prior” assumption with a data-driven approach.
Tim Roughgarden is an Associate Professor of Computer Science and (by courtesy) Management Science and Engineering at Stanford University, where he holds the Chambers Faculty Scholar development chair.
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 Lecturership of the Game Theory Society, a Sloan Fellowship, INFORM’s Optimization Prize for Young Researchers, the Mathematical Programming Society’s Tucker Prize, and the Gödel Prize.
- Daniel Spielman
(Yale University) - Laplacian Matrices of Graphs: Algorithms and Applications.
The Laplacian matrices of graphs arise in many fields including Machine Learning, Computer Vision, Optimization, Computational Science, and of course Network Analysis. We will explain what these matrices are and why they arise in so many applications. We then will survey recent progress on the design algorithms that allow us to solve such systems of linear equations in nearly linear time.
In particular, we will show how fast algorithms for graph sparsification directly lead to fast Laplacian system solvers. As an application, we will explain how Laplacian system solvers can be used to quickly solve linear programs arising from natural graph problems.
Daniel Alan Spielman received his B.A. in Mathematics and Computer Science from Yale in 1992, and his Ph.D in Applied Mathematics from M.I.T. in 1995. He spent a year as a NSF Mathematical Sciences Postdoc in the Computer Science Department at U.C. Berkeley, and then taught in the Applied Mathematics Department at M.I.T. until 2005. Since 2006, he has been a Professor at Yale University. He is presently the Henry Ford II Professor of Computer Science, Mathematics, and Applied Mathematics.
He has received many awards, including the 1995 ACM Doctoral Dissertation Award, the 2002 IEEE Information Theory Paper Award, the 2008 and 2105 Gödel Prizes, the 2009 Fulkerson Prize, the 2010 Nevanlinna Prize, the 2014 Polya Prize, an inaugural Simons Investigator Award, and a MacArthur Fellowship. He is a Fellow of the Association for Computing Machinery and a member of the Connecticut Academy of Science and Engineering. His main research interests include the design and analysis of algorithms, network science, machine learning, digital communications and scientific computing.
- Cedric Villani
(Université de Lyon and Institut Henri Poincaré) - Synthetic theory of Ricci curvature – when information theory, optimization, geometry and gradient flows meet.
Cedric Villani is a Professor of Mathematics at Université de Lyon. He received his PhD on the mathematical theory of the Boltzmann equation from University Paris 6. Since 2009 he is director of the Institut Henri Poincaré in Paris; this 80-year old national institute, dedicated to welcoming visiting researchers, is at the heart of french mathematics.
His main research interests are in kinetic theory (Boltzmann and Vlasov equations and their variants), and optimal transport and its applications, a field in which he wrote the two reference books: Topics in Optimal Transportation (2003); Optimal Transport, old and new (2008).
He received several national and international prizes for his research, in particular the Fields Medal in 2010. Since then, he has served as a spokesperson for the French mathematical community in media and political circles.