Budget-feasible Maximum Nash Social Welfare is Almost Envy-free

1 Introduction

Fairness and efficiency are two of the primary considerations in public economics. Yet, these two objectives are often unaligned and even conflict with each other. The Nash social welfare (NSW) - proposed by Nash as a solution for bargaining problems [Nash Jr, 1950; Kaneko and Nakamura, 1979] - is a well-known social welfare function that balances individual utilities and the overall efficiency. In more details, the NSW of a solution x is defined as the product of the agents' values vi(x) provided by this solution. As noted in [Brˆanzei et al., 2017], it can be viewed as a special case of a family of functions known as generalized (power) means:

When p = 1, Mp(x) defines the utilitarian social welfare, i.e., the average of all agents' values; and when p → -∞, Mp(x) defines the egalitarian social welfare, i.e., the minimum value received by an agent. The NSW corresponds to exactly the limit of Mp(x) when p → 0, i.e., (∏i∈N vi(x))1/n . Thus, it serves a middle ground between the two other cases. A MaxNSW allocation, i.e., an allocation that maximizes the NSW, naturally leads to balanced values among the agents while it also nudges the overall efficiency towards the maximum.

In the context of fair allocation of indivisible goods, it has been shown by Caragiannis et al. [Caragiannis et al., 2016; Caragiannis et al., 2019b] that a Max-NSW allocation is envy-free up to one good (EF1); namely, it ensures that every agent does not envy the bundle of any other agent by more than one item.

1.1 Our Results

In this paper, we study the fairness of the NSW in a budgetfeasible allocation problem. In this problem, every item j has a cost of cj that will be incurred to the agent that it is allocated to, and every agent i has a budget Bi > 0 that can be used to pay for the additive cost of the bundle S of items she receives, i.e., c(S) = ∑j∈S cj ≤ Bi. An allocation (X1, · · · ,Xn) is a collection of disjoint subsets of items, whereby Xi is the bundle of items allocated to agent i, yielding value vi(Xi) for this agent. In our model, we assume that unused budget cannot be converted to an agent's value. This is true in many real-world applications, e.g., when the cost is the processing time of a job while the value is the payment for finishing the job. With this assumption our model also subsumes the model proposed by Biswas and Barman [Biswas and Barman, 2018], where all items have size 1. An allocation is budget-feasible if c(Xi) ≤ Bi for all i, i.e., every agent can afford the cost incurred by this allocation. Accordingly, a Max-NSW feasible allocation is the optimal solution to the following problem.

Note that since allocations are subject to budget constraints, it is not always possible to allocate all items. The unallocated items are assumed to be allocated to a charity who has unlimited budget. Indeed, it is not hard to see that aMax-NSWallocation is Pareto-optimal (PO), i.e., we cannot hope to further improve some agent's utility without hurting the other agents. Here we do not consider the charity as an agent. This immediately implies that no agent has any incentive to exchange her bundle with any subset of unallocated items that fits within her budget. An interesting question is whether some agent would wish to exchange her bundle with other agents.

To answer this question, we adapt the classic EF (envyfree) notion to the budget-feasible setting. In our EF notion, an agent i envies another agent j if there is a subset of items allocated to agent j that costs at most Bi and gives agent i a strictly higher value. The EF1 notion can be defined similarly: agent i envies agent j for more than one item if there is a subset of Xj that costs at most Bi and gives i a strictly higher value even after removing agent i's most valuable item from this subset. An allocation is said to be EF (resp., EF1) if no agent envies any other agent (resp., for more than one item). We show that, unlike the setting without budget constraints, a Max-NSW allocation is no longer always EF1. However, it remains a good approximation of EF1. Our main contributions are summarized by the following two results, where we call an allocation α-EF1 is it achieves an α approximation of EF1, for α ∈ [0, 1].

