Michel Balinski
Michel Louis Balinski | |
---|---|
![]() From left: Michel Balinski, Friedrich Pukelsheim , Steven Brams, Oberwolfach 2004 | |
Born | Geneva, Switzerland | October 6, 1933
Nationality | American |
Alma mater | Princeton University |
Known for | Balinski's theorem |
Awards | John von Neumann Theory Prize, Lanchester Prize |
Scientific career | |
Fields | Mathematics, Economics, Operations Research, Political Science |
Doctoral advisor | Albert W. Tucker |
Doctoral students | Louis Billera |
Michel Louis Balinski (born October 6, 1933) is an applied mathematician, economist, operations research analyst and political scientist. As an American, educated in the United States, he has lived and worked primarily in the United States and France. He is known for his work in optimization (combinatorial, linear, nonlinear), convex polyhedra, stable matching, and the theory and practice of electoral systems, jury decision, and social choice. He is Directeur de Recherche de classe exceptionnelle (emeritus) of the C.N.R.S. at the Ecole Polytechnique (Paris). He was awarded the John von Neumann Theory Prize by INFORMS in 2013.
Early life
Michel Balinski was born in Geneva, Switzerland, the son of a Polish diplomat at the League of Nations and the grandson of the Polish bacteriologist and UNICEF founder Ludwik Rajchman.[1] He was living with his grandparents in France when in 1940 the family fled the Nazis via Spain and Portugal to the United States. He graduated from the Edgewood School in Greenwich CT in 1950, earned a B.A. degree cum laude in mathematics at Williams College in 1954 and a M.Sc. in economics at the Massachusetts Institute of Technology in 1956. He completed a Ph.D. in mathematics at Princeton University in 1959 under the supervision of Albert W. Tucker.[1][2]
Career
After completing his Ph.D. Balinski remained at Princeton University as a Research Associate then Lecturer in mathematics. From 1963 to 1965 he was Associate Professor of Economics at the Wharton School of the University of Pennsylvania. He was then appointed to the Graduate School of the City University of New York, first as Associate Professor then (as of 1969) Professor of Mathematics. One of his doctoral students at the City University was another noted mathematician, Louis Billera, through whom he has many academic descendants. In 1978 he was appointed Professor of Organization and Management and of Administrative Sciences at Yale.
In parallel with his academic work Balinski engaged in consulting as of the time he was a graduate student at Princeton. A participant in the beginnings of what became the consulting firm Mathematica, he was a Senior Consultant with the firm from 1962 to 1974. He also acted as a consultant elsewhere, including the Rand Corporation, Mobil Oil Research, the ORTF (Office de Radiodiffusion-Télévision Française), the Mayor's office of the City of New York (as member of the Operations Research Council), and Econ, Inc. From 1975 to 1977 he was Chairman of System and Decision Sciences at IIASA (International Institute for Applied Systems Analyses) at Laxenburg, Austria.
In 1980 Michel Balinski settled in France, becoming Directeur de Recherche de classe exceptionnelle of the CNRS (Centre National de Recherche Scientifique) at the Laboratoire d’Econométrie of the Ecole Polytechnique in 1983. Concurrently he was Leading Professor of Applied Mathematics and Statistics and of Economics at SUNY (State University of New York) Stony Brook (1983-1990), where he founded and was the first Director of the Institute for Decision Sciences (that has since become the Center for Game Theory in Economics).
Upon becoming Director of the Laboratoire d’Econométrie (1989 to 1999) he co-founded and co-directed the joint Ecole Polytechnique/Université de Paris 1 masters program "Modélisation et méthodes mathématiques en économie: optimisation et analyse stratégiques," and its successor the joint Ecole Polytechnique/Université Pierre et Marie Curie (Paris 6) masters program "Optimisation, jeux et modélisation en économie." [3]
He was a visiting professor at other institutions, including the Ecole Polytechnique Fédérale de Lausanne (1972-1973), the Université Scientifique et Médicale de Grenoble (1974-1975), the Universidad de Chile in Santiago (1994), and INSEAD in Fontainebleau (1997-1998).[1][3]
Balinski was the founding Editor-in-Chief of the journal Mathematical Programming in 1971, one of the founders of the Mathematical Optimization Society in 1970, and President of that society from 1986 to 1989.[4]
Research contributions
Balinski's Ph.D. thesis concerned the vertex enumeration problem, the algorithmic problem of listing all vertices of a convex polytope or finding all optimal solutions of a linear program, and some of his subsequent work continued to concern polyhedral combinatorics. The thesis includes the fundamental theorem, published in 1961, that the skeletons of polytopes in "n"-space viewed as graphs are "n"-connected, meaning that at least "n" edges must be removed to disconnect the graph of the remaining vertices and edges;[5] it is known as Balinski's theorem. He also proved the Hirsch conjecture for several different classes of polytopes associated with the transportation problem, showed that the diameter of the skeleton of the assignment polytope viewed as a graph is 2, and found the polytope whose vertices are the stable matchings of the university admissions problem.
His contributions to linear and nonlinear optimization include 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 (1968, 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.
Together with Mourad Baïou,[6] he developed a new formulation of stable matchings and generalizations in terms of graphs, providing a unified notation and tool leading to new proofs of known results and new results; notably, a characterization of the university admissions polytope, and a generalization of matching opposites (e.g., men and women, students and universities) to matching opposites in real numbers (e.g., time spent together).
In 1970, he published one of the earliest papers on the closure problem and its applications to transportation planning.[7]
Electoral systems
Balinski has made important contributions to the theory of electoral systems, namely, representation and apportionment on the one hand, and voting on the other. His 1982 book [8][9] with H. Peyton Young[10] has had direct practical application in apportioning the seats of assemblies to regions in several countries (including the UK). He conceived and developed with others "biproportional apportionment" that has been adopted (as of 2014) in five of Switzerland's cantonal elections. His 2010 book with Rida Laraki[11] proposes a new theory and method of voting called "majority judgment" where voters evaluate the merit of each candidate in a well-defined ordinal scale (instead of voting for one or several candidates, or rank-ordering them) and majorities determine society's evaluation of each candidate and thereby its rank-ordering of them all. This, they prove, overcomes the most important drawbacks of the traditional theory of voting (including Arrow's impossibility theorem).[12]
Awards and honors
Phi Beta Kappa, Williams College 1954; Frederick W. Lanchester Prize, INFORMS 1965;[13] I.B.M. World Trade Corporation Fellow 1969-1970; Lester R. Ford Award, Mathematical Association of America 1976;[14] Honorary Master of Arts, Privatum, Yale University 1978; Special Service Award, Mathematical Optimization Society, 1982; Honorary Doctorate (Ehrendoktors, Mathematisch-Naturwissenshaftlichen) Universität Augsburg, 2004;[1] Murat Sertel Lecturer (inaugural lecture), 8th International Meeting of the Society for Social Choice and Welfare, Istanbul, July 2006; Messenger Lecturer, Cornell University, September 2007;[15][16][17] IFORS Distinguished Lecturer, INFORMS National Meeting, Washington, D.C., October 2008;[18] George H. Hallet Award, 2009;[19] Lester R. Ford Award, Mathematical Association of America, 2009;[20] Celebration of Michel Balinski's 78 years at the 23rd International Conference on Game Theory, SUNY Stony Brook, July 2012;[21] John von Neumann Theory Prize, INFORMS, 2013;[13] INFORMS Fellow, 2014.[12][22]
Selected publications
Books
- Fair Representation: Meeting the Ideal of One Man, One Vote, Michel L. Balinski and H. Peyton Young, Yale University Press, 1982. 2nd edition, Brookings Institution Press, Washington, D.C., 2001. Japanese translation, Chikura-Shobo Publishing Co., Tokyo, 1987. ISBN 9780815716341. [Given the George H. Hallet Award, 2009, "[For] a book published at least 10 years ago that has made a lasting contribution to ... representation and electoral systems."]
- Le Suffrage Universel Inachevé, Michel Balinski, Editions Belin, 2004, ISBN 2-7011-3774-8.
- Majority Judgment: Measuring, Ranking, and Electing, Michel Balinski and Rida Laraki, MIT Press,[23] 2010, ISBN 9780262015134.
Articles
- Balinski, M. L. (1961), "An algorithm for finding all vertices of convex polyhedral sets", J. Soc. Indust. Appl. Math., 9: 72–88, doi:10.1137/0109008, MR 0142057.
- —— (1961), "On the graph structure of convex polyhedra in n-space", Pacific Journal of Mathematics, 11: 431–434, doi:10.2140/pjm.1961.11.431.
- —— (1965), "Integer Programming : Methods, Uses, Computation", Management Science, 12: 253–313, doi:10.1287/mnsc.12.3.253, JSTOR 2627582. Reprinted in Mathematics of the Decision Sciences (1968), in Proceedings of the Princeton Symposium on Mathematical Programming, 1970, and in 50 Years of Integer Programming 1958-2008 (2010). Given the 1965 Lanchester Prize
- ——; Baumol, W. J. (1968). "The dual in nonlinear programming and its economic interpretation". The Review of Economic Studies. 25: 237–256.
- ——; Tucker, A. W. (1968). "Duality theory of linear programs: a constructive approach with applications". SIAM Review. 11: 247–377.
- —— (1970), "On a selection problem", Management Science, 17 (3): 230–231, doi:10.1287/mnsc.17.3.230.
- ——; Young, H. P. (1974). "Interpreting von Neumann model prices as marginal values". Journal of Economic Theory. 9: 449–463. doi:10.1016/0022-0531(74)90045-3.
- ——; Young, H. P. (1975). "The quota method of apportionment" (PDF). Amer. Math. Monthly. 82: 701–730. doi:10.2307/2318729.. Given the 1976 Lester R. Ford Award
- —— (1984). "The Hirsch conjecture for dual transportation polyhedra". Mathematics of Operations Research. 9: 629–633. doi:10.1287/moor.9.4.629.
- ——; Demange, G. (1989). "An axiomatic approach to proportionality between matrices". Mathematics of Operations Research. 14: 700–719. doi:10.1287/moor.14.4.700.
- ——; Ramiréz, V. (1996). "A case study of electoral manipulation: the Mexican laws of 1989 and 1994". Electoral Studies. 15: 203–217. doi:10.1016/0261-3794(95)00033-x.
- ——; Sönmez, T. (1999). "A tale of two mechanisms: student placement". Journal of Economic Theory. 84: 73–94. doi:10.1006/jeth.1998.2469.
- Baïou, M.; Balinski, M. L. (2002). "The stable allocation (or ordinal transportation) problem". Mathematics of Operations Research. 27: 662–680. doi:10.1287/moor.27.4.662.302.
- Balinski, M. L. (2005), "What is just?", American Mathematical Monthly, 112: 502–5011, doi:10.2307/30037520.
- ——; Laraki, R. (2007). "A theory of measuring, electing and ranking". Proceedings of the National Academy of Sciences. 104: 8720–8725. doi:10.1073/pnas.0702634104.
- Balinski, M. L. (2008), "Fair majority voting (or how to eliminate gerrymandering)", American Mathematical Monthly, 115: 97–113, JSTOR 27642416.Given the Lester R. Ford Award
- —— (2009), "Projets électoraux: le droit rencontre les mathématiques", Recueil Dalloz, 3: 183–186.
- ——; Laraki, R. (2014). "Judge: Don't Vote". Operations Research. 62: 483–511. doi:10.1287/opre.2014.1269.
References
- ^ a b c d Laudatio, Friedrich Pukelsheim, University of Augsburg, retrieved 2013-11-27.
- ^ Michel Louis Balinski at the Mathematics Genealogy Project
- ^ a b Michel Balinski receives the 2013 John von Neumann Theory Prize, École Polytechnique, retrieved 2013-11-27.
- ^ Wolfe, Philip, The Mathematical Programming Society (PDF), Mathematical Optimization Society, retrieved 2013-11-27.
- ^ Ziegler, Günter M. (1995), "Section 3.5: Balinski's Theorem: The Graph is d-Connected", Lectures on Polytopes, Graduate Texts in Mathematics, vol. 152, Springer-Verlag.
- ^ http://fc.isima.fr/~baiou/pmwiki-2.2.61/pmwiki.php
- ^ Hochbaum, Dorit (2004), "50th Anniversary Article: Selection, Provisioning, Shared Fixed Costs, Maximum Closure, and Implications on Algorithmic Methods Today", Management Science, 50 (6): 709–723, doi:10.1287/mnsc.1040.0242.
- ^ Apportionment: Balinski and Young's contribution--- http://www.ams.org/samplings/feature-column/fcarc-apportionii3
- ^ Donald L. Vestal, Fair Representation: Meeting the Ideal of One Man, One Vote --- http://www.maa.org/press/maa-reviews/fair-representation-meeting-the-ideal-of-one-man-one-vote
- ^ http://www.economics.ox.ac.uk/Academic/h-peyton-young
- ^ https://sites.google.com/site/ridalaraki/
- ^ a b INFORMS award recipients: Michel L. Balinski, retrieved 2013-11-27.
- ^ a b https://www.informs.org/Recognize-Excellence/Award-Recipients/Michel-L-Balinski
- ^ Balinski, Michel L.; Young, H. P. (1975). "The quota method of apportionment" (PDF). Amer. Math. Monthly. 82: 701–730. doi:10.2307/2318729.
- ^ http://www.math.cornell.edu/~billera/misc/Messenger.html
- ^ http://www.math.cornell.edu/~billera/misc/Abstracts.html
- ^ http://www.orie.cornell.edu/news/index.cfm?news_id=62115&news_back=news_archive%26
- ^ http://www.ifors.org/michel-balinski/
- ^ http://jcolomer.blogspot.fr/2008/09/fair-representation-ideal-of.html?view=classic
- ^ Balinski, Michel (2008). "Fair Majority Voting (or How to Eliminate Gerrymandering)". Amer. Math. Monthly. 115 (2): 97–113. JSTOR 27642416.
- ^ http://www.gtcenter.org/Archive/2012/BalinskiSchedule.pdf
- ^ https://www.informs.org/Recognize-Excellence/Fellows/INFORMS-Fellows-Class-of-2014
- ^ https://mitpress.mit.edu/books/majority-judgment
External links
- Biography of Michel Balinski from the Institute for Operations Research and the Management Sciences
- Michel Balinski's website
- Messenger Lectures
- Messenger Lectures
- Apportionment: Balinski and Young’s Contribution
- Political calculus
- Le jugement majoritaire, video
- Majority Judgment: Measuring, Ranking and Electing
- A Biography of Michel Balinski in the book: A Mathematical View of Our World.
- IFORS Distinguished Lecture
- George H. Hallet Award 2009
- 1933 births
- Living people
- 20th-century American mathematicians
- Williams College alumni
- Massachusetts Institute of Technology alumni
- Princeton University alumni
- Princeton University faculty
- University of Pennsylvania faculty
- City University of New York faculty
- Yale University faculty
- Stony Brook University faculty
- Operations researchers
- Econometricians
- Political scientists
- 21st-century mathematicians
- John von Neumann Theory Prize winners