Height zeta function

From formulasearchengine
Revision as of 18:32, 3 August 2012 by Deltahedron (talk | contribs) (typo)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Template:Orphan

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

  • n players
  • each player i has utility Ui(x) for amount x of bandwidth
  • user i pays wi for amount x of bandwidth and receives net utility of Ui(x)wi
  • the total amount of bandwidth available is B

We also use assumptions regarding Ui(x)

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 argmaxxUi(x)px. Solving for the maximum yields Ui'(x)=p.

The 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.

A 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 amount they are willing to pay for the given resource denoted by wi. The resource is then distributed in xi amounts by the formula xi=(wijwj)*(B). This method yields an effective price p=jwjB. This price can proven to be market clearing thus the distribution x1,...,xn is optimal. The proof is as so:

Proof

argmaxxiUi(xi)wi

argmaxwiUi(wijwj*B)wi
Ui'(wijwj*B)(1jwj*Bwi(jwj)2*B)1=0
Ui'(xi)(1p1p*xiB)1=0
Ui'(xi)(1xiB)=p

Comparing this result to the equilibrium condition above, we see that when xiB is very small, the two conditions equal each other and thus, the fair sharing game is almost optimal.

References