PROBLEM 1 Assume that there are four drivers using the network of ...

  1. Home
  2. Homework Library
  3. Mathematics
  4. Game Theory
  5. PROBLEM 1 Assume that there are four drivers using the network of ...


Transcribed TextTranscribed 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 PreviewSolution 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.


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:

for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Game Theory Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Upload a file
Continue without uploading

We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats