Lanchester prize to Ashlagi, Kanoria, Leshno, Braverman and Shi (post 2 of 2)

 INFORMS has now announced the details of the Frederick W. Lanchester Prize, which went to two teams, one of which worked on matching and market design.

Here is the matching team, with a little more detail than in my previous post*, about the papers that were recognized by the award.

2024 Winner(s)

• Itai Ashlagi , Stanford University
• Mark Braverman, Princeton University
• Yash Kanoria, Columbia University
• Jacob Leshno, University of Chicago
• Peng Shi, USC Marshall School of Business
  

Winning material: Collection of Papers: “Unbalanced random matching markets: The stark effect of competition” and “Clearing matching markets efficiently: informative signals and match recommendations”

 ############

Here's the prize citation (sent to me by Sasa Pekec, the chair of the prize committee):

"The 2024 Lanchester Prize is awarded to Itai Ashlagi, Mark Braverman, Yash Kanoria, Jacob Leshno, and Peng Shi for their papers “Unbalanced random matching markets: The stark effect of competition” and “Clearing matching markets efficiently: Informative signals and match recommendations”.

These papers have advanced the field of market design by providing fundamental insights into the performance of two-sided matching markets. By introducing a novel theoretical approach, they resolve a long-standing empirical puzzle: why the set of stable matchings is small in many practically important matching markets. Moreover, by creatively integrating match recommendations and signaling strategies, they demonstrate how to reduce congestion in these markets. These contributions have profoundly impacted both methodological work and practical applications focused on the conduct and organization of centralized and decentralized markets."

The other members of the prize committee were Francis de Véricourt, Wedad Elmaghraby, Fatma Kilinç-Karzan, Azarakhsh Malekian, and Mengdi Wang

#########

Itai shared with me his brief remarks upon accepting the award on behalf of the team at the recent Seattle meeting:

 

"This is a real honor and it is very special to share the prize with my wonderful coauthors Mark Braverman, Yash Kanoria, Jacob Leshno and Peng Shi who could not attend this event today.  It is a great honor and humbling to share this award with  Anatoli Juditsky and Arkadi Nemirovski as well as the distinguished past recipients of the prize. 34 years ago, Alvin Roth and Marilda Sotomayor were awarded the prize for their remarkable and beautiful book on two-sided matching. The last two decades, matching in two-sided markets has been and still is a very active area in Operations Research and economics, with many successful applications and a rich theory. We are grateful to be able to contribute to this area. Thanks to Sasa and the committee. It is a real honor being part of this community."

 ###########

*Earlier: Wednesday, October 23, 2024 Lanchester Prize (Post 1 of 2)

Lanchester Prize (Post 1 of 2)

 The 2024 INFORMS meetings in Seattle this weekend was the occasion of a number of awards, including the Lanchester Prize, the big publication award in operations research and management science.  Congratulations to the two winning publication teams.

One of the teams will be familiar to the readers of this blog: Itai Ashlagi, Yash Kanoria, Jacob Leshno, Mark Braverman and Peng Shi.  They received the award for a series of papers on matching, about which I'll blog in a subsequent post.

Frederick W. Lanchester Prize

The Lanchester Prize is awarded for the best contribution to operations research and the management sciences published in English in the past five years. 

Learn more about the Lanchester Prize and how to be nominated on the INFORMS website.

WINNING TEAM ONE

Anatoli Juditsky

Université Grenoble-Alpes

Arkadi Nemirovski

Georgia Tech

WINNING TEAM TWO

Itai Ashlagi

Stanford University

Yash Kanoria

Columbia University

Jacob Leshno

Chicago University

Mark Braverman

Princeton University

Peng Shi

University of Southern California

Honorable Mention

Guillermo Gallego

The Chinese University of Hong Kong, Shenzhen

Huseyin Topaloglu

Cornell University

 

 

Call for papers: special issue on Market Design at Mathematics of Operations Research

 Paul Milgrom and Martin Bichler write:

We are excited to announce that, as an initiative arising from discussions during the fall program, the journal Mathematics of Operations Research will be dedicating a special issue on market design (deadline: Sep 30, 2024). This special issue is co-organized by the INFORMS Section on Auctions and Market Design and aims to showcase cutting-edge research in the field, reflecting the depth and diversity of thought that our program sought to cultivate.

