TUCKER, ALBERT WILLIAM

(b. Oshawa, Ontario, Canada, 28 November 1905;

d. High-tstown, New Jersey, 25 January 1995), mathematics, operations research.

Tucker’s name is in general associated with the mathematical disciplines of linear-nonlinear programming and game theory within operations research, and in particular with the duality theorem in linear programming, the Kuhn-Tucker conditions, and the Prisoner’s Dilemma. In 1948 he became the leader of a university-based project on linear programming and game theory funded by the Office of Naval Research (ONR) and as such he was very influential in the early advancement of these fields. In 1994 his student John Forbes Nash received the Nobel Prize for his work on game theory and Tucker himself was awarded the John von Neumann Theory Prize in 1980 for his contributions to operations research.

Albert Tucker grew up in different small towns along the north coast of Lake Ontario. His special talent for mathematics was first recognized by his mathematics teacher in high school who informed Tucker’s parents that he thought Tucker could have a career as an actuary. Tucker was awarded a provincial scholarship and began to study mathematics and physics at the University of Toronto in 1924 where his talent for mathematics was recognized for the second time. In 1928, Tucker received a bachelor degree and instead of pursuing further studies abroad he stayed at the University of Toronto for another year as a teaching assistant receiving a master’s degree in 1929.

Tucker attended Princeton University for his doctoral studies. Some might have seen this as an odd choice at the time. According to Tucker several mathematicians tried to convince him to study in Europe or if he insisted on attending school in the United States he should choose the University of Chicago or Harvard University. Tucker was interested in geometry and had seen a catalog of graduate courses offered at Princeton, which in his opinion listed the most interesting courses. In the end Tucker was supported by Professor Chapelon and in 1929 Tucker began his graduate studies at Princeton. He received his PhD in 1932 with a thesis in topology written under the supervision of Professor Lefschetz.

From 1933 and until his retirement in 1974 Tucker held positions at the mathematics department at Princeton University. Once retired he organized Princeton’s oral history project where he engaged in many of the oral history interviews with former Princeton mathematicians.

In 1938 he married Alice J. Curtiss. They had three children, a daughter who is an educator and two sons— both mathematicians. Tucker and Alice later divorced and in 1964 he married Mary F. Shaw.

ONR, Linear Programming, and Game Theory. Tucker’s ONR project was a consequence of the huge military funding of science in the wake of the mobilization of scientists in the United States during World War II. The linear programming problem—to optimize a linear function subject to linear inequality constraints originated in the U.S. Air Force as a consequence of work done notably by George B. Dantzig during and after the war on the problem of calculating huge logistic planning programs.

One of the more well-known examples of linear programming problems is the transportation problem of determining how to ship amounts of a product between several centers of supply and markets in such a way that the total cost of transportation is minimized while the demands are satisfied.

The connection between linear programming and game theory was realized in the fall of 1947 by John von Neumann at the Institute for Advanced Study at Princeton University who, in his capacity as a consultant for the military, was contacted by Dantzig. The navy was interested in the possibilities of linear programming as an effective decision tool and decided to promote research in its mathematical theory and its relation to game theory. The result was the establishment of a separate logistic branch of the ONR’s mathematics program. Tucker got involved in the project because he met Dantzig on one of Dantzig’s visits to Princeton. The project began as a trial project in the summer of 1948 and continued with support from the ONR until 1972.

The Duality Theorem. The first group consisted of Tucker and two graduate students, Harold W. Kuhn and David Gale. They laid the theoretical foundation for linear programming in their first article “Linear Programming and the Theory of Games,” which they presented at the first conference on linear programming in Chicago 1949. Among their main results was the first rigorous proof of the duality theorem, which states that for a linear maximizing/minimizing programming problem one can formulate another (dual) linear minimizing/maximizing programming problem on the same set of data. The original problem has a finite optimal solution if and only if the dual problem has a finite optimal solution and the optimal values are equal.

The Kuhn-Tucker Conditions. The linear programming problem did not originate in mathematics itself but in the context of solving a practical problem in the air force, but Tucker, Kuhn, and Gale’s first work was purely theoretical. The duality result is interesting from a mathematical point of view and Tucker continued the work on the project trying to generalize the duality result for linear programming to nonlinear programming. This led to Tucker’s famous paper coauthored with Kuhn (1951) in which they launched the mathematical theory of nonlinear programming.

Nonlinear programming is called for when some of the involved functions—either the function to be optimized or the constraints—are nonlinear. If in the transportation problem the location of the supply centers are not fixed but are to be determined so that the total distance weighted by the shipment from the supply centers is to be minimized, the problem turns into a nonlinear programming problem where both the shipments and the distances are to be determined.

Tucker took the Lagrangian multiplier method as the point of departure in the study of nonlinear programming problems because it exhibits the duality of linear programming in the following sense: To the linear programming problem

where x₁, …, x_n are n real variables constrained by m+ n linear inequalities

Kuhn and Tucker formed the corresponding Lagrangian function:

They realized that solves the linear programming problem if and only if there exists a vector with nonnegative components (multipliers) such that (x⁰, u⁰) is a saddlepoint for the Lagrangian. The vector u⁰ then solves the dual problem. Following this approach for the nonlinear case Kuhn and Tucker proved that a necessary condition such that a point x⁰in solves a nonlinear programming problem is the existence of a point u⁰ in such that (x⁰, u⁰) satisfy the necessary conditions for being a saddlepoint for the Lagrangian corresponding to the nonlinear programming problem. These necessary conditions later became known as the (Karush-) Kuhn-Tucker conditions and they constitute one of the main results in nonlinear programming.

