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 "Noncooperative 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
French or German? Should Ross make a sacrifice? Sa and Gil would like to take a language course. Rachel Sa prefers to study German,while Gil prefers Football Drink to study French. Football 2,1 0.0 They would rather take a Ross course together than alone Drink 0.0 1,2 Gil(B) Rachel(B) German French Football Drink Solution of a Game (C) (D) (C) (D) German 32 foot地al 1,1 2,1 0,0 Ross (C) Given a game,we would like to predict Sa(A) (C) French 0,0 2,3 (A) Drink the actual decision of each player. (D) 0,0 1,2 .These decisions of the players are A two person game is called a Dating Game if called a solution of the game. each of two players has two actions,say C and D. Let's consider the Prisoner's Dilemma Player A:(C.C)>(D.D)>(C.D)=(D.C) Game again to find out the solution of this game. Player B:(D.D)>(C.C)>(C.D)=(D.C) We want to predict the outcome of We want to predict the outcome of the game the game Suppose that John decides to confess.What is the Suppose that John decides not to confess.What is the best best decision for Peter? decision for Peter? Peter Peter Do not Do not Confess Confess Confess Confess Confess 5,5 0,10 Confess 5 0.10 John John Do not 108 22 Do not Comress Confess 10,0 2,2 6
6 Should Ross make a sacrifice? Drink 0,0 1,2 Football 2,1 0,0 Ross Football Drink Rachel Sa and Gil would like to take a language course. Sa prefers to study German, while Gil prefers to study French. They would rather take a course together than alone. French or German? A two person game is called a Dating Game if each of two players has two actions, say C and D. Player A: (C, C) > (D,D) > (C, D) = (D, C) Player B: (D, D) > (C, C) > (C, D) = (D, C) 0,0 2,3 French (D) 3,2 1,1 German (C) Sa (A) French (D) German (C) Gil (B) 0,0 1,2 Drink (D) 2,1 0,0 Football Ross (C) (A) Drink (D) Football (C) Rachel (B) Solution of a Game Given a game, we would like to predict the actual decision of each player. These decisions of the players are called a solution of the game. Let’s consider the Prisoner’s Dilemma Game again to find out the solution of this game. We want to predict the outcome of the game 10,0 2,2 Do not Confess Confess 5,5 0,10 John Do not Confess Confess Peter Suppose that John decides to confess. What is the best decision for Peter? 10,0 2,2 Do not Confess Confess 5,5 0,10 John Do not Confess Confess Peter Suppose that John decides not to confess. What is the best decision for Peter? We want to predict the outcome of the game
Dominant Strategy Outcome of the Game Dominant Strategy:a strategy which is Peter always better than any other strategy, regardless of what opponents may do. Do not Confess is the dominant strategy of Peter. Confess Confess Since John has the same preference,confess is also the dominant strategy of John. Confess 5.5 0,10 Assume,John and Peter are rational,then John Do not both of them will choose to confess. Confess 10,0 2,2 Dominant Strategy Dominant Strategy Equilibrium Equilibrium At dominant strategy equilibrium,every If every player has a dominant strategy, player will not change his decision any more. every player will choose that strategy and we can therefore predict the outcome of the If the dominant strategy equilibrium exists,it game. will be the solution (outcome)of the game. The decisions of the players form a However,in most of games (e.g.the Dating dominant strategy equilibrium if every Game),it does not exist.Therefore,we cannot player chooses his dominant strategy. use this method to predict the outcome of the game. Existence of Dominant Suppose Sa has chosen German, Strategy what should Gil choose John von Neumann proved that Gil (B) for any zero-sum game, G French dominant(mixed)strategy (C) (D) always exists. However,in most of the games German (e.g.the Dating Game),it does .In zero-sum (C) 3,2 1.1 Sa(A) not exist.Therefore,we cannot 8g28390sis French(D use this method to predict the outcome of the game. the other player's gain,e.g. chess. 7
7 Dominant Strategy Dominant Strategy: a strategy which is always better than any other strategy, regardless of what opponents may do. Confess is the dominant strategy of Peter. Since John has the same preference, confess is also the dominant strategy of John. Assume, John and Peter are rational, then both of them will choose to confess. Outcome of the Game 10,0 2,2 Do not Confess Confess 5,5 0,10 John Do not Confess Confess Peter Dominant Strategy Equilibrium If every player has a dominant strategy, every player will choose that strategy and we can therefore predict the outcome of the game. The decisions of the players form a dominant strategy equilibrium if every player chooses his dominant strategy. Dominant Strategy Equilibrium At dominant strategy equilibrium, every player will not change his decision any more. If the dominant strategy equilibrium exists, it will be the solution (outcome) of the game. However, in most of games (e.g. the Dating Game), it does not exist. Therefore, we cannot use this method to predict the outcome of the game. Existence of Dominant Strategy John von Neumann proved that for any zero-sum game, dominant (mixed) strategy always exists. However, in most of the games (e.g. the Dating Game), it does not exist. Therefore, we cannot use this method to predict the outcome of the game. In zero-sum games, one player's loss is the other player's gain, e.g. chess. Suppose Sa has chosen German, what should Gil choose ? French (D) 0, 0 2, 3 3, 2 1, 1 German (Ｃ) Sa (A) French (D) German (Ｃ) Gil (B)
Suppose Sa has chosen French,what should No Dominant Gil choose Strategy Equilibrium G1(B) German Fhch (C) (D) We are facing a situation that most of the (C 32 + games do not have a solution,what Sa(A) French(D) 0,0 2,3 should we do Therefore,Gil does not have any dominant strategy and hence this game does not have any dominant strategy equilibrium. How to resolve this problem? To resolve this problem,try to let a more general type of numbers to be zeros.These Let's look at a similar problem in numbers are called complex numbers, mathematics. a+bi(i=√厂，i2=l). A number a is a zero of a polynomial p(x), (e.g.p(x)=x2-2x +1)ifp(a)=0,e.g.1 is a zero of x2-2x +1. Not every polynomial has a real zero.For example,x2+4 has no zero as x2+4 >0 for all real number x. How did John Nash win a How to resolve this problem? Nobel -Prize in Economics? ■a=2i(=2√厂)is a zero ofx2+4as(2iy= 42=.4. In his thesis.John Nash introduced the so- (Gauss)Every non-constant polynomial called mixed Nash equilibrium which is a must have at least one zero. more general solution concept of a game. Try to introduce a more general solution concept of a game and show He proved that for most of the games,at least that every game has at least one such one mixed Nash equilibrium exists. solution. 8
8 Suppose Sa has chosen French, what should Gil choose ? French (D) 0, 0 2, 3 3, 2 1, 1 German (Ｃ) Sa (A) French (D) German (Ｃ) Gil (B) • Therefore, Gil does not have any dominant strategy and hence this game does not have any dominant strategy equilibrium. No Dominant Strategy Equilibrium We are facing a situation that most of the games do not have a solution, what should we do ? How to resolve this problem? Let’s look at a similar problem in mathematics. A number a is a zero of a polynomial p(x), (e.g. p(x)=x2 - 2x + 1) if p(a)=0, e.g. 1 is a zero of x2 - 2x + 1. Not every polynomial has a real zero. For example, x2+4 has no zero as x2+4 >0 for all real number x. To resolve this problem, try to let a more general type of numbers to be zeros. These numbers are called complex numbers, a + bi ( i = ,i 2=-1) . How to resolve this problem? a = 2i ( =2 ) is a zero of x2+4 as (2i)2 = 4i 2 = - 4. (Gauss) Every non-constant polynomial must have at least one zero. Try to introduce a more general solution concept of a game and show that every game has at least one such solution. How did John Nash win a Nobel -Prize in Economics? In his thesis, John Nash introduced the socalled mixed Nash equilibrium which is a more general solution concept of a game. He proved that for most of the games, at least one mixed Nash equilibrium exists
What should be the new A Beautiful Mind solution concept Suppose we have a theory which can predict the outcome (solution)of a game.What property should this solution has? -Suppose we have a theory which predicts that player 1,2,3 must choose A,B,C respectively,i.e.(A,B,C)is the solution of the game. What should be the new Nash Equilibrium solution concept Now if player 1 knows that player 2 and player 3 are going to choose B and The decisions of the players is a Nash C respectively,will he change his choice Equilibrium if no individual will change A? his position,given that the others do not .No,if the theory works.Similarly player change their positions. 2 and player 3 will not change their choices if the others don't. An Example of a Nash Equilibrium Splitting the bill .10 classmates are having In a very boring lecture,all of the students dinner together.Each one would like to leave the classroom early,but has the choice of a cheaper meal for 50 dollars or an no one is willing to leave before the end of excellent meal for 80 dollars. the lecture unless someone else leaves first. As usual,they decide to split the bill. Therefore,every student will choose to stay until the end of the lecture and this is a Everyone chooses the cheaper meal is not a Nash Nash Equilibrium. equilibrium. How about everyone chooses the excellent meal? 9
9 A Beautiful Mind What should be the new solution concept ? Suppose we have a theory which can predict the outcome (solution) of a game. What property should this solution has? Suppose we have a theory which predicts that player 1,2,3 must choose A, B, C respectively, i.e. (A,B,C) is the solution of the game. What should be the new solution concept ? Now if player 1 knows that player 2 and player 3 are going to choose B and C respectively, will he change his choice A? No, if the theory works. Similarly player 2 and player 3 will not change their choices if the others don’t. Nash Equilibrium The decisions of the players is a Nash Equilibrium if no individual will change his position, given that the others do not change their positions. An Example of a Nash Equilibrium In a very boring lecture, all of the students would like to leave the classroom early, but no one is willing to leave before the end of the lecture unless someone else leaves first. Therefore, every student will choose to stay until the end of the lecture and this is a Nash Equilibrium. Splitting the bill 10 classmates are having dinner together. Each one has the choice of a cheaper meal for 50 dollars or an excellent meal for 80 dollars. As usual, they decide to split the bill. Everyone chooses the cheaper meal is not a Nash equilibrium. How about everyone chooses the excellent meal?
Dominant Vs Nash Nash Equilibrium for Prisoner's Dilemma Game .At a dominant strategy equilibrium, Peter every player will not change his position any more. Confess Do not At a Nash Equilibrium,every player will not Confess change his position provided that the others Confess 5,5 0,10 do not change their positions. John .Therefore,a dominant strategy Do not 10,0 Confess 2,2 equilibrium must be a Nash equilibrium. What is a mixed What is not a Nash equilibrium? Nash equilibrium? .In the bar scene,Nash suggested everyone should go for his second .To understand what a mixed Nash choice. equilibrium is,let's play the following .This is not a Nash equilibrium because if three person game. you know all the others are going to choose their second choices,then you will certainly change your choice to the most beautiful girl. A three-person game ·Each one can show either one finger or Exercise two fingers. ·If you are the only one showing one Does this game have any finger,then you get dominant strategy equilibrium one dollar from me. If you are the only How many possible outcomes for one showing two this game?How many of them are fingers,then you get Nash equilibria?List all of them. two dollars. Otherwise,everyone gets nothing Can you find the Nash equilibria for this game 10
10 Dominant Vs Nash At a dominant strategy equilibrium, every player will not change his position any more. At a Nash Equilibrium, every player will not change his position provided that the others do not change their positions. Therefore, a dominant strategy equilibrium must be a Nash equilibrium. Nash Equilibrium for Prisoner’s Dilemma Game 10,0 2,2 Do not Confess Confess 5,5 0,10 John Do not Confess Confess Peter What is not a Nash equilibrium? In the bar scene, Nash suggested everyone should go for his second choice. This is not a Nash equilibrium because if you know all the others are going to choose their second choices, then you will certainly change your choice to the most beautiful girl. What is a mixed Nash equilibrium? To understand what a mixed Nash equilibrium is, let’s play the following three person game. A three-person game • Each one can show either one finger or two fingers. • If you are the only one showing one finger, then you get one dollar from me. • If you are the only one showing two fingers, then you get two dollars. • Otherwise, everyone gets nothing ! • Can you find the Nash equilibria for this game ? Does this game have any dominant strategy equilibrium ? How many possible outcomes for this game? How many of them are Nash equilibria? List all of them. Exercise