ESA 2018: Keynote speakers
26th Annual European Symposium on Algorithms
Claire Mathieu · CNRS, Paris
Stable Matching in Practice
Stable matching methods, based on the algorithm designed by Gale and Shapley, are used around the world in many applications such as college admissions. Several criteria measure the quality of the result: number of students assigned; rank of the college assigned to the applicant in their preference list; robustness; running time; etc.
After reviewing properties of the algorithm in the pure, ideal setting, we present issues arising in practice. The input data is uncertain and evolves with time, so a one-shot algorithm does not suffice. It is not feasible for admission committees to meet continuously, so the process cannot be fully dynamic. To reconcile those competing constraints, a hybrid implementation proceeding partly online on the student side was recently proposed for college admissions in France. The system also incorporates side constraints on joint assignment to schools and to dorms.
Claire Mathieu does research on the design and analysis of algorithms, with a focus on approximation algorithms, particularly approximation schemes for NP-hard problems. A former student of Ecole normale supérieure, she received a PhD in Computer Science in 1988 at Paris-Sud University. She has held research and faculty positions at CNRS, Paris-Sud University, Ecole Polytechnique, Brown University, and Collège de France. She is currently a CNRS research director in Paris, France.
Tim Roughgarden · Stanford
How Computer Science Informs Modern Auction Design
Over the last twenty years, computer science has relied on concepts borrowed from game theory and economics to reason about applications ranging from internet routing to real-time auctions for online advertising. More recently, ideas have increasingly flowed in the opposite direction, with concepts and techniques from computer science beginning to influence economic theory and practice.
In this lecture, Tim Roughgarden will illustrate this point with a detailed case study of the 2016–2017 Federal Communications Commission incentive auction for repurposing wireless spectrum. Computer science techniques, ranging from algorithms for NP-hard problems to nondeterministic communication complexity, have played a critical role both in the design of the reverse auction (with the government procuring existing licenses from television broadcasters) and in the analysis of the forward auction (when the procured licenses sell to the highest bidder).
Tim Roughgarden is a Professor of Computer Science and (by courtesy) Management Science and Engineering at Stanford University. He joined the Stanford faculty in 2004, following a PhD at Cornell and a postdoc at UC Berkeley. His research interests include the many connections between computer science and economics, as well as the design, analysis, applications, and limitations 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 Kalai Prize in Computer Science and Game Theory, the Social Choice and Welfare Prize, the Mathematical Programming Society’s Tucker Prize, and the EATCS-SIGACT Gödel Prize. He was an invited speaker at the 2006 International Congress of Mathematicians, the Shapley Lecturer at the 2008 World Congress of the Game Theory Society, and a Guggenheim Fellow in 2017. His books include Twenty Lectures on Algorithmic Game Theory (2016) and Algorithms Illuminated (2017).