Shulou(Shulou.com)11/24 Report--

John F. Nash Jr. 1928-2015) the most famous breakthrough was the discovery of Nash equilibrium, but before that, he wrote a paper on another problem, Nash bargaining. The Nash bargaining problem is a study of cooperative bargaining, which proves the only solution to the bargaining problem between two people (Nash,1950). The settings in the bargaining question can be briefly summarized as follows:

Each of the two players asks for some property (usually some money). If the sum of the two people's demands is less than the total amount of property, then both people can get what they want; if the sum exceeds the total amount of property, then they have nothing.

Nash proposed an axiomatic solution to the latter situation, and this article will introduce the first achievements of Nash when he first set foot in the field of game theory newly discovered by von Neumann and Morgenstern, which provides inspiration for future work on Nash equilibrium.

1. Invariance: the utility function should remain unchanged with the change of preference before and after bargaining.

two。 Weak Pareto effective: if both people can benefit more from the result s, then the player cannot agree to the other allocation t.

3. Independent selection independence: if the player chooses between the two solutions s and t, where s is the first choice; if an alternative solution r appears, t will not exceed s as the solution unless r's preference changes.

4. Symmetry: if there is no difference between players, there should be no favouritism in reaching an agreement between them.

Nash proved that the solution satisfying the above axiom conditions (x _ () y) can exactly make the following expression F take the maximum value: (u (x)-u (d)) (v (y)-v (d))

Among them, u and v are the utility functions of player 1 and player 2 respectively, and d is the result of the inability to reach an agreement. This solution includes current gains (non-cooperative gains) and cooperative benefits for each player.

The 20-year-old Nash entered college three years after leaving his hometown in Bloomfield, West Virginia. In 1948, when he was a junior at Carnegie Institute of Technology, he was admitted to Harvard, Princeton, Chicago and the University of Michigan, four of the top math programs in the United States. Although Nash's first choice is Harvard University, which is relatively more famous, social status and faculty, his scholarship at Harvard is slightly lower than Princeton because of his mediocre performance in the highly respected Putnam competition. At the same time, Nash's academic mentors at Carnegie, Richard Duffin (Richard Duffin,1909-1996) and John L. Synge,1897-1995, both strongly recommended him to choose Princeton, one of whom even called him "Little Gauss", believing that Princeton was "the cradle of pure mathematics (topology, algebra, and number theory)" and matched him perfectly (Nasar, 1998).

On the Princeton side, mathematics chairman Solomon Lefschitz (Solomon Lefschetz,1884-1972) was also eager to convince Nash to offer a Kennedy scholarship of $1,150 a year (equivalent to $13,200 in 2021):

We like to hold on to promising people while they are young and open-minded.

-- Lefschetz's letter to Nash

In his Nobel Prize-winning memo, Nash mentioned that proximity to his hometown of Brufeld was also a factor in choosing Princeton. So for a variety of reasons, Nash left New Jersey in the summer of 1948 and chose Princeton with the encouragement of Carnegie's mentor and the personal strong welcome of Lefschetz.

Duffin's letter of recommendation to Lefschetz contained only one sentence describing Nash's abilities, which later became very famous:

He is a genius in mathematics.

Letters of recommendation from Duffin and Singh are shown below:

Left: a letter of recommendation from Duffin, Nash's thesis mentor at Carnegie Tech, sent to Professor Solomon Lefschetz at Princeton University Right: letter of recommendation written by Singh, head of the mathematics department of Carnegie Institute of Technology (Picture Source: Princeton University Archives). When Nash left his hometown for Carnegie at the age of 20 to go to Carnegie, the Princeton mathematics department was full of smart minds, and the dean, Lefschetts and Ralph Fox (Ralph Fox,1913-1973) and Norman Stingrode (Norman Steenrod,1910-1971), took the lead in carrying out topology research in the United States. Emil Artin (Emil Artin,1898-1962) majored in algebra, while Albert W. Tucker,1905-1995, a student of Lefschetz, majored in game theory, a discipline that only emerged after Von Neumann (John von Neumann,1903-1957) and economist Oskar Morgenstern,1902-1977 published Game Theory and Economic behavior in 1944.

Princeton University's mathematics department, located in a building called Fine Hall, was synonymous with legends in mathematical circles in the 1940s and 1950s. As Nasar Sylvia Nasar described in 1998:

(as one European American said) I think Fine Hall is the most luxurious building for mathematical research, a math country club that can go on vacation.

Its cornerstone, designed by Oswald Veblen, contains copies of the work of Princeton mathematicians and lead boxes of some common tools in the industry: two pencils, a piece of chalk and, of course, an eraser.

