No-regret Algorithms for Fair Resource Allocation

We consider a fair resource allocation problem in the no-regret setting against an unrestricted adversary. The objective is to allocate resources equitably among several agents in an online fashion so that the difference of the aggregate \alpha -fair utilities of the agents achieved by an optimal static clairvoyant allocation and the online policy grows sublinearly with time. The problem inherits its difficulty from the non-separable nature of the global \alpha -fairness function. Previously, it was shown that no online policy could achieve a sublinear standard regret in this problem. In this paper, we propose an efficient online resource allocation policy, called Online Fair Allocation ( \texttt{OFA}), that achieves sublinear c_\alpha -approximate regret with approximation factor c_\alpha (1-\alpha) {-(1-\alpha)}\leq 1.445, for 0\leq \alpha 1 .