Question
Transcribed Text
PROBLEM 1
Assume that there are four drivers using the network of Figure 1, each with starting node A and
destination node B. The roads AC and DB have a travel time function (in minutes) T (x) = x
which gives the time it takes each driver to cross the edge (road) when there are x drivers in
total using it. The roads CB and AD take each driver 5 minutes to cross independently of traffic
congestion. Road CD is very fast and we assume it takes 0 minutes to cross it independently of
traffic congestion.
The Social Cost of a given traffic pattern of the 4 drivers is the sum of the travel times incurred
by all drivers when they use this traffic pattern. For example, when all drivers go through AC,
then CD, and then DB, then each takes 8 minutes to reach B and the social cost is 32 minutes.
The Individual Cost of a driver is the delay she gets in a particular traffic pattern of all drivers.
C
x
5
A
B
5
x
D
Figure 1: A road network.
(a) Model the situation above as a strategic game of 4players.
(b) Does the game have pure Nash equilibria? If yes, which?
(c) Justify your answer to (b).
(d) Which traffic pattern(s) achieve(s) the minimum possible social cost? What is the
minimum possible social cost?
(e) Justify your answer to (d).
(f) The (pure) Price of Anarchy, PoA, is defined as the ratio solel wheper SC(E) isthe worst
value of the social cost at a pure equilibrium (worst over all pure equilibria) and OPT is
the minimum possible social cost.
Calculate the PoA of this game.
Solution Preview
These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.
a)The strategic game is defined by the individual costs for a driver to go via this or that route. The costs are c(ACB)=c(ADB)=5+x,c(ACDB)=2x,c(ADCB)=10. (1a.1)
The payoff can be taken as the negatives of the costs,
p(route)= -c(route). (1a.2)
We note that, given 4 players, no matter what routes the players choose, p(ADCB) is smaller than any other payoff, so route ADCB is strongly dominated by other route and can be eliminated from the game when we look for equilibria....
By purchasing this solution you'll be able to access the following files:
Solution.docx.
Return to homework library