Uniform Welfare Guarantees Under Identical Subadditive Valuations

1 Introduction

A significant body of recent work, in artificial intelligence and computational social choice, has been directed towards the study of fair and efficient allocation of indivisible goods among agents; see, e.g., [Endriss, 2017] and [Brandt et al., 2016]. This thread of research has led to the development of multiple algorithms and platforms (e.g., Spliddit [Goldman and Procaccia, 2015]) which, in particular, address settings wherein discrete resources (that cannot be fractionally allocated) need to be partitioned among multiple agents. Contributing to this line of work, the current paper studies discrete fair division from a welfarist perspective.

We specifically address the problem of finding allocations (of indivisible goods) that (approximately) maximize the generalized means of the agents' valuations. Formally, for exponent parameter p ∈ R, the pth generalized mean, of n nonnegative values {vi}ni=1 , is defined as Mp(v1, . . . , vn) :=

( 1n ∑i vp i ) 1p . Parameterized by p, this family of functions includes well-studied fairness and efficiency objectives, such as average social welfare (p = 1), Nash social welfare (p → 0), and egalitarian welfare (p → -∞). In fact, generalized means-with the exponent parameter p in the range (-∞, 1]-admit a fundamental axiomatic characterization: up to monotonic transformations, generalized means (with p ∈ (-∞, 1]) exactly constitute the family of welfare functions that satisfy the Pigou-Dalton transfer principle and a few other key axioms [Moulin, 2004]. 1 Hence, by way of developing a single approximation algorithm for maximizing generalized means, the current work provides a unified treatment of multiple fairness and efficiency measures.

With generalized mean as our objective, we focus on fairdivision instances in which the agents have a common subadditive (i.e., complement free) valuation. Formally, a set function v, defined over a set of indivisible goods [m], is a said to be subadditive iff, for all subsets A and B of [m], we have v(A ∪ B) ≤ v(A) + v(B). This class of functions includes many other well-studied valuation families, namely XOS, submodular, and additive valuations. 2 These function classes have been used extensively in computer science and mathematical economics to represent agents' valuations. Of particular relevance here are results that (in the context of combinatorial auctions) address the problem of maximizing social welfare under submodular, XOS, and, more generally, subadditive valuations [Nisan et al., 2007].

As mentioned previously, we restrict attention to fairdivision instances wherein all the agents have an identical valuation. This focus on a common valuation function provides a technically interesting and applicable subclass of fairdivision problems-as a stylized application, consider a setting in which the agents' values represent money, i.e., for every agent, the value of each subset (of the goods) is equal to the subset's monetary worth. Here, one encounters subadditivity when considering goods that are substitutes of each other. Also, from a technical standpoint, we note that the problem of maximizing social welfare is APX-hard even under identical submodular [Khot et al., 2008] and subadditive valuations [Dobzinski et al., 2005]. One can extend this hardness result to all p ∈ (-∞, 1].

1.1 Our Results

Addressing fair-division instances with identical subadditive valuations, we develop an efficient constant-factor approximation algorithm for the generalized-mean objective (Theorem 1). Specifically, our algorithm computes an allocation (of the indivisible goods among the agents), A, with the property that its generalized-mean welfare, Mp(A), is at least 1/40

1 Note that generalized means are ordinally equivalent to CES (constant elasticity of substitution) functions.

2 Recall that a submodular function f is defined by a diminishing returns property: f(A + e) - f(A) ≥ f(B + e) - f(B), for all subsets A ⊆ B and e /∈ B.

times the optimal p-mean welfare, for all p ∈ (-∞, 1]. This result in fact implies an interesting existential guarantee as well: if in a fair-division instance the agents' valuations are identical and subadditive, then there exists a single allocation that uniformly approximates the optimal p-mean welfare for all p ∈ (-∞, 1].

The tradeoff between fairness and economic efficiency is an important consideration in fair division literature. 3 The relevance of the above-mentioned existential guarantee is substantiated by the fact that this result reasonably mitigates the fairness-efficiency tradeoff in the current context; it shows that for identical subadditive valuations there exists a single allocation which is near optimal with respect to efficiency objectives (in particular, social welfare) as well as fairness measures (e.g., egalitarian welfare).

