City Traffic Planner
-- A Member of REC Professional Services Group
Quality Professional Services
What is a Game
Game theory is a study of strategic decision making. It concerns with situations in which decision-maker interact with each other and in which the happiness of each participant with the outcome depends not only on his own decision but made by everyone. In other words, it studies after considering other player’s decision, how should one make a decision.
Basic Ingredients of a Game
A game is any situation with the following three aspects:
- Player – Participants of the Game
- Strategies – Players’ option for how to behave
- Payoff – For each strategy, player receives a payoff i.e. the outcome
Assumptions
There are some assumptions when players make his/her decision:
- Each player knows his own list of choice
- Each player knows his payoff under his choice
- Each player aims to maximize his payoff
01
02
03
Best Response and Dominant Strategies
Two concepts should also be introduced in considering player’s decision: Best Response and Dominant Strategies.
Best response is the best choice of one player, given a belief about what the other player will do. To notate this, assume a player will adopt a strategy T which you can choose either strategy S and strategy S’. If:
P(S, T) > P(S’, T)
Strategy S is the best response of you.
Dominant Strategy for a player is the strategy that is a best response to every strategy of Player 2.
Strictly Dominant Strategy for a player is the strategy that is a strict best response to every strategy of Player 2.
04
Nash Equilibrium
There is situation that neither of the players has a strictly dominant strategy. Under such situation, how does player decide? Nash Equilibrium is hereby introduced. If each player has chosen a strategy and no player can benefit by changing strategies while the other players keep theirs unchanged, such set of strategy constitute a Nash Equilibrium.
05
Game Theory
To investigate whether the ongoing undesirable traffic flow could be resolved by equalizing the toll charges, the driver’s behavior should be accessed i.e. how does a single driver choose between different paths? Game theory is hereby introduced to reach the purpose. The theory is adopted with an attempt to explain driver’s preference in choosing a path by considering several keep factors. After each driver’s behavior is known, we can deduce the expected traffic flow under a certain set of toll fee.
06
Example: The Exam/Presentation Game
To better illustrate the theory, here’s an example:
Suppose that you’re a student and you have two large pieces work due on next week: an exam and a group presentation. You need to decide which one you will do. There are two assumptions. First, you can either do the group presentation or prepare the exam, but not both. Second, you have an accurate estimate of the expected grade you’ll get under different decision.
For the outcome of exam, if you study, then your expected grade is 92. If you don’t, your expected grade is 80.
The situation of group presentation is more complicated, your expected grade depends not only on your decision but your partner’s decision. If both of you prepare for the presentation, you will get an expected grade of 100. If only one of you prepare for the presentation, you will get an expected grade of 92. If neither of you prepared for the presentation, your expected grade is 84.
So if you choose to study and so do your partner, you will get 92 in your exam and 84 in your presentation, with an average of 88.
If you choose to study and your partner prepared for the presentation by himself, you will get 92 in your exam and 92 in your presentation, with an average of 92.
If you choose to prepare for the presentation but your partner doesn’t do so, you will get 80 in your exam and 92 in your presentation, with an average of 86.
If both of you choose to prepare for the presentation, you will get 80 in your exam and 100 in your presentation, with an average of 90.
Here we have two players: you and your partner. Your options is to either study exam or prepare presentation and payoff is your grade.
For you, preparing for the exam is the best response to each strategy of your partner in which you can get the highest grade no matter what’s your partner’s decision. So preparing for the exam is the Dominant Strategy for you.
However, if both of you choose to prepare for the presentation, a Nash Equilibrium is achieved as neither of the players could be benefited by changing his strategy. (Say, if you now change your choice to study, your partner will also choose to study which as a result, the average grade for both of you decrease.)
07
Modeling Network Traffic using Game Theory
Game theory could be applied to predict drivers’ behavior in choice of route given that the assumptions underlying are valid.
Here’s an example. Assume every driver want to reach B from A. One either reach B thorugh C or through D. Let’s imagine CB and AD is a highway which no matter how many car is on the highway, it takes every car 45 minutes to go through it. Then, we also assume that AD and CB is two different downtown road which is sensitive to number of car x on it. Say the time taken for a car to travel through the path is x/100. The figure below best illustrate the game:
Now, suppose there are 4000 cars want to go to B from A. If all the cars take the upper route, the total travel time for everyone is 85 minutes. However, this is not a rational decision for the drivers. So, what will be the result?
Equilibrium traffic:
Obviously, there is no dominant strategy as each has the potential to the best choice for a player provided that all the users are using the other route. However, the game does have a Nash Equilibrium which x will be 2000. When x=2000, total travel time for each players is 65. None of the drivers has incentive to change their as this will only increase their own travel time. Hence, a Nash Equilibrium is achieved.
