# finding_fair_allocations_under_budget_constraints__c8dfc21d.pdf

Finding Fair Allocations under Budget Constraints

Siddharth Barman1, Arindam Khan1, Sudarshan Shyam*1,2, K. V. N. Sreenivas1

1Department of Computer Science and Automation, Indian Institute of Science, Bangalore 2Department of Computer Science, Aarhus University barman@iisc.ac.in, arindamkhan@iisc.ac.in, sudarshans.iitkgp@gmail.com, venkatanaga@iisc.ac.in

We study the fair allocation of indivisible goods among agents with identical, additive valuations but individual budget constraints. Here, the indivisible goods each with a specific size and value need to be allocated such that the bundle assigned to each agent is of total size at most the agent s budget. Since envy-free allocations do not necessarily exist in the indivisible goods context, compelling relaxations in particular, the notion of envy-freeness up to k goods (EFk) have received significant attention in recent years. In an EFk allocation, each agent prefers its own bundle over that of any other agent, up to the removal of k goods, and the agents have similarly bounded envy against the charity (which corresponds to the set of all unallocated goods). It has been shown in prior work that an allocation that satisfies the budget constraints and maximizes the Nash social welfare is 1/4approximately EF1. However, the computation (or even existence) of exact EFk allocations remained an intriguing open problem. We make notable progress towards this by proposing a simple, greedy, polynomial-time algorithm that computes EF2 allocations under budget constraints. Our algorithmic result implies the universal existence of EF2 allocations in this fair division context. The analysis of the algorithm exploits intricate structural properties of envy-freeness. Interestingly, the same algorithm also provides EF1 guarantees for important special cases. Specifically, we settle the existence of EF1 allocations for instances in which: (i) the value of each good is proportional to its size, (ii) all goods have the same size, or (iii) all the goods have the same value. Our EF2 result extends to the setting wherein the goods sizes are agent specific.

1 Introduction

Discrete fair division is an actively growing field of research at the interface of computer science, mathematical economics, and multi-agent systems (Brandt et al. 2016; Aziz et al. 2022; Amanatidis et al. 2022). This study is motivated, in large part, by resource-allocation settings in which the underlying resources have to be assigned integrally and cannot be fractionally divided among the agents. Notable examples of such settings include fair allocation of courses

Copyright 2023, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. *Part of this work was conducted while the third author was at the Indian Institute of Science, Bangalore.

(Budish 2011; Othman, Sandholm, and Budish 2010), public housing units (Deng, Sing, and Ren 2013), and inheritance (Goldman and Procaccia 2015). A distinguishing feature of discrete fair division is its development of fairness notions that are applicable in the context of indivisible goods. A focus on relaxations is necessitated by the fact that existential guarantees, under classic fairness notions, are scarce in the context of indivisible goods. The fundamental fairness criterion of envyfreeness which requires that each agent values the bundle assigned to her over that of any other agent cannot be guaranteed in the indivisible-goods setting; consider the simple example of a single indivisible good and multiple agents. Interestingly, such pathology can be addressed by considering a natural relaxation: prior works have shown that, among agents with monotone valuations, there necessarily exists an allocation in which envy towards any agent can be resolved by the removal of a good (Lipton et al. 2004; Budish 2011). More generally, recent research in discrete fair division has addressed existential and algorithmic questions related to the notion of envy-freeness up to k goods (EFk); see, e.g., the survey (Suksompong 2021) and references therein. In an EFk allocation, each agent prefers its own bundle over that of any other agent, up to the removal of k goods from the other agent s bundle. A mature understanding has been developed in recent years specifically for allocations that are envy-free up to one good (EF1), e.g., it is known that, under additive valuations, Pareto efficiency can be achieved in conjunction with EF1 (Caragiannis et al. 2019; Barman, Krishnamurthy, and Vaish 2018). However, most works on EF1, and further relaxations, assume that all possible assignments of the indivisible goods (among the agents) are feasible. On the other hand, combinatorial constraints are an unavoidable requirement in many resource-allocation settings. As an illustrative example to highlight the significance of constraints in discrete fair division settings, consider a curator tasked with fairly partitioning artwork among different museums (i.e., among different agents).1 Each artifact (indivisible good) has an associated value and a space requirement (depending on its size). Note that the artifacts assigned to a particular museum must fit

1This stylized example is adapted from (Gourv es, Monnot, and Tlilane 2014)

The Thirty-Seventh AAAI Conference on Artificial Intelligence (AAAI-23)