We are seeking contributions that not only push the boundaries of our current understanding but also highlight practical implications and potential applications of market design principles. We believe that your research and insights could greatly enrich this special issue, and we warmly invite you to submit your papers for consideration.

We are looking forward to submissions from program participants and to the opportunity to highlight the exceptional work emerging from our community.

My Morse Lecture at INFORMS 2022, tomorrow

 Tomorrow, Wednesday October19, from 8-9am Eastern time, I'll be giving the Morse Lecture at the INFORMS 2022 annual meeting in Indianapolis

Market Design: The Dialog Between Simple Abstract Models and Practical Implementation

I’ll review some of the elegantly simple models that underlie the initial designs for matching processes like the medical residency Match, school choice and kidney exchange, and the modifications, complications and  computations that were needed to get new designs adopted, implemented and maintained over the years.

You can read about the occasion of this lecture, my Philip McCord Morse Lectureship Award here.

Stability in Matching Markets with Complex Constraints by H. Nguyen, T. Nguyen, and A. Teytelboym

 Here's a paper motivated in part by the issues that arise in matching refugee families to localities in which to settle (once they have been granted asylum in a particular country).  It's also a good example of the way that operations research methods are playing an increasing role in market design.

Hai Nguyen, Thành Nguyen, Alexander Teytelboym (2021) Stability in Matching Markets with Complex Constraints. Management Science 67(12):7438-7454. https://doi.org/10.1287/mnsc.2020.3869

Abstract. "We develop a model of many-to-one matching markets in which agents with multiunit demand aim to maximize a cardinal linear objective subject to multidimensional knapsack constraints. The choice functions of agents with multiunit demand are therefore not substitutable. As a result, pairwise stable matchings may not exist and even when they do, may be highly inefficient. We provide an algorithm that finds a group-stable matching that approximately satisfies all the multidimensional knapsack constraints. The novel ingredient in our algorithm is a combination of matching with contracts and Scarf’s Lemma. We show that the degree of the constraint violation under our algorithm is proportional to the sparsity of the constraint matrix. The algorithm, therefore, provides practical constraint violation bounds for applications in contexts, such as refugee resettlement, day care allocation, and college admissions with diversity requirements. Simulations using refugee resettlement data show that our approach produces outcomes that are not only more stable, but also more efficient than the outcomes of the Deferred Acceptance algorithm. Moreover, simulations suggest that in practice, constraint violations under our algorithm would be even smaller than the theoretical bounds."

"Around 50,000 refugees are resettled to the United States every year. Nine American resettlement agencies coordinate networks of dozens of local communities (which we refer to as localities) that support refugees during their first few years in the United States. Localities are allowed to admit different numbers of refugees and offer different services (e.g., language support, support for large families, support for single parents, etc.) that may or may not match the needs of the refugees (Ahani et al. 2021, Delacrétaz et al. 2019). In order to secure government approval to conduct resettlement, resettlement agencies must aim to maximize the number of refugees who are employed within 90 days of arrival. Some resettlement agencies have begun using integer optimization and machine learning in order to improve refugee outcomes (Bansak et al. 2018, Ahani et al. 2021); however, as far as we know, refugees’preferences over localities are presently not collected anywhere in the world.

...

Our algorithm is a novel combination of Scarf’s Lemma and a rounding procedure. We build on the approach of Nguyen and Vohra (2018); however, we make a number of substantial extensions and modifications. The novelty of our approach is the way we apply Scarf’s Lemma to capture group stability. To use Scarf’s Lemma for stable matching problems, one needs to create a constraint matrix Q, where each column corresponds to a possible blocking coalition. Hitherto, two methods to construct such a matrix have been proposed: first, with columns corresponding to all possible blocking coalitions (Scarf 1967); second, with columns corresponding to small blocking coalitions (a hospital and a doctor or a doctor couple and two hospitals) (see Nguyen and Vohra 2018). Although the method of Nguyen and Vohra only obtains matchings that are immune to deviations by small coalitions, Scarf’s method can, in principle, capture group stability. However, the disadvantage of Scarf’s method is that the resulting constraint matrix is not sparse, which prevents us from guaranteeing small error bounds in the rounding procedure.

