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 α-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 α-fairness function. Previously, it was shown that no online policy could achieve a sublinear standard regret in this problem.