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 $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)\geq 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 ${\underset {x}{\operatorname {arg\,max} }}\,U_{i}(x)-px$. Solving for the maximum yields $U_{i}^{'}(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}}{\operatorname {arg\,max} }}\,U_{i}(x_{i})-w_{i}$ $={\underset {w_{i}}{\operatorname {arg\,max} }}\,U_{i}\left({\frac {w_{i}B}{\sum _{j}w_{j}}}\right)-w_{i}$. Hence,

$U_{i}^{'}\left({\frac {w_{i}B}{\sum _{j}w_{j}}}\right)\left({\frac {B}{\sum _{j}w_{j}}}-{\frac {w_{i}B}{(\sum _{j}w_{j})^{2}}}\right)-1=0$

from which we conclude

$U_{i}^{'}(x_{i})\left({\frac {1}{p}}-{\frac {1}{p}}\left({\frac {x_{i}}{B}}\right)\right)-1=0$

and thus $U_{i}^{'}(x_{i})\left(1-{\frac {x_{i}}{B}}\right)=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.