John Nash and the theory of games

John Forbes Nash and his wife Alicia nashwere tragically killed in a car crash on May 23, having just returned from a ceremony in Norway where John Nash received the prestigious Abel Prize in Mathematics (which, along with the Fields Medal, is the closest thing mathematics has to a Nobel Prize). Nash’s long struggle with mental illness, as well as his miraculous recovery, are depicted vividly in Sylvia Nasar’s book “A Beautiful Mind” and the Oscar-winning film which it inspired. In this post, I want to give a brief account of Nash’s work in game theory, for which he won the 1994 Nobel Prize in Economics. Before doing that, I should mention, however, that while this is undoubtedly Nash’s most influential work, he did many other things which from a purely mathematical point of view are much more technically difficult. Nash’s Abel Prize, for example (which he shared with Louis Nirenberg), was for his work in non-linear partial differential equations and its applications to geometric analysis, which most mathematicians consider to be Nash’s deepest contribution to mathematics. You can read about that work here. Continue reading

The Mathematics of Marriage

linking-wedding-ringsIt’s been a while since my last blog post — one reason being that I recently got married.  In honor of that occasion, and my return to math blogging, here is a post on Hall’s Marriage Theorem.

Consider the following game of solitaire: you deal a deck of cards into 13 piles of 4 cards each, and your goal is to select one card from each pile so that no value (Ace through King) is repeated.  It is a beautiful mathematical fact that this can always been done, no matter how the cards were originally dealt!

We will deduce this from a more general result due to Philip Hall commonly known as Hall’s Marriage Theorem.  Suppose you are given finite sets A_1, A_2,\ldots, A_n and you wish to find distinct elements x_1 \in A_1,\ldots, x_n \in A_n.  (In our solitaire example, take A_j to be the values of the cards in the j^{\rm th} pile.)  Such a collection is called a transversal or SDR (system of distinct representatives).  Under what conditions is this possible?  Well, for a transversal to exist it is necessary that for each subset J \subset \{ 1,\ldots, n \}, the set A_J:= \bigcup_{j \in J} A_j contains at least \#J elements.  Hall’s theorem asserts that these conditions are also sufficient. Continue reading