Dynamic Fair Division Problem with General Valuations

1 Introduction

Initiated by the work of [Steinhaus, 1948], the fair division problem has been widely studied in the literature of economics, mathematics and computer science [Dubins and Spanier, 1961; Stromquist, 1980; Alon, 1987; Brams and Taylor, 1995; 1996; Robertson and Webb, 1998; Aziz and Mackenzie, 2016]. It mainly considers the problem of fairly allocating a divisible resource among a group of players who have different preferences over the resource.

To capture fairness, many solution concepts have been proposed, such as proportionality and envy-freeness [Brams and Taylor, 1996; Neyman, 1946; Varian, 1974; Dubins and Spanier, 1961]. An allocation is proportional if each player's valuation for his received resource is at least 1n fraction of his valuation for the whole resource, where n is the number of players. An allocation is envy-free if no player values another player's allocation more than his own [Steinhaus, 1948]. One of the difficulties in finding allocations which are proportional or envy-free is that the resource may not be uniformly structured, such as time and land, and different players may hold different valuations over the same part of the resource.

Most of the previous studies have been focused on the static fair division problem, which assumes that all players arrive simultaneously. Recently, the dynamic fair division problem has been considered in [Walsh, 2011; Friedman et al., 2015; 2017]. A real-life application of the dynamic fair division problem is to fairly allocate the resource on a server among different jobs. In this case, different jobs arrive and depart at different time, and each job has different values for the resource allocated to it. The objective here is to balance the resource allocated to different jobs. Unlike the static setting where an envy-free allocation is guaranteed to exist [Brams and Taylor, 1995; Su, 1999], [Walsh, 2011] shows that envy-free or proportional allocations may not exist when the players arrive one by one over time. Therefore, a weak version of envy-freeness is discussed in [Walsh, 2011], where the only constraint is that each player does not envy the allocations of the players who will arrive after him. However, this may not be sufficient to capture fairness in reality because the players may still observe the allocations of the previous players and envy their allocations. For example, an allocation which allocates the whole resource to the first player is considered to be envy-free in [Walsh, 2011], which is not plausible. Thus it is natural to explore to what extent we can approximate the envy-freeness and proportionality in the dynamic setting. This problem has been discussed in the literature, but they only considered the case where the players have uniform valuations. In [Friedman et al., 2015], there is a single resource, and in [Friedman et al., 2017], there are multiple resources and the players have different demands for each resource. The latter one seems a general problem, but it can still be reduced to the problem with a single divisible resource while each player has piecewise linear valuations. We prove the results for settings with valuations more general than [Friedman et al., 2015; 2017].

Our Models and Results. In this paper, we aim at designing algorithms for the dynamic fair division (DFD) problem so that the maximum "dissatisfaction" among all players is minimized. We allow the players to have arbitrary heterogeneous yet additive valuations, which is a general class of valuations considered in almost all the fair division literature [Procaccia, 2016]. In our model, different players arrive and depart at different time, and the decision maker needs to decide each player's allocation upon his arrival. We say an allocation is ξ-envy-free if at any time, each player's valuation on his allocation is at least 1ξ fraction of his value on any other player's allocation. An allocation is σ-proportional if at any time, each player's value on his own allocation is at least 1 σn fraction of his value on the whole resource. We refer to ξ and σ as the approximation ratio of the allocation.

The algorithms proposed in this paper are τ-recallable algorithms with τ ∈ Z+, which means when a new player arrives, the decision maker can recall the resource from at most τ previous players and reallocate it [Friedman et al., 2015]. If reallocation is not permitted, it is easy to see that the approximation ratio is unbounded, because for any dynamic algorithm, the adversary can always choose the valuation for the second player such that he is only interested in the allocation of the first player. In this paper, we will focus on the 1-recallable algorithms and at the end of each section, we will briefly discuss the τ -recallable algorithms for any constant τ , since they basically share the same idea and the same bound.

Our first contribution is to design two dynamic 1-recallable algorithms for the general DFD problem which are O(n)- envy-free and O(log n)-proportional. Then we prove that for any dynamic 1-recallable algorithm, there exists an adversary instance such that the approximation ratio of the algorithm is at least Ω( n logn ), even if all the players' valuations are piecewise uniform [Chen et al., 2013]. Since the Ω(1) lower bound for proportionality is already proved in [Friedman et al., 2015], all our bounds are tight up to a logarithmic factor.

