John von Neumann Theory Prize

2023 - Winner(s)

2023 Winner(s)

Citation:

The 2023 INFORMS John von Neumann Theory Prize is awarded to Christos H. Papadimitriou and Mihalis Yannakakis for their fundamental and sustained contributions to computational complexity theory and providing an understanding of the limits of efficient solvability for a wide range of decision and optimization problems central to operations research and the management sciences (OR/MS).

As an example of a major contribution, Papadimitriou and Yannakakis introduced Max-NP and Max-SNP, natural variants of the NP complexity class, comprised of certain optimization problems that can be approximated with bounded error (Papadimitriou & Yannakakis 1988). Within these classes, they showed that several common problems have polynomial-time approximation schemes only if the whole class does. 

Other major contributions include establishing the NP-completeness of the Euclidean traveling salesman problem (Papadimitriou 1977), an early tour de force in the traditional framework, and characterizing the complexity of many other natural problems. Examples include: checking the validity of facets of polytopes (Papadimitriou and Yannakakis 1984); determining whether a problem has a unique optimal solution (Papadimitriou 1984); local search (Johnson, Papadimitriou and Yannakakis 1988); the extension complexity of LP formulations for the matching and traveling salesman problems (Yannakakis 1988), a paper that erected a firewall to scores of would-be P=NP proofs; and computing Nash equilibria. In the online setting, their work on finding online solutions with a bounded competitive ratio (Papadimitriou and Yannakakis 1991, 1993) has been highly influential. Finally, the introduction of the concept of the ā€œprice of anarchyā€ (Koutsoupias & Papadimitriou 1999, Yannakakis 2009) was a catalyst for major developments in algorithmic game theory, substantially reinforcing the links between economics, computer science, and operations research.

Such contributions have addressed modeling and computational issues at the core of multiple areas in OR/MS; they have helped characterize what is possible and inherently impossible, and more broadly, have provided new tools for such characterizations. Their work has resolved fundamental open problems and sparked new and fruitful lines of research, leading to a better understanding of the field of optimization at large.

Purpose of the Award

2023 Committee Chair

John Tsitsiklis
Massachusetts Institute of Technology

Have questions?  Please email: [email protected]

Click here for committee information.

The John von Neumann Theory Prize is awarded annually to a scholar (or scholars in the case of joint work) who has made fundamental, sustained contributions to theory in operations research and the management sciences. The award is given each year at the INFORMS Annual Meeting if there is a suitable recipient. Although the Prize is normally given to a single individual, in the case of accumulated joint work, the recipients can be multiple individuals.

The Prize is awarded for a body of work, typically published over a period of several years. Although recent work should not be excluded, the Prize typically reflects contributions that have stood the test of time. The criteria for the Prize are broad, and include significance, innovation, depth, and scientific excellence.

The award is $5,000, a medallion and a citation.

2024 Submission Deadline: June 1, 2024

The Prize Committee is currently seeking nominations, which should be in the form of a letter (preferably email) addressed to the prize committee chair (below), highlighting the nominee's accomplishments. Although the letter need not contain a detailed account of the nominee's research, it should document the overall nature of his or her contributions and their impact on the profession, with particular emphasis on the prize's criteria. The nominee's curriculum vitae, while not mandatory, would be helpful.

Click here for instructions

About the Award/Namesake

John von Neumann Award Photo

John von Neumann was a brilliant mathematician, synthesizer, and promoter of the stored program concept, whose logical design of the IAS became the prototype of most of its successors - the von Neumann Architecture. von Neumann was invited to visit Princeton University in 1930, and when the Institute for Advanced Studies was founded there in 1933, he was appointed to be one of the original six Professors of Mathematics, a position which he retained for the remainder of his life. Postwar von Neumann concentrated on the development of the Institute for Advanced Studies (IAS) computer and its copies around the world. His work with the Los Alamos group continued and he continued to develop the synergism between computers capabilities and the needs for computational solutions to nuclear problems related to the hydrogen bomb.

Learn more about John von Neumann


Past Awardees