within its premises and, hence, in this setting, not all allocations are feasible. Indeed, here the curator needs to identify a partition of the artifacts that is not only fair but also feasible with respect to the museums space constraints. The current work addresses an abstraction of this problem. We study the fair allocation of m indivisible goods among n agents with identical, additive valuations but individual budget constraints. Here, each good g [m] has a size s(g) Q+ and value v(g) Q+, and the goods need to be partitioned such that the bundle assigned to each agent a [n] is of total size at most the agent s budget Ba Q+. Note that in this constraint setting, one might not be able to assign all the m goods among the n agents. Specifically, consider a case wherein the total size s([m]) > Pn a=1 Ba. To account for goods that might remain unallocated, we utilize the construct of charity. This idea has been used in prior works; see, e.g., (Wu, Li, and Gan 2021; Chaudhury et al. 2021). The subset of goods that are not assigned to any of the n agents are, by default, given to the charity. In this framework, we consider envy-freeness up to k goods (EFk) while respecting the budget constraints. Recall that in the current model, the agents have identical, additive valuations, i.e., for any agent a [n], the value of any subset of goods S [m] is the sum of values of the goods in it, v(S) := P g S v(g). Also, we say that for an agent a [n] with assigned bundle Aa [m] EFk holds against a subset F iff the value of the assigned bundle, v(Aa), is at least as much as the value of F, up to the removal of k goods from F. An allocation (A1, A2, . . . An) in which agent a [n] receives subset Aa is deemed to be EFk iff for every agent a [n], the two following conditions hold (i) For every other agent b [n] and every subset F Ab of size at most Ba, the EFk guarantee holds for agent a against F. (ii) For every subset F of goods assigned to the charity, i.e., for every F [m] \ n i=1Ai, such that s(F) Ba, EFk holds for agent a against F. That is, while evaluating envy from agent a towards agent b (resp., the charity), we consider, within Ab (resp., [m] \ n i=1Ai), all subsets of size at most Ba, the budget of agent a. The fair-division model with budget constraints was proposed by Wu et al. (2021). Addressing agents with distinct, additive valuations, Wu et al. (2021) show that an allocation that satisfies the budget constraints and maximizes the Nash social welfare is 1/4-approximately EF1. A manuscript by Gan et al. (2021) improves this guarantee to 1/2-approximately EF1 for agents with identical, additive valuations. In addition, Gan et al. (2021) show that if all the agents have the same budget and in the case of two agents, an EF1 allocation can be computed efficiently. However, for a general number of agents with distinct budgets, the computation (or even existence) of exact EFk allocations remained an intriguing open problem.

1.1 Our Results and Techniques We make notable progress towards this open question by proposing a simple, greedy, polynomial-time algorithm that computes EF2 allocations under budget constraints (Theorem 1). Our algorithmic result implies the universal existence of EF2 allocations in this fair division context. The

same algorithm also provides EF1 guarantees for important special cases. Specifically, we settle the existence of EF1 allocations for instances in which: (i) the value of each good is proportional to its size, (ii) all goods have the same size, or (iii) all the goods have the same value; see Theorems 8, 9, and 10. That is, we prove that if the densities, values, or sizes of the goods are homogeneous, then an EF1 allocation is guaranteed to exist. Furthermore, our EF2 result extends to the setting wherein the goods sizes are agent-specific. This extension appears in the the full version of the current work (Barman et al. 2022). Our algorithm (Algorithm 1) allocates goods in decreasing order of density2 while maintaining the budget constraints. It is relevant to note that while the design of the algorithm is simple, its analysis rests on intricate structural properties of envy-freeness under budget constraints. We obtain the EF2 and EF1 guarantees using ideas that are notably different from the ones used in the unconstrained settings; in particular, they are different from the analysis of the envycycle-elimination method (Lipton et al. 2004) or the roundrobin algorithm (Aziz et al. 2022). Complementing the robustness of the algorithm, we also provide an example that shows that the greedy algorithm might not find an EF1 allocation, i.e., the EF2 guarantee is tight (Section 3.6).

The Knapsack Problem. The budget constraints, as considered in this work, are the defining feature of the classic knapsack problem. The knapsack problem and its numerous variants have been extensively studied in combinatorial optimization, approximation and online algorithms (Martello and Toth 1990; Kellerer, Pferschy, and Pisinger 2004; Albers, Khan, and Ladewig 2021). The knapsack problem finds many applications in practice (Skiena 1999). Recall that the objective in the knapsack problem is to find a subset with the maximum possible value, subject to a single budget constraint. That is, the goal in the standard knapsack problem is utilitarian and not concerned with fairness. Algorithmic aspects of the special cases considered in the current paper have been addressed in prior works: (i) knapsack instances in which the value of each good is proportional to its size are known as proportional instances (Cygan, Je z, and Sgall 2016) or subset-sum instances (Pisinger 2005), (ii) instances where all the goods have the same value are referred to as cardinality (G alvez et al. 2021; G alvez et al. 2021; Khan et al. 2021) or unit (Cygan, Je z, and Sgall 2016) instances. In addition, we also study the special case wherein all the goods have the same size. Proportional and cardinality versions of the knapsack problem are known to be technically challenging by themselves. In particular, in the context of online algorithms, it is known that there does not exist a deterministic algorithm with a bounded competitive ratio for these two versions (Lueker 1998; Marchetti-Spaccamela and Vercellis 1995). The knapsack problem has also been studied from the perspective of group fairness (Patel, Khan, and Louis 2021)

2The density of a good g is defined to be its value-by-size ratio, v(g)/s(g).

and fairness in aggregating voters preferences (Fluschnik et al. 2019). In these works, there is only one knapsack, and the single, selected subset of goods induces (possibly distinct) valuations among the agents. By contrast, the current work addresses multiple knapsacks, one for each agent.

Generalized Assignment Problem (GAP). We also consider instances in which the goods sizes are agent specific. While such instances constitute a generalization of the formulation considered in the rest of the paper, they themselves form a special case of the instances of a well-studied problem called GAP (Shmoys and Tardos 1993). In GAP, both the sizes and values of goods are agent specific. It is known that value maximization in GAP is APX-hard. In fact, even with common values and agent-specific sizes, the value-maximization objective does not admit a polynomial-time approximation scheme (Chekuri and Khanna 2005).

1.2 Additional Related Work

