Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose we model traffic flow between two points with a directed graph. Each route has either a constant travel time or one that linearly increases with traffic. We assume that each driver wishes to minimise their own travel time and we assume that the drivers form a Nash equilibria. Can removing a route ever decrease the average travelling time?

Note that the existence of multiple Nash equilibria makes this question a bit complicated. To clarify, I am looking for a route removal that will guarantee a decrease in the average traveling time regardless of the Nash equilibria that are chosen before and after.

share|improve this question
    
Seeded question –  Casebash Jul 25 '10 at 11:08
    
The "how long it takes" for everyone on the route can depend on the number of people taking that route, I presume? –  ShreevatsaR Jul 28 '10 at 0:21
    
@Shreevatsa: You are right - I mistated the question –  Casebash Jul 28 '10 at 21:03
add comment

1 Answer

up vote 2 down vote accepted

The form this question is usually asked is whether adding a route can increase the average traveling time, and this is known as Braess's paradox. The Wiki article gives an explicit example in which the travel time on some of the routes depends on the traffic.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.