# 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 is described as follows:

## The game

• $n$ players
• each player $i$ has utility $U_i(x)$ for amount $x$ of bandwidth
• user $i$ pays $w_i$ for amount $x$ of bandwidth and receives net utility of $U_i(x)-w_i$
• the total amount of bandwidth available is $B$

We also use assumptions regarding $U_i(x)$

• $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 $argmax_xU_i(x)-px$. Solving for the maximum yields $U_i^'(x)=p$.

## The 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.

## A possible solution

A popular idea to find the price is a method called fair sharing.[1] In this game, every player $i$ is asked for 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}{\sum_jw_j})*(B)$. This method yields an effective price $p=\frac{\sum_jw_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

$argmax_{x_i}U_i(x_i)-w_i$

$\implies argmax_{w_i}U_i(\frac{w_i}{\sum_jw_j}*B)-w_i$
$\implies U^'_i(\frac{w_i}{\sum_jw_j}*B)(\frac{1}{\sum_jw_j}*B-\frac{w_i}{(\sum_jw_j)^2}*B)-1=0$
$\implies U^'_i(x_i)(\frac{1}{p}-\frac{1}{p}*\frac{x_i}{B})-1=0$
$\implies U^'_i(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.

## References

1. ^ Tsitsiklis, Johari. "Qualitative Properties of a-Fair Policies in Bandwidth-Sharing Networks" (PDF). Massachusetts Institute of Technology. Retrieved 15 May 2012.