As mentioned previously, EFk allocations have been studied in various discrete fair division contexts (Suksompong 2021). In particular, Bil o et al. (2022) consider settings in which the indivisible goods correspond to vertices of a given graph G, and each agent must receive a connected subgraph of G. It is shown in (Bil o et al. 2022) that if the graph G is a path, then, under the connectivity constraint, an EF2 allocation is guaranteed to exist. Under connectivity constraints imposed by general graphs G, Bei et al. (2022) characterize the smallest k for which an EFk allocation necessarily exists among two agents (i.e., this result addresses the n = 2 case). We also note that exact EFk guarantees are incomparable with multiplicative approximations, as obtained in (Wu, Li, and Gan 2021). The current work focuses on settings in which the agents have an identical (additive) valuation over the goods. We note that, in the context of budget constraints, identical valuations already provide a technically-rich model. Fair division with identical valuations has been studied in multiple prior works; see, e.g., (Plaut and Roughgarden 2020; Barman and Sundaram 2021).

2 Notation and Preliminaries

We study the problem of fairly allocating a set of indivisible goods [m] = {1, 2, . . . , m} among a set of agents [n] = {1, 2, . . . , n} with budget constraints. In the setup, every good g [m] has a size s(g) Q+ and a value v(g) Q+. The density of any good g [m] will be denoted as ρ(g) := v(g)/s(g). Furthermore, every agent a [n] has an associated budget Ba Q+ that specifies an upper bound on the cumulative size of the set of goods that agent a can receive. We conform to the framework wherein the valuations and sizes of the goods are additive; in particular, for any subset of goods S [m], we write the value v(S) := P g S v(g) and the size s(S) := P g S s(g). Hence, in this setup, a subset S [m] can be assigned to agent a [n] only if s(S) Ba, and the subset has value v(S) for the agent. An instance of the fair divi-

sion problem with budget constraints is specified as a tuple [m], [n], {v(g)}g [m], {s(g)}g [m], {Ba}a [n] . Note that in fair division settings with constraints, one might not be able to assign all the m goods among the n agents. Specifically, consider a setting wherein s([m]) > Pn a=1 Ba. To account for goods that might remain unallocated, we utilize the construct of charity. The goods that are not assigned to any of the n agents are, by default, given to the charity agent. An allocation A = (A1, A2, . . . , An) refers to a tuple of disjoint sets of goods, i.e., for every a [n], Aa G and for all a, b [n] such that a = b, Aa Ab = . Here Aa indicates the set of goods allocated to agent a. Throughout, we will maintain allocations A = (A1, A2, . . . , An) that are feasible, i.e., satisfy the budget constraints of all the agents, s(Aa) Ba for every agent a [n]. As mentioned above, the set of remaining goods, [m] \ (A1 A2 An), will be assigned to the charity. Next, we define the fairness notions studied in this work. Consider an allocation A = (A1, A2, . . . , An). An agent a [n] is said to be envy-free up to one good (EF1) towards agent b [n] iff for every subset F Ab, with s(F) Ba (and |F| 1), there exists a good f F such that v(Aa) v(F \ {f}). Further, an agent a [n] is said to be EF1 towards the charity iff for every subset F [m] \ n a=1Aa, with s(F) Ba (and |F| 1), there exists a good f F such that v(Aa) v(F \ {f}). The allocation A is said to be EF1 iff every agent a [n] is EF1 towards every other agent b [n] and the charity. Analogously, we define EF2:

Definition 1 (EF2). Let A = (A1, A2, . . . , An) be an arbitrary allocation. An agent a [n] is said to be envy-free up to two goods (EF2) towards agent b [n] iff for every subset F Ab, with s(F) Ba (and |F| 2), there exist goods f1, f2 F such that v(Aa) v(F \ {f1, f2}). Further, an agent a [n] is said to be EF2 towards the charity iff for every subset F [m] \ n a=1Aa, with s(F) Ba (and |F| 2), there exist goods f1, f2 F such that v(Aa) v(F \ {f1, f2}). The allocation A is said to be EF2 iff every agent a [n] is EF2 towards every other agent b [n] and the charity.

Throughout, we will assume that the goods have distinct densities this assumption holds without loss of generality and can be enforced by perturbing the densities (and appropriately the values) by sufficiently small amounts. The assumption ensures that, in any nonempty subset S [m], the good with the maximum density arg maxg S ρ(g) is uniquely defined. Also, indexing the goods, in any subset S = {g1, g2, . . . , gk}, in decreasing order of density results in a unique ordering with ρ(g1) > ρ(g2) > . . . > ρ(gk). For any subset S [m] and good g [m], we will use the shorthands S + g := S {g} and S g := S \ {g}.

3 The Density Greedy Algorithm This section develops a greedy algorithm (Algorithm 1 - Densest Greedy) that allocates goods in decreasing order of density, while maintaining the budget constraints. We will prove that the algorithm achieves EF2 for general budgetconstrained instances and EF1 for multiple special cases.

Theorem 1. For any given fair division instance with budget constraints [m], [n], {v(g)}g [m], {s(g)}g [m], {Ba}a [n] , Algorithm 1 (Densest Greedy) computes an EF2 allocation in polynomial time.

Algorithm 1: Densest Greedy Given instance [m], [n], {v(g)}g, {s(g)}g, {Ba}a , allocate the goods [m] among agents [n] (the unassigned goods go to charity).