Furthermore, we note that even specific instantiations of our algorithmic guarantee provide novel results: while the problem of maximizing Nash social welfare, among n agents, admits an O(n log n)-approximation under nonidentical submodular valuations [Garg et al., 2020], the current work provides a novel (constant-factor) approximation guarantee for maximizing Nash social welfare when the agents share a common subadditive (and, hence, submodular) valuation. 4 Analogously, the instantiation of our result for egalitarian welfare is interesting in and of itself.

Given that the valuations considered in this work express combinatorial preferences, a naive representation of such set functions would require exponential (in the number of goods) values, one for each subset of the goods. Hence, to primarily focus on the underlying computational aspects and not on the representation details, much of prior work assumes that the valuations are provided via oracles that can only answer particular type of queries. The most basic oracle considered in literature answers value queries: given a subset of the indivisible goods, the value oracle returns the value of this subset. In this value oracle model, the work of Vondr´ak (2008) considers submodular valuations and provides an efficient e e-1 - approximation algorithm for maximizing social welfare. Using this method as a subroutine and, hence, completely in the value oracle model, our algorithm achieves the abovementioned approximation guarantee for identical submodular valuations.

Another well-studied oracle addresses demand queries. Specifically, such an oracle, when queried with an assignment of prices p1, . . . , pm ∈ R to the m goods, returns maxS⊆[m] (v(S) - ∑j∈S pj ), for the underlying valuation function v. 5 Demand oracles have been often utilized in prior work for addressing social-welfare maximization in the context of subadditive and XOS valuations [Nisan et al., 2007]. In particular, the work of Fiege (2009) shows that, under subadditive valuations and assuming oracle access to demand queries, 6 the social-welfare maximization problem admits an efficient 2-approximation algorithm. Demand queries are unavoidable in the subadditive case: one can directly extend the result of Dobzinski et al. (2010) to show that, even under identical (subadditive) valuations, any sub-linear (in n) approximation of the optimal social welfare requires exponentially many value queries. At the same time, we note that our algorithm requires demand oracle access only to implement the 2-approximation algorithm of Fiege (2009) as a subroutine. Beyond this, we can work with the value oracle.

3 For example, consider the work on price of fairness [Bertsimas et al., 2011; Bei et al., 2019]

4 We note that, under nonidentical additive valuations, there exists a polynomial-time 1.45-approximation algorithm for maximizing Nash social welfare [Barman et al., 2018a]. Furthermore, under identical additive valuations, maximizing Nash social welfare admits a polynomial-time approximation scheme [Nguyen and Rothe, 2014; Barman et al., 2018b].

5 Observe that a value query can be simulated via polynomially many demand queries. Though, the converse is not true [Nisan et al., 2007].

1.2 RelatedWork

Multiple algorithmic and hardness results have been developed to address welfare maximization in the context of indivisible goods. Though, in contrast to the present paper, prior work in this direction has primarily addressed one welfare function at a time.

As mentioned previously, maximizing social welfare and Nash social welfare (see, e.g., [Cole and Gkatzelis, 2018] and references therein) has been actively studied in algorithmic game theory. Egalitarian welfare has also been addressed in prior work-this welfare maximization problem is also referred to as the max-min allocation problem; see, e.g., [Annamalai et al., 2017; Chakrabarty et al., 2009]. Specifically, under nonidentical submodular valuations, the problem of maximizing egalitarian welfare (among n agents) is known to admit an ˜ O(n1/4m1/2 )-approximation [Goemans et al., 2009]; here m is the number of goods. Note that, in contrast to this sublinear approximation, this paper shows that, if the agents' valuations are identical, then even under subadditive valuations the problem of maximizing egalitarian welfare admits a constant-factor approximation guarantee.

2 Notation and Preliminaries

An instance of a fair-division problem corresponds to a tuple 〈[m], [n], v〉, where [m] = {1, 2, . . . ,m} denotes the set of m ∈ N indivisible goods that have to be allocated (partitioned) among the set of n ∈ N agents, [n] = {1, 2, . . . , n}. Here, v : 2[m] ↦→ R+ represents the (identical) valuation function of the agents; specifically, v(S) ∈ R+ is the value that each agent i ∈ [n] has for a subset of goods S ⊆ [m]. 7

