SIAM News Blog
SIAM News
Print

Obituaries: Harold Kuhn (1925-2014)

By James Case

Harold Kuhn, 1925-2014.
Harold Kuhn, a professor emeritus of mathematical economics at Princeton University and an early president of SIAM, died on July 2. He was 88.

Born in Santa Monica in 1925, to parents of decidedly limited means, Harold Kuhn attended public schools in Los Angeles during the Great Depression. Because of the scarcity of jobs at the time, the chemistry and physics courses at LA’s Manual Arts High School were taught by PhD scientists. As a result, Kuhn’s talents were quickly recognized, and arrangements were made for him to enter the California Institute of Technology on his graduation, in 1942. There, too poor to pay room and board, he was the only member of the freshman class permitted to live off campus.

Drafted into the army in the summer of 1944, Kuhn was selected for Japanese-language training at Yale. According to his son Nick, now a professor of mathematics at the University of Virginia, Harold discovered on a trip to Japan many years later that he could speak the language well enough to ask questions, but not well enough to understand the answers. In fact, Nick reports that his father was good at foreign languages. On occasion, he gave talks in French and Italian, and as an undergraduate he translated a new novel by Hermann Hesse from German to English as an independent project. While at Yale, Harold used his first extended military leave to visit a friend at Princeton, where he sat in for a day on courses taught by Emil Artin, Claude Chevalley, and Salomon Bochner. He returned to Caltech after leaving the army, determined to win admission for graduate study at Princeton.

Kuhn enrolled at Princeton in the fall of 1947. He wrote his doctoral dissertation in group theory under the direction of Ralph Fox. Concurrently, he joined mathematics professor A.W. Tucker and fellow graduate student David Gale in a hastily organized summer project to study the suspected equivalence between linear programming and matrix game theory. That project, he later wrote, “set the course of my subsequent academic career, which has centered around the applications of mathematics to economics.” In 1980, the three shared the John von Neumann Theory Prize of the Operations Research Society of America (now part of INFORMS) for their pioneering work in game theory and optimization.

The late 1940s and early 1950s were the glory years of game theory, both at Princeton and at the newly formed RAND Corporation, where the military applications of game theory were explored in depth. Von Neumann, Oskar Morgenstern, and Tucker from the Princeton faculty, along with Princeton graduate students Kuhn, Gale, Lloyd Shapley, John Nash, Robert Aumann, and Martin Shubik, joined RAND employees Melvin Dresher, Rufus Isaacs, Samuel Karlin, Leonard Berkowitz, and Wendell Fleming in exploring its potential.

Linear programs, it soon emerged, come in pairs. The canonical forms of the “primal” and “dual” problems are: 

\[
\begin{equation}
\mathrm{maximize~}_{x} ~c \cdot x~\mathrm{subject ~to}~Ax \leq b~\mathrm{and}~x \geq 0,\\
\mathrm{minimize~}_{u}~ b \cdot u~\mathrm{subject ~to}~uA \geq c~\mathrm{and}~u \geq 0,
\end{equation}
\]

in which \(A\) is an \(m \times n\) real matrix, and \(b\), \(c\), \(x\), and \(u\) are conformable real vectors. If the inequality constraints \(Ax \leq b\) and \(uA \geq c\) were replaced by equalities, the associated Lagrangian functions would be \(L = c \cdot x + \lambda \cdot (b~– Ax)\) and \(\Lambda = b \cdot u + (c~ – uA) \cdot \mu\) , suggesting that the decision variable \(u\) in the dual problem be identified with the vector \(\lambda\) of Lagrange multipliers in the primal, and vice versa.

With the introduction of additional conformable real vectors \(y\) and \(v\) of non-negative “slack variables,” the two problems can be rewritten in the standard form,

\[
\begin{equation}
\mathrm{maximize~}_{x}  ~m = c \cdot x~ \mathrm{subject~ to}~ Ax – b = –y,\\
\mathrm{minimize~}_{u}  ~M = u \cdot b~ \mathrm{subject~ to}~ uA – c = v,
\end{equation}
\]

and/or in Tucker’s admirably concise “tableau” format, shown in the following graphic:


 

 

From this it is immediately clear that \(0 ≤ v \cdot x + u \cdot y = M – m\) for all feasible solution quadruples \(x\), \(y\), \(u\), \(v\). Moreover, any such quadruple for which \(m = M\) must include the optimal decision vectors \(x^*\) and \(u^*\) for both problems. This is the famous duality theorem of linear programming, which leads more or less directly to all manner of pivoting algorithms for solving linear programs, matrix games, and other computer-friendly problems.

By considering differentials  \(dm = \sum_{i}m_{x_i}dx_{i}, \ldots\), the duality theorem can even be used to deduce the famous Kuhn–Tucker conditions of nonlinear programming, the result for which Kuhn is perhaps best known. It turned out later that the same conditions––though unpublished––had been discovered in 1939 by William Karush, a master’s-degree candidate at the University of Chicago. As a result, the conditions are more properly known as the Karush–Kuhn–Tucker optimality conditions. After Karush, but before Kuhn and Tucker, Fritz John discovered a slightly more general set of optimality conditions, which hold even when the “constraint qualifications” postulated by Karush, Kuhn, and Tucker are violated. In later years, Kuhn made an extended effort to identify and acknowledge any and all claims of priority.1 

