Michel L Balinski
|2013||John von Neumann Theory Prize: Winner(s) [+show more]|
Michel Balinski has made major theoretical and practical contributions in both traditional and nontraditional areas of operations research and management science over the decades. His 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.
It is an exceptional honor to be awarded the John von Neumann Theory Prize and to be placed in the company of many of the contributors to operations research whom I most admire.
My thanks go to all those that made this happen. They go to all my collaborators across the years without whom it would certainly not have happened, especially to those three with whom I worked on common projects over many years (in chronological order): Peyton Young (on apportionment), Mourad Baïou (on stable matchings and generalizations), and Rida Laraki (on ranking and electing).
My apologies go to the members of INFORMS for not being in Minneapolis to receive the prize in person. I would dearly have liked to attend but cannot due to obligations agreed to before I was notified of the prize.
The occasion invites reminiscences on OR and my beginnings in research.
I finished my undergraduate studies at Williams College in 1954, majoring in mathematics. I loved mathematics (and still do), but my ambition was decidedly to do somethinguseful. I had (and have) no intuition for the “hard” sciences, I had (and have) a strong interest in political and social affairs and in history. What, then, to do?
A chance encounter with an English friend of my family informed me of the existence of a new field –operational research– that seemed to encompass exactly what I sought. At that time there were two institutions in the United States where programs were offered, Johns Hopkins University and MIT. A professor at Williams whom I knew well (Emile Despres) sent me to see a young assistant professor of economics at MIT, Robert Solow. Operations research could be pursued at MIT but via an established discipline, among which were mathematics, physics, electrical, mechanical, and other types of engineering, and economics, the last of which I chose. This implied completing a Ph.D. in economics – that I began in the fall of 1954 – with a thesis on a problem considered satisfactory as OR. Thus began a life in research and teaching that both combined and oscillated between mathematics, economics and operations research in work, associations and appointments.
My assistantship involved me in a team effort to program the simplex method for the MIT von Neumann computer in machine language (my job, as I vaguely recall it today, was the code for the inner product of two vectors). One of the courses – conducted by the last two of its listed authors – followed the Dorfman, Samuelson and Solow book,Linear Programming and Economic Analysis,which was read as a series of Rand Reports. This awakened a life-long interest in linear programming and extensions. But as the first year progressed I became increasingly convinced that to advance in OR and economics required a strong mathematical background. So, I began taking some courses in mathematics, and after a second year, stopped with an M.S. in economics and left for Princeton in 1956 to do a Ph.D. in mathematics.
Those were heady years! Mathematical programming (linear, nonlinear, discrete, dynamic), mathematical economics, the theory of games, artificial intelligence, computing and computers were in full development. The likes of Richard Bellman, David Gale, Ralph Gomory, Samuel Karlin, Harold Kuhn, John McCarthy, John Nash, Herbert Scarf, and Lloyd Shapley had recently earned their graduate degrees in mathematics at Princeton. In my days Robert Aumann, Claude Berge, George Dantzig, and Philip Wolfe were visitors, as was my office-mate for a year, Jack Edmonds. Many among them were invited and/or protected (in an otherwise “pure” mathematics department) by Albert W. Tucker. He took me under his wing and became my official thesis advisor, though I prepared my thesis while he was on leave, benefitting from the guidance of my unofficial advisor, the then young Lecturer, Ralph Gomory (then engaged in establishing “integer programming”).
The remarkable innovation that flowered in Fine Hall at Princeton in those post-war years of the fifties often puzzles: Curtis Eaves has repeatedly questioned, why then, why there? The environment of mathematics at Princeton at that time imparted – or so I felt – a belief: the world is wide open, a solid grounding in mathematics suffices to tackle virtually any real problem whatever its origin, and it is precisely such endeavors that open new and exciting areas. I was very lucky to have been there at that time and to have mixed with such outstanding persons who proved, I believe, the truth of that belief.
Today, not surprisingly, I am most excited by my ongoing work with Rida Laraki on ranking and electing. Since 1299 (and who knows, maybe before!) the basic paradigm of voting (and judging) has been that voters compare the relative merits of candidates (or competitors): voters (or judges) rank-order them. If, instead, the basic paradigm is changed and voters evaluate the merit of every candidate in a well-defined ordinal scale then a methodnaturallyemerges – majority judgment – that overcomes the most important failures and paradoxes of voting (including Arrow’s Impossibility Theorem). It is a simple and practical method: majorities determine society’s evaluation of each candidate in the scale and thereby its rank-ordering of all. Discovering a proper model – that activity so very central to OR, economics and indeed all of the sciences – changes all, and in this case yields a procedure that has been and is being used, and continues to be studied and tested.
It is an ongoing source of wonder to me that the traditional paradigm of voting resisted challenge for so long. After all, as Arrow and others showed, it doesn’t work! This prompts me to cite two favorite passages written by persons whom I particularly admire. Richard Feynman points out: “During the Middle Ages there were all kinds of crazy ideas, such as that a piece of rhinoceros horn would increase potency. Then a method was discovered for separating the ideas – which was to try one to see if it worked, and if it didn’t work, to eliminate it. This method became organized, of course, into science.”
The famous American journalist and chief “muck-raker” Lincoln Steffens explains both the difficulty and the payoff of the remedy (in hisAutobiography): “There was a risk in theorizing. I had witnessed, close up, the fatal, comic effect upon professors and students of hypotheses which had become unconscious convictions. And thus warned, I had thrown overboard, as a reporter facing facts, many ... notions ... It is hard to do; ideas harden like arteries; indeed, one theory of mine is that convictions are identical with hardened arteries. But the facts ... forced me to drop my academic theories one by one; and my reward was the discovery that it was as pleasant to change one’s mind as it was to change one’s clothes. The practice led one to other, more fascinating ––– theories.”
Allof the afore mentioned – including Tucker himself – received the von Neumann Theory Prize (save John McCarthy and Claude Berge). Four of Tucker’s students have been recipients; more remarkable, two of them received Nobel Prizes in Economics.
Fine Hall then housed the Princeton Mathematics Department.
|1965||Frederick W. Lanchester Prize: Winner(s) [+show more]|
The 1965 Lanchester Prize was awarded to Michel Balinski for his paper, "Integer Programming : Methods, Uses, Computation," Management Science 12, 1965, 253-313. Also reprinted in Mathematics of the Decision Sciences, Lectures in Applied Mathematics, American Mathematical Society, vol. 11, 1968, 179-256, George B. Dantzig and Arthur F. Veinott, Jr., editors; and in H. W. Kuhn, editor, Proceedings of the Princeton Symposium on Mathematical Programming, Princeton University Press, 1970, 199-266.
The 1965 Lanchester Prize was also awarded to Rufus Isaacs for his book, Differential Games, John Wiley, 1965.