We also show that the approximation ratio we proved cannot be improved. Specifically, we construct an instance for which a Max-NSW allocation is exactly 1/4-EF1. We observe that this instance requires some items to have very high costs compared with the agents' budgets, i.e., the budget-cost ratio is κ = mini,j Bi cj = 1. This motivates our study of the large budget case where κ is large. Interestingly, we find that the approximation guarantee improves gracefully with κ and eventually converges to 1/2 when κ goes to infinity.

Note that instances with large budget are also a typical setting of the bin packing problem that has received considerable interest in the literature [Feldman et al., 2010; Devanur et al., 2011; Molinaro and Ravi, 2012; Kesselheim et al., 2014]. We remark that when κ goes to infinity our model does not degenerate to the one without budget constraints, because the number of items can increase to infinity as well. This is why the approximation ratio does not converge to 1 as in the setting without budget constraints.

Technical Novelty. We remark that deriving the above results requires techniques very different from those employed in previous work. The approach of Caragiannis et al. [Caragiannis et al., 2016; Caragiannis et al., 2019b] for proving the EF1-ness of Max-NSW allocations is by contradiction: if a Max-NSW allocation were not EF1, then by reallocating some items, the NSWcould be improved. In our setting, such reallocations need to conform to the budget constraints. We may need to discard some items when reallocating items to an agent. Thus, applying the same argument requires a larger difference between the agents' values. Indeed, this is why the Max-NSW allocation is only approximately EF1 in our setting, instead of being exactly EF1. Our analysis for the second main result is more challenging. We observe that if the items are divisible, then any Max-NSW allocation must be 1/2-EF1. To convert the analysis to the indivisible case, we show that in the divisible analysis at most a constant number of items are fractionally allocated. Then it suffices to give a rounding scheme for a small number of fractional items. A main challenge arises when we have to deal with fractional items with large values. We resolve this issue by using a finetuned classification of items into heavy and light ones and applying different analyses depending on the class the majority of the items belong to.

1.2 RelatedWork

The pioneering work of Caragiannis et al. [Caragiannis et al., 2016; Caragiannis et al., 2019b] triggered a series of followup interests in the fairness of the NSW. It is shown in [Biswas and Barman, 2018] that with matriod constraints a Max-NSW allocation is always EF1 if the agents have identical valuations. More recently, Amanatidis et al. [Amanatidis et al., 2020] proved that a Max-NSW allocation guarantees envyfreeness up to any item (EFX) if there are at most two possible values for the goods. The fairness of NSW has also been studied in the setting when the goods are public [Conitzer et al., 2017; Fain et al., 2018]. Furthermore, the algorithm in [Barman et al., 2018] showed that there is an allocation that is simultaneously 1/1.45-approximate Max-NSW, Pareto optimal, and (1-ϵ)-approximate EF1. Similarly, the algorithm in [McGlaughlin and Garg, 2020] computes an allocation that is 1/2-approximate Max-NSW, proportional up to one item, 1/(2n)-approximate maximin share fair, and Pareto optimal and can be found in polynomial time. No previous work has considered the setting with budget constraints to the best of our knowledge.

Our work is conceptually related to a line of work on fair division that involves a charity in the models. In our budgetfeasible setting, unallocated items are assumed to be donated to a charity. The concept of charity has also been used to simplify analysis of EFX allocations as was in [Caragiannis et al., 2016; Caragiannis et al., 2019b]. Caragiannis et al. [Caragiannis et al., 2019a] also showed that there is an EFX allocation on a subset of items that is a 1/2-approximation of Max-NSW over the original set of items. Similarly, Chaudhury et al. [Chaudhury et al., 2020] proved that by donating no more than n - 1 items, there is an EFX allocation for the remaining items and no agent envies the charity.

The complexity of computing a Max-NSW allocation has been studied for various types of valuation functions [Ramezani and Endriss, 2009; Darmann and Schauer, 2015]. The problem is APX-hard for additive valuation functions [Nguyen et al., 2014; Lee, 2017]. There has been some effort towards designing efficient algorithms to compute approximate Max-NSW allocations [Nguyen and Rothe, 2014; Cole and Gkatzelis, 2015; Cole et al., 2017]. The state-ofthe-art approximation ratio of NSW for additive valuations is 1.45 by [Barman et al., 2018].

