Bandwidth-sharing game

Template:Short description 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.Template:Cn

The game

The game involves $n$ players. Each player $i$ has utility $U_i(x)$ for $x$ units of bandwidth. Player $i$ pays $w_i$ for $x$ units of bandwidth and receives net utility of $U_i(x)-w_i$. The total amount of bandwidth available is $B$.

Regarding $U_i(x)$, we assume

• $U_i(x)\ge 0;$
• $U_i(x)$ is increasing and concave;
• $U(x)$ is continuous.

The game arises from trying to find a price $p$ so that every player individually optimizes their own welfare. This implies every player must individually find $\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{a}\mathrm{x}x{U}_i(x)-px$. Solving for the maximum yields $U_i^{\text{'}}(x)=p$.

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 $i$ is asked for the amount they are willing to pay for the given resource denoted by $w_i$. The resource is then distributed in $x_i$ amounts by the formula $x_i=\frac{w_{i}B}{\sum _j{w}_j}$. This method yields an effective price $p=\frac{\sum _j{w}_j}{B}$. This price can proven to be market clearing; thus, the distribution $x_1,...,x_n$ is optimal. The proof is as so:

Proof

We have $\underset{x_i}{\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{a}\mathrm{x}}{U}_i(x_i)-w_i$ $=\underset{w_i}{\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{a}\mathrm{x}}{U}_i\left(\frac{w_{i}B}{\sum _j{w}_j}\right)-w_i$. Hence,

$U_i^{\text{'}}\left(\frac{w_{i}B}{\sum _j{w}_j}\right)(\frac{B}{\sum _j{w}_j}-\frac{w_{i}B}{(\sum _j{w}_j{)}^2})-1=0$

from which we conclude

$U_i^{\text{'}}(x_i)(\frac{1}{p}-\frac{1}{p}\left(\frac{x_i}{B}\right))-1=0$

and thus $U_i^{\text{'}}(x_i)(1-\frac{x_i}{B})=p.$

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