"Our main structural contribution is a new way of combining ideas from matching with contracts with Scarf’s method in order to create an appropriate constraint matrix. A contract specifies both agents in the match as well as a “price” for one of the dimensions of the knapsack constraints. Our method allows us to get the best of both methods: the sparsity of our constraint matrix does not change, but the prices specified in the contracts still allow us to capture group stability via pairwise stability."

***********

Earlier:

Sunday, October 19, 2014

Near Feasible Stable Matchings with Complementarities, by Nguyen and Vohra

Tuesday, November 17, 2015

Herb Scarf, RIP

Thursday, September 3, 2015

Migrants aren't widgets: refugee resettlement is a matching problem

Morse lecture at INFORMS next year: market design and the study of operations

 In 1974, the year I received my Ph.D. from Stanford's (then) Department of Operations Research, it was unclear in what discipline game theory would best thrive.   As disciplinary boundaries shifted, I found that I was an economist.  But I've kept open my professional ties to OR, and indeed I think of market design as the engineering part of game theory, and very concerned with the operational detail of markets and marketplaces. So I was glad to accept an offer to compose a lecture on this for an OR audience, since market design is now a multi-disciplinary field that draws many students of operations.

Here's an announcement that includes the following:

Philip McCord Morse Lectureship Award

The Lectureship is awarded in honor of Philip McCord Morse in recognition of his pioneer contribution to the field of operations research and the management sciences. The award is given in odd-numbered years at the Annual Meeting if there is a suitable recipient. The term of the lectureship is two years. The award is $2,000, a certificate, a travel fund of $5,000, a copy of Morse's autobiography, In at the Beginnings: A Physicist's Life, and a copy of Morse and Kimball's Methods of Operations Research. Learn more about the Philip McCord Morse Lectureship Award and how to be nominated on the INFORMS website.

This year, the lectureship is awarded to:

Alvin E. Roth, Stanford University

Who exemplifies the true spirit of Professor Morse and who, like Morse, has been an outstanding spokesperson for the operations research profession in operations research tools and ideas in designing efficient markets for a range of applications. This award is given by the Institute for Operations Research and the Management Sciences in honor of Philip McCord Morse, in recognition of Professor Morse's pioneering contributions to the field of operations research and of his devoted service to the field's professional societies.

***********

See also

Tuesday, January 17, 2017

Market Design and Operations Research: an interview by the journal Mathematics of Operations Research

Informs Auctions and Market Design (AMD) Online Seminar Series

I recently gave a talk on kidney exchange, to help launch the Informs Auctions and Market Design (AMD) Online Seminar Series.  If I've done it right, the video below should begin at minute 6, skipping the first 6 minutes of silence when Zoom was started but the talk had not.

 

Auctions and Market Design Friday Seminar Series, organized by INFORMS (starting Oct 2)

 The auctions and market design section of INFORMS (the Operations Research and Management Science organization) is initiating a new seminar series,  every other week on Fridays, starting Oct 2.  I'll start the series off with a talk on contemporary kidney exchange, and there are talks scheduled through December, see below.

Auctions and Market Design Online Seminar Series

About the Seminar

The aim of this interdisciplinary seminar is to discuss pioneering and impactful work in the broad area of market design. Theoretical, computational, and experimental work as well as field studies will be featured. A wide range of applications, ranging from online advertising and labor markets to networks and platforms, will be presented. The seminar features research talks and expository talks to highlight trends in the field.

Organization

The seminar is organized by Ozan Candogan (Chicago Booth), Vahideh Manshadi (Yale), and Fanyin Zheng (Columbia).

The seminar will be bi-weekly on Fridays at 1-2 pm ET (10-11 am PT).

Email List

If this seminar interests you and you would like to be notified of upcoming speakers, you can join our email list.

Schedule

October 02 - Alvin Roth (Stanford University)

Title: Kidney Exchange: an Operations Perspective

October 16 - John Birge (University of Chicago)

Title: Increasing Efficiency in Electricity Market Auctions

October 30 - Jon Kleinberg (Cornell University)