2 Preliminaries

In our model, a set M of m goods will be allocated to a set N of n agents. Every item j ∈ M has a cost cj ≥ 0 and every agent i ∈ N has a budget Bi ≥ 0. Each agent i has an additive valuation function vi : 2M → R+ ∪ {0} on the subsets of items. Equivalently, we can express the valuation function vi as a vector vi = (vi1, · · · , vim), where vij ∈ R+ ∪ {0} denotes agent i's value for item j. Upon receiving a subset S ⊆ M of items, an agent i obtains an additive value vi(S) = ∑j∈S vij; in addition, the allocation incurs an additive cost c(S) = ∑j∈S cj to agent i, which needs to be paid using her budget. We assume that the values for the items and the cost of the allocation are not mutually convertible. For example, the cost may represent the size of the items and the budget represents the capacity of her knapsack, which cannot be converted from the items' values.

An allocation X = (X0,X1, · · · ,Xn) is a partition of the item set M into n + 1 bundles, where Xi ⊆ M is the bundle of items allocated to agent i for each i ∈ N and X0 is the set of unallocated items (recall that due to the budget constraints, we cannot guarantee ⋃ni=1 Xi = M). The unallocated items can be thought of as a donation to a special agent 0, i.e., a charity, who has an unbounded budget and value 0 for every item (in the sense that she does not envy any other agents no matter what they get). An allocation X is budget-feasible if

In the remainder of this paper, we require every allocation to be feasible. When we write "an allocation" we mean "a feasible allocation" unless otherwise stated. For convenience, for a set X and an element j, we will write X ∪ {j} as X + j and X \ {j} as X - j throughout the paper.

Definition 2.1 (Max-NSW). An allocation X∗ is a MaxNSW allocation if it maximizes the Nash social welfare, i.e., ∏i∈N vi(X∗ i ) ≥ ∏i∈N vi(Xi) for any allocation X. For the case when the maximum NSW is zero, the Max-NSW allocation is the one that (1) maximizes the number of agents |S| that have non-zero values; (2) maximizes the NSW of the induced problem instance on the subset of agents S.

In the budget-feasible setting, an agent cannot hope to take a bundle that costs more than her budget. We adapt the EF notion accordingly and define it as follows.

Definition 2.2 (EF). For any α ∈ [0, 1], an allocation X is αapproximate envy-free (α-EF) if for any two agents i, j ∈ N and any S ⊆ Xj with c(S) ≤ Bi, it holds that vi(Xi) ≥ α · vi(S). When α = 1, X is also said to be EF.

This definition is consistent with the standard EF notion when every agent's budget is c(M). Since the items are indivisible, (approximate) EF is hard to achieve. One of the most widely studied relaxed notion is envy-free up to one item.

Definition 2.3 (EF1). For any α ∈ [0, 1], an allocation X is α-approximate envy-free up to one item (α-EF1) if for any two agents i, j ∈ N and any S ⊆ Xj with c(S) ≤ Bi, there exists j ∈ S such that vi(Xi) ≥ α · vi(S - j). When α = 1, X is also said to be EF1.

Trivially, an allocation X = (M, ∅, . . . , ∅) (i.e., allocating all items to the charity) is already EF and EF1. Apparently, such an allocation is not efficient for the agents by any reasonable measurement of efficiency. Therefore, we consider Pareto optimality as a criterion for efficiency.

Definition 2.4 (PO). An allocation X is Pareto optimal (PO) if there exists no allocation X′ such that vi(X′ i ) ≥ vi(Xi) for all i ∈ N and vj(X′j ) > vj(Xj) for some j ∈ N.