"it represents the sanctuary of mathematicians, and the corridors surrounded by dark stones are suitable for both walking alone and 'socializing in mathematics'. The nine studies for senior professors-- not offices-- have carved slates, hidden cabinets, blackboards, oriental carpets and heavy upholstered furniture."

"each office is equipped with a telephone and a bathroom with reading lights; the library on the third floor is open all day with the richest math journals and books in the world; tennis mathematicians do not have to go home before going back to the office (there is a tennis court nearby) because it has a changing room with a shower."

Nasar's Beautiful mind (1998)

At that time, Nash was one of the members of a school led by Tucker to promote the development of early game theory. In the sense of pure mathematics, they basically did not care about the application of research content in the real world. According to Shubik (Martin Shubik,1926-2018), an economist, a good friend of Nash and a student of Morgan Stern:

At that time, math students and staff were so immersed in the happiness of game theory that they were completely unaware of the economics department's attitude towards it, and of course, even if they knew, they would not care. Not long after I stayed at Princeton, the distinct difference between the economics department and the mathematics department was rooted in me. The economics department has an atmosphere of conservatism that nurtures regular doctoral factories and business as usual, with stars without passion and challenge, while the latter is lit up by inspiration and the pure pleasures of hunting. Psychologically, they seem to come from different planets. If a 10-year-old homeless kid in bare feet and ragged jeans walks into Fine Hall at tea time with a very interesting theory, someone will listen; but when Feng Neumann conducts a seminar on growth models, with a few exceptions, Princeton's legion of economists are sure to be so bored as to yawn.

-- Shubik (see D ü ppe and Weintraub, Finding Equilibrium*, 2014 p. 94)

Tucker, the leader of the school, continues to guide Princeton's future top game theorists, including David Gore (David Gale,1921-2008), 2012 Nobel laureate Lloyd Shapley (Lloyd Shapley,1923-2016) and, of course, Nash.

Bargaining (1949) before studying the Nash equilibrium, Nash published his first journal paper, also on game theory, regarding classical economic issues as a bargaining process. Before this, many scholars (including Cournot, Bowley, Fellner and others) have studied this issue from different angles, including bilateral monopoly investigation.

Left: Nash as a student; right: Nash's 1950 paper bargaining (The Bargaining Problem. Econometrica 18 (2), pp. ) Nash's article describes a bargaining situation in which both people have the opportunity to benefit each other, but no one can unilaterally influence the profit of the other without permission. Similar to the classic "partition and choice agreement" situation: two people need to distribute a cake fairly, then one of them can cut the cake, and the other can first decide which one he wants. This is the jealousy-free cake distribution mechanism.

Nash's paper is based on such a bargaining situation for theoretical analysis, at the same time under specific conditions or other "idealized conditions" to give a definite "solution", that is, to determine the income to meet individual expectations. Such idealized conditions include the assumption that two individuals are rational and can have accurate preference perception of various items, have the same bargaining power, and fully understand each other's preference information.

Nash's solution uses the concept of utility developed from the books of von Neumann and Morgan Stern, as well as the concept of expectation to define the benefits recognized by different players under a given strategy. In Nash's article, he assumes that there is a man, Xiao Ming, who knows that he will get 100 yuan the next day, then it can be said that he has an expectation of 100 yuan; similarly, he can have an expectation of 200 yuan. If he knows that he will flip a fair coin the next day to decide whether he gets one hundred or two hundred, then it can be said that he has an expectation of "50% one hundred and 50% two hundred".

Nash provides sufficient assumptions about the individual utility theory in this case and distinguishes the situations proposed in his 1944 paper Game Theory and Economic behavior. He believes that the paper does not separately estimate the value of everyone's participation in the game, unless the game is zero-sum (the benefits of both sides add up to zero). So for a two-player non-zero-sum game, Nash deduces the expected values of the players:

First of all, a combination of two-person expectations is defined as two single-person expectations: if there are two players who have accurate expectations for the future, and one-person expectations can constitute two-person expectations, then the single-person utility function can be used to find the expected value of the two-person utility function. In this way, if there are two players who have accurate expectations for the future, and the expected value of a single player is the element that makes up the expectation of both, then we can use the utility function of the single player and their respective probabilities to calculate the expected value of the two:

If [A ≤ B] represents a double expectation and 0 ≤ p expectation 1, then p [A ≤ B] + (1) [C] = [pA + (1 mi p) C, pB + (1 m p) D].

