Type of resource allocation 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 involves
players.
Each player
has utility
for
units of bandwidth.
Player
pays
for
units of bandwidth and receives net utility of
.
The total amount of bandwidth available is
.
Regarding
, we assume
![{\displaystyle U_{i}(x)\geq 0;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/11a11fde2b5c653eeda7af252988d0bb8cea4d4d)
is increasing and concave;
is continuous.
The game arises from trying to find a price
so that every player individually optimizes their own welfare. This implies every player must individually find
. Solving for the maximum yields
.
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 popular idea to find the price is a method called fair sharing.
[1] In this game, every player
is asked for the amount they are willing to pay for the given resource denoted by
. The resource is then distributed in
amounts by the formula
. This method yields an effective price
.
This price can proven to be market clearing; thus, the distribution
is optimal. The proof is as so:
We have
.
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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/725c80b215e79c9d4747958eada7be7ae0b8ae0c)
from which we conclude
and thus
Comparing this result to the equilibrium condition above, we see that when
is very small, the two conditions equal each other and thus, the fair sharing game is almost optimal.