香港大学：From Nash to Nash’s Game Theory

From Nash to Nash's Game Theory Content --an explanation of the mathematics in the movie"A Beautiful Mind"and John Life of John Nash Nash's Nobel-winning theory Introduction to Game Theory Dr.Ng Tuen Wai Nash's Nobel-Prize Department of Mathematics, winning theory HKU Nash at HKU,2003 Who is John Nash When Nash applied to John Nash is an American graduate school at mathematician who was Princeton,his former born in 1928. teacher wrote only one line on his letter of He earned a doctorate recommendation:"This from Princeton University man is a genius". at the age of 22. He began teaching at MIT in 1951. Soon after.Nash met Alicia Larde ·In the late1950s, a 21-year-old physics major at MIT Nash left MIT because In 1957 they were married. of mental illness. ·It is a miracle that he can eventually recover twenty years later. LI口ANA5相 1

1 -- an explanation of the mathematics in the movie “A Beautiful Mind”and John Nash's Nobel-winning theory From Nash to Nash’s Game Theory Dr. Ng Tuen Wai Department of Mathematics, HKU Content „ Life of John Nash „ Introduction to Game Theory „ Nash’s Nobel-Prize winning theory Nash at HKU,2003 Who is John Nash ? John Nash is an American mathematician who was born in 1928. He earned a doctorate from Princeton University at the age of 22. When Nash applied to graduate school at Princeton, his former teacher wrote only one line on his letter of recommendation: "This man is a genius". • He began teaching at MIT in 1951. • Soon after, Nash met Alicia Larde, a 21-year-old physics major at MIT. • In 1957 they were married. • In the late 1950s, Nash left MIT because of mental illness. • It is a miracle that he can eventually recover twenty years later

In his 27 pages Ph.D thesis "Non- ■Inl994.Nash shared cooperative Games",Nash made very important contribution in establishing the the Nobel Prize in mathematical principles of Game Theory. Economics with John C.Harsanyi and Reinhard Selten In this thesis,Nash greatly extended the work of John von Neumann whose is the founder of Game Theory. What is Game Theory 1999 Steele prize for his Game theory is the study of mathematical works in pure mathematics. models on conflicts and co-operations between rational individuals. It studies the behavior of decision makers whose decisions affect each other. Game theory provides the language and framework for the discussion of problems in economics,social sciences,evolutionary biology,etc. John von Neumann John von Neumann Game theory was first Possibly the last true developed by the polymath.Also did mathematician John fundamental works in von Neumann in 1928 several branches of Born in 1903,Hungary pure mathematics and Involved in the theoretical physics. development of atomic His memory and the bombs. speed with which his Designed and built the mind worked were first computer. astounding. 2

2 • In his 27 pages Ph.D thesis "Non￾cooperative Games”, Nash made very important contribution in establishing the mathematical principles of Game Theory. • In this thesis, Nash greatly extended the work of John von Neumann whose is the founder of Game Theory. „ In 1994, Nash shared the Nobel Prize in Economics with John C. Harsanyi and Reinhard Selten. 1999 Steele prize for his works in pure mathematics. What is Game Theory ? „ Game theory is the study of mathematical models on conflicts and co-operations between rational individuals. „ It studies the behavior of decision makers whose decisions affect each other. „ Game theory provides the language and framework for the discussion of problems in economics, social sciences, evolutionary biology,etc. John von Neumann „ Game theory was first developed by the mathematician John von Neumann in 1928. „ Born in 1903, Hungary. „ Involved in the development of atomic bombs. „ Designed and built the first computer. John von Neumann „ Possibly the last true polymath. Also did fundamental works in several branches of pure mathematics and theoretical physics. „ His memory and the speed with which his mind worked were astounding

A story of von Neumann 向右走 Speed of the bee is 15 mp.h. 向左走 Someone asked him to solve the following problem. 10m.p.h. 10 m.p.h. Twenty miles apart A story of von Neumann Question:What total distance did the bee cover when the people meet First method:Calculate the distance the bee covers on each of its trips between the When the question was put to von Neumann,he two bicycles and finally sum the infinite solved it in an instant,and therefore disappointed series so obtained. the questioner: Second method:Observe that the bicycles ■“Oh,you must have heard the trick before" meet exactly an hour after they start so that s“What trick”,asked von Neumann,”all I did was fly had just an hour for his travel:the sum the infinite series." answer must therefore be 15 miles. John von Neumann Game Theory and Economics ■Game theory was first developed by John von Neumann in 1928.At Game theory studies how people that time,it was only behave in strategic situations,where considered as a branch the outcome for each player depends of pure mathematics. on the actions of all the players. In 1944.he and Oskar Since strategic interaction Morgenstern published the book“Theory of characterizes many economic Games and Economic situations,game theory has proved Behavior” very useful in economic analysis. 3

3 A story of von Neumann „ Someone asked him to solve the following problem. Twenty miles apart 10 m.p.h. 10 m.p.h. 向右走 向左走 Speed of the bee is 15 m.p.h. A story of von Neumann „ Question: What total distance did the bee cover when the people meet ? „ First method: Calculate the distance the bee covers on each of its trips between the two bicycles and finally sum the infinite series so obtained. „ Second method: Observe that the bicycles meet exactly an hour after they start so that fly had just an hour for his travel; the answer must therefore be 15 miles. „ When the question was put to von Neumann, he solved it in an instant, and therefore disappointed the questioner: „ “Oh, you must have heard the trick before !” “What trick”, asked von Neumann,”all I did was sum the infinite series.” John von Neumann „ Game theory was first developed by John von Neumann in 1928. At that time, it was only considered as a branch of pure mathematics. „ In 1944, he and Oskar Morgenstern published the book“Theory of Games and Economic Behavior”. Game Theory and Economics „ Game theory studies how people behave in strategic situations, where the outcome for each player depends on the actions of all the players. „ Since strategic interaction characterizes many economic situations, game theory has proved very useful in economic analysis