Note that in a PO allocation X no agent i can improve her value by exchanging items with the charity (subject to her budget constraint), i.e., for any S ⊆ Xi∪X0 such that c(S) ≤ Bi, it holds that vi(Xi) ≥ vi(S).

3 Max-NSWAllocation is 1 4 -EF1 and PO

In this section, we present our first main result, which is stated in the theorem below.

Theorem 3.1. AMax-NSW allocation X∗ is 14 -EF1 and PO.

Before presenting the proof, we remark that the 1/4 ap-

proximation ratio is tight, even when agents have identical valuation and budget. We present an instance for which a Max-NSW allocation is not c-EF1, for any constant c > 1/4. Example 3.2. Let ϵ > 0 be arbitrarily close to 0. Consider the instance with two agents who have the identical valuation v and budget B = 1. Let there be 1+ 1ϵ items, where v1 = 1+ ϵ, c1 = 1, vj = 4ϵ, and cj = ϵ for all j ∈ {2, 3, . . . , 1 + 1ϵ }. It can be verified that the allocation X∗ with X∗ 1 = {1} and X∗ 2 = {2, . . . , 1 + 1ϵ } maximizes the NSW with v(X∗ 1 ) · v(X∗ 2 ) = 4(1+ϵ). However, X∗ is not c-EF1, for any c > 14 , because v(X∗ 1 ) = 1+ϵ 4(1-ϵ) · v(X∗ 2 - j) for all j ∈ X∗ 2 .

Next we proceed to the proof of Theorem 3.1.

Proof of Theorem 3.1: We first show that we can assume without loss of generality that the maximum NSW is nonzero. If the maximum NSW is zero, let S be the agents with non-zero values in the Max-NSW allocation X∗ . It is not difficult to verify that (i) any agent not in S does not envy the charity (as otherwise we can increase the size of S); (ii) any agent not in S does not envy any other agent by more than one item (again, otherwise we can increase the size of S); (iii) any agent i ∈ S does not envy any agent j /∈ S, because if agent i has non-zero valuation on Xj then the Max-NSW on S can be improved. Hence it remains to argue the (approximate) EF1-ness and PO among agents in S ∪ {0}, which reduces to the case when Max-NSW is not zero 1 .

It is trivial to see that X∗ is PO because if there is another allocation that increases one agent's value without decreasing any other agent's value, it must also increase the NSW, which contradicts themaximumof NSWunderX∗ . Inwhat follows, we prove that X∗ is 14 -EF1 by contradiction. Suppose that a Max-NSW allocation X∗ is not 14 -EF1, we show that there exists another allocation X′ with a strictly larger NSW, which is a contradiction with X∗ being a Max-NSW allocation.

By assumption, there exist two agents, say 1 and 2, such that agent 1 finds a set T ⊆ X2 such that c(T) ≤ B1 and

For ease of description, we rename the items in T as {1, 2, · · · , t} such that v2j ≤ v2,j+1 for any 1 ≤ j < t. Let T1 = {j ∈ T-t : j is odd} and T2 = {j ∈ T-t : j is even}. Note that we have one of the following two inequalities:

1 Similar arguments appeared in Caragiannis et al. [Caragiannis et al., 2016; Caragiannis et al., 2019b].

In other words, under the valuation of agent 2, if we assign item t to the bundle with smaller value, then the resulting bundle has value at least that of the other bundle.

Now we can construct a new allocation X′ , where

• X′ i =Xi for all i ≥ 3,
• X′1 = Tl, where l ∈ argmaxℓ∈{1,2} v1(Tℓ),
• X′2 =X2 \ Tl, and
• X′0 =X0 ∪X1.

In other words, we first remove all the items originally allocated to agent 1. Then we pick the bundle agent 1 prefers in {T1, T2}, and move items in this bundle from X2 to X1. Note that under the valuation of agent 2, the items agent 2 loses have total value at most 12 · v2(T). In addition, X′ is a feasible allocation as c(Tl) ≤ c(T) ≤ B1 and c(X2 \ Tl) ≤ c(X2) ≤ B2. By Equation (1), we then have