1: Initialize allocation (A1, . . . , An) ( , . . . , ). Also, define the set of active agents N := [n] and the set of unallocated goods G := [m]. 2: while G = and N = do 3: Select arbitrarily a minimum-valued agent a N, i.e., a = arg min b N v(Ab).

4: if for all goods g G we have s(Aa + g) > Ba then 5: Set agent a to be inactive, i.e., N N \ {a}. 6: else 7: Write g = arg max g G: s(Aa+g) Ba ρ(g) and update

Aa Aa + g along with G G g . 8: end if 9: end while 10: return (A1, A2, . . . , An)

Recall the assumption that the goods have distinct densities and, hence, in Line 7 we obtain a unique good g (among the ones that fit within agent a s available budget). While our goal is to find a fair, integral allocation of the (indivisible) goods, for analytic purposes, we will consider fractional assignment of goods to agents. Towards this, for any scalar α [0, 1] and good g [m], we define α g to be a new good whose size and value are α times the size and value of good g, respectively. With fractional goods, we obtain set difference between subsets I and J by adjusting the fractional amount of each good present in I. Formally, for subsets I = {g1, g2, . . . , gk} and J, let αi denote the fraction of the good gi present in J,3 then I \J := k i=1{(1 αi) gi}. We next define key constructs for the analysis. For any subset of goods S, we define two density-wise prefix subsets of S; in particular, S(i) is the subset of the i densest goods in S and S[B] consists of the densest goods in S of total size B. Formally, for any subset of goods S = {s1, s2, . . . , sk}, indexed in decreasing order of density, and any index 1 i |S|, write S(i) := {s1, . . . , si}. Furthermore,

Definition 2 (Prefix Subset S[B]). For any subset of goods S = {g1, g2, . . . , gk}, indexed in decreasing order of density, and for any nonnegative threshold B < s(S), let P = {g1, . . . , gℓ 1} be the (cardinality-wise) largest prefix of S such that s(P) B. Then, we define S[B] := P {α gℓ}, where α = B s(P )

If the threshold B s(S), then we simply set S[B] = S.

3Note that, if αi = 0, then the good gi is not included in J. Complementarily, if αi = 1, then the good gi is completely included in J. Also, gi itself could be a fractional good.

Note that in S[B] at most one good is fractional and, for B s(S), the size of S[B] is exactly equal to B. It is also relevant to observe that, if Aa is the subset of goods assigned to agent a [n] at the end of Algorithm 1, then A(i) a is in fact the set of the first i goods assigned to agent a in the algorithm; recall that the algorithm assigns the goods in decreasing order of density. The following two propositions provide useful properties of Algorithm 1 and are based on the algorithm s selection criteria. All the missing proofs, including the ones of these two propositions, appear in the full version of the paper (Barman et al. 2022).

Proposition 1. Let X = {g1, g2, . . . , gk} denote the set of goods assigned to an agent a [n] i.e.,X = Aa and Y = {h1, h2, . . . , hℓ} be the set of goods assigned to one of the agents b [n], or to the charity, i.e., Y = Ab or Y = [m]\ n i=1 Ai , at the end of Algorithm 1. Further, let the goods in the sets X, Y be indexed in decreasing order of density. For indices i < |X| and j < |Y |, suppose v X(i) < v Y (j) and s X(i) + hj+1 Ba. Then, ρ(gi+1) > ρ(hj+1).

Proposition 2. Let X = {g1, g2, . . . , gk} denote the set of goods assigned to an agent a [n] and Y = {h1, h2, . . . , hℓ} be the set of goods assigned to one of the agents b [n], or to the charity, at the end of Algorithm 1. Further, let the goods in the sets X, Y be indexed in decreasing order of density. If, for any index j < |X|, the size s(X + hj+1) Ba, then we have v(X) v Y (j) .

We define the function EFCount( ) to capture envy count, i.e., the number of goods that need to be removed in order to achieve envy-freeness. Specifically, for any subset of goods X, Y , we define EFCount(X, Y ) as the minimum number of goods whose removal from Y yields a subset of goods with value at most v(X),

EFCount(X, Y ) := min R Y : v(Y \R) v(X) |R| (1)

3.1 Structural Properties of Envy Counts

This section develops important building blocks for the algorithm s analysis.

Lemma 2. For any subset of goods X and Y along with any index i < |Y |, let T := s Y (i) and b T := s Y (i+1) . Then,

EFCount X[ b T], Y [ b T] EFCount X[T ], Y [T ] + 1.

Proof. Write c := EFCount X[T ], Y [T ] . Therefore, by definition, there exists a size-c subset R Y [T ] with the property that v(X[T ]) v(Y [T ] \ R). Define subset R := R {hi+1}, where hi+1 is the good in the set Y (i+1) \ Y (i). For this set R of cardinality c + 1, we have

v X[ b T ] v X[T ] v Y [T ] \ R = v Y [ b T ] \ R .

This implies EFCount X[ b T], Y [ b T] c+1, and the lemma stands proved.

The following lemma shows that if EFCount from a subset X to a subset Y is more than two, then we can select prefix subsets of X and Y such that the count becomes exactly equal to two.

Lemma 3. Let X and Y be any subsets of goods with the property that EFCount(X, Y ) 2. Then, there exists an index t |Y | such that, with T := s Y (t) , we have EFCount X[T ], Y [T ] = 2.