November 13 - Winners of the Michael H. Rothkopf Junior Researcher Paper Prize

December 04 - Asuman Ozdaglar (MIT)

December 18 - Matthew Jackson (Stanford University)

Kidney Exchange: an Operations Perspective by Ashlagi and Roth

Here's a survey that puts some emphasis on the many changes in the design of kidney exchange operations and processes that have moved it from its small beginnings to its current situation facilitating annual transplants in the thousands, and might help to scale it up further, since the supply of transplants is still far short of the need. 

Kidney Exchange: an Operations Perspective
Itai Ashlagi and Alvin E. Roth
May 2020

Abstract: Many patients in need of a kidney transplant have a willing but incompatible living donor. Kidney exchange programs arrange exchanges among such incompatible patient-donor pairs, in cycles and chains of exchange, so each patient receives a compatible kidney. Kidney exchange has become a standard form of transplantation in the United States and a few other countries, in large part because of continued attention to the operational details that arose as obstacles were overcome and new obstacles became relevant. We review some of the key operational issues in the design of successful kidney exchange programs. Kidney exchange has yet to reach its full potential, and the paper further describes some open questions that we hope will continue to attract attention from researchers interested in the operational aspects of dynamic exchange.


Here's the concluding paragraph:

"Looking back, kidney exchange has accomplished a lot, but not nearly enough. The number of people waiting for a kidney transplant is growing, despite the growth of exchange. But there is room for kidney exchange to continue to grow and to increase the availability of transplants further, by designing international kidney exchanges, by starting chains with deceased donor kidneys, and by introducing other market design innovations that have yet to be explored or even conceived."

************

Now online in Management Science, Ahead of Print

Kidney Exchange: An Operations Perspective

Itai Ashlagi , Alvin E. Roth 

Published Online: 

2 Jul 2021 https://doi.org/10.1287/mnsc.2020.3954

Family legacies in Operations Research (and related fields)

ORMS Today has an article on multi-generations of operations researchers, broadly defined.

Like father, like son and daughter
All in the family tree: INFORMS rich with O.R. legacies

I know only some of the folks they interviewed: here's the full list.

The Wikums
Erick and his son Anders

The Weintraubs
Andres and his son Gabriel 

The Weins
Lawrence, his son Alex and daughter Nicole

The Roths
Al and his son Aaron

The Elmaghrabys
Wedad and her father Salah

The Bixbys
Robert and his daughter Ann

The Armacosts
Robert and his son Andrew

The Camms
Jeff and his daughter Allison

The Hilliers
Fred and his son Mark (and almost his granddaughter Sarah)

Special issue of NRL in honor of Uri Rothblum, February 2019

Occasionally an Operations journal can bring memories flooding back: here's a special issue in honor of my old friend Uri Rothblum, who passed away in 2012. (We met in 1971, when we entered the Ph.D. program in Operations Research at Stanford.)

 The Journal Naval Research Logistics 
Volume 66, Issue 1, Special Issue:Uriel Rothblum, Pages: 1-102, February 2019

Here is the introduction, and the first paper, coauthored by Uri...

Introduction

• Michael Katehakis

• Pages: 3
 
• First Published: 26 December 2018

• Full text
 
• PDF
 
• Request permissions

RESEARCH ARTICLES

Free Access

Constant risk aversion in stochastic contests with exponential completion times

• Pelin G. Canbolat
 
• Uriel G. Rothblum

• Pages: 4-14
 
• First Published: 24 January 2017

• Abstract
 
• Full text
 
• PDF
 
• References
 
• Request permissions
• ***************************

The previous issue was in honor of Pete Veinott, Uri's Ph.D. advisor:
Volume 65, Issue 8 Special Issue:Pete Veinott 

************

Here are other posts of mine remembering Uri.

The journal used to be called the Naval Research Logistics Quarterly, and I published three papers there from 1977 to 1982.

Afshin Nikzad defends (x2)

Defense 2, (Offense 0).
Afshin Nikzad defended twice in eight days, to qualify for two Ph.D.s, one from Management Science and Engineering, in Operations Research, and one from Economics (in economics:).  Here are photos from his Economics defense.

