Bandwidth-sharing game

A bandwidth-sharing game is a type of resource allocation game designed to model the real-world allocation of bandwidth to many users in a network. The game is popular in game theory because the conclusions can be applied to real-life networks.[citation needed]

The game

edit

The game involves   players. Each player   has utility   for   units of bandwidth. Player   pays   for   units of bandwidth and receives net utility of  . The total amount of bandwidth available is  .

Regarding  , we assume

  •  
  •   is increasing and concave;
  •   is continuous.

The game arises from trying to find a price   so that every player individually optimizes their own welfare. This implies every player must individually find  . Solving for the maximum yields  .

Problem

edit

With this maximum condition, the game then becomes a matter of finding a price that satisfies an equilibrium. Such a price is called a market clearing price.

Possible solution

edit

A popular idea to find the price is a method called fair sharing.[1] In this game, every player   is asked for the amount they are willing to pay for the given resource denoted by  . The resource is then distributed in   amounts by the formula  . This method yields an effective price  . This price can proven to be market clearing; thus, the distribution   is optimal. The proof is as so:

Proof

edit

We have    . Hence,

 

from which we conclude

 

and thus  

Comparing this result to the equilibrium condition above, we see that when   is very small, the two conditions equal each other and thus, the fair sharing game is almost optimal.

References

edit
  1. ^ Shah, D.; Tsitsiklis, J. N.; Zhong, Y. (2014). "Qualitative properties of α-fair policies in bandwidth-sharing networks". The Annals of Applied Probability. 24 (1): 76–113. arXiv:1104.2340. doi:10.1214/12-AAP915. ISSN 1050-5164. S2CID 3731511.