Proof. The lemma essentially follows from a discrete version of the intermediate value theorem. For indices t {0, 1, 2, . . . , |Y |}, define the function h(t) := s Y (t) , i.e., h(t) denotes the size of the t densest goods in Y . Extending this function, we consider the envy count at different size thresholds; in particular, write H(t) := EFCount X[h(t)], Y [h(t)] for each t {0, 1, 2, . . . , |Y |}. Note that H(0) = 0. We will next show that (i) H(|Y |) 2 and (ii) the discrete derivative of H is at most one, i.e., H(t + 1) H(t) 1 for all 0 t < |Y |. These properties of the integer-valued function H imply that there necessarily exists an index t such that H(t ) = 2. This index t satisfies the lemma. Therefore, we complete the proof by establishing properties (i) and (ii) for the function H( ). For (i), note that the definition of the prefix subset gives us v(X) v X[s(Y )] . Hence, EFCount X[s(Y )], Y EFCount(X, Y ) 2; the last inequality follows from the lemma assumption. Since h(|Y |) = s(Y ), we have H(|Y |) 2. Property (ii) follows directly from Lemma 2. This completes the proof.

The next lemma will be critical in our analysis. At a high level, it asserts that if we have two subsets X and Z with EFCount(X , Z ) = 2 and one adds more value into X than Z , then the envy count does not increase.

Lemma 4. Given two subsets of goods X and Z along with two nonnegative size thresholds T, b T R+ with the properties that

EFCount X[T ], Z[ b T] = 2 and

v X \ X[T ] v Z \ Z[ b T] .

Then, EFCount(X, Z) EFCount X[T ], Z[ b T] = 2.

Proof. Given that EFCount X[T ], Z[ b T] = 2, there exist

two goods g 1, g 2 Z[ b T] such that v Z[ b T] g 1 g 2

v X[T ] . Now, using the definition of the prefix subsets (Definition 2) we get

v(X) = v X[T ] + v X \ X[T ]

v Z[ b T] g 1 g 2 + v X \ X[T ]

v Z[ b T] g 1 g 2 + v Z \ Z[ b T]

(via lemma assumption)

= v(Z) (v(g 1) + v(g 2)) (2)

The definition of the prefix subset Z[ b T] ensures that, corresponding to goods g 1, g 2 Z[ b T], there exist two goods g1, g2 Z such that v(g1) + v(g2) v(g 1) + v(g 2). This bound and inequality (2) give us v(X) v(Z g1 g2). This implies EFCount(X, Z) 2 and completes the proof of the lemma.

Remark 1. Lemma 4 continues to hold when EFCount X[T ], Z[ b T] = c, for a general integer c 1.

3.2 Proof of Theorem 1: Densest Greedy Achieves EF2 This subsection establishes Theorem 1. The runtime analysis of the algorithm is direct. Therefore, we focus on proving that Densest Greedy necessarily finds an EF2 allocation. Towards this, let X = {x1, x2, . . . , xk} be the subset of goods allocated to a fixed agent a [n], and let Y = {y1, y2, . . . , yℓ} be the subset of goods allocated to an agent b [n] or to the charity at the end of Densest Greedy. The goods in both X and Y are indexed in decreasing order of density. Proving EF2 between the sets of goods X and Y corresponds to showing that, for any subset of goods Z Y , with s(Z) Ba, we have EFCount(X, Z) 2. Consider any such subset Z and index its goods in decreasing order of density, Z = {z1, z2, . . . , zℓ }. Note that, if EFCount(X, Z) 1, we already have the EF2 guarantee. Therefore, in the remainder of the proof we address the case wherein EFCount(X, Z) 2. We will in fact show that this inequality cannot be strict, i.e., it must hold that the envy count is at most 2 and, hence, we will obtain the EF2 guarantee. Our proof relies on carefully identifying certain prefix subsets, showing that they satisfy relevant properties, and finally invoking Lemma 4. We start by considering function h(i) which denotes the size of the i densest goods in set Z, i.e., h(i) := s(Z(i)) for i {0, 1, 2, . . . , |Z|}. Furthermore, define index

t := min n i : EFCount X[h(i)], Z(i) = 2 o (3)

Figure 1: Figure illustrating size thresholds τ, bτ, and the good g Z.

Existence of such an index t 2 follows from Lemma 3. Also, note that Z(i) = Z[h(i)]. We will denote the tth good

in Z by g Z, i.e., g Z = zt. In addition, using t we define the following two size thresholds (see Figure 1)

τ := s Z(t 1) and bτ := s Z(t) (4)

That is, τ = h(t 1) and bτ = h(t). Now, Lemma 2 and the definition of t (equation (3)) give us EFCount X[τ], Z[τ] 1. Furthermore, using the minimality of t we get EFCount X[τ], Z[τ] < 2. Hence,

EFCount X[τ], Z[τ] = 1 (5)

We will establish two properties for the sets X and Z under consideration and use them to invoke Lemma 4. Specifically, in Lemma 5 we will show that EFCount X[τ], Z[bτ] = 2 and in Lemma 7 we prove v X \ X[τ] v Z \ Z[bτ] . These are exactly the two properties required to apply Lemma 4 with T = τ and b T = bτ. Lemma 5. EFCount X[τ], Z[bτ] = 2.

Proof. Since EFCount X[τ], Z[τ] = 1 (see equation (5)), there exists a good g1 Z[τ] such that v X[τ] v Z[τ] g1 . Also, by definition, we have Z[bτ] = Z[τ] {g Z}. Hence, the previous inequality reduces to v X[τ] v Z[bτ] g Z g1 . That is, removing g1 and g Z from Z[bτ]