Afshin Nikzad and some of his admirers: Philip Strack, Fuhito Kojima, Daniela Saban, Niloufar Salehi, Al Roth, Afshin, Paul Milgrom, and Itai Ashlagi

The papers he presented for his Economics defense were
Thickness and Competition in Ride-sharing Markets 
and 
Financing Transplant Costs of the Poor: A Dynamic Model of Global Kidney Exchange 

The papers he presented for his MS&E defense were 
Approximate Random Allocation Mechanisms 
and
What matters in tie-breaking rules? How competition guides design 


Welcome to the club(s), Afshin

Auctions and Market Design Section of INFORMS

Martin Bichler writes:

We are excited about the successful formation of the Auctions and Market Design Section of INFORMS! Please visit and bookmark the INFORMS Auctions and Market Design homepage.

Events organized by the new INFORMS Section in 2018 include:

Cluster on Auctions and Market Design at the INFORMS Annual Meeting Nov. 4-7, 2018 in Phoenix, Arizona

As in the last few years, the cluster (previously the Auctions Cluster) will be chaired by Bob Day. Please email Bob at robert.day@uconn.edu if you are interested in being a session chair or want to have him find a spot for you in a session.  Please try to respond in the next two weeks (by March 4) to assure your session. Later requests by individual authors will be considered, but the sooner the better to lock in a slot.

Workshop on Mathematical Optimization in Market Design
June 18-19, 2018, Gates Hall, Cornell University, Ithaca, NY (co-located with ACM EC 2018)

We are pleased to announce a new focused workshop co-located with and immediately preceding ACM EC 2018. The workshop will have invited speakers from academia and industry including Itai Ashlagi (Stanford), Peter Cramton (Cologne), Scott Kominers (Harvard), Sébastien Lahaie (Google), Sasa Pekec (Duke), Tuomas Sandholm (CMU), and many more.

The final program and registration will be online end of March at the event website. Please direct questions to Martin Bichler (bichler@in.tum.de).

Section Officers:

• President: Robert Day, School of Business, University of Connecticut
• Vice-President: Martin Bichler, Department of Computer Science, Technical University of Munich
• Secretary: Ben Lubin, School of Business, Boston University
• Treasurer: Thayer Morill, Department of Economics, NC State University

Advisory Board

• Itai Ashlagi, Management Science and Engineering, Stanford University
• Karla Hoffman, School of Engineering, George Mason University
• Paul Milgrom, Department of Economics, Stanford University
• Sasha Pekec, School of Business, Duke University
• Al Roth, Department of Economics, Stanford University
• Tuomas Sandholm, Department of Computer Science, Carnegie Mellon University

The academic market for operations researchers

Operations Academia is a relatively new website, organized by a postdoctoral fellow in his free time (see below) whose purpose is to provide a centralized information location for jobs and job candidates in Operations.

"This website is intended to appeal to any Operations academic (broadly defined), but particularly to those who are looking for information about this academic year's Operations Job Market. 

Specifically, are you a:

• Job Market Candidate? Help Universities and Business Schools find you easier by creating your research profile.

• University/ Business School with an open position? Reach out a wider audience for your academic vacancies by posting a job.

• Candidate who has already accepted an academic placement? Let the rest of the operations community know about it by updating this form.

Or, were you on the Job Market last year? Help us further understand the process of finding an Academic placement in Operations (broadly defined), by taking our Annual Job Market Survey.

Suggestions on how to improve this website and organize our Job Market? Please submit here an idea and/ or vote for new features suggested by others. Or, otherwise contact us."

About 

 "Our vision is to make the search for an academic job in Operations (and related areas) more efficient and transparent. We also aim to better understand the dynamics and research trends in our field to better inform: PhD Candidates, recently hired faculty members and hiring decision-makers, as well as prospective graduate Students who wish to apply to PhD Programmes in our field.

In this website you will find the first Job Market Survey ever conducted for Job Market Candidates in Operations Management/Research (and related areas), academic job postings, PhD Candidates looking for an academic position, confirmed placements, and recently hired faculty members.

This website is supported by the MSOM Society of INFORMS and is owned and managed by Konstantinos I. Stouras, Post-doctoral Research Fellow, Operations Management, University of Virginia (Darden School of Business) in his free time. All inputs are posted by the academic community by verified individuals. We are always open for feedback and suggestions on how to improve this initiative; please post suggested improvements/comments, and vote for already existing ones to encourage their development."