ONR’s way of funding science through university-based projects had the effect that ONR functioned as a mediating link between the interests of the military and peacetime research at the universities. A consequence of this is that ONR research, originally inspired by practical problems, could lead to highly theoretical results. The duality theorem in linear programming and the Kuhn-Tucker theorem in nonlinear programming are both such examples of theoretical results developed in the context of an ONR research project.

The Prisoner’s Dilemma. Through Tucker’s project Princeton became a main center for game theory in the postwar period. Tucker supervised PhD theses in game theory, the most famous being Nash’s Nobel Prize– winning work on noncooperative games. Tucker himself is most famous for his interpretation—known as the Prisoner’s Dilemma—of a payoff matrix for a two-person non-zero-sum game devised by Merrill Flood and Melvin Dresher at RAND in 1950: Two people are charged with a joint crime. If both confess they will be fined one unit each, if both deny they will both go clear. If one confesses and the other does not, the confessor will be rewarded with one unit the other will be fined two units. The game has a unique equilibrium point, the noncooperative solution of both confessing, but—and this is the dilemma— the prisoners are better off if they chose the nondominant strategy of denial. The prisoner’s dilemma has played a significant role in social science.

The Influence on the Theory of Convexity. Tucker’s project also initiated new research in the theory of convexity. In their joint nonlinear programming paper he and Kuhn proved that if the involved functions are concave and differentiable there will be complete equivalence between the saddle value problem for the corresponding Lagrangian function and the nonlinear programming problem suggesting that the theory of convex (concave) functions might be a promising tool in the theory of nonlinear programming. A convex (concave) function is a function whose graph curves upward (downward) so it has the property that a local minimum (maximum) will also be a global minimum (maximum). The new developments in the theory of convexity were primarily due to a series of lectures given by Werner Fenchel at Princeton University in the spring of 1951 during which Fenchel derived the first duality result for nonlinear programming. Tucker’s project published the notes from these lectures in 1953 and they had a profound influence on the further development of the theory of convexity in the United States. This is another example where ONR research originally initiated by the need for solving practical logistic problems led to theoretical results and influenced developments in so-called pure mathematics.

BIBLIOGRAPHY

WORKS BY TUCKER

“A Two-Person Dilemma.” Unpublished notes (May 1950), later published in Readings in Games and Information, edited by Eric Rasmusen. Oxford: Blackwell Publishers Ltd., 2001.

With Harold W. Kuhn, eds. Contributions to the Theory of Games. Annals of Mathematics Studies, no. 24. Princeton, NJ: Princeton University Press, 1950.

With David Gale and Harold W. Kuhn. “Linear Programming and the Theory of Games.” In Activity Analysis of Production and Allocation, edited by T. C. Koopmans. New York: John Wiley and Sons, 1951.

With Harold W. Kuhn. “Nonlinear Programming.” In Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability, edited by J. Neyman. Berkeley: University of California Press, 1951.

———, eds. Contributions to the Theory of Games, vol. 2. Annals of Mathematics Studies, no. 28. Princeton, NJ: Princeton University Press, 1953.

———, eds. Linear Inequalities and Related Systems. Annals of Mathematics Studies, no. 38. Princeton, NJ: Princeton University Press, 1956.

With M. Dresher and P. Wolfe, eds. Contributions to the Theory of Games, vol. 3. Annals of Mathematics Studies, no. 39. Princeton, NJ: Princeton University Press, 1957.

With R. D. Luce, eds. Contributions to the Theory of Games, vol. 4. Annals of Mathematics Studies, no. 40. Princeton, NJ: Princeton University Press, 1959.

OTHER SOURCES

Albers, Donald J., and G. L. Alexanderson, eds. Mathematical People: Profiles and Interviews. Boston: Birkhäuser, 1985.

“A Guide to the Albert William Tucker Papers, 1946–1979,” in Archives of American Mathematics, Center for American History, The University of Texas at Austin. Available from http://www.lib.utexas.edu/taro/utcah/00301/cah-00301.html. Consists of interviews with Albert W. Tucker from 1979 and reprints and photocopies of papers by and about Tucker and mathematics at Princeton University.

Kjeldsen, Tinne H. “The Emergence of Nonlinear Programming: Interactions between Practical Mathematics and Mathematics Proper.” Mathematical Intelligencer 22 (Summer 2000): 50–54.

———. “A Contextualized Historical Analysis of the Kuhn-Tucker Theorem in Nonlinear Programming: The Impact of World War II.” Historia Mathematica 27 (November 2000): 331–361.

———. “The Development of Nonlinear Programming in Post War USA: Origin, Motivation, and Expansion.” In The Way through Science and Philosophy: Essays in Honour of Stig Andur Pedersen, edited by H. B. Andersen, F. V. Christiansen, K. F. Jørgensen, et al., 31–50. College Publications, 2006.

Kuhn, Harold W. “Nonlinear Programming: A Historical View.” SIAM-AMS Proceedings 9 (1976): 1–26.

Nasar, Sylvia. “Obituary.” New York Times, 27 January 1995.

Tinne Hoff Kjeldsen