Because of the strong lower bound in the general setting, no one can hope to improve the fairness for settings with valuations more general than the piecewise uniform valuations. Thus, it is natural to discover the set of valuations with better dynamic performance. In [Friedman et al., 2015], the authors show that if the players' valuations are uniform, there exist O(1)-envy-free algorithms. In this paper, we generalize their model, by allowing different players to have different demands over the resource. When the players have uniform valuations with different demands, an allocation is fair if (1) it meets all the players' demands or (2) each player gets at least his demand divided by total demand [Ghodsi et al., 2011]. As before, in the static setting, a fair allocation always exists. However, in the dynamic setting, the adversary can manipulate the future players to violate the fairness. We say an allocation is η-fair if each player gets 1 η fraction of his allocated resource in a fair allocation. We design an O(logn)-fair 1recallable algorithm and we prove that the bound is tight by constructing an adversary instance such that no 1-recallable algorithm can be better than Ω(log n)-fair.

Additional Related Work. The fair division problem with multiple indivisible resources is also a problem widely studied in the literature [Budish, 2011; Kurokawa et al., 2018; Amanatidis et al., 2017; Brandt et al., 2016; Endriss, 2017]. Since the envy-free allocation cannot be guaranteed in this setting, the notion of fairness is captured by different relaxed versions, such as envy-free up to one item (EF1), which can be found in polynomial time [Budish, 2011]. A stronger fairness concept, envy-free up to any item (EFX), is proposed in [Caragiannis et al., 2016]. It is shown in [Plaut and Roughgarde, 2018] that such an allocation exists for identical valuations, but the existence of EFX allocations is still unknown for general valuations. However, the authors show that there exists an allocation which is a 2 approximation to the EFX allocation. Another solution concept adopted for indivisible resources is the maxmin share, which can be approximated within a factor of 2/3 in polynomial time [Kurokawa et al., 2018]. The approximation ratio of this problem is improved to 3/4 in [Ghodsi et al., 2017]. The authors in [Ghodsi et al., 2017] also prove that the maximin fair allocation can be approximated within a factor of 3 when the valuations of the players are submodular, a factor of 5 when the valuations of the players are XOS, and a logarithmic factor when the valuations of the players are subadditive.

2 Preliminaries

Fair Division Problem. The fair division problem is to divide and allocate a divisible and heterogeneous resource fairly among n players, where the resource is represented by the real number interval [0, 1] and the player set is represented by N = {1, · · · , n}. Each player i has a valuation vi, mapping any subset of the resource to a nonnegative value, representing i's preference over the resource. Formally, for any set I ⊆ [0, 1], player i's value for taking set I is vi(I) ∈ R+ ∪ {0}. The valuation profile is denoted by v = {v1, . . . , vn} and the set of all possible valuation profiles is denoted by V. In this paper, besides the most general valuations, we also consider two special ones.

One widely studied valuation is piecewise uniform valuation [Chen et al., 2013]. A player has piecewise uniform valuation if and only if he has uniform valuation over a subset of the resource (which may not be a continuous interval). That is, for player i, the valuation vi is piecewise uniform if and only if there exists Ii ⊆ [0, 1] such that vi(I) = |I ∩ Ii| for all I ⊆ [0, 1]. By normalizing each player's valuation to range [0, 1], we have that for any I ⊆ [0, 1], vi(I) = |I∩Ii| |Ii| .

Another valuation studied in this paper is called uniform with demand. In this model, each player has uniform valuation over the resource and he only cares the size of the resources he gets rather than which part of the resource is allocated to him. In general, different players may have different demand over the resource, and when the allocated resource exceeds the player's demand, his valuation for the allocated resource will not increase. For player i, we denote his demand as di ∈ (0, 1], and his valuation vi is uniform with demand if and only if for any I ⊆ [0, 1], vi(I) = min{|I|, di}. By normalizing each player's valuation to range [0, 1], we have that for any I ⊆ [0, 1], vi(I) = min{ |I| di , 1}. In our paper, we adopt the normalized form of the valuations, but all the results hold for the valuations without normalization.

