While I was doing some research on machine learning, I unexpectedly came across an old economics problem that I hadn’t seen in a long time — the Nash Bargaining Problem. Suppose Bill and Jack have some items. Each item has a different utility to each man, for example, Bill values a ball at 2 utils but Jack values the ball only as 1 util. How can the two men swap some of their items in a “good” way? (Note: I abuse terminology in this blog post, using normal words instead of those used by economists).

One possible approach is to use the Nash Bargaining solution. It is best explained by example. I’ll use the original example that Nash presented in his 1950 paper “The Bargaining Problem”. See the screenshot of an Excel spreadsheet below.

First, the problem sets up an initial state. Bill has a book, whip, ball, bat, box. He values these as 2 + 2 + 2 + 2 + 4 = 12 utils. Jack has a pen, toy, knife, hat with value 1 + 1 + 2 + 2 = 6 utils. The Nash Solution is for Bill to give to Jack the book, whip, ball, bat, and for Jack to give to Bill the pen, toy, knife.

After the swap, Bill values his items as 4 + 10 + 4 + 6 = 24 utils and so his utility increase is +12. After the swap, Jack values his items as 2 + 4 + 2 + 1 + 2 = 11 and so his utility increase is +5.

Notice that a key idea here is that Bill and Jack value items very differently.

The Nash Solution is the exchange of items that maximizes the product (not the sum) of the increases in utility. For this exchange, the product is 12 * 5 = 60. As it turns out, there is no other exchange of items that will produce a greater product of utility increase.

*Here are screenshots of two pages from the original 1950 research paper by John F. Nash, Jr. Whenever possible, I like to read source material because it’s almost always shorter and more clear than follow-up papers.*

The Excel sheet has a second example where Bill gives to Jack just the book (which Jack values highly), and Jack gives to Bill just the pen (which Bill values highly). Bill’s increase in utility is +8 and Jack’s increase is +3 so the product of the increases is 8 * 3 = 24 which isn’t as good as the first exchange of items.

Nash Bargaining is very closely related to an idea called Nash Social Welfare where the problem is to divide up (allocate) a collection of resources to a group of people in a way that is “fair”. I’ll write up an example of Nash Social Welfare soon because it’s an interesting problem.

Well, there’s a lot more to Nash Bargaining but the first step when trying to understand anything is to understand exactly what the problem is. Nash’s original analysis used classical mathematical geometry (as you can see in the screenshot of the pages above). This was well before computers were available to most researchers. I’d probably tackle the problem using a machine learning technique such as greedy agglomeration or evolutionary optimization instead. Maybe I’ll code up the Nash Bargaining Problem example someday.

*Here are three images from a Louis Vuitton fashion show in Paris. I don’t know anything about fashion but I like the classical geometry. Interesting how the models are all paired up. I’m not a fan of pair programming in most software development scenarios, but the pair modeling that’s going on here is very clever.*

Cool!!! π

It would be great to see Nash Bargaining example with a greedy agglomeration as ML approach. Both techniques was unknown to me. For the greedy agglomeration I couldn’t find good material, bad google skills from me?