Week 1: Why Do We Need Game Theory, and What Does it Tell Us?
Week 1: Why Do We Need Game Theory, and What Does it Tell Us?
“Course Preview…What is Game Theory?…Modeling Social Problems as a Game…In Search for the Governing Principle…Concerns About a Mathematical Theory of Human Behavior…Let’s Play a Game…Card Game Tutorial (No Audio)…John Nash Discovered the Governing Principle…Nash Equilibrium…Traffic Game in Reality…Location Game…Policies of Two Parties…”
1-4 Concerns About a Mathematical Theory of Human Behavior
1-5 Let's Play a Game
Card Game Tutorial (No Audio)
1-6 John Nash Discovered the Governing Principle
1-7 Nash Equilibrium
1-8 Traffic Game in Reality
1-9 Location Game
1-10 Policies of Two Parties
Course Preview
Game theory provides a very digital framework to analyze such a situation to tell you what kind of behavior is observed in such strategic situations.
I don’t presume any prior knowledge of game theory or economics and I emphasize the basic ideas and the philosophies often hidden behind mathematical definitions and quite often not explicitly stated in text.
Game theory has been applied through a number of fields, including economics, political science, philosophy, psychology, and sociology, biology, and computer science.
I’m going to ask you to play a simple card game.
1-1 What is Game Theory?
Well, game theory is a very fancy or sexy name, which naturally attracts lots of people’s attention.
Game theory has been applied to a number of fields in social sciences, humanities, and natural sciences engineering.
Well, this is an introductory course on game theory.
I focus on conceptual aspects of game theory, and I use very little math.
So if you are interested in how to solve mathematical models and what kind of mathematical models are presented by game theory.
So let me give you an example of the subject of game theory.
This is an example of the research subject of game theory.
Okay, so the game theory constructs mathematical models to examine or to predict how people behave in such a strategically situation.
So game theory examines people’s behavior in strategic situations.
Game theory is not about your favorite video game.
So if you are interested in video games and came to this course well, this is not for you.
Okay, so let me give you a few examples about what game theory tells you.
Okay? After learning game theory, you can solve the following interesting questions.
Game theory provides you a unified way of solving all social problems including this one.
Then you apply the basic solution concept of game theory and then you get an answer.
The question is what happens if we construct a new road coming from X to Y? How does it affect the traffic on the existing road? And how you can save travelling time from X to Y? Okay.
This is a perfect example of game theoretic or strategic situation.
Again, you formulate this social problem as a mathematical model game and then you apply the basic solution concept.
So game theory has been applied a number of research fields.
This is the first place where game theory was born, because in all social sciences, economics was the first to use mathematical approach.
Now game theory has been applied to other you know, fields of research in social sciences.
Outside of social sciences and humanity, game theory has also been applied to natural science, notably biology and also computer science.
Okay? So the struggle for existence of animals and plants, it’s a kind of game.
So you can apply the concept of game theory to biology and the branch of biology which uses game theory is called evolutionary game theory.
Okay? What about the relationship between game theory and computer science? Computer science used to analyze the calculation performed in a single computer.
Now computers all over the world are interconnected with network, okay? So those computers are collaborating or often competing to perform their calculations.
Okay? This is also a strategic situation, and game theory can be fruitfully applied to computer science.
Well, I am an economist and I do research in economic theory.
Game theory provides a common language which facilitates in to disciplinary research in all those different fields.
1-2 Modeling Social Problems as a “Game”
Then apply this illusion concept to get some predictions, okay? So, in the second lecture I’m going to tell you how you can formulate or formalize a social problem as a mathematical model called a game.
Okay, so those are the examples of social interaction, strategic problems, I explained in the first lecture.
What happens if you construct a bypass from city x to city y? How it affects the traffic of the existing roads, and how it affects the traveling time from city x to city y. Okay.
As a human being you have some experience about politics, and maybe you have been driving your car.
In those instances, you, you can use your intuition to get some answer to those two questions, okay? In politics, such and such things are going to happen.
In contrast, game theory tried to find, a unified approach which can be applied to all those social problems, okay? So what are common, what is common between all those social problems? Well, those problems share two features.
In political struggle between Democrats and Republicans, there are certain things they can do, okay? They can design their policy platform, but they cannot really bribe people.
Okay, so every social problem has a certain set of rules.
Okay, so let’s try to formulate social problems which have those two features, as a simple mathematical model, which is called a game.
Player number 1, player number 2, up to player number N. Okay, so first you specify who participates in the social problem.
Okay? So each player in a social problem takes some action or strategy.
So strategy of player i. Is denoted by a sub i, okay? And do you have to specify the range of possible strategies for each player.
Okay, so it’s large A, sub i. Okay, this is a set.
Okay so let’s denote each player’s payoff by, g sub i. And your payoff, your profit or your benefit, usually depends on what everybody does, okay? So, it may depend on player number 1’s action.
It may depend on player number 2’s action, up to action or strategy chosen by the last player, okay? So this player function represents the nature of a strategic interaction.
Political struggle between the Democrats and the Republican, okay? So, obviously, there are two players.
Player number 2 is the Republican Party, okay? That’s fine.
Here we need some simplification, okay? We have to look at the crucial aspect of political campaign.
Even that critical aspect can be formulated as a symbol of model of game, okay? So the item number two, the scope of strategies, what is the set of all feasible strategies, in this particular instance it’s not so obvious.
You have to capture the essence of reality in the simple model of gain, okay? And let me turn to the third item.
Okay, so again, you have to look at the essence of reality and formulate the essential part of their benefit as a payout function.
Okay, so players, let’s say the players are the drivers commuting from city X to city Y. There may be thousands of players in this traffic game.
Route an, route b, you can also take this route b to go from City X to Y. And there are finitely many routes coming from X to Y, so the set of strategies for each player is the set of roads, coming from city X to city Y. Okay, so item number two strategies is very easy to specify in this particular social problem.
Okay, in this traffic problem each driver tries to minimize the time to destination, okay? So you can say that the payoff to each player is minus negative of traveling time.
Okay, so after formulating a social situation as a mathematical model of game, then you have to solve.
So there might be a general theory which can be applicable to all those social problems, okay.
The question boils down to, finding a unified solution to all games, okay.
Okay, so this is a picture of the fathers of game theory, von Neumann, a computer scientist and mathematician and fill, of physicist, and Oskar Morgenstern a professor of economics at Princeton University.
Okay together they published a book called, The Theory of Games and Economic Behavior, back in 1944.
1-3 In Search for the Governing Principle
So the question is the following, can we find anything like Newton’s law of motion which can be applied to everything? In social science, in social problems.
So let’s focus on the first feature of all those, social problems.
So let’s try to formulate this, aspect of social interaction by means of mathematics.
So you have a better choice and worse choice, and what would you do? Well, obviously, you choose the better one.
So let’s try to come up with a single unified principle, which can be applied to all those social problems by means of this basic idea.
So to examine that question, let’s compare two gambles, roulette and poker.
Okay roulette and poker seem very similar they are gambles.
I’m going to argue that poker is substantially more complex than roulette, and let me explain why? Okay? So what is a rational behavior of Mr. A in roulette? Well, it’s very easy to formulate as a mathematical model, because behavior of roulette machine is fixed.
Each outcome happens with a positive probability, positive and equal probability so behavior is given.
So maybe he has $100 and his task is to maximize his money, by betting on roulette 10 times, what would be the optimal strategy? Well, I don’t know the answer, but you can certainly formulate this as a mathematical maximization or optimization problem, and use mathematics to determine Mr. A’s behavior.
The difference here is that Mr. A is playing poker with Miss B, but Miss B’s behavior is not given.
So what would you do if you don’t know the behavior of your environment? What are you going to do if you don’t know the weather tomorrow? Well, you form some expectation maybe it rains or maybe it’s going to be fine.
So you form some expectation when your environment is uncertain.
This guy here doesn’t know exactly what Miss B is going to do, so he forms expectation.
So the first task of Mr. A is to predict Miss B’s behavior.
Miss B is not like roulette, the behavior of roulette is mechanically given.
She is another intelligent human being, so she must be thinking in the same way as Mr. A is thinking.
Okay, so to better predict B’s behavior, Mr. A needs to examine what she is thinking about.
Okay? So to better predict Miss P’s behave, B’s behavior, Mr. A tried to think that what she is thinking about its own strategy.
Okay? So a deeper strategic thought requires Mr. A’s belief about Miss B’s belief about Mr. A’s behavior.
Okay? So this is a deeper strategic thought, but think, but the, uh, but the analysis doesn’t stop here, you can go further and further.
So to better predict with miss B’s behavior, you have to think about A’s belief about B’s belief about A’s belief about B’s belief about A’s behavior and so.
If intelligent agents are trying to predict each other’s behavior and maximize their payoff, we end up with the infinite regress problem.
The simple mathematical model or mathematical theory of maximization is not enough; we need a new mathematical theory.
So given this observation, finding a governing prin, principle, finding a single governing principle which can be applied to all those social problems, is a very challenging scientific problem.
1-4 Concerns About a Mathematical Theory of Human Behavior
Okay? I do research in game theory, and whenever I say I do research in game theory in a party, for example, I get three common reactions.
Reaction number one oh, wonderful, you do research in video games.
Well, I have to disappoint the person, saying that game theory is not about the video game.
Common reaction number two, you know, suddenly, you know, they get very defensive, thinking that I’m a very good strategist and I’m going to exploit them by using game theory.
Well, I’d say that game theory is not for use, not so usable in exploiting other people, and at least I don’t use game theory in that way.
The third criticism is that, third common reaction is that well, it shouldn’t work, okay? And the reasoning is based on the following three points.
I’m going to tell you that game theory tries to predict human behavior by a mathematical formula.
So the question which was posed by the fathers of game theory, von Neumann and Morgenson what’s to find something like Newton’s Law, which can be applied to all social problems.
So the task of game theory is to find a general unified principle to explain people’s behavior.
So the skeptic’s point of view number one, is that free will defeats any attempt to predict human behavior by a mathematical formula, okay? Suppose game theory tells you that you must choose, well you should choose certain strategy in a certain social situation.
Well, you can always deviate because you have free will, okay? So just by the fact that humans have free will defeats any attempt to predict human behavior.
That’s the criticism number one, okay? Number two says well, we don’t need mathematical theories to explain a perfect human behavior because eventually, you can ask why you did that. Why did you do that? Right? You cannot ask this question to falling ball.
Okay, criticism number three says, well, I have never seen or heard that game theory works.
Okay? If game theory has a wonderful formula to explain everything in human interaction, we must have some evidence but I have never heard of it.
Well, back in 1939, before the birth of game theory, what did the economist Paul Samuelson say? Well, he couldn’t say anything.
He said this was a test that I always failed, okay? But then, game theory was created, and now we have some evidence that mathematical approach actually works very well.
1-5 Let’s Play a Game
Okay, before going any further, maybe it’s a good time to play a very simple game, to see what the nature of strategic thought is.
You need to find a partner to play a simple card game with you.
One player is the red player, okay? And red player holds four cards.
The other player is the black player who has black card king, one, two, and three.
Each player carefully chooses one card and shows it to the opponent, simultaneously with the opponent.
Okay? And payoff is dependent on what cards those players chose.
Okay, suppose red player and black player chose king.
Suppose those two players choose cards with different numbers.
Black player chose three cards with different numbers.
The go, I’m going to ask you and your partner to play this game for a certain number of iterations.
It’s a very strange game but its fun to play.
Or players choose cards with different numbers such as one and three.
Okay? In all other cases, the black player wins but let me explain when black player wins.
So one player chooses king, the other player chooses a card with a number.
Or if players choose cards with the same number, like one and one, then black player wins.
Okay? So I’m going to ask you to you know, play this card game again and again with your partner.
Okay, this is a perfect example of a strategic situation, because what is best for you crucially depends on what other player is going to do.
Each player is trying to do their best; each player is trying to do his or her best against the other player.
So after playing this game, I’d like to ask you to think about the following three interesting questions.
Okay? So maybe the set of rules here favors red player.
So the first question if the following, who has an advantage, red player or the black player.
What is the winning rate or winning probability of each player?
Okay? What is the nature of the distribution of the cards chosen by the players? Okay? This is a very, very tough question.
Card Game Tutorial (No Audio)
No audio, no subtitle
1-6 John Nash Discovered the Governing Principle
So we have learnt that any social problem can be formulated as a mathematical model of a game.
The next question is to find a single solution concept which can be applied to all those social problems.
Any social interaction can be formulated as a mathematical, mathematical model of a game which specified players, strategies and payoffs.
The question is if we can find a unified general theory to find the solution to all of those social problems.
Is there any single solution concept that can be applied to all those social interactions? The answer was discovered by a mathematical genius, John Nash.
The problem is to find a unifying solution concept, which can be applied to all those social problems.
Okay, so suppose the surface of coffee represents the set of all possible human behavior in a social problem.
If you buy this analogy between coffee surfaces and the set of possible human behavior in a social problem you can realize that the following is true.
So a point in this fixture now represents original behavior of people in a social situation.
Okay? And the destination, this point here, represents another social situation where players are moving towards best replies.
Then social situation changes from this point to that point.
What about a social situation? Okay? The vortex represents a case where people already are taking best replies.
Okay? So at the vortex point, all players are doing their best against the others.
Okay? So this is a stable situation and a social problem.
Okay? And just as coffee surface has a vortex point, any social problem has such a stable point.
So by using advanced mathematics called topology, Nash discovered or found that any social problem has a natural equilibrium point.
Now, you can apply the idea of Nash to any of those social situations.
You formulate a social situation as a game, a mathematical model of a game, by specifying players, strategies, and payoffs.
Then you use your mathematics to find out something like a vortex point, okay, where all individuals are doing their best against others.
Then you get a prediction in every single social problem.
1-7 Nash Equilibrium
So John Nash has found a unified principle which can be applied to all social problems, Nash equilibrium.
So in this lecture, I’m going to give you the formal definition of Nash equilibrium and then I’m going to apply the idea of Nash equilibrium to the second question I posed in the first lecture.
Okay? So we consider our game which has two players, player one and two.
So A-1-star is the Nash equilibrium action or strategy for player 1.
A-2-star is the Nash equilibrium strategy for player 2.
If the pair of strategies, A-1-star and a-2-star satisfy the following condition- We call it Nash equilibrium.
Okay, if everybody chooses the Nash equilibrium strategy, a1 star and a2 star, this is Mr. One’s payoff.
Okay? What happens if he changes his behavior from equilibrium to something else? Well, the answer is given by g1 of a1 which may not be equal to the Nash equilibrium strategy and the a2 star.
Okay? So originally everybody was speaking to Nash equilibrium.
Now Mr. One is changing his action from equilibrium to something else.
Okay? Well Nash equilibrium requires that player one cannot increase his payout by deviant.
Okay? So what is Nash equilibrium? Well, this condition says that Nash equilibrium has the following property.
If you are the only one person deviating from equilibrium, you cannot really gain.
Okay? That’s the definition of Nash equilibrium.
Are taking Nash equilibrium strategies, a1 star and a2 stars.
Mr. One cannot increase his payoff by deviating from the equilibrium strategy.
Question number two says, what happens to the traffic flows if we construct a new bypass from city x to city y? Okay? You can answer this question by calculating Nash equilibrium before construction, constructing of the new bypass, and after the construction of a new bypass.
If you compare those two Nash equilibrium, you can see the answer.
So I’m not- Let’s stick to this very simple formulation to solve for Nash equilibrium.
Okay? It’s 350 and it’s better to choose the route in between.
Nash equilibrium has a property, saying that no single driver can save his or her traveling time by deviating to another route.
Okay, at the Nash equilibrium, you have zero cars traveling from x to y. On this route.
Okay, so what’s the traveling time of the the route in between? Okay.
So if you sum up the length and number of cars, the traveling time is again 300, okay? So traveling time is equal on those routes and you can see that.
The Nash condition says that no single player can increase his payout by deviating by himself or by herself, okay? This allocation has a Nash philosophy that no one can save traveling time by changing his or her route, okay? So if you are driving on this new bypass coming from x to y, your traveling time is 300.
So by using this kind of reasoning, you can see the answer to the original traffic question, okay? So you can calculate the Nash equilibrium before construction of the new bypass.
You can calculate the Nash equilibrium of traffic allocation after the construction of new bypass.
1-8 Traffic Game in Reality
In the last lecture, I explained traffic allocation on different routes, can be determined by Nash equilibrium in a very much simplified version of traffic game.
So to perform the comparison between the real traffic allocation and the national prediction, first you need must collect some data.
Secondly, you have to examine, you know, the traffic location of each segment of each segment of road. So maybe from city x to y. One 500 cars are commuting on this route.
Okay? Nash equilibrium traffic location can computed.
Secondly, you have to know, the relationship between travelling time and the traffic on a given road segment.
In the very simple traffic game, in the last lecture, I assumed that travelling time is a summation, between the lengths of the road and the amount of traffic.
According to the estimation of those scholars in Japan, the relationship between travelling time and traffic is not linear and it looks like this.
As you increase the number of crowds, traffic time or, or travelling time really doesn’t change at the beginning.
So by using those two pieces of information, how many cars are commuting from, say, city x to city y? And how many cars are commuting from each origin and each destination and the relationship between travelling time and traffic.
You can compute a Nash equilibrium traffic allocation.
Nash equilibrium traffic allocation has a property, that no single driver can save their traveling time by deviating, and I use that word.
There is a computer programmer to find out or to compute, Nash equilibrium traffic allocation.
Basically thickness of routes thickness of route indicates the amount of traffic on the route.
Okay? So let’s compare, the prediction of game theory, with the real traffic allocation.
Okay? So for this segment, you can compare the real traffic and Nash equilibrium prediction.
Okay? And you can plot the comparison between actual traffic and Nash equilibrium like this point, for all of the segments.
Okay? The horizontal axis measures actual traffic on each segment, and the vertical axis measures the Nash equilibrium prediction of the traffic on each segment.
You can see that it’s not perfect, but it does reasonably good job of predicting traffic in reality.
So Nash equilibrium is a very simple concept, but it does a fairly good job of predicting traffic allocation in reality.
Okay? So it can be applied to any social situation, but if you apply it to this particular traffic problem, it did a wonderful job of predicting the al, the al traffic.
1-9 Location Game
The customers are uniformly distributed over this row. And each customer goes to the nearest vendor.
Half of the customers are going to place A and the half, the other half goes to place B. Okay, what about vendors payoff? I’m going to assume that a vendors payoff is equal to the number of customers it gets.
Okay, so let’s try to understand the nature of this game and suppose vendor A is here and vendor B is located here, okay? Okay, so this is a point in between A and B And all the customers located here, all the customers located goes to vendor A. And all the customers working here are going to buy ice cream from vendor B. This is the nature of this location game.
The number of customers here is Mr. A’s payoff, and the number of customers here is Mr. B’s payoff, okay.
Okay, so suppose this is the locations of this picture depicts the locations of A and B. And A is getting customers here, and B is getting customers here, is this a Nash equilibrium? Well, it is not a Nash equilibrium.
Okay, I would argue that this is not a Nash equilibrium because originally Mr. A is getting half of the customers.
So originally he was getting half of the customers but by deviating by himself, Mr. A is getting more than half customers.
Okay, by deviating slightly to the left, A can get more customers.
The original configuration is not a Nash equilibrium, okay? So, the only natural equilibrium in this location game is this one, okay? A and B are located exactly at the same point, exactly in the middle of the road. Well, this is very unfortunate for the customers if A is located here and B is here, it’s more convenient, but Nash equilibrium predict that they choose the same location.
Okay, so let’s examine if this configuration satisfies the Nash condition, okay? So, in the original situation, A and B are splitting customer, they are getting half of the customer.
Even if A moves to the left or right Mr. A cannot really increase the number of customers.
1-10 Policies of Two Parties
What determines the policies of two parties? The Democrats, and the Republicans, okay.
The question is, what are the sets, of possible policies of those two parties.
Well they can take many different policies and campaigns and, it’s very hard to formulate everything in a simple mathematical model, okay.
Let’s suppose that they just choose policies or policy platforms.
Let’s suppose they have the policies can be linearly ordered from very liberal to very conservative.
Maybe the Republicans can implement very conservative policies.
This segment represents the set of all the possible policies.
They simultaneously choose policy platforms on this line, okay.
Okay, so I have specified players and the possible strategies, and payoffs to ea, to all those players.
Okay, now let’s assume that both these ideal policies are uniformly distributed over this segment.
So their ideal policies maybe located here and some people are very liberal, so their ideal policies are somewhere around here.
For simplicity for the moment, let’s assume that voters’ ideal policies are uniformly distributed.
Okay and let’s suppose your ideal policy is here.
Let’s suppose Democrat’s policy is here.
Okay? So then the Republican’s policy is closer to your ideal policy.
Okay, so if Democrat chooses a policy platform here, very liberal policy, and the Republican chooses a very conservative policy here, what happens? Well this is a point in-between.
All of the people whose ideal policy is located here, vote for Democrats.
All conservative people, whose ideal policy is located over here, vote for Republicans.
You can apply the Nash equilibrium concept to the policy choice game.
Okay, Democrats, and the Republican choose exactly the same policy.
Okay so let’s re-examine my basic assumption, saying that voter’s ideal policies are uniformly distributed.
Okay, so let’s consider a general distribution of voters ideal policies.
Okay, so median over distribution is determined by the following way.
Okay, so you linearly order everybody from very liberal to very conservative.
So our analogies shows that, policies parties when there are only two parties tend to be very similar and they choose this location, Median location where they get half of the of the voters.
The answer is given by median voter’s opinion, okay.
So you linearly order everybody from very liberal to conservative and you find someone, just in the middle, okay.
The opinion of this guy, the median voter, determines two parties policy.
Okay, so let’s reexamine this game’s already prediction.
Well, prediction says that the democrats and the republicans should choose exactly the same policy, and in reality it’s not true.
Okay, the game theory prediction is not as accurate as Newton’s law, like in this example, the prediction is lopsided, but.
Okay, so they are inclined to choose very similar policies.
What determines the policies of two parties? It’s a very vague and general question.
Game theory says well, any social problem can be formulated as a mathematical model of game, and then you can apply the solution concept, the Nash equilibrium, and then you get an answer, okay.
Okay, so let’s suppose, this falling leaf represents human behavior which you’d like to examine.
It’s very, very complex, and maybe you cannot get a very simple theory to explain everything perfectly, okay.
So game theoretic prediction, captures one of the very important driving forces, okay.
Okay, game theory provides you a unifying solution concept, Just like Newton’s law, but it’s not as accurate as Newton’s law.
Week 1: Why Do We Need Game Theory, and What Does it Tell Us?