An allocation is denoted by a partition of [0, 1], A = (A0,A1, · · · ,An) where A0 is the unallocated resource and Ai is the resource allocated to player i for any i ∈ N. The set of all such possible partitions of [0, 1] is denoted by U. A fair division algorithm (or an allocation rule) A is a mapping from a valuation profile to an allocation, i.e., A : V → U.

Two widely adopted fairness solution concept are proportionality and envy-freeness. An allocation A is proportional if and only if each player gets at least 1n fraction of the whole resource, and an allocation A is envy-free if and only if each player will not envy any other player's allocation. In this paper, we care more about the relaxed version of them. Formally, we say an allocation A is σ-proportional if vi(Ai) ≥ 1 σn vi([0, 1]) for any player i, and an allocation A is ξ-envy-free if vi(Ai) ≥ 1ξ vi(Aj) for any player i and j.

When players' valuations are uniform with demand, a fairness solution concept stronger than proportionality is required here because for a proportional allocation AP , it only guarantees that for each player i, vi(APi ) ≥ vi([0,1]) n = 1n . However, in the static setting there exists an allocation A such that each player i gets di max{d,1} fraction of the whole resource, where d = ∑j∈N dj is the total demand of the players, and player i's value is guaranteed to be vi(Ai) = 1 max{d,1} . Since the total demand d might be significantly smaller than n, vi(Ai) might be significantly larger than vi(APi ). Therefore, a stronger notion of fairness is defined as follows for uniform with demand valuations [Ghodsi et al., 2011]. Formally, an allocation A is fair if vi(Ai) ≥ 1 max{d,1} , and A is η-fair if vi(Ai) ≥ 1 η·max{d,1} .

Dynamic Fair Division Problem. Now we extend the fair division problem to the dynamic setting, where player i arrives at time ti and departs at time tdi , with tdi > ti. Without loss of generality, we have 0 < t1 ≤ t2 ≤ · · · ≤ tn, where n is the maximum number of players that could possibly arrive and is given to the algorithm as an input. However, the algorithm does not know the exact number of arriving players, or the players' valuations until their arrival. The algorithm needs to allocate the resource to each player when he arrives without knowing future events, including his departure time. In this paper, we will design our algorithms and state our results for the arrival only model, where td1 = td2 = · · · = tdn > tn. However, all our lower bounds and upper bounds can be directly applied for settings where players have arbitrary departure time with the same approximation ratio. See the full version [Li et al., 2018] for more details.

Formally, the allocation of the algorithm at time ti is denoted by Ai = (Ai0 ,Ai1 , · · · ,Aii ) and the total output from time 0 to time tn is denoted by A = (Ai )i∈{0,1,··· ,n} where A0 = {A00 } and A00 = [0, 1]. An algorithm is called τrecallable if for any i ∈ [n-1], there exists s ≤ min{τ, i} and a set of players S = {i1, · · · , is} ⊆ [i] such that Ai+1 j = Aij for all j ∈ [i]\S, and Ai+1 j ⊆ Aij for all j ∈ S.

In the following we extend the definition for fairness to the dynamic setting. An allocation A is σ-proportional if

and an allocation A is ξ-envy-free if

For the uniform with demand valuations in the dynamic setting, an allocation A is η-fair if

In this paper, we say an algorithm A is σ-proportional, ξenvy-free or η-fair for valuation space V if for any valuation profile v ∈ V, A(v) is σ-proportional, ξ-envy-free or η-fair. Note that, since we do not assume that the resource must be allocated to any player, a trivial envy-free algorithm is that everyone gets nothing. Such an algorithm is called empty in this paper.

Remark. In this paper, we only consider deterministic algorithms because there exists a trivial randomized algorithm which is proportional and envy-free in expectation in the dynamic setting [Chen et al., 2013]. This randomized algorithm is also fair for uniform with demand valuations.

3 Dynamic Fair Division (DFD) Problem