gives us a set with value at most that of X[τ]. Therefore, we have EFCount X[τ], Z[bτ] = 2. The lemma stands proved.

We define γ as the size of the goods in X that are at least as dense as g Z, i.e.,

g X:ρ(g) ρ(g Z) s(g) (6)

We will establish bounds considering γ and use them to prove Lemma 7 below.

Claim 6. It holds that γ bτ and v X[γ] < v Z[τ] .

Proof. We will first establish the stated upper bound on γ. Assume, towards a contradiction, that γ > bτ. By definition of γ, we have that all the goods in X[γ] have density at least ρ(g Z). Now, given that γ > bτ, we get that the density of each good in X[bτ] is at least ρ(g Z). In particular, all the goods in the set X[bτ] \ X[τ] are at least as dense as g Z. Hence, v X[bτ] \ X[τ] v Z[bτ] \ Z[τ] = v(g Z). This inequality and equation (5) give us EFCount(X[bτ], Z[bτ]) 1; see Lemma 4. This bound, however, contradicts the definition of t (and, correspondingly, bτ) as specified in equation (3). This gives us the desired upper bound, γ bτ. Next, we prove the second inequality from the claim. For a contradiction, assume that v X[γ] v Z[τ] . Since γ bτ, we further get v X[bτ] v Z[τ] = v Z[bτ] g Z . That is, EFCount X[bτ], Z[bτ] 1. This envy count contradicts the definition of t (and, correspondingly, bτ); see equation (3). Therefore, by way of contradiction, we obtain the second part of the claim.

We will now prove Lemma 7.

Lemma 7. v X \ X[τ] v Z \ Z[bτ] .

Proof. Since Z Y , the good g Z appears in the subset Y . Recall that the goods in the subsets Z and Y = {y1, y2, . . . , yℓ} are indexed in order of decreasing density. Write t [|Y |] to denote the index of g Z in Y (i.e., g Z = yt ). Claim 6 gives us v X[γ] < v Z[τ] = Pt 1 i=1 v(zi) Pt 1 i=1 v(yi). That is, v X[γ] < v Y (t 1) . Also, by def-

inition of γ (equation 6), we have that the goods in X \ X[γ] (if any) have density less than ρ(g Z). These observations and Proposition 1 imply that including g Z in X[γ] must violate agent a s budget Ba, i.e., it must be the case that

γ + s(g Z) > Ba (7)

Using inequality (7), we will prove that v X[γ] \ X[τ] v Z \ Z[bτ] . This bound directly implies the lemma, since X[γ] X. In particular, the size of the concerned set satisfies

s X[γ] \ X[τ] = γ τ

= γ bτ + s(g Z) (bτ s(g Z) = τ) > Ba bτ (via inequality (7))

s Z \ Z[bτ] (8)

The last inequality follows from the facts that s(Z) Ba and s(Z[bτ]) = bτ. Furthermore, by definition of γ, we have that every good g X[γ] \ X[τ] has density ρ(g) ρ(g Z). In addition, for every good g Z \ Z[bτ], the density ρ(g ) ρ(g Z). These bounds on the densities and the sizes of the subsets X[γ] \ X[τ] and Z \ Z[bτ]

give us v X[γ] \ X[τ] v Z \ Z[bτ] . As mentioned previously, this inequality and the containment X[γ] X imply v X \ X[τ] v Z \ Z[bτ] . The lemma stands proved.

Overall, Lemma 5 gives us EFCount X[τ], Z[bτ] = 2. In addition, via Lemma 7, we have v X \ X[τ] v Z \ Z[bτ] . Therefore, applying Lemma 4, we conclude that EFCount(X, Z) 2. This establishes the desired EF2 guarantee for the allocation computed by Algorithm 1 and completes the proof of Theorem 1.

3.3 Fair Division in Proportional Instances This section shows that, if all the goods have the same density, then an EF1 allocation can be computed in polynomial time. While in the rest of the paper we assume that the goods have distinct densities, here we in fact address goods with exactly the same densities. We address this technical difference, by simply including any consistent tie breaking rule in Algorithm 1. That is, for proportional instances, the Densest Greedy algorithm applies a tie breaking rule (e.g., lowest index first) while selecting among the unallocated goods in Line 7. With this minor modification, all the previously established results (specifically, Lemma 7) continue

to hold for proportional instances. The following theorem asserts the EF1 guarantee for proportional instances.

Theorem 8. For any given budget-constrained fair division instance [m], [n], {v(g)}g, {s(g)}g, {Ba}a in which all the goods have the same density (i.e., v(g)/s(g) = v(g )/s(g ) for all goods g, g [m]), Algorithm 1 (Densest Greedy) computes an EF1 allocation in polynomial time.

Proof. We use the constructs defined in Sections 3.1 and 3.2. In particular, let X be the set of goods allocated to an agent a [n] and let Y be the set of goods allocated to an agent b [n], or to the charity at the end of Algorithm 1. Consider any subset Z Y , with size s(Z) Ba (and |Z| 2). By way of contradiction, we will show that EFCount(X, Z) 1 and, hence, obtain the stated EF1 guarantee. Assume, towards a contradiction, that EFCount(X, Z) 2. In such a case, the constructs (specifically, t, τ, bτ, and the good g Z) considered in Sections 3.1 and 3.2 are welldefined. Using the previously-established properties of these constructs, we will show that there necessarily exists a good g Z such that v(X) v(Z g). Hence, by contradiction, we will get that EFCount(X, Z) < 2, i.e., EF1 holds between X and Z. We first note that the size of the set X is at least τ. This follows from inequality (8), which gives us s X[γ] \ X[τ] > 0 and, hence, we have s(X) τ s X[γ] τ > 0. This lower bound on the size of X implies that the prefix subset X[τ] has size exactly equal to τ. In addition, s(Z[τ]) = τ. Now, given that all the goods have the same density, we obtain v(X[τ]) = v(Z[τ]). Therefore,

