Bandwidth-sharing game

Last updated June 16, 2023

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 $n$ players. Each player $i$ has utility $U_{i}(x)$ for $x$ units of bandwidth. Player $i$ pays $w_{i}$ for $x$ units of bandwidth and receives net utility of $U_{i}(x)-w_{i}$ . The total amount of bandwidth available is $B$ .

Regarding $U_{i}(x)$ , we assume

$U_{i}(x)\geq 0;$
$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 ${\underset {x}{\operatorname {arg\,max} }}\,U_{i}(x)-px$ . Solving for the maximum yields $U_{i}^{'}(x)=p$ .

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 $i$ is asked for the 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}B}{\sum _{j}w_{j}}}$ . This method yields an effective price $p={\frac {\sum _{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:

Proof

We have ${\underset {x_{i}}{\operatorname {arg\,max} }}\,U_{i}(x_{i})-w_{i}$ $={\underset {w_{i}}{\operatorname {arg\,max} }}\,U_{i}\left({\frac {w_{i}B}{\sum _{j}w_{j}}}\right)-w_{i}$ . Hence,

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

from which we conclude

U_{i}^{'}(x_{i})\left({\frac {1}{p}}-{\frac {1}{p}}\left({\frac {x_{i}}{B}}\right)\right)-1=0

and thus $U_{i}^{'}(x_{i})\left(1-{\frac {x_{i}}{B}}\right)=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.

Related Research Articles

A histogram is an approximate representation of the distribution of numerical data. The term was first introduced by Karl Pearson. To construct a histogram, the first step is to "bin" the range of values—that is, divide the entire range of values into a series of intervals—and then count how many values fall into each interval. The bins are usually specified as consecutive, non-overlapping intervals of a variable. The bins (intervals) must be adjacent and are often of equal size.

In probability theory and statistics, variance is the squared deviation from the mean of a random variable. The variance is also often defined as the square of the standard deviation. Variance is a measure of dispersion, meaning it is a measure of how far a set of numbers is spread out from their average value. It is the second central moment of a distribution, and the covariance of the random variable with itself, and it is often represented by $,,,, or .$

In game theory, the Nash equilibrium, named after the mathematician John Nash, is the most common way to define the solution of a non-cooperative game involving two or more players. In a Nash equilibrium, each player is assumed to know the equilibrium strategies of the other players, and no one has anything to gain by changing only one's own strategy. The principle of Nash equilibrium dates back to the time of Cournot, who in 1838 applied it to competing firms choosing outputs.

In probability theory and statistics, covariance is a measure of the joint variability of two random variables. If the greater values of one variable mainly correspond with the greater values of the other variable, and the same holds for the lesser values, the covariance is positive. In the opposite case, when the greater values of one variable mainly correspond to the lesser values of the other,, the covariance is negative. The sign of the covariance, therefore, shows the tendency in the linear relationship between the variables. The magnitude of the covariance is the geometric mean of the variances that are in-common for the two random variables. The correlation coefficient normalizes the covariance by dividing by the geometric mean of the total variances for the two random variables.

<span class="mw-page-title-main">Gumbel distribution</span> Particular case of the generalized extreme value distribution

In probability theory and statistics, the Gumbel distribution is used to model the distribution of the maximum of a number of samples of various distributions.

In mathematics, the arguments of the maxima are the points, or elements, of the domain of some function at which the function values are maximized. In contrast to global maxima, which refers to the largest outputs of a function, arg max refers to the inputs, or arguments, at which the function outputs are as large as possible.

In the physical sciences, the Airy function (or Airy function of the first kind) $Ai(x)$ is a special function named after the British astronomer George Biddell Airy (1801–1892). The function $Ai(x)$ and the related function $Bi(x)$ , are linearly independent solutions to the differential equation

In mathematics, the upper and lower incomplete gamma functions are types of special functions which arise as solutions to various mathematical problems such as certain integrals.

In mathematics, the exponential integral Ei is a special function on the complex plane.

Mechanism design is a field in economics and game theory that takes an objectives-first approach to designing economic mechanisms or incentives, toward desired objectives, in strategic settings, where players act rationally. Because it starts at the end of the game, then goes backwards, it is also called reverse game theory. It has broad applications, from economics and politics in such fields as market design, auction theory and social choice theory to networked-systems.

In Bayesian statistics, a maximum a posteriori probability (MAP) estimate is an estimate of an unknown quantity, that equals the mode of the posterior distribution. The MAP can be used to obtain a point estimate of an unobserved quantity on the basis of empirical data. It is closely related to the method of maximum likelihood (ML) estimation, but employs an augmented optimization objective which incorporates a prior distribution over the quantity one wants to estimate. MAP estimation can therefore be seen as a regularization of maximum likelihood estimation.

<span class="mw-page-title-main">Chebyshev function</span>

In mathematics, the Chebyshev function is either a scalarising function (Tchebycheff function) or one of two related functions. The first Chebyshev function $ϑ (x)$ or $θ (x)$ is given by

The softmax function, also known as softargmax or normalized exponential function, converts a vector of $K$ real numbers into a probability distribution of $K$ possible outcomes. It is a generalization of the logistic function to multiple dimensions, and used in multinomial logistic regression. The softmax function is often used as the last activation function of a neural network to normalize the output of a network to a probability distribution over predicted output classes, based on Luce's choice axiom.

In mathematics and statistics, a circular mean or angular mean is a mean designed for angles and similar cyclic quantities, such as times of day, and fractional parts of real numbers.

The method of iteratively reweighted least squares (IRLS) is used to solve certain optimization problems with objective functions of the form of a p-norm:

<span class="mw-page-title-main">Quantile regression</span> Statistics concept

Quantile regression is a type of regression analysis used in statistics and econometrics. Whereas the method of least squares estimates the conditional mean of the response variable across values of the predictor variables, quantile regression estimates the conditional median of the response variable. Quantile regression is an extension of linear regression used when the conditions of linear regression are not met.

A kernel smoother is a statistical technique to estimate a real valued function $as the weighted average of neighboring observed data. The weight is defined by the kernel, such that closer points are given higher weights. The estimated function is smooth, and the level of smoothness is set by a single parameter. Kernel smoothing is a type of weighted moving average.$

The Price of Anarchy (PoA) is a concept in economics and game theory that measures how the efficiency of a system degrades due to selfish behavior of its agents. It is a general notion that can be extended to diverse systems and notions of efficiency. For example, consider the system of transportation of a city and many agents trying to go from some initial location to a destination. Let efficiency in this case mean the average time for an agent to reach the destination. In the 'centralized' solution, a central authority can tell each agent which path to take in order to minimize the average travel time. In the 'decentralized' version, each agent chooses its own path. The Price of Anarchy measures the ratio between average travel time in the two cases.

In machine learning, Manifold regularization is a technique for using the shape of a dataset to constrain the functions that should be learned on that dataset. In many machine learning problems, the data to be learned do not cover the entire input space. For example, a facial recognition system may not need to classify any possible image, but only the subset of images that contain faces. The technique of manifold learning assumes that the relevant subset of data comes from a manifold, a mathematical structure with useful properties. The technique also assumes that the function to be learned is smooth: data with different labels are not likely to be close together, and so the labeling function should not change quickly in areas where there are likely to be many data points. Because of this assumption, a manifold regularization algorithm can use unlabeled data to inform where the learned function is allowed to change quickly and where it is not, using an extension of the technique of Tikhonov regularization. Manifold regularization algorithms can extend supervised learning algorithms in semi-supervised learning and transductive learning settings, where unlabeled data are available. The technique has been used for applications including medical imaging, geographical imaging, and object recognition.

A Stein discrepancy is a statistical divergence between two probability measures that is rooted in Stein's method. It was first formulated as a tool to assess the quality of Markov chain Monte Carlo samplers, but has since been used in diverse settings in statistics, machine learning and computer science.

References

↑ Shah, D.; Tsitsiklis, J. N.; Zhong, Y. (2014). "Qualitative properties of α-fair policies in bandwidth-sharing networks". The Annals of Applied Probability. 24 (1): 76–113. arXiv: 1104.2340 . doi:10.1214/12-AAP915. ISSN 1050-5164. S2CID 3731511.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Shah, D.; Tsitsiklis, J. N.; Zhong, Y. (2014). "Qualitative properties of α-fair policies in bandwidth-sharing networks". The Annals of Applied Probability. 24 (1): 76–113. arXiv: 1104.2340 . doi:10.1214/12-AAP915. ISSN 1050-5164. S2CID 3731511.

[1]