Nash's Bargaining Problem (1950)
Discover more from Privatdozent
Just before John Nash made his breakthrough discovery of the Nash equilibrium, he wrote his first paper on another problem later to be known as Nash’s bargaining game. Nash’s bargaining game is a study of cooperative bargaining and the demonstration of a unique solution to a two-person bargaining problem (Nash, 1950). Stated simply, the setup for the bargining problem is as follows:
Two players demand a portion of some good (usually some amount of money). If the total amount requested by the players is less than that available, both players get their request. If their total request is greater than that available, neither gets their request.
Nash’s axiomatic approach proposes that a solution to the latter case must satisfy the axioms of:
Invariance (INV), such that a transformation of the utility function that maintains the same ordering over preferences should not alter the outcome of the bargaining process;
Weak Pareto efficiency (WPO), such that players never agree on an outcome s when there is an outcome t in which both are better off;
Independence of irrelevant alternatives (IIA), such that if the players are choosing between two outcomes s and t, where s is preferred, and an alternative outcome r is introduced, then if only preferences of r change, the outcome cannot lead to t being chosen over s;
Symmetry (SYM), such that if the players are indistinguishable, the agreement should not discriminate between them;
Nash proved that the solutions satisfying these axioms are exactly the points (x,y) in F which maximize the following expression:
(u(x) — u(d)) (v(y) — v(d))
where u and v are the utility functions of players 1 and 2, respectively, and d is a disagreement outcome. The solution consists of each player getting their status quo payoff (i.e., non-cooperative payoff) in addition to a share of the benefits occurring from cooperation.
This week’s newsletter is about Nash’s first result, his first foray into von Neumann and Morgenstern’s newly founded field of game theory and the inspiration to his future work on the Nash equilibrium.
Background
John F. Nash Jr. (1928-2015) entered graduate school when he was 20 years old, three years after leaving his hometown of Bluefield, West Virginia. While still in—what would have been—his junior year at Carnegie Institute of Technology in 1948, Nash had been accepted to Harvard, Princeton, Chicago and Michigan University, the top four graduate-level mathematics programs in the United States at the time. Although Harvard had been his first choice (on account of its reputation, social standing and faculty), Nash’s mediocre performance on the esteemed Putnam Competition had lead Harvard to offer him a slighly less generous scholarship than did Princeton. Nash’s academic advisors at Richard Duffin (1909-1996) and John Synge (1897-1995) at Carniegie both pushed for Nash to choose Princeton. Its “hothouse milieu of pure mathematicians (topologists, algebraists, number theorists)” likely seemed like the perfect place for “a young Gauss”, which one of them had called him (Nasar, 1998).
On the Princeton side, the chairman of the mathematics department Solomon Lefschetz (1884-1972) was equally eager in persuading Nash, eventually offering a John S. Kennedy Fellowship of $1,150 per year (approx $13,200 in 2021 adjusting for inflation).
“We like to catch promising men when they are young and open-minded”
- Excerpt from a letter from Solomon Lefschetz to Nash
Princeton’s proximity to his hometown of Bluefield was an additional consideration according Nash’s Nobel autobiography. These factors, adding to the encouragement both of his supervisors at Carnegie and Lefschetz’s personal appeal above, lead Nash to decide on Princeton, leaving for New Jersey in the summer of 1948. Duffin’s letter of recommendation to Lefschetz famously included only had a single sentence on Nash’s abilities:
“He is a mathematical genius”
The letter, as well as Synge’s letter of recommendation are both included below:
At Princeton University (1948–51)
Nash entered graduate school when he was 20 years old, three years after leaving Bluefield for Carnegie. At the time, Princeton’s math department was filled with brilliant minds, lead by Lefschetz who jointly with Ralph Fox (1913-73) and Norman Steenrod (1910-71) headed research on topology, first in the country. Emil Artin (1898-1962) lead algebra. Student of Lefschetz, Albert W. Tucker (1905-95) lead game theory which at that point was a newly established discipline entirely, invigorated by the publication of the book Theory of Games and Economic Behavior by John von Neumann (1903-1957) and economist Oskar Morgenstern (1902-1977) in 1944.
Princeton’s math department, housed in Fine Hall, in the 40s and 50s has since become somewhat legendary in mathematical circles. As Nasar recounted in 1998, “Fine Hall is, I believe, the most luxurious building ever devoted to mathematics, [according to] one European émigré. [..] A country club for math, where you could take a bath.”.
“Its cornerstone contains a lead box with copies of works by Princeton mathematicians and the tools of the trade — two pencils, one piece of chalk, and, of course, an eraser. Designed by Oswald Veblen [...] it was meant to be a sanctuary that mathematicians would be ‘loath to leave’. The dim stone corridors that circled the structure were perfect for both solitary pacing and “mathematical socializing. The nine “studies” — not offices! — for senior professors had carved paneling, hidden file cabinets, blackboards that opened like altars, oriental carpets, and massive, overstuffed furniture. [...] Each office was equipped with a telephone and each lavatory with a reading light.” Its well-stocked third-floor library, the richest collection of mathematical journals and books in the world, was open twenty-four hours a day. Mathematicians with a fondness for tennis (the courts were nearby) didn’t have to go home before returning to their offices — there was a locker room with showers.”
- Excerpt, A Beautiful Mind* by Sylvia Nasar (1998)
Nash was part of the clique of mathematicians and graduate students advancing the nascent discipline of game theory under Tucker, in the purest mathematical sense, i.e. largely uninterested in relating their research to applications in the real world. According to economist and personal friend of Nash at the time, Morgenstern’s student Martin Shubik (1926-2018):
"The graduate students and faculty in the mathematics department interested in game theory were both blissfully unaware of the attitude in the economics department, and even if they had known it, they would not have cared.. The contrast of attitudes between the economics department and the mathematics department was stamped on my mind soon after arriving at Princeton. The former projected an atmosphere of dull business-as-usual conservatism of a middle league conventional Ph.D. factory; there were some stars but no sense of excitement or challenge. The latter was electric with ideas and the sheer joy of the hunt. Psychologically they dwelt on different planets. If a stray ten-year-old with bare feed, no tie, torn blue jeans and an interesting theorem had walked into Fine Hall at tea time, someone would have listened. When von Neumann gave his seminar on his growth model, with few exceptions, the serried ranks of Princeton Economics cold scare forbear to yawn."
- Martin Shubik, 1992- Excerpt, Finding Equilibrium* by Düppe and Weintraub (2014 p. 94)
The head of the group, Tucker, would go on to supervise virtually all of the future top game theorists at Princeton, including David Gale (1921-2008) and 2012 Nobel laureate Lloyd Shapley (1923-2016), in addition to, of course, Nash.
The Bargaining Problem (1949)
Nash’s first journal paper (written prior to his work on the Nash equilibrium) — also in game theory — regarded the classic economic problem of bargaining. The problem had previously been investigated by a number of scholars (Cournot, Bowley, Fellner among others) for various purposes including investigations of bilateral monopoly (Nash, 1950).
Nash’s paper describes a bargaining situation where two individuals have the opportunity for mutual benefit, but no action taken by one of the individuals (without consent) can unilaterally affect the well-being of the other. Think of the classic “divide and choose protocol” of two people trying to divide a cake evenly, where one carves and the other chooses which piece he or she wants, the so-called envy-free cake-cutting procedure.
Nash’s paper is positioned to be a theoretical discussion of such bargaining situations, as well as to provide a definitive “solution” (meaning determine the amount of satisfaction each individual should expect to obtain) under certain conditions and other “idealizations”. Such idealizations include the assumption that the two individuals are rational and can accurately compare their preferences for various things, have equal bargaining skills and complete information about the preferences of the other person. Nash’s treatment employs the concept of utility as developed in von Neumann and Morgenstern’s book. It also employs the concept of expectation in determining what various players’ payoffs will be, given various strategies. In his paper, Nash uses as an illustration a man named Mr. Smith who knows he will be given a Buick tomorrow, and so that he may be said to have “Buick expectation”. Similarly, he may have “Cadillac expectation”. If he knew that tomorrow a fair coin would be tossed to decide whether he would get a Buick or a Cadillac, we can say he had 50% Buick and 50% Cadillac expectation.
Nash provides sufficient assumptions for the development of a utility theory for a single individual in such scenarios and proceeds to differentiate his paper from that presented in Theory of Games and Economic Behavior* (1944). In his view, the theory there comes short in that it does not attempt to find values for each person’s valuations of the opportunity to engage in a game, unless that games is zero-sum. Nash then goes on to derive values for the anticipation of players in such two-person non-zero-sum games:
We may define a two-person anticipation as a combination of two one-person anticipations. Thus we have two individuals, each with a certain expectation of his future environment. We may regard the one-person utility functions as applicable to the two-person anticipations, each giving the result it would give if applied to the corresponding one-person anticipation which is a component of the two-person anticipation. A probability combination of two two-person anticipations is defined by making the corresponding combinations for their components. Thus if [A, B] is a two-person anticipation and 0 ≤ p ≤ 1, then
p[A,B] + (1 - p)[C,D] will be defined as [pA + (1-p)C, pB + (1-p)D]
Nash defines the utility functions u₁, u₂ of two individuals and c(S) as the solution point in a set S which is compact, convex and includes the origin. He puts forth the necessary assumptions and show that these conditions require that the solution be the point of the set in the first quadrant where u₁u₂ is maximized. The compactness of the set guarantees its existence and its convexity guarentees its uniqueness.
Example of a bargaining problem (Nash, 1950)
Let us suppose that two intelligent individuals, Bill and Jack, are in a position where they may barter goods but have no money with which to facilitate exchange. Further, let us assume for simplicity that the utility to either individual of a portion of the total number of goods involved is the sum of the utilities to him of the individual goods in that portion. We give below a table of goods possessed by each individual with the utility of each to each individual. The utility functions used for the two individuals are, of course, to be regarded as arbitrary.Bill's good, Bill's utility and Jack's utility:
(book, 2, 4), (whip, 2, 2), (ball, 2, 1), (bat, 2, 2), (box, 4, 1)Jack's goods, Bill's utility and Jack's utility:
(pen, 10, 1), (toy, 4, 1), (knife, 6, 2), (hat, 2, 2)The graph for the bargaining situation turns out to be a convex polygon in which the point where the product of the utility gains is maximized is at a vertex and where there is but one corresponding anticipation, which is:
Bill gives Jack: book, whip, ball and bat
Jack gives Bill: pen, toy and knife
The graph depicting the bargain from Nash’s paper is as follows:
How Nash arrived at the result remains unclear. Nash’s close friend and co-editor of his 2002 autobiography The Essential John Nash*, Harold Kuhn (1925-2014), recalls about the paper: “It is my recollection that it had been sent to von Neumann during Nash’s first year as a graduate student and that Nash made an appointment to remind von Neumann of its existence. In this scenario, it had been written at Carnegie Tech as a term paper in the only course in economics that Nash ever took.”, adding however that “Nash’s current memory differs from mine; in a luncheon with Roger Meyerson in 1995, he expressed the opinion that he had written the paper after his arrival at Princeton.
“Whatever the true history of the paper, the examples suggest that it was written by a teenager; they involve bats, balls, and penknives. What is certain is that Nash had never read the works of Cournot, Bowley, Tintner, and Fellner cited in the paper’s Introduction.”
— Harold Kuhn
Nash was 20 years old when he arrived in Princeton. His paper was eventually published in the prestigious journal Econometrica in 1950:
Nash (1950). The Bargaining Problem. Econometrica 18(2), pp. 155-162.
Meeting John von Neumann
Although somewhat in opposition to von Neumann and Morgenstern’s work on cooperative game theory, Nash’s results establishing a foundation for non-cooperative game theory clearly had its origins in the formers’ work (indeed, illustrative of this, in 1978 Nash was awarded the John von Neumann Theory Prize for his discovery of the Nash equilibrium).
Only one documented account of communication between Nash on von Neumann can now be found, although there were surely many more which are now lost to time. According to Nasar, Nash went to talk to von Neumann a few days after he passed his general examination at Princeton in 1949, prior to his definition of the Nash equilibrium. As she writes:
“He wanted, he had told the secretary cockily, to discuss an idea that might be of interest to Professor von Neumann. It was a rather audacious thing for a graduate student to do. [...] But it was typical of Nash, who had gone to see Einstein the year before with the germ of an idea. [...] He listened carefully, with his head cocked slightly to one side and his fingers tapping. Nash started to describe the proof he had in mind for an equilibrium in games of more than two players. But before he had gotten out more than a few disjointed sentences, von Neumann interrupted, jumped ahead to the yet unstated conclusion of Nash’s argument, and said abruptly, “That’s trivial, you know. That’s just a fixed point theorem.”
- Excerpt, "A Beautiful Mind" by Sylvia Nasar (1998)
von Neumann, in other words, did not see the value in Nash’s concept of non-cooperative game theory. Nash himself however would later defend the great man’s reaction in a letter to historian Robert Leonard, stating, characteristically analytically, “I was playing a non-cooperative game in relation to von Neumann rather than simply seeking to join his coalition. And of course, it was psychologically natural for him not to be entirely pleased by a rival theoretical approach”.
Both von Neumann and Morgenstern ultimately did however provide Nash with valuable guidance, and in the published version of his paper Nash ensures to acknowledge the role of both, writing “The author wishes to acknowledge the assistance of Professors von Neumann and Morgenstern who read the original form of the paper and gave helpful advice as to the presentation.”
I hope you enjoyed this week’s brief newsletter!
Thank you, as always, for being a subscriber.
Sincerely,
Jørgen
Related Privatdozent Essays
John F. Nash Jr.’s Game of “Hex”, October 10th 2021
John von Neumann’s Minimax Theorem, March 26th 2021
Oskar Morgenstern’s Transformation, August 27th 2021
David Hilbert’s Influence on Economics, November 26th 2021
The Unparalleled Genius of John von Neumann, May 19th 2021
About
The Privatdozent newsletter currently goes out to 8,193 subscribers via Substack.
References
Düppe, T. & Weintraub, E.R. 2014. Finding Equilibrium*. Princeton University Press.
Nasar, S. 1998. A Beautiful Mind. Simon & Schuster.
Nash, J. F. 1950. The Bargaining Problem. Econometrica 18(2), pp. 155-162.
von Neumann, J. & Morgenstern, O. 1944. Theory of Games and Economic Behavior. Princeton University Press.