Nash defines the utility function of two individuals as the sum, and defines c (S) as the solution point in the compact convex set S containing the origin. First of all, he puts forward some necessary assumptions to ensure that the maximum solution falls in the first quadrant: the compactness of the set ensures the existence of the solution, while the convexity ensures that the solution is unique.

Figure 1 is from Nash's paper bargaining problem, which illustrates the single best point in the utility set S of player 1 and player 2. An example of bargaining (Nash, 1950) assumes that Xiaoming and Xiao Hong are two very smart people who have only goods to exchange, but no money for change. For the sake of simplicity, suppose that the utility of all the items obtained by a person is the sum of the effects of the goods in this part. The table below lists the ownership of each item and the utility for each person. The utility function units of the two individuals are arbitrary.

Goods owned by Xiaoming:

Xiao Ming's goods Xiao Ming's utility book 24 whips 22 balls 21 ball rackets 22 boxes 41 goods owned by Xiao Hong:

Xiao Hong's goods Xiao Ming's utility pen 101 toys 41 knives 62 hats 22 the image of the bargaining problem is a convex polygon, in which the maximum utility product is at a vertex, corresponding to the only expectation, where:

Xiao Ming gives Xiao Hong: books, whips, balls and rackets

Xiao Hong to Xiao Ming: pen, toy and knife.

Nash's drawing on this bargaining issue in his paper

Example: the solution point is located on the only tangent point of the first quadrant, rectangular hyperbola and optional set. It is not clear how Nash came to this result. His best friend, Harold Kuhn,1925 (Harold Kuhn,1925-2014), one of the authors of Nash's biography "The Essential John Nash" published in 2002, recalled the paper.

I remember it was sent to von Neumann in the first year after Nash graduated, and Nash reminded him of the existence of von Neumann. In this way, this article should be the only economics elective paper that Nash took when he was at Carnegie Tech.

But he added:

Nash's memory is different from mine, he said at a lunch with Roger Meyerson in 1995. He wrote the paper after he arrived at Princeton. Regardless of the true history of this article, the examples imply that the writer is a young man, because items include rackets, balls or pen knives and the like. To be sure, Nash had never read the work of Cournot, Bowley, Tyntner and Ferner mentioned in the citations of the paper.

-- Kuhn

Nash arrived at Princeton University at the age of 20 and finally published his paper bargaining in the famous journal Econometrics in 1950:

Nash (1950). The Bargaining Problem. Econometrica 18 (2), pp.

Communication with von Neumann although Nash's inference is to some extent contrary to the work of von Neumann and Morgan Stern on cooperative game theory, his foundation for non-cooperative game theory obviously comes from the work of his predecessors. Also inspired by this, Nash discovered the Nash equilibrium and won the John von Neumann Prize for Theory in 1978.

Only one record of the communication between Nash and von Neumann has been found in the existing documents, and it is certain that most of the rest have been lost over time. According to Nasar, Nash spoke to von Neumann just days after the 1949 Princeton exam-before he discovered the Nash equilibrium:

At that time, he proudly told his secretary that he was going to discuss an idea that would interest him with Professor Feng Neumann. For a graduate student, this is quite a bold thing.

... Of course, this is like what Nash would do. After all, he went to see Einstein with an idea the year before. He listened attentively, tapping his fingers and tilting his head from time to time. Nash began to describe the mental proof of the equilibrium of the game between more than two players.

Von Neumann interrupted him before he uttered more messy sentences and suddenly said to Nash inconclusively: "it's not interesting, it's just a fixed point theory."

Nasar's Beautiful mind (1998)

Von Neumann did not seem to see value in the concept of non-cooperative game theory discussed by Nash, but Nash later defended the great man's reaction in a letter to historian Robert Leonard, he analyzed:

I was playing a non-cooperative game with von Neumann, not just seeking to join his alliance; obviously, psychologically, he would not be completely satisfied with a competitive theory.

Even so, both von Neumann and Morgan Stern eventually gave Nash valuable guidance, thanking both in their published papers:

The author would like to thank Professor Feng Neumann and Professor Morgan Stern for their help, both of whom provided very helpful suggestions after reading the first draft of the paper.

reference

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.

Von Neumann, J. & Morgenstern, O. 1944. Theory of Games and Economic Behavior. Princeton University Press.

Author: junirgen Veisdal

Translation: zhenni

Revision: Tibetan idiots

Original link: Nash's Bargaining Problem (1950)

This article comes from the official account of Wechat: Institute of Physics, Chinese Academy of Sciences (ID:cas-iop). Author: junirgen Veisdal

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.