Bandwidth-sharing game
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.
The game The game involves <math>n</math> players. Each player <math>i</math> has utility <math>U_i(x)</math> for <math>x</math> units of bandwidth. Player <math>i</math> pays <math>w_i</math> for <math>x</math> units of bandwidth and receives net utility of <math>U_i(x)-w_i</math>. The total amount of bandwidth available is <math>B</math>.
Regarding <math>U_i(x)</math>, we assume <math>U_i(x)\ge0;</math> <math>U_i(x)</math> is increasing and concave; * <math>U(x)</math> is continuous.
The game arises from trying to find a price <math>p</math> so that every player individually optimizes their own welfare. This implies every player must individually find <math>\underset x{\operatorname{arg\,max}}\,U_i(x)-px</math>. Solving for the maximum yields <math>U_i^'(x)=p</math>.
Problem 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 A popular idea to find the price is a method called fair sharing. In this game, every player <math>i</math> is asked for the amount they are willing to pay for the given resource denoted by <math>w_i</math>. The resource is then distributed in <math>x_i</math> amounts by the formula <math>x_i=\frac{w_i B}{\sum_jw_j}</math>. This method yields an effective price <math>p=\frac{\sum_jw_j}{B}</math>. This price can proven to be market clearing; thus, the distribution <math>x_1,...,x_n</math> is optimal. The proof is as so:
Proof We have <math>\underset{x_i}{\operatorname{arg\,max}}\,U_i(x_i)-w_i</math> <math>= \underset{w_i}{\operatorname{arg\,max}}\,U_i\left(\frac{w_i B}{\sum_jw_j}\right)-w_i</math>. Hence, :<math> U^'_i\left(\frac{w_i B}{\sum_jw_j}\right)\left(\frac{B}{\sum_jw_j}-\frac{w_i B}{(\sum_jw_j)^2}\right)-1=0</math> from which we conclude :<math> U^'_i(x_i)\left(\frac{1}{p}-\frac{1}{p} \left( \frac{x_i}{B}\right)\right)-1=0</math> and thus <math>U^'_i(x_i)\left(1-\frac{x_i}{B}\right)=p. </math>
Comparing this result to the equilibrium condition above, we see that when <math>\frac{x_i}{B}</math> is very small, the two conditions equal each other and thus, the fair sharing game is almost optimal.