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 [math]\displaystyle{ n }[/math] players. Each player [math]\displaystyle{ i }[/math] has utility [math]\displaystyle{ U_i(x) }[/math] for [math]\displaystyle{ x }[/math] units of bandwidth. Player [math]\displaystyle{ i }[/math] pays [math]\displaystyle{ w_i }[/math] for [math]\displaystyle{ x }[/math] units of bandwidth and receives net utility of [math]\displaystyle{ U_i(x)-w_i }[/math]. The total amount of bandwidth available is [math]\displaystyle{ B }[/math].
Regarding [math]\displaystyle{ U_i(x) }[/math], we assume
- [math]\displaystyle{ U_i(x)\ge0; }[/math]
- [math]\displaystyle{ U_i(x) }[/math] is increasing and concave;
- [math]\displaystyle{ U(x) }[/math] is continuous.
The game arises from trying to find a price [math]\displaystyle{ p }[/math] so that every player individually optimizes their own welfare. This implies every player must individually find [math]\displaystyle{ \underset x{\operatorname{arg\,max}}\,U_i(x)-px }[/math]. Solving for the maximum yields [math]\displaystyle{ U_i^'(x)=p }[/math].
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 [math]\displaystyle{ i }[/math] is asked for the amount they are willing to pay for the given resource denoted by [math]\displaystyle{ w_i }[/math]. The resource is then distributed in [math]\displaystyle{ x_i }[/math] amounts by the formula [math]\displaystyle{ x_i=\frac{w_i B}{\sum_jw_j} }[/math]. This method yields an effective price [math]\displaystyle{ p=\frac{\sum_jw_j}{B} }[/math]. This price can proven to be market clearing; thus, the distribution [math]\displaystyle{ x_1,...,x_n }[/math] is optimal. The proof is as so:
Proof
We have [math]\displaystyle{ \underset{x_i}{\operatorname{arg\,max}}\,U_i(x_i)-w_i }[/math] [math]\displaystyle{ = \underset{w_i}{\operatorname{arg\,max}}\,U_i\left(\frac{w_i B}{\sum_jw_j}\right)-w_i }[/math]. Hence,
- [math]\displaystyle{ U^'_i\left(\frac{w_i B}{\sum_jw_j}\right)\left(\frac{B}{\sum_jw_j}-\frac{w_i B}{(\sum_jw_j)^2}\right)-1=0 }[/math]
from which we conclude
- [math]\displaystyle{ U^'_i(x_i)\left(\frac{1}{p}-\frac{1}{p} \left( \frac{x_i}{B}\right)\right)-1=0 }[/math]
and thus [math]\displaystyle{ U^'_i(x_i)\left(1-\frac{x_i}{B}\right)=p. }[/math]
Comparing this result to the equilibrium condition above, we see that when [math]\displaystyle{ \frac{x_i}{B} }[/math] is very small, the two conditions equal each other and thus, the fair sharing game is almost optimal.
References
- ↑ Shah, D.; Tsitsiklis, J. N.; Zhong, Y. (2014). "Qualitative properties of α-fair policies in bandwidth-sharing networks" (in EN). The Annals of Applied Probability 24 (1): 76–113. doi:10.1214/12-AAP915. ISSN 1050-5164. https://projecteuclid.org/euclid.aoap/1389278720.
 |  |
