Bandwidth-sharing game

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[edit]

  • 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[edit]

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[edit]

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[edit]

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[edit]

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