2023 Winner(s)
Christos Papadimitriou, Columbia University Mihalis Yannakakis, Columbia University
2022 Winner(s)
Vijay Vazirani, University of California, Irvine
2021 Winner(s)
Alexander Shapiro
2020 Winner(s)
Adrian S. Lewis, Cornell University
2019 Winner(s)
Dimitris J. Bertsimas , Massachusetts Institute of Technology, Sloan School of Management and Operations Research Center Jong-Shi Pang, University of Southern California
2018 Awardee(s)
Dimitri P. Bertsekas, Massachusetts Institute of Technology
John N. Tsitsiklis, Massachusetts Institute of Technology
2017 Winner(s)
Donald Goldfarb, Columbia University Jorge Nocedal, Northwestern University
2016 Winner(s)
Martin I. Reiman, Columbia University Ruth J. Williams, University of California - San Diego
2015 Winner(s)
VaÅ”ek ChvĆ”tal, Concordia University, Dept. of Computer Science & Software Engineering Jean Bernard Lasserre, CNRS, France
2014 Winner(s)
Nimrod Megiddo, IBM
2013 Winner(s)
Michel L Balinski, C.N.R.S. and Ecole Polytechnique
2012 Winner(s)
George L. Nemhauser, Georgia Institute of Technology, Dept. of Industrial & Systems Engineering Laurence A. Wolsey, Universite Catholique de Louvain, C O R E
2011 Winner(s)
Gerard P. Cornuejols, Carnegie Mellon University, Tepper School of Business
2010 Winner(s)
Peter Glynn, Stanford University SĆøren Asmussen, Aarhus University, Denmark
2009 Winner(s)
Yurii Nesterov, CORE/UCL Yinyu Ye, Stanford University, Department of Management Science & Engineering
2008 Winner(s)
Frank P. Kelly, Centre for Mathematical Science, University of Cambridge
2007 Winner(s)
Arthur F. Veinott, Jr., Stanford University
2006 Winner(s)
Martin Grƶtschel, ZIB
Konrad-Zuse-Zentrum
LĆ”szlĆ³ LovĆ”sz, Eotvos University, Institute of Mathematics Alexander Schrijver, CWI, National Research Institute for Mathematics & Computer Science
2005 Winner(s)
Robert J. Aumann, The Hebrew University of Jerusalem, Center for Rationality
2004 Winner(s)
J. Michael Harrison, Stanford University, Graduate School of Business
2003 Winner(s)
Arkadi Nemirovski, Georgia Institute of Technology, School of ISyE Michael J. Todd, Cornell University
School of Operations Research and Information
2002 Winner(s)
Cyrus Derman, Professor Operations Research, Columbia University Donald L. Iglehart, Stanford University
2001 Winner(s)
Ward Whitt, Columbia University, Industrial Engineering & Operations Research Dept.
2000 Winner(s)
Ellis L. Johnson, School of Industrial & Systems Engineering, Georgia Institute of Technology Manfred W. Padberg, New York University, Stern School of Business
1999 Winner(s)
R. Tyrrell Rockafellar, University of Washington, Dept. of Mathematics
1998 Winner(s)
Fred W. Glover, OptTek Systems, Inc.
1997 Winner(s)
Peter Whittle
1996 Winner(s)
Peter C. Fishburn
1995 Winner(s)
Egon Balas, Carnegie Mellon University, Tepper School of Business
1994 Winner(s)
Lajos Takacs
1993 Winner(s)
Robert Herman, University of Texas-Austin
1992 Winner(s)
Alan J. Hoffman, IBM Philip S. Wolfe, IBM
1991 Winner(s)
Richard E. Barlow, University of California-Berkeley Frank Proschan
1990 Winner(s)
Richard M. Karp, University of California - Berkeley, Dept. of Electrical Engineering & Computer Science
1989 Winner(s)
Harry M. Markowitz , Baruch College
1988 Winner(s)
Herbert A. Simon
1987 Winner(s)
Samuel Karlin , Stanford University
Dept of Mathematics
1986 Winner(s)
Kenneth J. Arrow , Stanford University, Dept. of Economics
1985 Winner(s)
Jack Edmonds, University of Waterloo, Dept. of Combinatorics & Optimization
1984 Winner(s)
Ralph E. Gomory , Alfred P. Sloan Foundation
1983 Winner(s)
Herbert E. Scarf, Yale University
1982 Winner(s)
Abraham Charnes William W. Cooper, University of Texas - Austin, MSIS Department Richard J. Duffin
1981 Winner(s)
Lloyd S. Shapley , University of California - Los Angeles, Dept. of Economics
1980 Winner(s)
David Gale Harold W. Kuhn, Princeton University Albert W. Tucker
1979 Winner(s)
David Blackwell , University of California - Berkeley
1978 Winner(s)
John F. Nash, Princeton University, Mathematics Dept. Carlton E. Lemke
1977 Winner(s)
Felix Pollaczek
1976 Winner(s)
Richard Bellman
1975 Winner(s)
George B. Dantzig, Stanford University