Hungary - 2022
For fundamental research contributions to combinatorial optimization, approximation algorithms, and algorithmic game theory, and for dedicated mentoring and service to these communities
Éva Tardos is one of the most influential scientists in theoretical computer science. Her impact spans deriving deep theoretical results, shaping new research areas, and influencing a broad range of applications. Her key contributions in combinatorial optimization include the first strongly polynomial-time algorithm for the minimum-cost flow problem (for which she received the Fulkerson prize) and a general framework for fast approximation of packing and covering linear programs. Tardos developed fundamental approximation algorithms, developing new algorithmic techniques for the use of linear programming and rounding in network design problems. Applications include problems in facility location, network routing, and the spread of influence in social networks. Tardos also played a key role in founding the field of algorithmic game theory by developing algorithms in the presence of self-interested agents that are governed by incentives and economic constraints. She received the Gödel prize for her pioneering work using game-theoretic ideas to quantify the performance gaps between centrally managed network traffic and the flow of traffic directed by self-interested agents (selfish routing). She subsequently developed new approaches to analyzing dynamic games, and new algorithms for mechanism design including composable ones.
Tardos is an outstanding educator, mentor, and leader in the community. She has received awards for excellence in teaching and leadership for her work supporting women in computer science. She is the current chair of the Computer Science department at Cornell and previously served as associate dean for diversity and inclusion. She co-authored one of the leading textbooks used in undergraduate computer science, Algorithm Design, and co-edited Algorithmic Game Theory, a significant book at the intersection of economics and computation (EC). She is deeply involved in mentoring, and several of her former students have become leaders in algorithms and EC. She has served as program chair for conferences in theory and EC, editor for more than a dozen journals including recently as editor-in-chief of the Journal of the ACM, and advisory numerous scientific and national boards. The breadth of Tardos' influence is reflected in her election as a Fellow of the ACM, INFORMS, SIAM, AMS, and the Game Theory Society, and her election to the National Academy of Engineering, National Academy of Sciences, Hungarian Academy of Sciences, the American Philosophical Society, and the National Academy of Arts and Science.
USA - 1998
For fundamental contributions in the design and analysis of algorithms, combinatorial optimization, network flows, and approximation algorithms.