Fair resource allocation over time

Overview & Synopsis

We consider the overtime version of the Max-Min Fair Allocation problem. Given a time horizon t = 1, 2,. .. , T , with at each time t a set of demands and a set of available resources that may change over the time defining instance I t , we seek a sequence of solutions S 1 , S 2 ,. .. , S T that (1) are near-optimal at each time t, and (2) as stable as possible (inducing small modification costs). We focus on the impact of the knowledge of the future on the quality and the stability of the returned solutions by distinguishing three settings: the off-line setting where the whole set of instances through the time horizon is known in advance, the on-line setting where no future instance is known, and the k-lookahead setting where at time t, the instances at times t + 1,. .. , t + k are known. We first consider the case without restrictions where the set of resources and the set of agents are the same for all instances and where every resource can be allocated to any agent. For the off-line setting, we show that the overtime version of the problem is much harder than the static one, since it becomes N P-hard even for families of instances for which the static problem is trivial. Then, we provide a ρ ρ+1-approximation algorithm for the off-line setting using as subroutine a ρ-approximation algorithm for the static version. We also give a ρ ρ+1-competitive algorithm for the online setting using also as subroutine a ρ-approximation algorithm for the static version. Furthermore, for the case with restrictions, we show that in the off-line setting it is possible to get a polynomial-time algorithm with the same approximation ratio as in the case without restrictions. For the online setting, we prove that it is not possible to find an online algorithm with bounded competitive ratio. For the 1-lookahead setting however, we give a ρ 2(2ρ+1)-approximation algorithm using as subroutine a ρ-approximation algorithm for the static version.