INFORMS NEWS: Balinski earns von Neumann Theory Prize

The 2013 John von Neumann Theory Prize of INFORMS was awarded to Michel L. Balinski, C.N.R.S. and Ecole Polytechnique, for his “major theoretical and practical contributions in both traditional and nontraditional areas of operations research and management science over the decades.”

Committee Chair Yinyu Ye announced the winner at the INFORMS Award Ceremony held in conjunction with the INFORMS Annual Meeting in Minneapolis. George Nemhauser accepted the award on behalf of Balinski.

The prize recognizes scholars who have made fundamental, sustained contributions to theory in operations research and the management sciences.

The award citation read in part:

[Balinski’s] contributions in linear and nonlinear optimization include an algorithm for finding all optimal solutions to linear programs, a primal/dual simplex method that incorporates a natural proof of termination and leads to a self-contained, elementary but rigorous, constructive account of the theory and the basic computational tool of linear programming; the use and economic interpretation of dual prices; and a proof that prices in von Neumann’s model of an expanding economy are marginal values.

His work in integer programming includes the formulation and analysis of the fixed cost transportation problem; one of the first computationally successful practical uses of Gomory’s cutting plane algorithm (truck deliveries with cost functions in part concave, in part convex); and an extensive survey paper on integer programming, which was awarded INFORM’s Lanchester Prize in 1965.

His contributions on convex polyhedra and combinatorics include the fundamental theorem that the skeletons of polytopes in n-space viewed as graphs are n-connected; an analysis of assignment polytopes and a proof of the Hirsch conjecture for dual transportation polyhedra; a characterization of the convex hull of one-to-many stable matchings; competitive primal algorithms to solve assignment and transportation problems; and a labelling algorithm to solve the maximum matching problem. In particular, he developed with Mourad Baïou a unified formulation and approach to stable (Gale-Shapley) matchings leading to new proofs of known results as well as new results (notably concerning algorithms, players’ strategies, and the university admissions polytope). He also produced characterizations of the unique fair mechanism for assigning students to universities (or applicants to positions) when students’ (or applicants’) rankings are determined by their performance and generalizations of the results to stable one-to-many and many-to-many matching and the stable allocation of real numbers (e.g., hours).

Balinski’s most important contributions are in the domain of electoral decisions, namely, representation and apportionment on the one hand, and voting on the other. They are significant, innovative, deep and of the highest scientific excellence. His papers and book with H. P. Young, “Fair Representation: Meeting the Ideal of One Man, One Vote,” have had direct practical application in several countries. The book received the 2008 George H. Hallett Award of the American Political Science Association “for a book published at least 10 years ago that has made a lasting contribution to … representation and electoral systems.”

His most recent book with Rida Laraki, “Majority Judgment: Measuring, Ranking and Electing,” proves that majority judgment (MJ) is the only method that satisfies the important traditional criteria of social choice. A reformulation of the basic model of voting that seeks more precise expressions of voters’ opinions – evaluations of candidates rather than rank-ordering them – permits a theory that overcomes/bypasses the Arrow and other classical impossibility theorems. The book also reports on experiments and applications of MJ in a variety of settings, including elections in France, ranking competing wines and awarding an international prize in journalism.