Pricing Network Servicesby Jun Shu, Pravin VaraiyaIntroduction: Two Network ProblemsSPAC mechanismVCG Mechanism RevisitVCG: Payoff to each AgentVCG: PaymentIntuition behind VCG mechanismsRequirements for SPAC mechanismSPAC Mechanism Definitions (1)SPAC Mechanism Definitions (2)SPAC Mechanism Definitions (3)Illustration of SPAC defintionsSolution RequirementsSolution ImplementationIs SPAC strategy-proof?Is SPAC strategy-proof??Illustration of Congestion PriceRelation to VCG mechanismSPAC is strategy-proofConclusion and Open QuestionsPricing Network Servicesby Jun Shu, Pravin VaraiyaPresented byHayden SoSeptember 25, 2003Introduction: Two Network Problems• Engineering:– A game theoretical sound congestion control mechanism that is incentive compatible– Unlike TCP, which is not incentive compatible– Use pricing for congestion control• Economic:– Derive a pricing scheme for QoS– Free ISP from “Flat Rate” woesSPAC mechanism• Smart Payment Admission Control Mechanism• Assume users compete for network bandwidth in non-cooperative manners• Find an economically efficient way to provide statistically guaranteed service to users, based on their value on services• SPAC mechanism to be implemented on the edge of network management domain– Treats aggregated packet flows of different QoS as agents in the mechanism• SPAC calculates service prices using VCG mechanismVCG Mechanism Revisit• A family of mechanisms• Each agent has quasi-linear preference• Characteristic of VCG mechanism:– Direct revelation– Strategy-proof– Allocatively-Efficient• With careful design, can also be:– Individual-rational– (Weak) budget-balanceVCG: Payoff to each Agent***whereAgent 's payoff isˆˆ() ( (), )ˆ( ) is the optimal choice of mechanismˆˆ() arg max (, )ˆ is the reported type profile is the true type of agent is the payment from ii iijjxXjiiiuvx pxxvxipθθθθθθθθ∈=−=∑agent to the mechanismiVCG: Payment**Payment has the form:ˆˆˆ() ((),)ˆ( ) is a value independent of agent 's presenceˆFor , ( ) is usually defined as:ˆˆˆ() ((),)Therefore, ii j jjiiiijijjiph vxhiIndividual Rationality hhvxθθθθθθθθ−≠−−−−≠=−=∑∑** *ˆˆ ˆˆ ˆˆ ( ) ( ( ), ) ( ( ), ) ( ( ), )ii ijjjijji jiuvx vx vxθθθ θθ θ θ−≠≠=+ −∑∑Intuition behind VCG mechanismsDon’t care: Nothing I can doMy own happiness mightlead to a social choice that makes Miss j less happyMy Happiness:Higher = better** *ˆˆ ˆˆ ˆˆ() ( (), ) ( (), ) ( ( ), )ii ijjjijji jix vx vxθθθ θθ θ θ−≠≠=+ −∑∑I better make a sensible choice so that I am happy, miss j’s are happy, and thus everyone in the society is happy!!~ Truth Telling ~uvRequirements for SPAC mechanism• Incentive Compatible– Truth-telling dominant strategy– Strategy-proof– User tends to cheat if not strategy-proof• Individual Rational– User will not join the mechanism if it were not IR– ISP will not implement the mechanism if it were not IR to them• Efficient allocation• Fall back to best-effort– Everyone admitted, must and is willing to play– Auction for “additional service”– Charge only if user induces “congestion”SPAC Mechanism Definitions (1)• n + 1 players (n agents + 1 principal)• m levels of statistically guaranteed QoS (delivery rate), denoted d = (d0,d1,…,dm-1), and 0 ≤ d0 < d1<…< dm-1< 1• For simplicity, assume a constant number Akof agent admitted with guaranteed delivery rate of dk• Prior to receiving service, each agent announces their values, called bids, of the service: b = (b1,…,bi ,…,bn)• Each agent’s true value of the service is denoted:θ= (θ1,…,θi ,…,θn)SPAC Mechanism Definitions (2)• Denote the final ordering of all n bids be b(1),b(2),…,b(n)• Based on b, the principal computes a solution vector x = (x1,…,xi,…,xn)– xiis the service delivery rate agent i gets• For mathematical notation convenience, define1if ()0otherwiseikkixdQx==SPAC Mechanism Definitions (3)• Based on b, the principal computes a congestion price vector p = (p0,p1,…,pm-1) for each QoS level• The utility for agent i is therefore:1011()where() 0and 1,..., 1,() () ( )mllkkk kknApbkmpb p b d d b−=−−−≡∀= −=+−∑10(, ) ( )mii ii kkikub x pQ xθθ−==−∑Illustration of SPAC defintionsdq-1dm-1dm-2Xr ratedq(n)bb(1)=0b(n-1)d1 d0Am-1Am-2AqAq-1A1A0$b(e-1)(e)bxe= dqxe-1= dq-1xn= xn-1= dm-1Best EffortZoneb(j)> 0Solution Requirements• The final solution to the auction, x*(b), must be efficient and feasible, therefore• And subject to capacity constraint• And subject to universal service coverage1*( ) argmaxiniixXixb bx∈==∑1()nki kiQx A=≤∑10mkkAn−=≥∑Solution Implementation• Sort all the bids in descending order• The highest Am-1bidders are admitted to QoS level m-1 with delivery rate dm-1• The next higher Am-2bidders receive dm-2• Continue until all bidders are admitted (at least to level 0)What about strategy-proofness?Is SPAC strategy-proof?• SPAC is a VCG mechanism implementation– It is strategy proof– How? It doesn’t look like so…• Each agent’s utility (at QoS level k) in SPAC is:• In word, it is agent i’s happiness xiθiminus the congestion price, pk, she has to pay:(, ) ()ii iikub x p bθθ=−111()() () ( )mllkkk kknApb pb ddb−=−−−=+−∑Is SPAC strategy-proof??• Expanding the recursive definition of pkyields• Now, note that denotes the highest bid of agents who are rejected from the q-th or above levels of QoS• In other word: the payment term of agent i’s utility is to compensate those suffered because agent ienters the gameWHO suffers?11()1(, ) ( )mllqkii ii qqnAqub x d d bθθ−=−−==− −∑∑1()mllqnAb−=−∑Illustration of Congestion Price(n)b(n-1)bXr ratedm-1dm-2dqdq-1d1d0Am-1Am-2AqAq-1A1A0$b(e-1)(e)bbb(n)(n+1)bA’0b(e-1)b(e)b(e+1)After arrival of agent iNOT HAPPY!! Utility decreases from dqb(e)to dq-1b(e)b(e+1)(e+2)not affected not affected not affectedRelation to VCG mechanism• Therefore, agent i’s utility• Now, it looks very much like the VCG quasi-linear utility function of an agent, with11()1(, ) ( )can be rewritten as:(, )where denotes 's allocation before joins the gamemllqkii ii qqnAqii i ii jj jjji jiijub x ddbub x bx bxxj iθθθθ−=−−=−≠≠−=− −∑=+ −∑∑∑((), )iiiivx xθθθ=SPAC is strategy-proof• VCG mechanisms are strategy-proof• By showing SPAC is an
View Full Document
Unlocking...