Market Design and Operations Research: an interview by the journal Mathematics of Operations Research

The journal Mathematics of Operations Research, where the main paper from my dissertation was published in 1976, has published an interview with me in their Author Spotlight section: In Conversation with...ALVIN E. ROTH.

Here's the first question and answer:

INFORMS:  Your first published paper, “Subsolutions and the Supercore of Cooperative Games,” [2]based on your doctoral thesis, appeared in MOR in 1976. The paper was handled by Nobel winner and MOR Founding Area Editor Robert Aumann. Can you share with us how your first experience with the peer review process went?

ROTH:  I recall that experience vividly. Aumann, in his editor’s letter, told me to ignore the referees, but to revise the paper along the lines he would describe. One revision he wanted had to do with the proof of my main theorem, for which I had used Zorn’s Lemma. He advised me to try to construct a proof which instead used transfinite induction. I didn’t know what transfinite induction was, so I was very skeptical, but I grimly trudged to the math library and got a copy of Hausdorff’s book Set Theory [3] to repair this gap in my education. I still remember how my hopes lifted when I opened the book and saw that it had been translated from the German by…Aumann. It turned out that he knew what he was talking about, and the proof that appears in my published MOR paper uses transfinite induction.

...

At the Author Spotlight page they also link to the several papers I published in MOR:

Roth AE (1976) Subsolutions and the Supercore of Cooperative Games. Math. Oper. Res. 1(1):43–49.  

Roth AE (1977) Individual rationality and Nash’s solution to the bargaining problem. Math. Oper. Res. 2(1): 64–65. 

Roth AE (1982) The economics of matching: Stability and incentives. Math. Oper. Res. 7(4):617–628. 

Roth AE (1985) Conflict and coincidence of interest in job matching: Some new results and open questions. Math. Oper. Res. 10(3):379–389.*  

Roth AE, Rothblum UG, Vande Vate, JH (1993) Stable matchings, optimal assignments, and linear programming. Math. Oper. Res. 18(4): 803–828. 

Since becoming a notorious economist, I've had a number of conversations with operations researchers that begin with a question like "Why did you switch from OR to Economics?"

My usual answer is that I got my Ph.D. in OR in 1974 with a dissertation in game theory, and it looked at that time as if OR would be a natural place for game theory to flourish, particularly since Bob Aumann was the founding game theory editor of MOR. But, as it turned out, game theory grew first and fastest in Economics. So I just stood my ground, while the disciplinary boundaries shifted around me. Today, market design has become the engineering part of game theory, and it's time for OR and Economics to reconnect around market design. And indeed at Stanford, many of the Ph.D. students in our market design classes in the econ department are OR students from our MS&E department or from our Business school, both of which in turn have market designers on their faculty.  So I'm optimistic that my dual identities as an economist and operations researcher may soon seem seamless.
****************



*Beware, my 1985 paper contains an error about the lattice structure of stable matchings, that was noted and corrected by
Charles Blair (1988), "The Lattice Structure of the Set of Stable Matchings with Multiple Partners,"  Mathematics of Operations Research 13(4):619-628. http://dx.doi.org/10.1287/moor.13.4.619
and also by
Jianrong Li, (2013) A Note on Roth's Consensus Property of Many-to-One Matching. Mathematics of Operations Research 38(2):389-392. http://dx.doi.org/10.1287/moor.1120.0576 

Stanford Engineering Hero Lecture: Ken Arrow on his intellectual history and the history of Operations Research (video)

I've had occasion to think about Operations Research recently, and it's relationships with Economics.  Here's Ken Arrow recalling some early history.



Ken speaks about his intellectual history, and the history of Operations Research as a field and at Stanford. The question and answers at the end are a lot of fun too.

Ken's talk begins at around 7:30 of the video, after an introduction.
The occasion is the March 4, 2014 celebration of Ken as an Engineering Hero. 

More on Nimrod Megiddo winning the INFORMS von Neumann Theory Prize

Here's the citation for Nimrod Megiddo winning the John von Neumann Theory Prize