An example of a strategic Both newspapers can choose to cut situation in economics price or don't cut. If both newspapers choose don't cut Apple Daily and Oriental Daily are then each will earn 20 million dollars considering whether to have a price If one chooses don't cut and the war. other chooses cut price,then the newspaper choosing don't cut will Vs only earn 5 million,while the one choosing cut price can earn 30 報果 million dollars. If both newspapers choose cut price, Prisoner's Dilemma then each can earn 10 million dollars. ·John and Peter have been arrested for possession of guns.The police suspects that they Oriental Daily are going to commit a major crime. Cut Don't If no one confesses,they will both be jailed for 2 price cut years. Cut If only one confesses. 10,10 price 30,5 he'll go free and his Apple partner will be jailed for Daily Don't 10 years. 5,30 20.20 cut If they both confess,they both get 5 years. Matrix Representation Common features of the two of Prisoner's Dilemma examples Both have two players,say A and B. Peter Each player has two strategies,say C Don't and D. Confess confess There are four possible outcomes of the moves (C,C),(C,D)(D,C),(D,D). Confess 5,5 0,10 John Payoffs of each possible outcome are Don't 10.0 2,2 known to each player. confess ×

4 An example of a strategic situation in economics „ Apple Daily and Oriental Daily are considering whether to have a price war. Vs „ Both newspapers can choose to cut price or don’t cut. „ If both newspapers choose don’t cut then each will earn 20 million dollars. „ If one chooses don’t cut and the other chooses cut price, then the newspaper choosing don’t cut will only earn 5 million, while the one choosing cut price can earn 30 million dollars. „ If both newspapers choose cut price, then each can earn 10 million dollars. 5,30 20,20 Don’t cut 10,10 30,5 Cut Apple price Daily Don’t cut Cut price Oriental Daily Prisoner’s Dilemma „ John and Peter have been arrested for possession of guns. The police suspects that they are going to commit a major crime. „ If no one confesses, they will both be jailed for 2 years. „ If only one confesses, he’ll go free and his partner will be jailed for 10 years. „ If they both confess, they both get 5 years . Matrix Representation of Prisoner’s Dilemma 10,0 2,2 Don’t confess Confess 5,5 0,10 John Don’t confess Confess Peter Common features of the two examples „ Both have two players, say A and B. „ Each player has two strategies, say C and D. „ There are four possible outcomes of the moves : (C,C),(C,D)(D,C),(D,D). „ Payoffs of each possible outcome are known to each player

Oriental Daily (B) Peter(B) Cut Don't Confess Don' price(C)cut (D) (C) Confess (D) Cut 10,10 30,5 Confess 5,3 0,10 .Player A:(C.D)>(D.D)>(C.C)>(D.C) Apple C Daily John Don't (A) Don't .Player B (D.C)>(D.D)>(C.C)>(C.D) (A) 5,30 20,20 Confess cut (D) 10,0 22 (D) If we can analyze what A and B are going to choose based on the above information,then we can apply the In both examples,based on the payoffs,A and result to both of the examples. B have the same preferences of the outcomes. We shall see later that both A and B will choose C even Player A (C D)>(D,D)>(C C)>(D,C though they can have a better outcome (D,D)>(C.C). Player B:(D,C)>(D,D)>(C C)>(C D) What is a Game? Four Elements of a Game 1.The number of players. The previous two situations are the examples of the games considered in Game 2.A complete description of the possible Theory. strategies of each player We shall only focus on those games with -when each player moves,what are the the following information. possible moves?what is known to each player before moving? Dating Game Four Elements of a Game Ross and Rachel would like 3.A description of the outcome of the to go out on Friday night. moves. Ross prefers to see football, while Rachel prefers to 4.Payoff of each possible outcome have a drink. -how much money each player receive However,they would rather for any specific outcome. go out together than alone. 5

5 y In both examples, based on the payoffs, A and B have the same preferences of the outcomes. y Player A : (C, D) > (D, D) > (C, C) > (D, C) y Player B : (D, C) > (D, D) > (C, C) > (C, D) 10,0 2,2 Don’t Confess (D) 5,5 0,10 Confess (C) John (A) Don’t Confess (D) Confess (C) Peter (B) 5,30 20,20 Don’t cut (D) 10,10 30,5 Cut price (C) Apple Daily (A) Don’t cut (D) Cut price(C) Oriental Daily (B) y Player A : (C, D) > (D, D) > (C, C) > (D, C) y Player B : (D, C) > (D, D) > (C, C) > (C, D) y If we can analyze what A and B are going to choose based on the above information, then we can apply the result to both of the examples. y We shall see later that both A and B will choose C even though they can have a better outcome (D,D) > (C,C). „ The previous two situations are the examples of the games considered in Game Theory. „ We shall only focus on those games with the following information. What is a Game? 1. The number of players. 2. A complete description of the possible strategies of each player. - when each player moves, what are the possible moves? what is known to each player before moving? Four Elements of a Game Four Elements of a Game 3. A description of the outcome of the moves. 4. Payoff of each possible outcome - how much money each player receive for any specific outcome. Dating Game Ross and Rachel would like to go out on Friday night. Ross prefers to see football, while Rachel prefers to have a drink. However,they would rather go out together than alone