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

The game involves ${\displaystyle n}$ players. Each player ${\displaystyle i}$ has utility ${\displaystyle U_{i}(x)}$ for ${\displaystyle x}$ units of bandwidth. Player ${\displaystyle i}$ pays ${\displaystyle w_{i}}$ for ${\displaystyle x}$ units of bandwidth and receives net utility of ${\displaystyle U_{i}(x)-w_{i}}$. The total amount of bandwidth available is ${\displaystyle B}$.

Regarding ${\displaystyle U_{i}(x)}$, we assume

• ${\displaystyle U_{i}(x)\geq 0;}$
• ${\displaystyle U_{i}(x)}$ is increasing and concave;
• ${\displaystyle U(x)}$ is continuous.

The game arises from trying to find a price ${\displaystyle p}$ so that every player individually optimizes their own welfare. This implies every player must individually find ${\displaystyle {\underset {x}{\operatorname {arg\,max} }}\,U_{i}(x)-px}$. Solving for the maximum yields ${\displaystyle 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.^[1] In this game, every player ${\displaystyle i}$ is asked for the amount they are willing to pay for the given resource denoted by ${\displaystyle w_{i}}$. The resource is then distributed in ${\displaystyle x_{i}}$ amounts by the formula ${\displaystyle x_{i}={\frac {w_{i}B}{\sum _{j}w_{j}}}}$. This method yields an effective price ${\displaystyle p={\frac {\sum _{j}w_{j}}{B}}}$. This price can proven to be market clearing; thus, the distribution ${\displaystyle x_{1},...,x_{n}}$ is optimal. The proof is as so:

Proof

We have ${\displaystyle {\underset {x_{i}}{\operatorname {arg\,max} }}\,U_{i}(x_{i})-w_{i}}$ ${\displaystyle ={\underset {w_{i}}{\operatorname {arg\,max} }}\,U_{i}\left({\frac {w_{i}B}{\sum _{j}w_{j}}}\right)-w_{i}}$. Hence,

${\displaystyle 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

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

and thus ${\displaystyle U_{i}^{'}(x_{i})\left(1-{\frac {x_{i}}{B}}\right)=p.}$

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

References

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.