The Impact of Exponential Utility Costs in Bottleneck Routing Games

Details The Impact of Exponential Utility Costs in Bottleneck Routing Games The Impact of Exponential Utility Costs in Bottleneck Routing Games

2009-11-21

arxiv.org/abs/0911.4150v1

Computer Science

Computer Science and Game Theory

AMS Latex 10 pages 2 Figures

Scientific paper

We study bottleneck routing games where the social cost is determined by the worst congestion on any edge in the network. Bottleneck games have been studied in the literature by having the player's utility costs to be determined by the worst congested edge in their paths. However, the Nash equilibria of such games are inefficient since the price of anarchy can be very high with respect to the parameters of the game. In order to obtain smaller price of anarchy we explore {\em exponential bottleneck games} where the utility costs of the players are exponential functions on the congestion of the edges in their paths. We find that exponential bottleneck games are very efficient giving a poly-log bound on the price of anarchy: O(log L log |E|), where L is the largest path length in the players strategy sets and E is the set of edges in the graph.

Affiliated with

Also associated with

No associations

Rating

The Impact of Exponential Utility Costs in Bottleneck Routing Games does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Impact of Exponential Utility Costs in Bottleneck Routing Games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Impact of Exponential Utility Costs in Bottleneck Routing Games will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-315845