Kuhn’s favorites among his achievements include the perhaps less well-known “decision-tree” definition of a game. It is little known only because most interested parties––including a surprising number of professional game theorists––are unaware that the definition given by von Neumann and Morgenstern is quite different, being less succinct than Kuhn’s. So quickly and completely did Kuhn’s definition eclipse the original that the latter is now all but forgotten.

Another of Kuhn’s pet results was the so-called “Hungarian method” of solving the “assignment problem,” which asks for the allocation of \(n\) workers to \(n\) tasks that––given that worker \(i\) can complete task \(j\) at a cost of \(c_{ij}\) dollars––will finish the work most affordably. He called the method “Hungarian” because Dénes Kőnig and Jenő Egerváry had used it many years earlier to treat specific problems. In 2004, the editors of the journal Naval Research Logistics selected Kuhn’s 1955 paper on the method as the paper “best representing the journal since its founding in 1954.” “This pioneering paper,” they wrote, “set a style for both the content and the exposition of many other algorithms in combinatorial optimization, and also directly inspired the primal–dual algorithm for more general linear optimization problems.”

James Munkres revisited Kuhn’s algorithm in 1957, observing that the computational complexity is \(O(n^{4})\); it was improved later by J. Edmonds and R.M. Karp to \(O(n^{3})\). Then, in 2006, it was discovered that Jacobi (1804–1851) had also solved the assignment problem, and that his solution had been published posthumously (in the original Latin) in 1890. With his accustomed grace, Kuhn responded to the discovery by presenting a seminar at Concordia University titled “The Hungarian Method for the Assignment Problem and How Jacobi Beat Me by 100 Years.”

Harold was a charter member of SIAM––which was incorporated on April 12, 1952––and served as the organization’s third president (1954–1955). In May 2009, he was named to the inaugural group of Fellows of SIAM, for seminal contributions to game theory and to linear and nonlinear programming, and for leadership of SIAM in its early years.

In the early 1950s, with the encouragement of SIAM founder Ed Block, Harold took charge of a series of well-attended meetings held in and around Philadelphia. For a SIAM meeting in Pittsburgh at the end of 1954, in conjunction with a joint meeting of the American Mathematical Society, the Mathematical Association of America, and the Association for Symbolic Logic, Harold arranged for three SIAM lectures––two to be delivered by friends of his at no cost to the society––on cutting-edge topics of the day. One of the friends was Herbert Simon, then teaching at Carnegie Tech, who discussed  the command and control of industrial operations; Simon later received a Nobel Prize in economics.

In the spring of 1970, following President Nixon’s incursion into Cambodia, student unrest came to a head. At Princeton, with round-the-clock teach-ins occurring in the main gymnasium, class attendance declined to the point that final exams had to be cancelled. Harold’s ability to listen––together with his longstanding interest in civil liberties––made him an effective liaison between angry elements of the student body and the embattled administration. He went on to serve on the Committee of the Structure of the University, which designed the present-day Council of the Princeton University Community, a forum offering diverse campus groups a voice in the governance of the university.

At about the same time, Harold became a principal in the consulting firm Mathematica. Eventually acquired by Martin Marietta, the firm was located in Princeton (and had nothing to do with the Wolfram product of the same name). As a director, Harold managed projects for the Atomic Energy Commission, the Arms Control Agency, and the Department of Transportation.

Harold’s son Nick relates that, perhaps because of preoccupation with matters of national concern, Harold was occasionally guilty of procrastination. Indeed, when Princeton University Press decided to bring back its multi-volume Annals of Mathematics series in “print on demand” format, they had trouble locating a copy of Volume 37: Lectures on the Theory of Games, by Harold W. Kuhn. Volumes 36 and 38 had appeared in 1956, but number 37 was nowhere to be found. It turned out that Harold had never returned the page proofs! The book was duly published in 2003, 47 years after its companion volumes. Though records are made to be broken, that one seems likely to last!

Harold was a gifted lecturer whose undergraduate course on linear and nonlinear programming was cross-listed in the mathematics and economics departments at Princeton and was regularly numbered among the best on campus by the (often acerbic) student newspaper. He edited and/or co-edited numerous volumes of conference proceedings and was an active organizer of international conferences. In particular, he teamed with G.P. Szego to direct NATO International Summer Schools on Mathematical Systems Theory (1968) and Differential Games (1970) and directed a NATO Advanced Study Institute on Games with Incomplete Information and Bounded Rationality (Capri, 1987).

He was also asked to convene a special seminar on the work of John Nash in conjunction with the Nobel Award Ceremonies in Stockholm in 1994, having lobbied long, hard, and effectively for Nash to receive the honor. He then served as a technical adviser on the movie A Beautiful Mind, which was based loosely––too loosely, in Harold’s forthright opinion––on Sylvia Nasar’s book of the same name.

He is survived by his wife, Estelle, sons, Clifford, Nicholas, and Jonathan, six grandsons, and one granddaughter. Memorial donations can be made to the American Civil Liberties Union, of which Harold was a longtime supporter. 

1Kuhn’s piece, “Nonlinear Programming: A Historical Note,” appeared in History of Mathematical Programming: A Collection of Personal Reminiscences, edited by J.K. Lenstra, A.H.G. Rinnooy Kan, and A. Schrijver (CWI North Holland, 1991).

James Case writes from Baltimore, Maryland.

blog comments powered by Disqus