We will assume throughout that the valuation function v is (i) normalized: v(∅) = 0, (ii) monotone: v(A) ≤ v(B) for all A ⊆ B ⊆ [m], and (iii) subadditive: v(A∪B) ≤ v(A)+v(B) for all subsets A, B ⊆ [m].

Write Πn([m]) to denote the collection of all n partitions of the indivisible goods [m]. We use the term allocation to refer to an n-partition A = (A1 , . . .An ) ∈ Πn([m]) of the m goods. Here, Ai denotes the subset of goods allocated to agent i ∈ [n] and will be referred to as a bundle.

6 This result holds even if the agents have distinct, but subadditive, valuations.

7 Recall that this work addresses fair-division instances in which all the agents have a common valuation function.

For an exponent parameter p ∈ R, the pth generalized mean of n nonnegative numbers x1, . . . , xn ∈ R+ is defined as Mp(x1 , . . . , xn ) := ( 1n ∑ni=1 xpi ) 1p .

Note that, when p = 1, Mp reduces to the arithmetic mean. Also, as p tends to zero, Mp, in the limit, is equal to the geometric mean and limp→-∞Mp(x1 , . . . , xn ) = min{x1, x2, . . . , xn}. Hence, following standard convention, we will write M0(x1, . . . , xn) = (∏ni=1 xi)1/n and M-∞(x1, . . . , xn) = mini xi.

Considering generalized means as a parameterized collection of welfare objectives, we define the p-mean welfare, Mp(A), of an allocation A = (A1,A2, . . . ,An) as Mp(A) := Mp (v(A1), . . . , v(An)) = ( 1n ∑ni=1 v(Ai)p )1/p . Here, v is the (common) valuation function of the agents. Indeed, with p equal to one, zero, and -∞, the p-mean welfare, respectively, corresponds to (average) social welfare , Nash social welfare, and egalitarian welfare.

Given a fair-division instance I = 〈[m], [n], v〉 and p ∈ (-∞, 1], ideally, we would like to find an allocation A = (A1, . . . , An) with as large an Mp(A) value as possible, i.e., maximize the p-mean welfare. An allocation that achieves this goal will be referred to as a p-optimal allocation and denoted by A∗ (I, p) = (A∗1 , . . . ,A∗n ). If required, for clarity, we will specifically associate I and p with these bundles, i.e., write {A∗i (I)}i or {A∗i (I, p)}i to denote the bundles in the p-optimal allocation A∗ (I, p) of instance I.

We note that, under identical subadditive valuations and for all p ∈ (-∞, 1], finding a p-optimal allocation is APX-hard; [Dobzinski et al., 2005] establish this hardness result for p = 1. 8 Hence, the current work considers approximation guarantees. In particular, for fair-division instances I in which the agents have a common subadditive valuation, we develop a polynomial-time algorithm that computes a single allocation A with the property that Mp(A) ≥ 1 40 Mp(A∗ (I, p)) for all p ∈ (-∞, 1].

The work of Feige (2009) shows that, for subadditive valuations, the social-welfare maximization problem (equivalently, the problem of maximizing M1(·)) admits an efficient 2-approximation algorithm, assuming oracle access to demand queries. In particular, such an oracle, when queried with an assignment of prices p1, . . . , pm ∈ R to the m goods, returns maxS⊆[m] (v(S) - ∑j∈S pj ). Our algorithm requires demand oracle access only to implement the 2-approximation algorithm of [Feige, 2009] as a subroutine. Beyond this, we can work with the basic value oracle, which when queried with a subset of goods S ⊆ [m], returns v(S). 9

For a fair-division instance I, write F(I) to denote the 1mean welfare M1 (i.e., the average social welfare) of the allocation computed by the algorithm of [Feige, 2009]. The ap-

8 An extension of this APX-hardness result to all p ∈ (-∞, 1] is deferred to a full version of this work.

9 In fact, if the underlying valuation is submodular, then one can invoke the result of [Vondr´ak, 2008] (instead of using the approximation algorithm by [Feige, 2009]) and efficiently obtain a e e-1 - approximation for the social-welfare maximization problem in the value oracle model. Hence, under a submodular valuation, our algorithm can be implemented entirely in the value oracle model.

