Abstract
In this paper, we focus on how to dynamically allocate a divisible resource fairly among n players who arrive and depart over time. The players may have general heterogeneous valuations over the resource. It is known that exact envy-free and proportional allocations may not exist in the dynamic setting [Walsh, 2011]. Thus, we will study to what extent we can guarantee the fairness in the dynamic setting. We first design two algorithms which are O(log n)-proportional and O(n)-envy-free for the setting with general valuations. Then by constructing the adversary instances such that all dynamic algorithms must be at least ?(1)-proportional and ?( logn n )-envy-free, we show that the bounds are tight up to a logarithmic factor. Moreover, we introduce a setting where the players’ valuations are uniform on the resource but with different demands, which generalizes the setting of [Friedman et al., 2015]. We prove an O(log n) upper bound and a tight lower bound for this case.