v(X) = v X[τ] + v X\X[τ]

= v Z[τ] + v X\X[τ]

v Z[τ] + v Z\Z[bτ] (via Lemma 7)

= v Z[τ] + v Z\Z[τ] v(g Z)

(since Z[bτ] \ Z[τ] = {g Z}) v(Z g Z)

Hence, we obtain that EFCount(X, Z) 1, which is a contradiction. This establishes the theorem.

3.4 Fair Division of Equal-Sized Goods This section establishes that the Densest Greedy algorithm finds EF1 allocations for instances in which all the goods have equal sizes.4

Theorem 9. For any given budget-constrained fair division instance [m], [n], {v(g)}g, {s(g)}g, {Ba}a in which all the goods have the same size (i.e., s(g) = s(g ) for all goods g, g [m]), Algorithm 1 (Densest Greedy) computes an EF1 allocation in polynomial time.

4As in the general case, the values of the goods can be distinct. Here, we also retain the assumption that all the goods have distinct densities.

3.5 Fair Division in Cardinality Instances Here, we establish the existence of EF1 allocations in instances wherein each good has the same value.5 Note that, in such a setup, the densest good is the one with the smallest size. We establish the following theorem for cardinality instances. Theorem 10. For any given budget-constrained fair division instance [m], [n], {v(g)}g, {s(g)}g, {Ba}a in which all the goods have the same value (i.e., v(g) = v(g ) for all goods g, g [m]), Algorithm 1 (Densest Greedy) computes an EF1 allocation in polynomial time.

3.6 Tightness of the Analysis In this section we provide an example for which Algorithm 1 does not find an EF1 allocation. This shows that the EF2 guarantee obtained for the algorithm (in Theorem 1) is tight. We consider an instance with two agents and three indivisible goods, i.e., n = 2 and m = 3. Both the agents have a budget of one, B1 = B2 = 1. We set the sizes and values of the three goods as shown in the following table; here ε (0, 1/2) is an arbitrarily small parameter.

Good Size Value g1 ε 10 g2 0.5 0.5 g3 1 ε 1 2ε

Table 1: An instance showing that the EF2 guarantee obtained by Algorithm 1 is tight.

The densities of the goods satisfy ρ(g1) > ρ(g2) > ρ(g3). Also, note that Algorithm 1 returns the allocation with A1 = {g1, g3} and A2 = {g2}. Since v(g1) > v(g2) and v(g3) > v(g2), the retuned allocation is not EF1.

4 Conclusion and Future Work The current work makes notable progress towards efficient computation (and, hence, universal existence) of exact EFk allocations under budget constraints. Our algorithmic results are obtained via a patently simple algorithm, which lends itself to large-scale and explainable implementations. The algorithm s analysis, however, relies on novel insights, which are different from the ideas used for EFk guarantees in prior works and also from the ones used in approximation algorithms for the knapsack problem. In budget-constrained fair division the existence and computation of EF1 allocations is an intriguing open problem. We note that, interestingly, a constrained setting s computational (in)tractability does not reflect the fairness guarantee one can expect. For instance, the knapsack problem is NPhard for proportional instances and yet, EF1 allocations can be computed for such instances in polynomial time. With this backdrop, obtaining EFk guarantees in the GAP formulation6 is another interesting direction for future work.

5As in the general case, the goods can have different sizes. 6As mentioned previously, in the GAP version of the problem, the goods have agent-specific sizes and values.

Acknowledgements Siddharth Barman gratefully acknowledges the support of a SERB Core research grant (CRG/2021/006165). Arindam Khan was partially supported by Pratiksha Trust Young Investigator Award, Google India Research Award, and Google Explore CS Award. Sudarshan Shyam was partially supported by the Independent Research Fund Denmark (DFF) under grant 2032-00185B. K. V. N. Sreenivas is grateful to the Google Ph D Fellowship Program for supporting his research.

