John von Neumann Theory Prize

2016 - Winner(s)
2016 Winner(s): Martin I. Reiman, Columbia University ; Ruth J. Williams, University of California - San Diego
Citation:

The award recognizes seminal research contributions that Marty Reiman and Ruth Williams have made, over the past several decades, to the theory and applications of “stochastic networks/systems” and their “heavy traffic approximations.” These profound contributions have been and have further led to breakthroughs in stochastic operations research in general, and queueing theory in particular. Their analysis of complex stochastic networks under conditions of heavy traffic, has not only led to the discovery and rigorous articulations of properties of the networks, and penetrating insights into the operational laws of real-world systems they model, but also led to deep theoretical developments in the study of reflected diffusions.

Starting with his Ph.D. thesis, Marty Reiman has had a lasting impact on the heavy traffic analysis of queueing systems. In it, he identified and characterized the diffusion limit of a generalized Jackson queueing network in heavy traffic. Specifically, this limit is a reflected Brownian motion (RBM) in the non-negative orthant, namely a multi-dimensional Brownian motion restricted to the non-negative orthant by oblique reflection at the orthant’s boundary. In companion and subsequent works, Reiman enunciated two heavy-traffic principles that rank among the most important and elegant contributions of heavy traffic theory: the snapshot principle, which relates waiting- and sojourn-times processes to queue-lengths, and the phenomenon of state-space collapse, that is, dimensionality reduction in the effective descriptions of the evolution of a stochastic system in heavy traffic.

Reiman’s research is characterized by deep intuition and penetrating understanding of the physical and mathematical laws that govern the systems that he studies. These virtues are clearly manifested in the following illustrative examples: the averaging principle for polling systems, jointly with Coffman and Puhalskii; the interpolation approximation, with Simon, that combines their light-traffic and the familiar heavy-traffic viewpoints; the study, motivated by call centers, of operational regimes (efficiency-driven, quality-driven and their balancing QED, namely, quality-and-efficiency driven) in many-server queueing models with abandoning customers (with Garnett and Mandelbaum); asymptotically optimal staffing of many-server queues (with Borst and Mandelbaum), e.g., square-root staffing in the Halfin-Whitt (QED) regime; the analysis in the latter regime, with Puhalskii, of the multiclass queue with phase-type service-times and static-priorities; the constant-order policy in lost-sales inventory systems with long lead times; and, jointly with Wang, his analysis of certainty equivalent control for network revenue management.

In Reiman’s work, one sees real inventiveness combined with strong mathematical and expository skills, supported by a solid command of several distinct application domains. His research has influenced and inspired work by the very best people in stochastic OR, including several previous winners of the von Neumann Theory Prize.

Ruth Williams has also had a deep and lasting impact on the study of heavy traffic analysis. This started with her PhD thesis and further work on RBM in a wedge, establishing semimartingale, local time, excursion and recurrence properties. It continued with her establishing a multidimensional generalization that identified necessary and sufficient conditions for weak existence and uniqueness in law of RBMs in the nonnegative orthant, which provides an alternative to the pathwise theory of Harrison and Reiman; and it culminated in the development of invariance principles (analogous to the Donsker-Varadhan invariance principle for the classical (unreflected) Brownian motion). This enabled the identification and verification of diffusion approximations, for multiclass queueing networks under certain state-space collapse conditions.

The above research provided the foundations for subsequent significant research, by Williams and others. One example is queues operating under a processor-sharing service discipline. Jointly, first with Gromoll and Puha and later with Puha and Stolyar, Williams described the evolution of such systems by a measure-valued process that keeps track of the residual service times of all jobs. Another example is asymptotically optimal control of parallel-server systems in heavy-traffic, first under complete resource pooling (with Bell) and recently under partial pooling (with Pesic); further examples include applications, with Kelly, to the analysis of a controlled motorway in heavy traffic; and, with Kang, Lee and Kelly and later with Gromoll, to bandwidth sharing networks that model congestion of data on the internet. For the latter, Williams established fluid limits and subsequently discovered that networks with proportional fairness admit a product-form (and hence tractable) stationary distribution in heavy traffic.

Williams’ research is characterized by its mathematical depth and elegance. She has greatly influenced researchers in operations research, stochastic processes and mathematics, doing so through survey lectures and articles that are exemplary in clarity and insight. Her expositions have introduced the field to researchers and described challenging open problems and directions, which have spurred further research.

In summary, Reiman and Williams have carried out pioneering research over the past several decades. This has led to fundamental breakthroughs in stochastic operations research in general, and queueing theory in particular, with a focus on stochastic networks and their behavior under heavy-traffic conditions. Their research, in which they have both influenced and built upon each other’s work, has had a lasting theoretical and practical impact that stands the test of time.

Purpose of the Award

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.

Past Awardees

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)
Laurence A. Wolsey, Université Catholique de Louvain George L. Nemhauser, Georgia Institute of Technology, Dept. of Industrial & Systems Engineering
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
Featured Award

Nominations due July 31, 2016

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

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 »

Committee

2016 Committee Chair:

David B. Shmoys
Professor
Cornell University
Ithaca, NY 14853-3801 U.S.A.

email: david.shmoys@cornell.edu

Click here for committee information