In this section, we consider the players' values to be additive. First we state the results for proportionality. In Theorem 6.1 of [Friedman et al., 2015], no 1-recallable algorithm can be better than (2 ln2)-proportional even if the players' valuations are uniform, i.e., vi(I) = |I|, for any i ∈ [n]. In the following, we design the 1-recallable algorithm A1DFD , defined in Algorithm 1, which is O(logn)-proportional for the DFD problem with general valuations. Roughly speaking, when player i arrives, algorithm A1DFD divides the previous players' allocated resource into 2i(3+ln i) subsets and lets player i choose his favorite bundle of resource from one player, where the size of the bundle depends on the current approximation ratio of any player j who arrived before player i. The performance of algorithmA1DFD is formally analyzed in Theorem 1.

Algorithm 1 1-Recallable Algorithm A1DFD

Input: A sequence of players N = {1, · · · , n} arriving and departing along time.

• 1: Initially, Aij = ∅ for all 1 ≤ i ≤ n and 0 ≤ j ≤ i.
• 2: When the first player arrives, setting A11 = [0, 1].
• 3: for any arriving player i > 1 do
• 4: σ = ⌊2i(3+ ln i)⌋.
• 5: for 0 < j < i do
• 6: Partition Ai-1 j into σ sets {Ai-1 j,1 , · · · ,Ai-1 j,σ } with vj (Ai-1 j,1 ) = · · · = vj(Ai-1 j,σ ).
• 7: σj = ⌈ vj([0,1]) vj (Ai-1 j ) ⌉.
• 8: end for

• 11: Aij ∗ = ∪k/∈S∗Ai-1 j ∗ ,k .
• 12: Aij = Ai-1 j , ∀j ∈ [i -1] -{j ∗ }.
• 13: end for

Output: Allocation A = (Aij )0≤i≤n,0≤j≤i.

Theorem 1. For any n ≥ 1, 1-recallable algorithm A1DFD is O(log n)-proportional for the DFD problem with n players.

Proof. In the following, we prove the theorem by induction. When there is only 1 player, algorithm A1DFD is proportional since the player gets the whole resource. Assuming that when there are i - 1 players, algorithm A1DFD is 2(3 + ln(i - 1))- proportional, we show that when player i arrives at time ti, algorithm A1DFD is 2(3 + ln i)-proportional.

First, we show that for any j < i, player j is 2(3 + ln i)- proportional at time ti. Note that at least σj elements from {Ai-1 j,1 , · · · ,Ai-1 j,⌊2i(3+ln i)⌋ } is allocated to player j and player j has the same value for them. Thus,

Next, note that for player i, the worst case happens when his value for the resource allocated to player j is ρj·vi([0,1]) ∑j≤i-1 ρj , where ρj = ⌊2i(3+ln i)⌋ ⌊2i(3+ln i)⌋-σj . In any other cases, by choosing his favorite bundle, player i's value will increase. Thus,

The second inequality holds by carefully analyzing the value σj for each player j who arrived before player i. Note that at any time tj , the algorithm can only make the assignment such that the approximation ratio of the new arriving player and the player whose resource is recalled is 2j(3 + ln j), while the approximation ratio for all other players remain unchanged. Thus when player i arrives, there exist at least i+1-2x players with approximation ratio less than 2(i-x)(3+ln(i-x)). By properly eliminating the rounding in the term, the third inequality holds. Therefore, by induction, algorithm A1DFD is O(log n)-proportional and Theorem 1 holds.

Next we show how to design the O(n)-envy-free algorithm A2DFD , which is quite similar to algorithm A1DFD . Briefly speaking, A2DFD allocates the whole resource to the first player. Then, when player i arrives, for each player j < i, A2DFD uniformly divides the resource allocated to player j into i equal subsets and let player i chooses his favorite set. The formal description is omitted here due to the space limit.

Theorem 2. For any n ≥ 1, 1-recallable algorithm A2DFD is O(n)-envy-free for the DFD problem with n players.

Proof. Again we prove by induction. When player 1 arrives, A11 is exactly [0, 1]. That is, A2DFD is envy-free. Assume that for player i ≥ 2, A2DFD is (i - 1)-envy-free at time ti-1. Now let us prove that all i players are i-envy-free at time ti by analyzing their value at time ti.

First, we prove that player i is i-envy-free at time ti. Assume that the allocation of player j, Ai-1 j , is partitioned into i sets {Ai-1 j,1 , · · · ,Ai-1 j,i }. Since player i is allocated with his favorite set Ai-1 j ∗ ,k∗ ∈ {Ai-1 j,k }j<i,k≤i, for any j < i,

