Tip:
Highlight text to annotate it
X
Selfish routing can cause suboptimal outcome
to many or even all the players in a routing game.
We have seen this in base paradox, but, in fact, it
can happen in even smaller examples on just two notes.
Players want to go from A to B, and have two different route choices.
So in this example, there are 500 players as before, and two route
choices.
One, which always takes 50 minutes, and the second one that takes
x/10 minutes where x is the number of players.
The unique Nash equilibrium in this game is for all the 500 players
to use the congestible path taking 500/10 equals 50 minutes.
And, in fact, this is indeed a Nash because there's nothing they can do.
The alternative path also costs 50 minutes.
But in some sense, this is not the optimal solution.
We could split the traffic, and send 250 people
in each of the two different options.
This would make the travel time for the 250 people
who chose the 50-minute path the same 50 minute as before,
but improved the travel time for the other 250 people
to 250/10, which is 25 minutes.
Quite a bit of improvement.
So what happened in this improved solution
is that you made it better for some people without making it worse
for anyone.
And, in particular, we decreased the average travel time from 50 to 50
plus 25 over 2, which is 37 and 1/2.
In fact, this is the smallest average travel
time possible in this particular network.
It's nice, but it's not clear how we can convince
users to choose a longer path that doesn't help them, it helps others.
Unlike in the base paradox, we can't just
improve the situation by deleting edges.
If you delete any one of the two edges, the remaining edge
can carry the traffic, but it doesn't decrease the time.
One way to help is to discourage people from using the congestible path
by putting in tolls, or additional expenses,
and maybe using these tolls to subsidize other people who
have to use the longer path.
So tolls or even rewards like subsidies can be implemented via highway tolls.
To think about what this does to people's interest or choices,
we need to think of travel time expressed in money.
So maybe the money that people are willing to pay
for saving time and going on a faster route.
So cost expressed in money-- use the same example again.
There is a 50 fee for one path and an x/10 fee
when x people use that choice of a pass.
And what we're going to do is add an additional cost
to the congestible path and a reward for people
who are using the noncongestible path.
And the optimal reward and fee number here is 12 and 1/2.
So let's assume we put in this additional cost or reward.
So on the noncongestible edge, the cost is to be 50
and now we're giving your reward of 12 and a 1/2, which
makes the cost come at 37 and 1/2, and that's the cost of the lower edge.
On the upper edge, you have a function that expresses cost
in terms of the congestion or the number of people
who choose was the path, x/10 plus 12 and 1/2,
where 12 and 1/2 doesn't depend on the congestion.
It's just an additional reward.
Everyone gets on that path.
So this changed the cost function, or the people's incentives,
and now the unique Nash equilibrium is, in fact,
to speed the traffic of 250 people going on each of the two paths.
The travel cost on the lower edge is, obviously, 37 and 1/2.
On the upper edge, it turns out to also be 37 and 1/2.
There are 250 people, so x/10 is 25, plus the 12 a 1/2 additional cost comes
out to be 37 and 1/2-- exactly the same, and, indeed,
this is the Nash equilibrium.
It's interesting to think about how much money this costs to institute
this kind of solution.
So in one edge, the congestible edge, we are collecting money.
The tax collected is 250 people each have to pay an additional 12 and 1/2,
comes out to be some number.
On the other hand, the noncongestible edge,
we are offering a subsidy to people, and in the equilibrium
there are 250 people on that path too, and the total subsidy
is 250 people times the 12 and a 1/2 subsidy we offered there.
And my note is that the tax collected equals the subsidy.
So what happened here is that with taxes and subsidies
we could help improve the solution.
We improved the unique Nash equilibrium, which used to cost 50 for everyone
to an equilibrium which is only costing 37 and 1/2 to everyone.
And we did that without actually any cost.
That is the total cost of subsidies and taxes actually came out to be 0.
250 people got a subsidy, a toll of over $3,000, but the same amount over $3,000
is collected in tolls so it comes out to equal 0.