John von Neumann Theory Prize

2014 Winner(s): Nimrod Megiddo, IBM

Citation:

Of all of the areas in which he has worked, Megiddo has had perhaps the most profound impact on the theory of linear programming. His work on the probabilistic analysis of the simplex method, alone and with Adler, established some of the most important results in the area, including the best (quadratic) bound for the complexity of a complete parametric pivoting method and an explanation of why this is possible for the lexicographic version but not the standard Lemke perturbation. He also established a quadratic lower bound for this method. This, along with work of Smale, Borgwardt, and Haimovich, together with independent proofs of the quadratic result by Adler-Karp-Shamir and Todd provided the first theoretical justification for the success of the simplex method. 

Megiddo was an early leader in the theory of interior-point methods, and laid the framework for the development of primal-dual methods in his seminal paper on pathways to the solution. This paper was the foundation for the hugely successful primal-dual interior-point methodology for linear programming, implementations of which are now included in every serious software package. His contributions to interior-point methods culminated in his work on the linear complementarity problem with Kojima and Noma. 

Megiddo’s work has also played a role in highlighting the question, still unresolved today, of whether there is a strongly polynomial algorithm for linear programming. Megiddo made two strikingly beautiful contributions in the design of strongly polynomial algorithms: his innovative multi-dimensional searching technique that yielded a strongly polynomial algorithm for linear programming in constant dimensions, and its forerunner in parametric search algorithms, which showed how to leverage an algorithm to optimize a linear objective into a corresponding strongly polynomial algorithm to optimize a rational objective function over the same feasible region. 

In algorithmic game theory, Megiddo has done groundbreaking work that anticipated by two decades the more recent blossoming of the field. In particular, Megiddo raised the question of the complexity of equilibrium computation in the 80’s and showed that the usual notion of NPhardness is not adequate to capture the apparent difficulty of the problem, anticipating and opening the way to subsequent developments in the area. On the algorithmic side, his later work (with Kholler and von Stengel) also showed how equilibrium solutions for 2-person games can be computed in polynomial time, even if the game were given in extensive form. Bridging between concepts in game theory and traditional combinatorial optimization, Megiddo initiated the investigation of computing fair flows in networks, and did path-setting work on efficient algorithms to compute the fair allocation of costs in a number of game-theoretic settings. 

In summary, Nimrod Megiddo has made fundamental contributions across a broad range of areas of operations research and management science, most notably in linear programming, combinatorial optimization, and algorithmic game theory. His work has been highly influential, in both identifying key concepts and in developing new algorithmic approaches for fundamental problems.

Nimrod Megiddo awarded the John von Neumann Theory Prize at INFORMS 2014

Nimrod Megiddo was announced as the winner of the 2014 von Neumann Theory Prize at the INFORMS meeting yesterday (although as of this writing the web page hasn't been updated).

He is a deserving member of a distinguished club:

Past Awardees

2013 Winner(s)

Michel L Balinski, C.N.R.S. and Ecole Polytechnique

2012 Winner(s)

George L. Nemhauser, Georgia Institute of TechnologyLaurence A. Wolsey, Université Catholique de Louvain

2011 Winner(s)

Gerard P. Cornuejols, Carnegie Mellon University, Tepper School of Business

2010 Winner(s)

Peter Glynn, Stanford UniversitySøren Asmussen, Aarhus University, Denmark

2009 Winner(s)

Yurii Nesterov, CORE/UCLYinyu 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-ZentrumLászló Lovász, Eotvos University, Institute of MathematicsAlexander 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 ISyEMichael J. Todd, Cornell University
School of Operations Research and Information

2002 Winner(s)

Cyrus Derman, Professor Operations Research, Columbia UniversityDonald 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 TechnologyManfred 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, IBMPhilip S. Wolfe, IBM

1991 Winner(s)

Richard E. Barlow, University of California-BerkeleyFrank 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 CharnesWilliam W. Cooper, University of Texas - Austin, MSIS DepartmentRichard J. Duffin

1981 Winner(s)

Lloyd S. Shapley , University of California - Los Angeles, Dept. of Economics

1980 Winner(s)

David GaleHarold W. Kuhn, Princeton UniversityAlbert 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