Next, we show that for any j ∈ [i - 1], player j is i-envyfree at time ti. By induction hypothesis, for any j, j ′ ∈ [i-1],

Note that Ai-1 j is partitioned into i sets with equal values, and at most one of them is allocated to player i. Hence, for any j, j ′ ∈ [i - 1],

Since the allocation of player i at time ti is also a subset of player j ∗ 's allocation at time i-1, according to Inequality 3, we have

Combining Inequalities 2, 3 and 4, all players are i-envyfree at time ti. By induction, algorithmA2DFD is n-envy-free. Thus finishes the proof of Theorem 2.

We have designed an 1-recallable algorithm which is O(n)-envy-free for the DFD problem with general valuations. Next we show that this bound is almost tight by proving that all 1-recallable algorithms must be at least Ω( n log n )- envy-free, even if the players' valuations are piecewise uniform (DFDPU). Formally, we have the following theorem.

Theorem 3. For any 1-recallable algorithm A (except empty algorithm) for the DFDPU problem, A is Ω( n log n )-envy-free with n players.

Proof. Assume there exists an algorithmA which is ξ-envyfree and not empty. Consider the following adversary instance where for player 1, v1(I) = |I| and for any player i ≥ 2, vi(I) = |I∩Ai-1 1 | |Ai-1 1 | . That is, the first player wants the whole resource and each new arriving player only wants the resource allocated to the first player by A at time ti-1. Since A is ξ-envy-free and not empty, we must have Ai1 ̸= ∅ for any i ≤ n, and the adversary instance is well defined.

First we consider the envy-freeness for player i ≥ 2. Since the resource that player i values is exactly the resource allocated to player 1 at time ti-1, to ensure that player i is ξenvy-free at time ti, the algorithm must recall the resource from player 1's and reallocate at least 1 1+ξ fraction of the resource to player i. Therefore,

When all n players have arrived, to ensure that player 1 is ξ-envy-free, we have

The first and the second inequality holds due to the ξenvy-freeness of player 1 at time tn and player 2 at time t2. The first equality holds because player 1 is always the player who needs to be recalled. Therefore, Ai2 = A22 for any 2 ≤ i ≤ n. The second and the last equality holds because by the construction of the valuations of player 1 and player 2, v1(I) = 1 |A11 | v2(I) for any I ⊆ A11 .

Combining inequalities 5 and 6, we have

By solving the above inequality, ξ = Ω( n log n ) and Theorem 3 holds.

Remark. Given a valuation profile v, we say an allocation A is non-wasteful if for all player i, we only allocate the resource that he values to him. That is, for any i ≤ j ≤ n and I ⊆ Aji , vi(I) > 0. We say an algorithm A is non-wasteful for valuation space V if for any v ∈ V, A(v) is non-wasteful. Then if we consider the τ -recallable algorithm where τ can be any constant, the adversary instance in the proof of Theorem 3 still shows that no non-wasteful algorithm can be o( n log n )- envy-free even for piecewise uniform valuations.

4 When the Valuation Function is Uniform with Demand (UD)

In this section, we study the dynamic fair division problem with uniform with demand valuations. Since in this model, the players do not care which part of the resource is allocated to him, we regard the allocation Aij in A = (Aij )0≤i≤n,0≤j≤i as the size of the allocated resource.

For the UD problem, a simple greedy algorithm is 2-envyfree and 2-proportional. However, our main focus in this section is its performance under the more demanding fairness solution concept. First we consider the following special case where the smallest demand is within a constant fraction of the largest demand. This case will provide enough intuition about solving the general case. In order to make our algorithm clear, we explicitly write out all the parameters in ASUD (d, c, η), where the algorithm has those extra parameters as input. Here parameter d is the minimum demand in the adversary instance and c is the ratio between the largest and smallest demand. Note that cd ≤ 1. Also, η is an extra parameter representing the total amount of resource can be allocated to the arriving players. AlgorithmASUD is formally defined in Algorithm 2. The general idea of the algorithm is to treat each arriving player's demand as the maximum demand, and the total demand as the sum of the minimum demand. Then the algorithm only allocates the resource to each arriving player such that the approximation ratio is not violated. The performance of the algorithm is analyzed in Lemma 1.