Algorithm 1 ALG

Input: A fair-division instance I = 〈[m], [n], v〉 with demand oracle access to the subadditive valuation function v. Output: An allocation A = (A1, A2, . . . , An)

• 1: Initialize the set of agents U = [n], the set of goods G = [m], and bundle Ai = ∅ for all i ∈ U
• 2: Index all the goods in non-increasing order of value v(g1) ≥ v(g2) ≥ . . . ≥ v(gm)
• 3: Set I 0 = 〈G,U, v〉 and initialize t = 1 {Recall that F(I) = M1(S), where S denotes the allocation obtained by executing Feige's algorithm [Feige, 2009] on instance I .}
• 4: while v(gt) ≥ 1 3.53 F(I t-1 ) do
• 5: Allocate At ← {gt} and update G ← G \ {gt} along with U ← U \ {t}
• 6: Set I t = 〈G,U, v〉 and update t ← t +1
• 7: end while
• 8: Set (At,At+1, . . . ,An) = ALGLOW(G,U, v) {This step corresponds to the second phase of the algorithm which assigns bundles to the remaining |U| = n - t + 1 agents. Also, note that, in the current instance J := 〈G,U, v〉, for every good g ∈ Gwe have v(g) < 1 3.53 F(J ).}
• 9: return allocation A = (A1,A2, ...,An).

proximation guarantee established in [Feige, 2009] ensures that-for any instance I with a subadditive valuation-we have F(I) ≥ 1 2 M1(A∗ (I, 1)). Here, A∗ (I, 1) denotes a 1optimal allocation in I.

3 Maximizing p-MeanWelfare

Addressing fair-division instances with identical subadditive valuations, this section presents an efficient algorithm for computing a constant-factor approximation to the p-mean welfare objective, uniformly for all p ∈ (-∞, 1].

The algorithm consists of two phases; see Algorithm 1 (ALG) and Algorithm 2 (ALGLOW). In the first phase, "highvalue" goods are assigned as singletons-we use the approximation algorithm of [Feige, 2009] to obtain an estimate of the optimal 1-mean welfare and deem a good to be of high value if its valuation is at least a constant (specifically, 3.53) times this estimate. Intuitively, the estimate provides a useful benchmark, since the optimal 1-mean welfare upper bounds the optimal p-mean welfare for all p ∈ (-∞, 1] (this bound essentially follows from the generalized mean inequality and is stated in Proposition 1).

Therefore, in phase one of the algorithm, we sort the goods in non-decreasing order by value and iteratively select goods, which by themselves provide a value comparable to that of the optimal p-mean welfare. In each iteration, the selected good is assigned as a singleton to an agent and this agentgood pair is removed from consideration. Note that such an update leads to a new fair-division instance with one less good and one less agent, as well as a potentially different optimal 1-mean welfare. The key technical issue here is that the change in the optimal 1-mean welfare (and, hence, its estimate obtained via Feige's algorithm) can be non-monotonic.

Algorithm 2 ALGLOW

Input: A fair-division instance J = 〈G,U, v〉 with demand oracle access to the subadditive valuation function v. Output: An allocation B = (B1, B2, . . . , B|U|)

• 1: Execute Feige's approximation algorithm [Feige, 2009] on the given instance J to compute allocation S = (S1, S2, . . . , S|U|). {Note that allocation S provides a 2-approximation to the optimal 1-mean welfare of J , M1(S) = F(J ) ≥ 12 M1 (A∗ (J , 1))}
• 2: Index the bundles such that v(S1) ≥ . . . ≥ v(S|U|) and initialize i = a = 1 along with Bℓ = ∅ for 1 ≤ ℓ ≤ |U| {Lemma 1 shows that the following loop runs to completion}
• 3: while agent index a < |U| do
• 4: Consider an arbitrary good g ∈ Si
• 5: if v(Ba ∪ {g}) < 13 F(J) then
• 6: Update Ba ← Ba ∪ {g} and Si ← Si \ {g} {Here good g is assigned to bundle Ba to increase its value}
• 7: else
• 8: Update a ← a+ 1 {This update is performed when sufficient value has been accumulated in a bundle}
• 9: end if
• 10: if v(Si) < 13 F(J ) then
• 11: Update i ← i+1 {Once the value of Si drops below 1 3 F(J ) we consider the next bundle in S}
• 12: end if
• 13: end while

ing elements to B|U|}

• 15: return partition B = (B1, . . . ,B|U|).

Nonetheless, we show that the welfare contribution of the goods assigned (as singletons) in the first phase is sufficiently large (Lemma 2).

The first phase terminates when we obtain an instance J wherein each good is of value no more than a constant times its optimal 1-mean welfare. The second phase (ALGLOW) is designed to address such a fair-division instance. In particular, we show that, in the absence of high-value goods, we can efficiently find an allocation B = (Bi)i such that each bundle Bi is of value at least constant times the optimal p-mean welfare of J . To obtain the allocation B, we first compute (via Feige's approximation algorithm) an allocation S = (Sj)j that provides a 2-approximation to the optimal 1-mean welfare of J . Subsequently, we show that the subsets Sjs, that have appropriately high value, can be partitioned to form the desired bundles Bis, which constitute the allocation B.

We note that, while the above-mentioned ideas hold intuitively, the formal guarantees are obtained by analyzing different ranges of the exponent parameter p separately. Also, at a high level, the approximation ratio of 40 is obtained by balancing different factors (e.g., the threshold that identifies high-value goods) and other analytical considerations so as to achieve the best-possible approximation ratio across all values of p ∈ (-∞, 1].

The following theorem is the main result of this work.

Theorem 1 (Main Result). Let I = 〈[m], [n], v〉 be a fairdivision instance wherein all the agents have an identical, subadditive valuation function v. Given demand oracle access to v, ALG computes in polynomial time an allocation A that, for all p ∈ (-∞, 1], provides a 40-approximation to the optimal p-mean welfare, i.e., Mp(A) ≥ 1 40 Mp(A∗ (I, p)), for all p ∈ (-∞, 1]; here, A∗ (I, p) is the p-optimal allocation in I.

We start with the following observation to upper bound the optimal p-mean welfare in terms of the optimal 1-mean welfare. In the interest of space, proofs of the following proposition, Lemma 1, and Lemma 2 are deferred to a full version of this work.

Proposition 1. Let I be a fair-division instance in which all the agents have an identical, subadditive valuation v. Then, for each p ∈ (-∞, 1], the optimal 1-mean welfare is at least as large as the optimal p-mean welfare: M1(A∗ (I, 1)) ≥ Mp(A∗ (I, p)) for all p ∈ (-∞, 1].

Next we address the second phase of the algorithm (ALGLOW) that-by the processing performed in the whileloop of ALG-solely needs to consider fair-division instances J = 〈G, U, v〉 wherein all the goods g ∈ G satisfy v(g) ≤ 1 3.53 F(J ), i.e., the goods are of "low value." Lemma 1 asserts that, for such an instance J , ALGLOW finds an allocation in which the value of every bundle is comparable to the optimal average social welfare of J . In Section 4, we use this fact and Lemma 2 to prove Theorem 1 for p ∈ (-∞, 0.4). Finally, in Section 5, we prove the main result for p ∈ [0.4, 1].

Lemma 1. Let J = 〈G,U, v〉 be a fair-division instance in which all the agents have an identical subadditive valuation function v, and every good g ∈ G satisfies v(g) ≤ 1 3.53 F(J). Then, in the demand oracle model, the algorithm ALGLOW efficiently computes an allocation B = (B1, . . . , B|U|) with the property that v(Bi) ≥ 1 40 M1(A∗ (J , 1)) ≥ 1 40 Mp(A∗ (J , p)), for all 1 ≤ i ≤ |U|.

With an approximation guarantee for ALGLOW in hand, we next analyze the first phase of the algorithm-specifically, analyze the while-loop in ALG. Note that in each iteration of this while-loop (Steps (4) to (7)) a good of value at least constant times the optimal 1-mean welfare (of the current instance) is allocated as a singleton to an agent. Lemma 2 shows that these singleton assignments complement the subsequent use of ALGLOW, in the sense that the two phases together retain welfare guarantees. Lemma 2 holds for p ∈ (-∞, 0.4); for the complementary range [0.4, 1], we develop different techniques in Section 5.

Given a fair-division instance I = 〈[m], [n], v〉 as input, let {g1, . . . , gk} denote the set of goods that get assigned as singletons in the while-loop of ALG (Algorithm 1). Also, let J := I k be the instance that remains after the termination of the while-loop in ALG. Note that J is passed on to ALGLOW as input and it consists of n - k agents. Hence, in J , any p-optimal allocation A∗ (J , p) contains (n - k) bundles. For notational convenience, we will index these bundles from k+ 1 to n, i.e., A∗ (J , p) = (A∗k+1 (J ), . . . , A∗n (J )).

Lemma 2. Given a fair-division instance I = 〈[m], [n], v〉 with an identical subadditive valuation v, let {g1, . . . , gk} denote the set of goods that get assigned as singletons in the while-loop of ALG and let J = 〈[m] \ {g1, . . . , gk}, [n] \ [k], v〉 be the instance that remains after the termination of this loop. In addition, let A∗ (I, p) = (A∗1 (I), . . . ,A∗n (I)) and A∗ (J , p) = (A∗k+1 (J ), . . . , A∗n (J )) denote p-optimal allocations of instances I and J , respectively. Then, with constant α = 40,

Using these lemmas, we now prove Theorem 1 for exponent parameter p ∈ (-∞, 0.4).

4 Proof Sketch of Theorem 1 for

Write J = I k = 〈[m] \ {g1, . . . , gk}, [n] \ [k], v〉 to denote the instance obtained at the termination of the while loop in ALG. Also let A∗ (J , p) = (A∗k+1 (J ), . . . , A∗n (J )) denote the p-mean optimal allocation of the instance J .

Lemma 2 establishes that, for p ∈ (-∞, 0.4), the allocation C := ({g1}, . . . , {gk},A∗k+1 (J), . . . ,A∗n (J)) achieves welfare comparable to the optimal p-mean welfare, i.e., comparable to Mp (A∗ (I, p)).

In contrast to this allocation C considered in Lemma 2, the algorithm ALG returns the allocation A = ({g1}, {g2}, . . . , {gk},Bk+1, . . . ,Bn), where Bjs are the bundles computed by ALGLOW. 10 However, Lemma 1 ensures that, for p ∈ (-∞, 1], the value of each bundle Bj (with k + 1 ≤ j ≤ n) is comparable to the p-optimal welfare in J , i.e., is comparable to Mp (A∗ (J , p)):

At a high level, these bounds imply that replacing the bundles {A∗j }nj=k+1 (in the allocation C) by {Bj}nj=k+1 maintains the welfare guarantee, up to a constant factor loss. Since this replacement gives us the computed allocation A, the desired approximation guarantee follows. Formally proving these approximation bounds requires a case analysis, depending on the sign of p in the range (-∞, 0.4). These technical details are deferred to a full version of the paper.

Also, note that Lemma 2 holds only for p ∈ (-∞, 0.4) and, 11 hence, the above-mentioned arguments apply to this range. To complete the proof of Theorem 1, next we address the complementary range [0.4, 1].

10 Specifically, with instance J as input, ALGLOW computes the allocation B = (Bk+1, . . . ,Bn); here, for notational convenience, we index the bundles in B from k + 1 to n.

11 By contrast, Lemma 1 holds for all p ∈ (-∞, 1].

5 Proof of Theorem 1 for p ∈ [0.4, 1]

Write ̂G = {g1, . . . , gk} to denote the k highest-valued goods assigned as singletons in the while-loop (Step 4) of ALG. Instance J = 〈[m] \ ̂G, [n] \ [k], v〉 is passed as input to ALGLOW, which returns allocation B = (Bk+1, . . . ,Bn). Recall that B satisfies Lemma 1. Finally, let A = ({g1}, . . . , {gk},Bk+1, . . . ,Bn) denote the allocation returned by ALG.

We will prove the following bound for p ∈ [0.4, 1] and, hence, establish the stated approximation guarantee Mp(A) ≥ 1 40 Mp(A∗ (I, p)).

Write A∗ (I, p) \ ̂G to denote the allocation (specifically, an n-partition) obtained by removing the goods ̂G = {g1, . . . , gk} from the bundles in A∗ (I, p), i.e., A∗ (I, p) \ ̂G := (A∗i (I, p) \ ̂G)n i=1 . Subadditivity of v ensures that,

for all i ∈ [n], the bundle A∗i (I, p) satisfies

Since p > 0, exponentiating the previous inequality by p gives us

The last inequality follows from the fact that (x + y)p ≤ xp + yp , for all p ∈ [0.4, 1] and x, y ∈ R+.

Summing equation (1) over i ∈ [n] leads to

To show that the k goods in ̂G (which are allocated as singletons) substantially contribute towards p-mean welfare of the computed allocation A, we will next establish the following lower bound for all 1 ≤ t ≤ k: v(gt)p ≥ 1 (7.06)p ( 1n ∑nj=1 v(A∗j (I, p) \ ̂G)p).

Recall that I t denotes the fair-division instance 〈[m] \ {g1, . . . , gt}, [n] \ {1, . . . t}, v〉, for 1 ≤ t ≤ k. Write A∗ (I t , p) = (A∗t+1 (I t , p), . . . ,A∗n (I t , p)) to denote a poptimal allocation of instance I t ; here, we associate the exponent parameter p with each bundle, for notational clarity, and index these bundles from t + 1 to n.

The selection criterion of the while-loop in ALG and the fact that Feige's algorithm achieves an approximation ratio of 2 ensure

Index the n bundles in allocation A∗ (I, p) \ ̂G in nonincreasing order of value v(A∗1 (I, p) \ ̂G) ≥ v(A∗2 (I, p) \

̂G) ≥ . . . ≥ v(A∗n (I, p) \ ̂G) and note that the arithmetic mean of the values of the first n - t + 1 bundles is at least as large as the overall arithmetic mean

Given that allocation A∗ (I, p) \ ̂G constitutes an n-partition of the set of goods [m] \ ̂G and allocation A∗ (I t-1 , 1) = (A∗t (I t-1 , 1), . . . , A∗n (I t-1 , 1)) is an (n-t+1)-partition of [m] \ {g1, . . . , gt-1} ⊇ [m] \ ̂G, we have the following containment n-t+1 ⋃ j=1 (A∗j (I, p) \ ̂G) ⊆ n⋃ j=t ( A∗j (I t-1 , 1)). Fur-

thermore, by definition, allocation A∗ (I t-1 , 1) achieves the maximum possible average social welfare among all (n-t+ 1) partitions of [m] \ {g1, . . . , gt}. Therefore, we have

Equations (3) and (5) lead to

(via the generalized mean inequality)

Exponentiating both sides of the previous inequality by p ∈ [0.4, 1] gives us the desired lower bound

Equation (6) enables us to bound the p-welfare contribution of the goods ̂G = {g1, . . . , gk} assigned as singletons

Recall that ALGLOW-with input instance J = I k-returns allocation B = (Bk+1, . . .Bn). Using arguments similar to the ones mentioned above and Lemma 1, we lower bound the values of these bundles Bk+1, . . . , Bn.

Exponentiating by p ∈ [0.4, 1] and summing over all j ∈ {k + 1, . . . n}, we have

Combining inequalities (7) and (8) gives us

Note that 2 × (7.06)p ≤ (40)p for all p ∈ [0.4, 1], hence, the previous inequality simplifies to

Taking the pth root on both sides of the last inequality gives us the desired result for the computed allocation A = ({g1}, . . . , {gk}, Bk+1, . . . , Bn)

Mp(A) ≥ 1 40 Mp(A∗ (I, p)). This completes the proof of Theorem 1.

6 Conclusion and FutureWork

This work studies the problem of allocating indivisible goods among agents that share a common subadditive valuation. We show that, for such settings, one can always (and in polynomial-time) find a single allocation that simultaneously approximates a range of generalized-mean welfares, to within a constant factor of the optimal.

An interesting direction of future work is to address settings in which we have a fixed number of distinct valuation functions across all the agents. A nontrivial improvement on the developed approximation guarantee will also be interesting.

Acknowledgements

Siddharth Barman gratefully acknowledges the support of a Ramanujan Fellowship (SERB - SB/S2/RJN-128/2015) and a Pratiksha Trust Young Investigator Award.