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)\ge0;$
* $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\,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$. This method yields an effective price $p=\frac$.
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\,U_i(x_i)-w_i$
$= \underset\,U_i\left(\frac\right)-w_i$.
Hence,
:$U^'_i\left(\frac\right)\left(\frac-\frac\right)-1=0$

from which we conclude

:$U^'_i(x_i)\left(\frac-\frac \left( \frac\right)\right)-1=0$

and thus
$U^'_i(x_i)\left(1-\frac\right)=p.$

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

References

Game theory game classes