Algorithm 2 1-Recallable Algorithm ASUD (d, c, η)

Input: A sequence of players N = {1, · · · , n} arriving and departing along time.

• 1: Initially, Aij = 0 for all 0 ≤ i ≤ n, 0 ≤ j ≤ i.
• 2: for any arriving player i ≥ 1 do
• 3: Let j ∗ = argmax1≤j≤i-1{Ai-1 j }.
• 4: Set Aii = Aij ∗ = d 2η ln 3·max{d·i,1} .
• 5: Aij = Ai-1 j , ∀j ∈ [i -1] -{j ∗ }.
• 6: Ai0 = A00 - ∑j∈[i] Aij .
• 7: end for

Output: Allocation A = (Aij )0≤i≤n,0≤j≤i.

Lemma 1. For any c, d, η > 0, algorithm ASUD is (2cη ln 3)- fair and at most 1 η fraction of the resource is allocated.

Proof. We first show that algorithm ASUD is well defined by showing that the reallocation in Step 4 is always feasible and the total allocated resource is no more than 1 η . First note that d 2η ln3·max{i·d,1} is non-increasing with respect to i. Next we divide the analysis into three cases.

Case 1: i ≤ ⌊ 1d ⌋. When i ≤ ⌊ 1d ⌋, Aij = d 2η ln 3 for all j ≤ i. Therefore, ∑j∈[i] Aij = id 2η ln3 ≤ 1 2η ln3 < 1 η . In this case, no resource is recalled and the total allocation never exceed 1 η .

Case 2: ⌊ 1d ⌋ < i ≤ 2⌊ 1d ⌋. In this case, the first ⌊ 1d ⌋ players still satisfy Case 1, but when the (⌊ 1d ⌋ + l)-th player arrives, player l's allocation will be recalled, where 1 ≤ l ≤ i - ⌊ 1d ⌋. Then both player l and (⌊ 1d ⌋ + l) will be allocated with 1 2η ln 3·(⌊ 1d ⌋+l) . The total allocated resource is

The above inequality holds by analyzing the monotonicity. Case 3: i > 2⌊ 1d ⌋. When i > 2⌊ 1d ⌋, all the resource allocated to the first ⌊ i2 ⌋ players will be recalled. In Algorithm ASUD , whenever the resource is recalled from a player, the algorithm will create two sets of resource with the same size, and allocate them to both the recalled player and the new arriving player. Thus the total allocated resource in this case is at most twice of the resource allocated to players from ⌊ i2 ⌋ to i, that is,

Finally, we analyze the performance of ASUD . At anytime ti, 1 ≤ i ≤ n, since player i's demand di ≤ c · d, his value for allocation Aii is vi(Aii ) ≥ 1 2cη ln 3·max{i·d,1} . When player i arrives, the total demand ∑l≤i dl ≥ d · i, and the value of player i at time ti is

Similarly, the value of any player j < i satisfies the above inquality. Therefore, algorithm ASUD is (2cη ln3)-fair, and thus finishes the proof of Lemma 1.

Next we design the algorithm AUD for the valuations with arbitrary demands, which is formally defined in Algorithm 3. The idea for this algorithm is to classify the players with demands that differ up to a constant factor into the same group and run the algorithmASUD for the players in each group. By analyzing the performance of algorithm AUD, we have the following theorem.

Algorithm 3 1-Recallable Algorithm AUD

Input: A sequence of players N = {1, · · · , n} arriving and departing along time. Each player i ∈ N has demand di. Let m = ⌈log n⌉.

• 1: Divide the demand space [0, 1] into m + 1 sets (S0, S1, . . . , Sm), where S0 = [0, 2-m], Sl = (2-l , 21-l ], l ∈ [m].
• 2: for player i with demand di do
• 3: Find j such that di ∈ Sj.
• 4: Aii = 21-j 2η ln 3 max{∑l≤i dl ,1} .
• 5: Let i∗ = argmaxi′{Ai-1 i′ |di′ ∈ Sj}.
• 6: Aii∗ = Aii , and Aii′ = Ai-1 i′ , ∀i′ ̸= i, i∗ .
• 7: Ai0 = 1- ∑j∈[i] Aij .
• 8: end for

