John von Neumann Theory Prize
Share:
2022 Winner(s)
- Vijay Vazirani, University of California, Irvine
The 2022 INFORMS John von Neumann Theory Prize is awarded to Vijay Virkumar Vazirani for his fundamental and sustained contributions to the design of algorithms, including approximation algorithms, computational complexity theory, and algorithmic game theory, central to operations research and the management sciences.
While a first year Ph.D. student, Vazirani developed what is still the most efficient algorithm for the classical maximum matching problem, with fellow student Silvio Micali. His co-authored seminal 1990 paper proposed an optimal algorithm for the online bipartite matching problem, in which the underlying graph is revealed one vertex at a time and needs to be instantaneously matched without knowledge of future arrivals. Numerous matching markets, including Google’s AdWords, Uber, and Airbnb, share this online decision-making feature, and this algorithm has become a paradigm in this area. More recent joint work introduced a tradeoff-revealing family of linear programs and the notion of bid-scaling – ideas that have had enormous influence within digital advertising markets.
In addition, Vazirani is known for his role in developing approximation algorithms for NP-hard optimization problems, including set covering, survivable network design, multicommodity flow and multicut, k-cuts, facility location, and k-medians, culminating in his now classic book, Approximation Algorithms. He has been a major contributor to the primal-dual approach that is now recognized as the most powerful algorithmic design technique within this area.
Vazirani is one of the founders of algorithmic game theory, focusing on the computability of market equilibria. In a 2012 paper, he introduced the notion of a rational convex program, established that they “behave like” linear programs, and showed that certain market equilibria programs have this property. He and his co-authors also provided complementary pivot algorithms for markets under additively-separable, piecewise-linear concave utilities and markets with production, thereby yielding practical tractability for this class of problems. In other joint work, he gave the first polynomial-time algorithm for a market model, namely the Fisher market with linear utility functions.
Purpose of the Award
2023 Committee Chair
Donald Goldfarb
Columbia University
Have questions? Please email: christy.blevins@informs.org
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.
2023 Submission Deadline: June 1, 2023
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.
About the Award/Namesake
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.
Past Awardees
The Institute for Operations Research and the Management Sciences
5521 Research Park Drive, Suite 200Catonsville, MD 21228 USA
phone 1 443-757-3500
phone 2 800-4INFORMS (800-446-3676)
fax 443-757-3515
email informs@informs.org