Since vi(X′ i ) = vi(Xi) for all i ≥ 3, it follows that

which contradicts the fact that X∗ is Max-NSW.

Remark. While we assume that the valuation functions are additive, our result holds with sub-additive valuation functions as well (see the full version of the paper [Wu et al., 2020]).

4 Improved Ratios with Large Budgets

We have shown that in general, the 1/4 approximation ratio can not be improved. However, one observation is that in the tight instance we presented (Example 3.2), the budgets are such that B1 = B2 = 1 = maxj∈M cj. In other words, an agent's budget may be exhausted by allocating only one item to her. Interestingly, we find that when this is not the case, the approximation ratio can be improved.

4.1 Warm-up Analysis

As a warm up, we show that if it takes at least two item to exhaust the budget of any agent, then the approximation ratio can be slightly improved to 3 11 ≈ 0.273.

Lemma 4.1. Suppose that Bi ≥ 2 · cj for all agent i ∈ N and item j ∈M. Then aMax-NSWallocationX∗ is 3 11 -EF1.

Proof. Suppose for the sake of contradiction that a MaxNSW allocation X∗ is not 3 11 -EF1. Without loss of generality, let agents 1 and 2 be the two agents that block X∗ from being 3 11 -EF1. In other words, there exists T ⊆ X2 with c(T) ≤ B1 such that for any j ∈ T , we have

We use a similar approach to the proof of Theorem 3.1 and partition T into three subsets T1, T2, and {t} such that

Case 1: If there exists l ∈ {1, 2} such that v1(Tl) > 2 · v1(X1), we construct a new allocation X′ with X′ i = Xi for all i ≥ 3, X′1 = Tl, X′2 = X2 \ Tl, and X′0 = X0 ∪ X1. By this construction, we have that v1(X′1 ) > 2 · v1(X1) and v2(X′2 ) ≤ 1 2 · v2(X2); thus,

which contradicts the fact that X∗ is a Max-NSW allocation. Case 2: max{v1(T1), v1(T2)} ≤ 2 · v1(X1). Since

we have min{v1(T1), v1(T2)} > 5 3 ·v1(X1). Pick an arbitrary l ∈ arg minℓ∈{1,2} c(Tℓ). Since c(T1)+c(T2) ≤ B1, we have c(Tl) ≤ 1 2 · B1.

We construct a new allocation in which we allocate all the items in Tl to agent 1, along with a sufficiently valuable portion of items in X1. To ensure that the budget constraint is not violated, we need the following result.

Claim 4.1. There exists ˆX1 ⊆ X1 such that c( ˆX1) ≤ 1 2 · B1 and v1( ˆX1) ≥ 13 · v1(X1).

Proof. If c(X1) ≤ 1 2 · B1, we can let ˆX1 = X1. Note that under this case, v1( ˆX1) = v1(X1). Now suppose c(X1) > 12 · B1. We create a set T and let it be an empty set initially. Then we add into T items in X1 one at a time until c(T) > 12 · B1. Let j be the last item added into T . We have

Consider the partition of X1 into three sets: T - j, {j} and X1\T . Note that all three sets have cost at most 1 2 ·B1. Let ˆX1 be the set with maximum value (under v1) among T - j, {j} and X1 \ T . Obviously, we have v1( ˆX1) ≥ 1 3 · v1(X1).

By the above claim, we can now construct a new allocation X′ with X′ i = Xi for all i ≥ 3, X′1 = Tl ∪ ˆX1, X′2 = X2 \Tl, and X′0 = X0 ∪ (X1 \ ˆX1). This allocation is feasible since

By construction, we have that

As we can see from the analysis, the improvement in the approximation ratio comes mainly from the fact that when reallocating items in Tl fromX2 to X1, we are able to keep a constant fraction of the items in X1 (as in Claim 4.1).

