# dynamic_fair_division_problem_with_general_valuations__2aacd106.pdf Dynamic Fair Division Problem with General Valuations Bo Li1, Wenyang Li2, Yingkai Li3 1 Stony Brook University 2 Melbourne University 3 Northwestern University boli2@cs.stonybrook.edu, wenl6@student.unimelb.edu.au, yingkai.li@u.northwestern.edu 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 Ω( n log 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. 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 1 n 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 allo- Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18) cation 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 log n), 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(log n)-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 Rough- garde, 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 propor- Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18) tional if and only if each player gets at least 1 n 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 σnvi([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(AP i ) vi([0,1]) n. 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 = P 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(AP i ). 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 td i , with td i > 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 td 1 = td 2 = = td n > 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 = (Ai 0, Ai 1, , Ai i) and the total output from time 0 to time tn is denoted by A = (Ai)i {0,1, ,n} where A0 = {A0 0} and A0 0 = [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 = Ai j for all j [i]\S, and Ai+1 j Ai j for all j S. In the following we extend the definition for fairness to the dynamic setting. An allocation A is σ-proportional if i, j i, vj(Ai j) 1 σ ivj([0, 1]); and an allocation A is ξ-envy-free if i, j, j i, vj(Ai j) 1 ξ vj(Ai j ). For the uniform with demand valuations in the dynamic setting, an allocation A is η-fair if i, j i, vj(Ai j) 1 η max{P l i dl, 1}. 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 ln 2)-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 A1 DF D, defined in Algorithm 1, which is O(log n)-proportional for the DFD problem with general valuations. Roughly speaking, when player i arrives, algorithm A1 DF D 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 algorithm A1 DF D is formally analyzed in Theorem 1. Algorithm 1 1-Recallable Algorithm A1 DF D Input: A sequence of players N = {1, , n} arriving and departing along time. 1: Initially, Ai j = for all 1 i n and 0 j i. 2: When the first player arrives, setting A1 1 = [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 9: (j , S ) = arg max j 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 Ai j in A = (Ai j)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 AS UD(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. Algorithm AS UD 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 AS UD(d, c, η) Input: A sequence of players N = {1, , n} arriving and departing along time. 1: Initially, Ai j = 0 for all 0 i n, 0 j i. 2: for any arriving player i 1 do 3: Let j = arg max1 j i 1{Ai 1 j }. 4: Set Ai i = Ai j = d 2η ln 3 max{d i,1}. 5: Ai j = Ai 1 j , j [i 1] {j }. 6: Ai 0 = A0 0 P j [i] Ai j. 7: end for Output: Allocation A = (Ai j)0 i n,0 j i. Lemma 1. For any c, d, η > 0, algorithm AS UD is (2cη ln 3)- fair and at most 1 η fraction of the resource is allocated. Proof. We first show that algorithm AS UD 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η ln 3 max{i d,1} is non-increasing with respect to i. Next we divide the analysis into three cases. Case 1: i 1 d . When i 1 d , Ai j = d 2η ln 3 for all j i. Therefore, P j [i] Ai j = id 2η ln 3 1 2η ln 3 < 1 η. In this case, no resource is recalled and the total allocation never exceed 1 η. Case 2: 1 d . In this case, the first 1 d players still satisfy Case 1, but when the ( 1 d + l)-th player arrives, player l s allocation will be recalled, where 1 l i 1 d . Then both player l and ( 1 d + l) will be allocated with 1 2η ln 3 ( 1 d +l). The total allocated resource is d i) d 2η ln 3 + 2 1 2η ln 3 ( 1 The above inequality holds by analyzing the monotonicity. Case 3: i > 2 1 d . When i > 2 1 d , all the resource allocated to the first i 2 players will be recalled. In Algorithm AS UD, 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 i 2 to i, that is, 1 2η ln 3 l 1 η ln 3 ln i i Finally, we analyze the performance of AS UD. At anytime ti, 1 i n, since player i s demand di c d, his value for allocation Ai i is vi(Ai i) 1 2cη ln 3 max{i d,1}. When player i arrives, the total demand P l i dl d i, and the value of player i at time ti is vi(Ai i) 1 2cη ln 3 max{P l i dl, 1}. Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18) Similarly, the value of any player j < i satisfies the above inquality. Therefore, algorithm AS UD is (2cη ln 3)-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 algorithm AS UD 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: Ai i = 21 j 2η ln 3 max{P 5: Let i = arg maxi {Ai 1 i |di Sj}. 6: Ai i = Ai i, and Ai i = Ai 1 i , i = i, i . 7: Ai 0 = 1 P j [i] Ai j. 8: end for Output: Allocation (Ai j)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 1 n and there are at most n players in total, the resource allocated to those players is bounded by 1 2η ln 3. 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 algorithm AUD is (4η ln 3)-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 play- ers by m = log n 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, n 2 players arrive one by one and each of them has demand 8 n. 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 P 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 u = ( n 2 4j ) (1 1 4) = n 6 4j 1 . It is easy to see that u = 1 3nj. Therefore, at least 2 3nj = 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 before stage j is P j