Output: Allocation (Aij )0≤i≤n,0≤j≤i.

Theorem 4. For any n ≥ 1, 1-recallable algorithm AUD is O(log n)-fair for the UD problem with n players.

Proof. It is clear that AUD classifies all players in m + 1 sets. Let Nj denote the set of players with demand in Sj. Then except the players in N0, the demands of the players in the same set differ up to a constant factor 2.

First we find the parameter η such that algorithm AUD is feasible. For players in N0, since the maximum demand is at most 1n and there are at most n players in total, the resource allocated to those players is bounded by 1 2η ln3 . For player i in Nj , where j ∈ [m], the total demand when player i arrives is at least the total demand of the players in Nj who arrived before player i. Using the similar argument in Lemma 1 and applying the case studies, the total resource allocated to players in Nj is at most 1 η . By setting η = 1 + m = 1 + ⌈log n⌉, algorithm AUD is always feasible. Then, similar to Lemma 1, it is easy to get that algorithmAUD is (4η ln3)-fair, which is O(log n)-fair. Therefore, Theorem 4 holds.

Next we construct an adversary instance for the UD problem to show that the bound of our algorithm is tight. Formally, we have the following theorem.

Theorem 5. For any 1-recallable algorithm A for the UD problem, A is Ω(log n)-fair with n players.

Proof. Let A be any 1-recallable algorithm which is η-fair. Here we consider the following adversary instance. In order to make the instance clear, we describe the arriving players by m = logn

3 rounds (n is a large enough integer such that m is also a large enough integer). Formally, within stage j ≤ m, nj = n 2×4j-1 players arrive one by one and each of them has demand 8j n . That is, in the first round, n2 players arrive one by one and each of them has demand 8n . For each of the following rounds, the number of the arriving players decreases by a multiplicative factor of 4, but the demand of each player increases by a multiplicative factor of 8. Note that in the last round the demand of each player is 8m n = 1. Also, the total number of players in the designed instance is ∑j≤m nj < n. Thus this instance is well defined, and it is sufficient to prove that all 1-recallable algorithm is Ω(log n)- fair for this instance.

In each stage j ≤ m, the total number of players that would arrive in the future is less than

It is easy to see that u = 13 nj. Therefore, at least 23 nj = n 3×4j-1 players who arrive during the jth round won't get recalled by in the future. Then we can lower bound the resource allocated to those players. First note that the total demand be-

fore stage j is ∑j ′<j n 2×4j′-1 × 8j ′ n = ∑j ′<j 8j ′ 2×4j′-1 . The total demand when the ith player in stage j arrives is

Since algorithm A is an 1-recallable algorithm, for any integer x ≤ nj+1 2 , there exists at least nj + 1 - 2x players whose allocated resource is at least 8j nη·Dnj-x . Thus the total resource allocated to the players in stage j is

when we set n → ∞. The computation detail of the above inequality can be found in the full version of this paper [Li et al., 2018]. Thus the total allocated resource is

Therefore, η ≥ 2 3 ln 65 log n and Theorem 5 holds.

Remark If we consider τ-recallable algorithms here, where τ is a constant, by designing the similar adversary instance, except that the number of players and the demand change in the ratio of 1 4τ and 8τ respectively between each stage, we can still obtain the Ω(log n) lower bound.

5 Conclusion and Future Direction

In this paper, we study the dynamic fair division problem with a divisible resource. We design O(logn)-proportional and O(n)-envy-free algorithms for players with general valuations. We also show that those bounds are tight up to a logarithmic factor. However, for the valuations that are uniform with demand, we design an O(log n)-fair algorithm and we prove that this ratio is tight.

There are a lot of future directions that are worthy exploration. An immediate open question is whether we can find algorithms with better approximation ratio for τ -recallable algorithms without the non-wasteful assumption when τ ≥ 2. Another particularly interesting question is to consider the problem via a game theoretic view in the dynamic setting. Moreover, the dynamic version of allocating multiple indivisible resources is also worthy of effort.

Acknowledgments

This work has been partially supported by NSF CAREER Award No. 1553385. The first and the last author thank Jing Chen for introducing them to the area of algorithmic game theory. Finally, the authors would like to acknowledge several wonderful anonymous referees for many helpful comments.