It is natural to expect that if we are able to obtain an even finer dissection of X1, we should be able to improve the approximation ratio even further. Indeed, this is the case. We show that when all items are very small compared with the budgets, the approximation ratio approaches 1/2. While the idea is clear, as we will show in the following section, to accomplish the analysis is a highly non-trivial task.

4.2 Large Budget Case

Let κ = mini∈N,j∈M⌊ Bi cj ⌋. Without loss of generality, assume κ is an integer; otherwise we round κ down to the nearest integer. In words, it takes at least κ items to exhaust the budget of any agent.

Observe that when κ → ∞ the approximation ratio (with respect to EF1) approaches 1/2. Before we present the proof of Theorem 4.2, we first show that the approximation ratio is tight. In particular, we give an example with arbitrarily large κ, for which a Max-NSW allocation is ( 12 + O( 1κ ))-EF1.

Suppose that x ≤ κ items in M2 are allocated to agent 2 in a Max-NSW allocation, then it is optimal to allocate the remaining κ - x items in M2 together with x items in M1 to agent 1. The NSW is thus given by v1(X1) · v2(X2) = (2κ - x) · 2x, which is maximized when x = κ. That is, X1 = M1 and X2 = M2. Since for any j ∈ X2,

the Max-NSW allocation is κ 2κ-1 -EF1, and the approximation ratio approaches 12 when κ →∞.

4.3 Proof of Theorem 4.2

Next we prove Theorem 4.2. For ease of notation we let k = κ1/4 . Note that it suffices to consider the case when k > 20, as otherwise the theorem follows from Theorem 3.1.

Definition 4.4 (Density). We define the density of item j ∈ M under the valuation of agent i ∈ N as ρij = vij cj .

Lemma 4.5. Given two sets of items X and Y , both having cost at most B, and a valuation function v, there exists a subset of items Z ⊆ X ∪ Y with c(Z) ≤ B and

Proof. We prove by constructing the subset Z satisfying the claimed properties. In particular, we compute a subset X′ ⊆ X with c(X′ ) ≤ B - c(Y ), and

Then the lemma follows immediately by setting Z = X′ ∪Y .

To ease the analysis, we assume without loss of generality that c(X) = B. If c(X) < B then imagine that we include into X many items with 0 value and arbitrarily small cost until c(X) = B, which does not increase the value of X.

We construct X′ by repeatedly removing an item in X with the smallest density (under valuation function v), until c(X′ ) ≤ B - c(Y ). Since each item has cost at most B k4 by definition of k, the total cost of items removed in this procedure is at most c(Y ) + B k4 .

Since the items removed are among those with the smallest density, their average density is at most the overall density of items in X; the total value of items removed is at most

As before, we prove by contradiction, and assume the allocation is not ( 12 - 5k )-EF1, say, between agents 1 and 2. We show that this assumption leads to contradictions.

Let T ⊆ X2 with c(T ) ≤ B1 such that

where j ∗ = argmaxj∈T v2j is the item in T with the maximum value under the valuation of agent 2.

Let ˆ T = T - j ∗ . For each item j ∈ ˆ T, we refer to v2j/v2( ˆ T) as the contribution of item j to set ˆ T under valuation of agent 2. The total contribution of items in ˆ T is 1. Depending on the contributions of items, we partition ˆ T into a set Th of heavy items and a set Tl of light items:

We first show that under the valuation of agent 1, the contribution of heavy items must be small.

Proof. Suppose that there exists j ∈ Th such that v1j v1( ˆ T) ≥ 12 · v2j v2( ˆ T) . We show that there exists an allocation (by reallocating item j) that achieves a strictly larger NSW, which is a contradiction. Let c = v2( ˆ T ) v2j . By definition of heavy item, we have c ≤ k3 . Consider the allocation obtained by moving item j from ˆ Th to X1. Since v2j ≤ v2j ∗ , we have

