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:
n playerseach player i has utility U i ( x ) for amount x of bandwidthuser 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 ) ≥ 0 U i ( x ) is increasing and concave U ( x ) is continuousThe 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 a r g m a x x U i ( x ) − p x . Solving for the maximum yields U i ′ ( x ) = p .
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. 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 = ( w i ∑ j w j ) ∗ ( B ) . This method yields an effective price p = ∑ 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:
a r g m a x x i U i ( x i ) − w i
⟹ a r g m a x w i U i ( w i ∑ j w j ∗ B ) − w i
⟹ U i ′ ( w i ∑ j w j ∗ B ) ( 1 ∑ j w j ∗ B − w i ( ∑ j w j ) 2 ∗ B ) − 1 = 0
⟹ U i ′ ( x i ) ( 1 p − 1 p ∗ x i B ) − 1 = 0
⟹ U i ′ ( x i ) ( 1 − x i B ) = p
Comparing this result to the equilibrium condition above, we see that when x i B is very small, the two conditions equal each other and thus, the fair sharing game is almost optimal.