References Albers, S.; Khan, A.; and Ladewig, L. 2021. Improved online algorithms for knapsack and GAP in the random order model. Algorithmica, 83(6): 1750 1785. Amanatidis, G.; Birmpas, G.; Filos-Ratsikas, A.; and Voudouris, A. A. 2022. Fair division of indivisible goods: A survey. ar Xiv preprint ar Xiv:2202.07551. Aziz, H.; Li, B.; Moulin, H.; and Wu, X. 2022. Algorithmic fair allocation of indivisible items: A survey and new questions. ar Xiv preprint ar Xiv:2202.08713. Barman, S.; Khan, A.; Shyam, S.; and Sreenivas, K. V. N. 2022. Finding Fair Allocations under Budget Constraints. ar Xiv preprint ar Xiv:2208.08168. Barman, S.; Krishnamurthy, S. K.; and Vaish, R. 2018. Finding fair and efficient allocations. In Proceedings of the 2018 ACM Conference on Economics and Computation, 557 574. Barman, S.; and Sundaram, R. G. 2021. Uniform welfare guarantees under identical subadditive valuations. In Proceedings of the International Conference on International Joint Conferences on Artificial Intelligence, 46 52. Bei, X.; Igarashi, A.; Lu, X.; and Suksompong, W. 2022. The price of connectivity in fair division. SIAM Journal on Discrete Mathematics, 36(2): 1156 1186. Bil o, V.; Caragiannis, I.; Flammini, M.; Igarashi, A.; Monaco, G.; Peters, D.; Vinci, C.; and Zwicker, W. S. 2022. Almost envy-free allocations with connected bundles. Games and Economic Behavior, 131: 197 221. Brandt, F.; Conitzer, V.; Endriss, U.; Lang, J.; and Procaccia, A. D. 2016. Handbook of Computational Social Choice. Cambridge University Press. Budish, E. 2011. The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes. Journal of Political Economy, 119: 1061 1103. Caragiannis, I.; Kurokawa, D.; Moulin, H.; Procaccia, A. D.; Shah, N.; and Wang, J. 2019. The unreasonable fairness of maximum Nash welfare. ACM Transactions on Economics and Computation (TEAC), 7(3): 1 32. Chaudhury, B. R.; Kavitha, T.; Mehlhorn, K.; and Sgouritsa, A. 2021. A little charity guarantees almost envy-freeness. SIAM Journal on Computing, 50(4): 1336 1358. Chekuri, C.; and Khanna, S. 2005. A polynomial time approximation scheme for the multiple knapsack problem. SIAM Journal on Computing, 35(3): 713 728. Cygan, M.; Je z, Ł.; and Sgall, J. 2016. Online knapsack revisited. Theory of Computing Systems, 58(1): 153 190.

Deng, Y.; Sing, T. F.; and Ren, C. 2013. The story of Singapore s public housing: From a nation of home-seekers to a nation of homeowners. In The future of public housing, 103 121. Springer. Fluschnik, T.; Skowron, P.; Triphaus, M.; and Wilker, K. 2019. Fair Knapsack. In The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI, 1941 1948. G alvez, W.; Grandoni, F.; Ingala, S.; Heydrich, S.; Khan, A.; and Wiese, A. 2021. Approximating geometric knapsack via l-packings. ACM Transactions on Algorithms (TALG), 17(4): 1 67. G alvez, W.; Grandoni, F.; Khan, A.; Ram ırez-Romero, D.; and Wiese, A. 2021. Improved Approximation Algorithms for 2-Dimensional Knapsack: Packing into Multiple L-Shapes, Spirals, and More. In 37th International Symposium on Computational Geometry, So CG, volume 189, 39:1 39:17. Gan, J.; Li, B.; and Wu, X. 2021. Approximately envy-free budget-feasible allocation. ar Xiv preprint ar Xiv:2106.14446. Goldman, J.; and Procaccia, A. D. 2015. Spliddit: Unleashing Fair Division Algorithms. SIGecom Exch., 13(2): 41 46. Gourv es, L.; Monnot, J.; and Tlilane, L. 2014. Near Fairness in Matroids. In ECAI, 393 398. Kellerer, H.; Pferschy, U.; and Pisinger, D. 2004. Knapsack problems. Springer. Khan, A.; Maiti, A.; Sharma, A.; and Wiese, A. 2021. On Guillotine Separable Packings for the Two-Dimensional Geometric Knapsack Problem. In 37th International Symposium on Computational Geometry, So CG. Lipton, R. J.; Markakis, E.; Mossel, E.; and Saberi, A. 2004. On approximately fair allocations of indivisible goods. In Proceedings of the 5th ACM Conference on Electronic Commerce, 125 131. Lueker, G. S. 1998. Average-case analysis of off-line and on-line knapsack problems. Journal of Algorithms, 29(2): 277 305. Marchetti-Spaccamela, A.; and Vercellis, C. 1995. Stochastic on-line knapsack problems. Mathematical Programming, 68(1): 73 104. Martello, S.; and Toth, P. 1990. Knapsack problems: algorithms and computer implementations. John Wiley & Sons. Othman, A.; Sandholm, T.; and Budish, E. 2010. Finding Approximate Competitive Equilibria: Efficient and Fair Course Allocation. In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 10. Patel, D.; Khan, A.; and Louis, A. 2021. Group Fairness for Knapsack Problems. In AAMAS 21: 20th International Conference on Autonomous Agents and Multiagent Systems, 1001 1009. Pisinger, D. 2005. Where are the hard knapsack problems? Computers & Operations Research, 32(9): 2271 2284. Plaut, B.; and Roughgarden, T. 2020. Almost envy-freeness with general valuations. SIAM Journal on Discrete Mathematics, 34(2): 1039 1068.

Shmoys, D. B.; and Tardos, E. 1993. An approximation algorithm for the generalized assignment problem. Mathematical programming, 62(1): 461 474. Skiena, S. S. 1999. Who is interested in algorithms and why? Lessons from the Stony Brook algorithms repository. ACM Sigact News, 30(3): 65 74. Suksompong, W. 2021. Constraints in fair division. ACM SIGecom Exchanges, 19(2): 46 61. Wu, X.; Li, B.; and Gan, J. 2021. Budget-feasible Maximum Nash Social Welfare is Almost Envy-free. In The 30th International Joint Conference on Artificial Intelligence (IJCAI 2021), 1 16.