Polynomial Bottleneck Congestion Games with Optimal Price of Anarchy

Details Polynomial Bottleneck Congestion Games with Optimal Price of Anarchy Polynomial Bottleneck Congestion Games with Optimal Price of Anarchy

2010-10-22

arxiv.org/abs/1010.4812v1

Computer Science

Computer Science and Game Theory

Scientific paper

We study {\em bottleneck congestion games} where the social cost is determined by the worst congestion of any resource. These games directly relate to network routing problems and also job-shop scheduling problems. In typical bottleneck congestion games, the utility costs of the players are determined by the worst congested resources that they use. However, the resulting Nash equilibria are inefficient, since the price of anarchy is proportional on the number of resources which can be high. Here we show that we can get smaller price of anarchy with the bottleneck social cost metric. We introduce the {\em polynomial bottleneck games} where the utility costs of the players are polynomial functions of the congestion of the resources that they use. In particular, the delay function for any resource $r$ is $C_{r}^\M$, where $C_r$ is the congestion measured as the number of players that use $r$, and $\M \geq 1$ is an integer constant that defines the degree of the polynomial. The utility cost of a player is the sum of the individual delays of the resources that it uses. The social cost of the game remains the same, namely, it is the worst bottleneck resource congestion: $\max_{r} C_r$. We show that polynomial bottleneck games are very efficient and give price of anarchy $O(|R|^{1/(\M+1)})$, where $R$ is the set of resources. This price of anarchy is tight, since we demonstrate a game with price of anarchy $\Omega(|R|^{1/(\M+1)})$, for any $\M \geq 1$. We obtain our tight bounds by using two proof techniques: {\em transformation}, which we use to convert arbitrary games to simpler games, and {\em expansion}, which we use to bound the price of anarchy in a simpler game.

Affiliated with

Also associated with

No associations

Rating

Polynomial Bottleneck Congestion Games with Optimal Price of Anarchy 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 Polynomial Bottleneck Congestion Games with Optimal Price of Anarchy, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Polynomial Bottleneck Congestion Games with Optimal Price of Anarchy will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-115373