Subject: [conex] On Economic Heavy Hitters: Shapley Value Analysis of the 95th-Percentile Pricing

From: Lars Eggert <[email-masked]>
Date: Mon, 1 Nov 2010 16:57:54 +1100

Of potential interest to the WG:

On Economic Heavy Hitters: Shapley Value Analysis of the 95th-Percentile Pricing
Rade Stanojevic (Telefonica Research)
Nikolaos Laoutaris (Telefonica Research)
Pablo Rodriguez (Telefonica Research)
http://conferences.sigcomm.org/imc/2010/papers/p75.pdf

Cost control for the Internet access providers (AP) influ- ences not only the nominal speeds offered to the customers, but also other, more controversial, policies related to traf- fic shaping and discrimination. Given that the cost for the AP is determined by the peak-hour traffic (e.g. through the 95th-percentile), the individual user contribution towards the aggregate cost is not a linear function of its byte usage. In this paper we propose a metric for evaluating the contri- bution each individual user has on the peak demand, that is based on Shapley value, a well known game-theoretic con- cept. Given the computational complexity of calculating the Shapley value, we use a Monte Carlo method for approxi- mating it with reasonable accuracy. We employ our method- ology to study a dataset that logs per-subscriber temporal usage patterns over one month period for 10K broadband subscribers of a European AP and report observed results.