Éva Tardos

Éva Tardos is a Hungarian mathematician and the Jacob Gould Schurman professor of computer science and department chair at Cornell University. Tardos's work includes algorithms and algorithmic game theory, the subarea of theoretical computer science theory of designing systems and algorithms for selfish users. Her research focuses on algorithms and games on networks and simple auctions with a focus on designing algorithms and games that provide provably close-to-optimal results. She is most known for her work on network-flow algorithms, approximation algorithms, and quantifying the efficiency of selfish routing.

Éva Tardos was born October 1, 1957, in Budapest, Hungary, where she also grew up. Éva's younger brother is Hungarian mathematician Gábor Tardos (born July 11, 1964). Tardos graduated (DiplMath) from Eötvös Loránd University in 1981, majoring in mathematics.

After graduation, she worked at the Telecommunication Research Institute in Budapest, where she started working with Andras Frank. Tardos worked on algorithms for combinatorial problems, such as maximum flows and matroids, an area at the interface of mathematics and computer science. This work led to being awarded a Ph.D. in 1984 from Eötvös Loránd University under advisor András Frank.

After her Ph.D., Tardos spent two years working on a Humboldt Postdoctoral Fellowship at the University of Bonn. She spent a year as a postdoc at the Mathematical Science Research Institute at Berkeley before returning to Hungary to teach for a year in the computer science department at Eötvös University. Next, she returned to the US, spending two years at MIT as a visiting assistant professor.

During the years after her Ph.D., Tardos switched focus from mathematics to computer science and married American researcher David Shmoysm, now Laibe/Acheson professor of business management & leadership studies at the School of Operations Research and Information Engineering within the department of computer science, Cornell University. The couple looked for tenure track positions together, and both found work at Cornell University.

Tardos joined the faculty at Cornell University in 1989. Éva Tardos is now a Jacob Gould Schurman professor of computer science and in her second term as chair of the department of computer science, having previously held the position between 2006-2010. Tardos was was interim dean for computing and information sciences between 2012-2013 and more recently held the position of associate dean for diversity & inclusion at Cornell University.

While at Cornell University, Tardos has taught a number of computer science courses:

• Introduction to Algorithms
• Algorithmic Game Theory
• Networks
• Design and Analysis of Algorithms
• Discrete Structures
• Introduction to Theory of Computing
• Approximation and Network Algorithms
• Seminar on Approximation Algorithms
• Mathematical Programming
• Optimization
• Data Structures

Tardos's past PhD students include Tim Roughgarden (2002), a professor of computer science and member of the Data Science Institute at Columbia University and head of research at a16z crypto.

Tardos's work in combinatorial optimization includes introducing a new algorithm for the minimum cost flow problem. The classical maximum flow problem concerns designing transportation of goods in a network, aiming to get the goods from a source to a given destination obeying capacities on the edges. The classical formulation of the problem ignores that transportation has costs and using different routes will affect the cost of the resulting solution. The minimum cost flow problem is the natural extension of the maximum flow problem where the goal is to find a flow with low cost. Maximum flow algorithms have running times that can be bounded by the size of the network. Before Tardos's work, algorithms for the minimum cost version worked directly with the digits of the numbers involved in either the costs or the capacities, and running times grew as the numbers have more significant digits. Tardos's new algorithm is strongly polynomial, with a running time that depends on the size of the network only. The minimum cost flow problem is one of the outstanding open problems in this area if such an algorithm is possible for the class of all linear programs.

Tardos began working on selfish routing while spending the 1999–2000 academic year at Berkeley. At this time, the importance of understanding large networked systems, where each component is optimizing on its own, came to the forefront. This was a significant change of focus for the computer science community. Rather than designing algorithms for a particular task, they need to also think about how to design and manage large networked systems, such as the internet, where each participating component is optimizing itself. The classical Braess’s paradox is an example showing how each part separately optimizing can lead to suboptimal global solutions. Understanding the outcomes as multiple participants interact, each optimizing for themselves, is something game theory has been studying for decades.

From 2015 until 2021, Tardos served as editor-in-chief of the Journal of the ACM (JACM), ACM’s flagship journal covering the most significant work on the principles of computer science. Previously, she was the editor of several other journals, including the SIAM Journal of Computing and Combinatorica.

Tardos co-authored a textbook called Algorithm Design with Jon Kleinberg. The textbook introduces algorithms through real-world problems and teaches students a range of design and analysis techniques for problems that arise in computing applications. Originally published in 2005 by Addison-Wesley, a 2nd edition was released in 2022. In 2007, she co-edited the textbook Algorithmic Game Theory"with Noam Nisan, Vijay Vazirani, and her former Ph.D. student, Tim Roughgarden. The textbook contains chapters written by over forty of the top researchers in the field.

Tardos has authored more than one hundred publications on topics that include approximation algorithm and algorithm design for optimization problems as well as network planning and design. A list of selected publications is shown below:

• Thodoris Lykouris, Karthik Sridharan, and Eva Tardos. 2018. Small-loss bounds for online learning with partial information. Paper presented at Conference on Learning Theory (COLT'18).
• Tim Roughgarden, Vasilis Syrgkanis, and Eva Tardos. The Price of Anarchy in Auctions, Journal of Artificial Intelligence Research (JAIR), Volume 59, pages 59-101, 2017.
• Lykouris, Thodoris, Vasilis Syrgkanis, Eva Tardos. 2016. Learning and Efficiency in Games with Dynamic Population. Paper presented at ACM-SIAM Symposium on Discrete Algorithms (SODA)
• Roughgarden, T., Eva Tardos. 2002. How bad is selfish routing? Journal of the ACM 49 (2): 236-259.

Éva Tardos's awards include the following:

• IEEE John von Neumann Medal
• Fulkerson Prize
• George B. Dantzig Prize
• Van Wijngaarden Award
• Gödel Prize

Éva Tardos receiving the 2011 Van Wijngaarden Award with fellow winner John Butcher.

Tardos has been elected to the National Academy of Engineering, the National Academy of Sciences, and the American Academy of Arts and Sciences and is an external member of the Hungarian Academy of Sciences. Tardos was named the 2022–2023 ACM Athena Lecturer for fundamental research contributions to combinatorial optimization, approximation algorithms, and algorithmic game theory, and for her mentoring and service to these communities.