Note that including j into X1 may result in a violation of the budget constraint of agent 1. To resolve this issue, we use Lemma 4.5 with B = B1, v = v1, X = X1 and Y = {j}, and let X′1 = Z (as specified in Lemma 4.5). Since item j has cost cj ≤ B1 k4 , we have

Recall that by assumption of the proof we have

By inequality (2), we have

where the last inequality holds since c ≤ k3 .

Hence, we have v1(X′1 ) · v2(X′2 ) > v1(X1) · v2(X2) and ∏i∈N vi(X′ i ) > ∏i∈N vi(Xi), which is a contradiction.

Let f = v2(Tl) v2( ˆ T) be the total contribution of light items to ˆ T . By the above claim we have

In other words, under the valuation of agent 1, the light items have a larger total contribution to ˆ T. Next, we show the following lemma (the proof of the lemma is included in the full version [Wu et al., 2020]). Roughly speaking, we can partition the light items into k sets with about the same cost and value.

Lemma 4.6. We can partition Tl into k sets such that each set Y satisfies

We partition Tl into k sets as specified in Lemma 4.6, then pick the one most valuable to agent 1 out of the k sets, and reassign it to agent 1. Let Y be the set chosen. Note that

After losing set Y , the remaining value of agent 2 is

where the inequality holds by Lemma 4.6.

After acquiring set Y , agent 1 has the set of items X′1 = X1 ∪ Y , which might have a larger cost than B1. Similarly, we use Lemma 4.5, with B = B1, v = v1 and X = X1. Let X′1 = Z be the set specified in Lemma 4.6.

As a result, the bundle agent 1 receives has value

where in the last inequality we use f ≥ 0 and k ≥ 20.

Combining inequalities (4) and (3), we have

It follows that ∏i∈N vi(X′ i ) > ∏i∈N vi(Xi), which is a contradiction.

5 Discussion and Future Directions

We showed that in the presence of budget constraints a MaxNSW allocation may not be EF1 but achieves a constant approximation of EF1. The tight approximation ratio is 1/4 and in the case of large budgets, the ratio improves with the budget-cost ratio and converges to 1/2 when this ratio goes to infinity. There are several directions for future work.

First, our results imply that in a budget-feasible setting, a 1/4-EF1 allocation always exists and is compatible with Pareto optimality, but it is not known whether an exact EF1 allocation always exists or not and this appears to be a nontrivial problem. However, we do know that every PO allocation is at most 1/2-EF1: the hard instance can be obtained by modifying Example 3.2 and making the value of the first item to be 2. Second, the computation of maximum NSW in our setting is an interesting question which we did not study in this paper. Indeed, an APX-hardness for the complexity of this problem can be readily established since the setting without budget can be seen as a special case of our setting (where every agent has budget c(M)). Thus, an natural task is to design efficient approximation algorithms. Theorem 3.1 can be extended to show that an α-approximation of the MaxNSW is also α4 -EF1. Hence an approximation algorithm for Max-NSW would also compute an approximate EF1 allocation. However, in the large budget case, an α-approximation of the Max-NSW is not necessarily α · ( 12 - 5 κ1/4 )-EF1 (we include a hard instance in our full version [Wu et al., 2020]). Finally, while we focus on EF in this paper, it would also be interesting to consider other fairness notions such as proportionality and maximin share fairness and study whether a Max-NSW allocation provides any fairness guarantee under these notions.

Acknowledgments

Xiaowei Wu is funded by the Science and Technology Development Fund, Macau SAR (File no. SKL-IOTSC-20212023) and the Start-up Research Grant of University of Macau (File no. SRG2020-00020-IOTSC). Bo Li is supported by The Hong Kong Polytechnic University (Grant no. P0034420). Jiarui Gan was supported by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement no. 945719). The authors thank Edith Elkind, Georgios Birmpas, Warut Suksompong, and Alexandros Voudouris for helpful discussions at the early stage of this work.