posted by Rakesh Vohra, 27 January 2015
Harold Kuhn passed away July 2nd, 2014. Members of the Society will recognize the name because of the integral role he played in the development of Game Theory. Robert Aumann, former president of the Society, writes:
“One can’t call him game theory’s father and mother – those were von Neumann and Morgenstern (respectively). But continuing with the family analogy, one might liken him to a particularly family-minded older brother. Not only did he make fundamental research contributions which continue to shape the field to this day, he contributed greatly – and very importantly – to the social fabric of the discipline.”
Born in 1925, he came of age in the Princeton mathematics department when Giants, one is reliably informed, roamed the earth. Among his fellow students were John Nash, David Gale, Martin Shubik and Lloyd Shapley, John Milnor and John McCarthy. Genius, as plentiful as weeds.
Kuhn is famous for his contributions to both game theory and mathematical programming. I will recall three of them here. First, the paper with William Tucker and David Gale establishing the connection between the duality theorem of linear programming and equilibria of zero sum games. Second, Kuhn invented extensive form games with information sets and established the equivalence between behavior strategies and mixed strategies in extensive form games with perfect recall. Like the first result, Kuhn’s Theorem (published in 1953) is so much a part of our mental furniture that it is a staple of homework sets in Game Theory classes. Third, the Kuhn-Tucker-Karush theorem for optimality. Members of the Society will recall that Karush’s name did not always grace this theorem even though he had arrived at it in 1939 (Kuhn-Tucker is from 1951). How Kuhn responded is an example to us all. He wrote Karush:
“In March I am talking at an AMS Symposium on ‘Nonlinear Programming – A Historical View.’ Last summer I learned through reading Takayama’s Mathematical Economics of your 1939 Master’s Thesis and have obtained a copy. First, let me say that you have clear priority on the results known as the Kuhn-Tucker conditions (including the constraint qualification). I intend to set the record as straight as I can in my talk.”
The letter closes with this paragraph:
“Dick Cottle, who organized the session, has been told of my plans to rewrite history and says ‘you must be a saint’ not to complain about the absence of recognition. Al Tucker remembers you from RAND, wonders why you never called this to his attention and sends his best regards.”
Karush’s reply, 6 days later, equally gracious:
“Thank you for your most gracious letter. I appreciate your thoughtfulness in wanting to draw attention to my early work. If you ask why I did not bring up the matter of priority before, perhaps the answer lies in what is now happening – I am not only going to get credit for my work, but I am going to be crowned a “saint”.’
Interestingly, one of Kuhn’s contributions to optimization was the Hungarian algorithm for the assignment problem (1955). This algorithm anticipated later primal-dual methods for optimization and was inspired by the work of Kőnig and Egerváry (hence Hungarian). It was discovered quite recently that Carl Jacobi (1890, posthumously) had derived the same algorithm. No doubt Harold Kuhn, wherever he might be, is setting the record straight.