Dynamics of Quota Sharing in Shared Data Plans
16 June 2016
We consider the problem of managing the sharing of data among multiple users in a mobile shared data plan. Such plans allow for quota to be shifted from a user with only small requests in a given month to a user with larger requests. However, in the long run we wish for this sharing tobe done in a fair manner. We consider a number of different variants of the problem, depending on whether we are optimizing fairness on a month-by-month basis or within a single month. Our results also differ depending on whether user requests for data are stochastic or adversarial. Our first result is that for the month-by-month problem we can achieve optimality using a gradient-ascent algorithm for the case of stochastic requests. However, for the month-by-month problem with adversarial arrivals some user can receive service that is only a 1/n fraction of optimal, where n is the number of users in the group. The adversarial situation is better for the intra-month problem in that we can achieve a 1/O(log n) fraction of the optimal service for all users.
