Field of Operations Research member Éva Tardos is elected to the National Academy of Sciences

Jacob Gould Schurman  Professor Éva Tardos, a member of the graduate Field of Operations Research,  has been elected to the National Academy of Sciences.  New members are elected by the membership based on outstanding contributions to research.  Members serve as “advisers to the nation on science, engineering, and medicine,” according to the organization.

Tardos, who received her undergraduate “Diploma” and Ph.D. from Eötvös University in Budapest, Hungary, was chair of Cornell’s Department of Computer Science from 2006 to 2010 and senior Associate Dean of the Faculty of Computing and Information Science for the last year.   She joined the faculties of ORIE and Computer Science in 1989, subsequently moving to Computer Science while remaining a member of the Field of Operations Research.     

Her research interests include the study of a diverse array of problems at the intersection of operations research and computer science, such as economic games and optimization on networks.   She is a member of the American Academy of Arts and Sciences and the National Academy of Engineering, an external member of the Hungarian Academy of Sciences, and the recipient of many honors including the Packard Fellowship, the IEEE Technical Achievement Award, and prizes named for Kurt Gödel, George Dantzig, and the late ORIE faculty member Ray Fulkerson. 

A diverse research agenda

In her research, Tardos has contributed extensively to the literature of games on networks, auction mechanisms, social networks, information classification, network design, network routing, scheduling, facility location, and other areas.  Her early work included development of a particularly effective approach for solving the so-called transportation problem, in which quantities of a commodity are to be delivered, at least cost, from a set of supply points to a set of demand points.  

A more detailed discussion of a few of her publications illuminates the flavor of her work, which supplies strong theoretical underpinnings for practical questions in operations research, computer science, and economics.    

• With her student and coauthor Tim Roughgarden, Tardos answered the question of how large a total travel time penalty is paid by network users if individual users are allowed to pick their own routes minimizing their own travel time, versus being assigned routes by a central authority that aims to minimize total travel time.  They show mathematically that, under some simplifying assumptions, the penalty, known as “the price of anarchy,” is no more than 1/3 of the minimum possible total travel time, and under much more general assumptions this price can be offset by a moderate increase in the network capacity. 
• In another paper, Tardos and others examine networks in which routes are neither optimally assigned to users (while preventing them from defecting to routes that reduce their cost but increase the total cost to all users) nor completely chosen by them.   Instead, the network designer suggests routes that are selected so as to be stable, in the sense that no user will be motivated to defect from their suggested route, but are optimal among all such route allocations.   Here again, the authors compute a bound on the total penalty of this approach, “the price of stability,” versus an optimal assignment not constrained to be stable.  
• When users of search engines such as Google examine at their search results, they also see the  results of a process by which advertisers bid for specific search terms and slots on the page.  The process used by allocating such paid ads is an auction form, known as a Generalized Second Price Auction (GSP), is the primary means by which companies such as Google make money on the internet.   Tardos and coauthors study the economic efficiency of GSP auctions and show that “the efficiency of GSP is very robust with respect to the belief and rationality assumptions imposed on the participants.” 
•  The classical Vickrey second price auction is an example of a mechanism designed to produce a desired outcome, such as maximizing revenue or social welfare.   In the world of the Internet, people participate in various simple, independent “local” mechanisms ,  that are often not optimal (such as GSP), run by different principals, such as sellers on eBay or ad-exchange platforms.   Tardos and her student Vasilis Syrgkanis ask “what properties of local mechanisms guarantee global efficiency in a market composed of such mechanisms.”    They found a class of mechanisms that “compose well” in that combining mechanisms in the class yields global efficiency.
• With other colleagues at Cornell,  including OR Field members Jon Kleinberg and Robert Kleinberg, Tardos investigated a problem common to financial networks, disease epidemics, distributed file-sharing, and clandestine organizations:  the possibility that participation imposes risks of contagion (in the clandestine case, revealing of linked identities).   They develop a general model that captures the underlying trade-off between the benefit of forming links within a network and the risk of contagion, and “expose a fundamental sense in which very small amounts of ‘over-linking’ in networks with contagious risk can have strong consequences for the welfare of participants.”

In a lighter vein, Tardos co-authored a whimsical article that appeared in an online academic magazine, comparing "service a la Francaise" to "service a la Russe" in an auction context, as a way of illustrating issues covered in a scientific publication by the authors.      

With Tardos, one other Cornell faculty member was elected to the Academy this year.   Juris Hartmanis, the Walter R. Read Professor Emeritus of Computer Science and is the founding chair of the Department Computer Science.

Tardos and her husband, ORIE's Acheson/Laibe Professor of Business Management and Leadership Studies David Shmoys, have two daughters, Rebecca, who just graduated from college, and Amy, a rising junior at Ithaca High School.