# how_to_resolve_envy_by_adding_goods__ff33b7ba.pdf

How to Resolve Envy by Adding Goods

Matthias Bentert1 , Robert Bredereck2 , Eva Deltl2 , Pallavi Jain3 , Leon Kellerhals2

1University of Bergen, Norway 2TU Clausthal, Germany 3Indian Institute of Technology Jodhpur, India matthias.bentert@uib.no, {robert.bredereck,eva.deltl,leon.kellerhals}@tu-clausthal.de, pallavijain.t.cms@gmail.com

We consider the problem of resolving the envy of a given initial allocation by adding elements from a pool of goods. We give a characterization of the instances where envy can be resolved by adding an arbitrary number of copies of the items in the pool. From this characterization, we derive a polynomialtime algorithm returning a respective solution if it exists. If the number of copies or the total number of added items are bounded, the problem becomes computationally intractable even in various restricted cases. We perform a parameterized complexity analysis, focusing on the number of agents and the pool size as parameters. Notably, although not every instance admits an envy-free solution, our approach allows us to efficiently determine, in polynomial time, whether a solution exists an aspect that is both theoretically interesting and far from trivial.

1 Introduction

Fair allocation of indivisible goods to agents is a fundamental problem in resource allocation [Amanatidis et al., 2023; Liu et al., 2024; Mishra et al., 2023; Nguyen and Rothe, 2023] and has a plethora of applications such as dorm room allocations, donations by a food bank, inheritance matters, divorce disputes, or job allocations. While most work assumes that the allocation starts with a blank sheet, i.e., all items are initially unassigned and the agents do not envy each other, there are many scenarios where some items are already allocated. For example, in inheritance matters, the testament may likely allocate some of the heritable goods in an unfair way. Recent work provides a toolbox of approaches to increase the fairness of such unfair allocations, such as deleting or donating some of the allocated goods [Dorn et al., 2021; Chaudhury et al., 2021; Boehmer et al., 2024], sharing goods [Sandomirskiy and Segal-Halevi, 2022; Bredereck et al., 2023], reallocating them [Aziz et al., 2019; Gourv es et al., 2017], or providing subsidies [Halpern and Shah, 2019; Brustle et al., 2020; Barman et al., 2022]. Naturally, these approaches to increase fairness cannot be a good match for every real-world scenario. Donating or sharing goods is not

always possible: The goods could have lost their value already (think of food donations by a community center), the current allocation may need to abide some constraints such as a testament, or the agents may become attached to their assigned goods. Clearly, subsidies are also not amenable in every scenario, as they may fail to address urgent non-monetary needs such as shelter, food, or medical care. Sometimes, certain approaches, such as reallocation, sharing, or subsidies, are impossible for legal reasons. We extend the toolbox with an approach for scenarios where the initial allocation is fixed and the goal is to alleviate unfairness by allocating items from a pool of additional goods. The feature of adding items that sets it apart from the above approaches is that, theoretically, there is no natural limit on the budget: While one cannot delete/reallocate/share more than all items of the initial allocation, there is no bound on the number of items one can add. Of course, if one could add from the infinite pool of all possible resources, the problem would become trivial. Thus, we assume to be given a finite set of resources with possibly unlimited supply. While true infinity of course is unattainable in reality, scenarios where resources are plentiful or practically sufficient provide a fertile ground for applications of our theoretical results. Consider, for instance, a community center distributing leftover charity items. In such a setting, the center might possess a large stock of various goods that can be reallocated with minimal constraint on quantities. This abundance allows for flexible distributions that can address disparities and highlights a scenario where adding items is feasible, whereas redistributing money is not. Similarly, in some settings, offering cash may be ineffective or even harmful. Recipients might purchase unsuitable items, and non-monetary needs may not be immediately met. Here, directly adding appropriate goods or services is more impactful than offering cash. Another instance of practical abundance involves the use of vouchers or gift cards, which can be thought of as having an infinite supply from the perspective of the allocating authority. Here, the challenge of achieving fairness can be substantially alleviated by issuing as many as needed to satisfy fairness, thereby achieving a more balanced distribution of intangible resources. Additionally, in the context of office liquidations, there may exist vast amounts of leftover resources such as laptops, chairs, and other equipments. We study the computational complexity of alleviating un-

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25)

fairness by adding items from a pool of goods to an initial allocation. Herein, we focus solely on envy-freeness and additive, non-negative valuations.

Related work. When envy-freeness cannot be achieved, one approach is to compensate agents with a divisible resource (e.g., money) to eliminate envy [Haake et al., 2002]. The study of fair division with subsidies or money transfers [Halpern and Shah, 2019; Aziz, 2021] has focused on finding allocations for which minimal subsidies will result in envyfreeness. Instead of adding one divisible resource, our model considers achieving envy-freeness by adding a given set of additional indivisible items. The idea of controlling fair division scenarios by adding or deleting items, in order to arrive at an instance which can be allocated fairly, has been explored in various contexts. Aziz et al. [2016] consider the problem of adding/deleting/replacing few items such that there is an envy-free complete allocation with ordinal valuations. This is similar to our setting when our initial allocation is empty; their NP-hardness results carry over to our problem with ordinal valuations (but not with cardinal, additive valuations). While we focus on achieving envy-freeness through the addition of resources, previous studies have primarily explored fairness by considering item deletions. For example, Dorn et al. [2021] analyzed the complexity of achieving proportional allocations by removing items in settings with ordinal preferences. Similarly, Boehmer et al. [2024] investigated the complexity of ensuring envy-free (and EF1) allocations through item donations, when agents have additive utility-based valuations. Unlike these approaches, our work does not allow modifications to the initial allocation. Closest to ours is the recent work by Prakash et al. [2025] who looked at scenarios where specific resources have been pre-assigned to particular agents and the goal is to complete the allocation by allocating all remaining resources such that the overall allocation is fair and efficient. The key difference to our work is that our pool of additional goods does not need to be fully allocated and that our focus lies on variants where the supply is unbounded.

Our contributions. We study the computational complexity of ENVY ELIMINATION BY ADDING GOODS (defined in Section 2), where the task is to extend an initial unalterable allocation by adding items from a pool of additional goods to the agents such that the extended allocation becomes envyfree. We focus on the setting where the agents have additive, non-negative valuations. A major difference to settings where one can delete or reallocate items from the initial allocation is that there is no natural bound on the number of additionally allocated items. For example, the problem of deleting an unlimited amount of items from an initial allocation is trivial: empty allocations are envy-free. As it turns out, this is not the case when we add an unlimited amount of items which all have infinite supply: Consider the following example with two agents with identical valuations. The initial allocation gives an item of value one to the first agent, and we may add any number of copies of an item with value two. While such observations often pave the way for an NP-

Polynomial-time solvable (Thm 3)

all supply unbounded

k (Thms 7, 8) XP, W[1]-hard |R| (Prop 4) para-NP-hard

|A| (Prop 5) W[1]-hard

p (Thm 8) FPT

|A| + |R| (Obs 6) FPT

bounded budget

Figure 1: Overview over our results for ENVY ELIMINATION BY ADDING GOODS with different parameterizations. Results in dashed boxes hold only for instances with the respective restriction. Here, A denotes the set of agents, R the set of additional items, k the upper bound on the number of items, and p the sum of the supplies. An edge between two parameter boxes implies that the upper parameter upper-bounds the lower parameter.

hardness proof, our main technical contribution shows that whether one can resolve envy by adding any number of copies of a given set of items can be decided in polynomial time (Section 3). The main challenge herein are agents whose valuations over the additional items are identical (or proportional). As a special case, the envy between two agents can only be resolved by an extension if there is an integer divisible by the greatest common divisor within a certain ranges quantified by the agents envy gaps. To resolve the envy between multiple agents, we verify whether this property can be simultaneously fulfilled by an integer linear program (ILP) derived from the above ranges. Polynomial-time solvability of the ILP follows from the constraint matrix being totally unimodular. We next studied how bounding the supply of some items (Section 4) or size (also called budget) of the extension (Section 5) affects the computational complexity of our problem. Motivated by computational intractability even when there are only three additional items with finite supply, we initiate a parameterized complexity analysis of our problem, showing two other parameterized hardness results, but also fixedparameter tractability by the sum of item supplies if the budget is bounded and by the parameter combination number of agents plus number of resources. We refer to Figure 1 for an overview of our results.

2 Preliminaries

For n N, we denote by [n] the set {1, 2, . . . , n}. Let A = {a1, . . . , an} be the set of agents. We have two sets of items: The (multi-)set P of initial items and the set R of additional items. Moreover, each item r R has a supply #(r) N { } and each agent a A has a valuation va : P R N. Throughout this work, we assume valuation functions to be additive and define va(S) := P r S va(r) for all S P R. We call a valuation va binary if va(r) {0, 1}, and say that a approves item r if va(r) = 1. Two valuations va and va are identical if va = va and pro-

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25)

portional if there is an α Q such that va(r) = αva (r) for all r R. We then write va = αva for short. In our work, we are given an initial allocation σ: A 2P , which allocates sets of initial items to agents. The set σ(a) is called the initial bundle of a and is disjoint from the initial bundle of any other agent. We look for an extension ρ: A R N which specifies the number of copies of item r to allocate to agent a. We assert P a A ρ(a, r) #(r) for each r R. The size or budget of ρ is the number P a A P r R ρ(a, r) of allocated items. For agents a, a A, we define va(ρ, a ) := P r R ρ(a , r) va(r). An extended allocation (σ, ρ) consists of an initial allocation σ and an extension ρ. For two agents a, a A and an extended allocation (σ, ρ), we say that a envies a if

va(σ(a)) + va(ρ, a) < va(σ(a )) + va(ρ, a ).

We say that a initially envies a if va(σ(a)) < va(σ(a )). We say that a is (initially) envious if it (initially) envies some other agent. The envy graph Gσ,ρ of (σ, ρ) has a vertex for each agent and a directed edge (a, a ) (also called envy edge) if a envies a . For any pair a, a of agents, the envy gap of a and a with respect to (σ, ρ) is γρ(a, a ) = va(σ(a )) + va(ρ, a ) (va(σ(a)) + va(ρ, a)). We call an extended allocation (σ, ρ) envy-free if Gσ,ρ is edgeless. We then also say that ρ resolves envy. The initial envy gap of a and a is γ(a, a ) = va(σ(a )) va(σ(a)). We mention that the (initial) envy gap can be both positive and negative (as well as 0). In this work, we consider the computational problem of finding an envy-resolving extension, defined as follows.

Input: Sets P, R of items, a supply #(r) N { } for each r R, a set A of agents, each with a valuation function va : P R N, an initial allocation σ, and an integer k N. Question: Is there a size-k envy-resolving extension ρ?

ENVY ELIMINATION BY ADDING GOODS

We point out that the main part of this work is on the case where the budget k is unrestricted, i.e., there is no restriction on the number of items the extension can allocate. We use standard notation from parameterized algorithmics [Cygan et al., 2015]. A problem parameterized with some integer k is called (1) fixed-parameter tractable (FPT), if it can be solved in f(k) |I|O(1) time, and (2) in XP, if it can be solved in |I|f(k) time, where f is a computable function only depending on k and |I| is the instance size. One can show that a parameterized problem is likely not FPT by proving it to be W[1]-hard (using parameterized reductions, which generalize standard polynomial-time many-one reductions). Moreover, if a parameterized problem is NP-hard even for constant parameter values, we call it para-NP-hard. In our running time analysis, we assume that basic arithmetic operations over any numbers in the input (or of similar size) can be performed in constant time.

3 When Supply and Budget are Unbounded We first look at the case where each item r R has infinite supply. We show that this case is polynomial-time solvable. We first show how to decide whether the envy between two agents can be resolved. Afterwards, we generalize the result to more than two agents. We distinguish between agents with non-proportional and proportional valuations. In the first case, envy can always be overcome as shown next. Observe that valuations can only be non-proportional if there are at least two items in R. Lemma 1. Let a, a be two agents with non-proportional valuations. If each item in R has infinite supply, then there exists an extension ρ that resolves envy between a and a . Moreover, ρ can be computed in O(m) time, where m = |R|.

Proof. Non-proportionality implies the existence of r1, r2 R with differing ratios of valuations between agents. For brevity, let va(r1) = x, va(r2) = c, va (r1) = y, and va (r2) = d. Furthermore, assume without loss of generality that r1 is more valuable relative to r2 for agent a compared to agent a , i.e., x y > c

which is equivalent to cy < xd. As all of these values are integers, we have xd cy 1. We now show how we can leverage the differing valuation ratios to eliminate envy by careful distribution of these items. If initially a envies a , consider the extension ρ with ρ(a, r1) = d and ρ(a , r2) = y. Then

va(ρ, a) = d x > y c = va(ρ, a ) and

va (ρ, a) = d y = y d = va (ρ, a ),

that is, the gap γ(a, a ) decreases by xd cy 1 while the valuation of a regarding the bundles of a and a does not change as both values increase by dy. Thus, allocating γ(a, a ) copies of ρ resolves the envy of a to a without creating new envy from a to a. If initially a envied a, then we can do the same with the roles of a and a reversed by allocating c γ(a , a) copies of r1 to a and x γ(a , a) copies of r2 to a . Note that finding r1, r2 R with different valuation ratios takes O(m) steps as we can start with any object and then all remaining objects either have the same valuation ratio or at least one differs. Hence, we can compute an extension that resolves envy between a and a in O(m) time.

We next turn to the case with proportional valuations. We first prove a necessary and sufficient condition for resolving envy between two agents a and a . We mention that the valuation of initial items does not need to be proportional. Lemma 2. Let a, a be two agents with va(r) = αva (r) for all r R and some α. Suppose that a envies a and let γ(a, a ) and γ(a , a) be the envy gaps of a and a and of a and a, respectively. If each item in R = {r1, . . . , rm} has infinite supply, then there exists an extension ρ that resolves the envy between a and a if and only if there exists an integer γ(a, a ) T αγ(a , a) that is divisible by gcd(va(r1), . . . , va(rm)). Moreover, ρ can be computed in O(m log W) time, where W is the largest item valuation.

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25)

Proof. For brevity we let bi := ρ(a, ri) and b i := ρ(a , ri) for each i [m]. Then ρ is envy-resolving if and only if

i=1 biva(ri) va(σ(a )) +

i=1 b iva(ri)

and va (σ(a )) +

i=1 b iva (ri) va (σ(a)) +

i=1 biva (ri).

These inequalities can be reformulated as

i=1 (bi b i)va(ri) va(σ(a )) va(σ(a)) = γ(a, a ), and

i=1 (bi b i)va (ri) va (σ(a ) va (σ(a)) = γ(a , a).

As va(r) = αva (r) for each r R, ρ is envy-resolving if and only if

γ(a, a ) Pm i=1(bi b i)va(ri)

= Pm i=1(bi b i)αva (ri) αγ(a , a).

Next, if d := gcd(va(r1), . . . , va(rm)), then there are ki N such that va(ri) = d ki. Thus, Pm i=1(bi b i)va(ri) = d Pm i=1(bi b i)ki,

and ρ is envy-resolving if and only if there is an integer

T = d Pm i=1(bi b i)ki

with γ(a, a ) T αγ(a , a). Clearly, T is divisible by d. We now show how such an extension can be computed if it exists. By B ezout s Lemma [B ezout, 1779], the equation d := gcd(va(r1), va(r2), . . . , va(rm)) implies the existence of integers c1, c2, . . . , cm with d = Pm i=1 civa(ri). The computation of d and the coefficients ci can be carried out iteratively using the EXTENDED EUCLIDEAN ALGORITHM [Knuth, 1997]. As d divides T, there is a q N such that T = q d; therefore

T = q Pm i=1 civa(ri) = Pm i=1(q ci) va(ri).

We then decompose each q ci into positive and negative parts

bi = max{0, q ci}, b i = max{0, q ci}.

Then bi b i = q ci, and therefore Pm i=1(bi b i) va(ri) = T. Once coefficients bi and b i are computed, we define ρ to be an extension, such that ρ(a, ri) = bi and ρ(a , ri) = b i, for all ri R. As γ(a, a ) T αγ(a , a), we get

va(σ(a)) + Pm i=1 biva(ri)

= va(σ(a)) + Pm i=1 b iva(ri) + T

va(σ(a)) + Pm i=1 b iva(ri) + γ(a, a )

= va(σ(a )) + Pm i=1 b iva(ri).

This confirms that agent a does not envy agent a under the extended allocation. Similarly, since va(r) = αva (r),

va (σ(a )) + Pm i=1 b iva (ri)

= va (σ(a )) + Pm i=1 biva (ri) T

α va (σ(a )) + Pm i=1 biva (ri) + γ(a , a)

= va (σ(a)) + Pm i=1 biva (ri).

Thus, agent a does not envy agent a, ensuring that neither agent envies the other in the extended allocation. The EXTENDED EUCLIDEAN ALGORITHM runs in O(m log W) time where W = maxa A,r R va(r). Scaling the coefficients and decomposing them into bi and b i is linear in m. Thus, the overall running time is in O(m log W).

We next generalize the above to more than two agents and show the main result of this section.

Theorem 3. ENVY ELIMINATION BY ADDING GOODS is polynomial-time solvable when #(r) = for all r R and k is unbounded.

Proof. Let σ be an initial allocation. We start with an empty extension ρ. Let Gσ,ρ denote the envy graph. Note that, as shown in Lemma 2, finding an envy-resolving extension is not always possible. Our algorithm proceeds in two phases. The first phase addresses envy among agents which have proportional valuations of all items in R, while the second phase eliminates envy between agents with non-proportional valuations. To implement the first phase, we utilize the fact that proportional valuations form an equivalence relation. This allows us to partition A into equivalence classes A1 At, where a, a Ai if and only if a and a have proportional valuations over R. We begin by trying to resolve envy edges within each equivalence class. Once this is completed, we move on to the second phase, where we eliminate envy between agents from different equivalence classes.

Phase 1: Eliminating envy between two agents with proportional valuations. Let Ai be an equivalence class and recall that R = {r1, r2, . . . , rm}. First, we compute a normalized valuation v as follows. For each a Ai, we compute da = gcd(va(r1), va(r2), . . . , va(rm)) and set v a(ri) = va(r)

da for all r P R. Note that v a(r) is an integer for all r R but not necessarily for r P. Moreover, it holds that gcd(v a(r1), v a(r1), . . . , v a(rm)) = 1 and an extension ρ resolves envy with respect to valuations v a if and only if it resolves envy with respect to the original valuation va. Note that the envy gap γ(a, a ) of two agents a, a Ai with respect to v might not be integral. However, we can round all these values up to the nearest integer as valuations can only go up in integer steps as v a(r) is an integer for each r R. Slightly abusing notation, we will refer to γ (a, a ) as the rounded value. We next show that v a(r) = v a (r) for all a, a Ai and all r R. Since a, a Ai, it holds that va(r) = αva (r) for all r R. Moreover, since va(r) and va (r) are nonnegative integers, it holds that α = p

q for two positive coprime

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25)

integers p and q. We claim that p = q = 1. If p = 1, then v a(r) is divisible by p for all r R, contradicting the fact that gcd(v a(r1), v a(r1), . . . , v a(rm)) = 1. Similarly, if q = 1, then v a (r) are divisible by q for each r R, another contradiction. Hence α = 1 and v a(r) = v a (r) for all r R. We next build an integer linear program (ILP) that encodes whether a solution exists. We start with a variable xa for each agent a Ai that roughly encodes how much utility agent a should get in a solution (with respect to the valuation v a). Note that since v a(r) = v a (r) for all r R, the meaning of variable xa is universal for all agents in Ai. For each pair a, a Ai of agents, we add the constraint xa xa γ (a, a ). Note that γ (a, a ) is a constant that can be precomputed in polynomial time. This constraint encodes that if a gets an additional utility of xa and a gets an additional utility of xa , then a does not envy a . If there is an extension that resolves all envy within Ai, then the constructed ILP has a solution. It remains to show how to construct an extension from a solution to the ILP and to discuss why a solution to the constructed ILP can be found in polynomial time. Towards the former, note that if a solution exists, then it remains a solution if all agents in Ai get c additional utility for any c N. Moreover, we use the fact that gcd(v a(r1), v a(r2), . . . , v a(rm)) = 1 for all a Ai. This implies that there are two multisets X, Y of items such that v a(X) = v a(Y ) + 1. If a solution is found, then for each agent a Ai, we do the following. For each a Ai, let za be the value assigned to variable xa in the solution. We give za times the bundle X to agent a and za times the bundle Y to all other agents in Ai. Note that the valuation of all bundles except for a increases by za v a(Y ) and the valuation of the bundle of a increases by za v a(X) = za v a(Y ) + za. That is, the valuation of a s bundle increases by precisely za compared to the bundles of all other agents in Ai. After doing the above for all agents in Ai, it holds that the difference in valuation of the bundles of a and a changed by za za , which is precisely what the solution to the ILP required. Since all of the above can be computed in polynomial time, we can compute an extension resolving envy given a solution to the constructed ILP. To conclude the first phase, we note that the constructed ILP encodes a totally unimodular matrix as each constraint contains exactly two variables and one has coefficient 1 and the other has coefficient -1 [Tamir, 1976]. Since all constants in the ILP are integral, it holds that the corresponding polyhedron only has integer vertices and the ILP can be solved in polynomial time [Hoffman and Kruskal, 1956] (or it can be concluded that no (integral) solution exists).

Phase 2: Eliminating envy between two agents with nonproportional valuations. Once the first phase has been applied to every equivalence class Ai A, any remaining envy must necessarily exist between agents with non-proportional valuations. Let Ediff denote the set of remaining envy edges between agents with non-proportional valuations. Next, we eliminate envy between two agents with non-proportional valuations without creating new envy similar to what we did in Lemma 1. Let a, a be two agents with non-proportional valuations

such that a envies a . By Lemma 1, we know that it is always possible to compute an extension ρ to eliminate this envy. Let x, x be the number of items r, r , respectively, added in ρ to resolve the envy between a and a . We update ρ such that for each agent a A we set ρ(a , r) = ρ(a , r) + x if x va (r) x va (r ) and ρ(a , r ) = ρ(a , r ) + x otherwise. For an agent a , assume w.l.o.g. that x va (r) x va (r ). If agent a did not envy an agent a before the allocation, no matter which item set a gets, no new envy will be created. This follows from the fact that va (σ(a )) va (σ(a)) implies

va (σ(a )) + x va (r) va (σ(a)) + x va (r)

va (σ(a)) + x va (r ).

As no new envy edges are created, we can apply this step until Ediff = , implying that we have reached an envy-free extended allocation of the items.

Running time. As shown above, phase one can be solved in polynomial time for each equivalence class Ai. Since the number of equivalence classes is at most n and they can be computed in polynomial time, the first phase takes polynomial time overall. At the beginning of phase 2 there can be at most n2 envy edges. For non-proportional envy edges, Lemma 1 guarantees that no new envy edges are created during their elimination. Consequently, this step is executed at most n2 times. As resolving one conflict edges takes O(m) time, the total running time for the second phase is in O(n2 m). This concludes the proof of Theorem 3.

4 When some Supply is Bounded

We next focus on the case where we still have no restrictions on the budget, but some items may have finite supply. This makes finding an envy-resolving extension computationally hard, even if we have only three different items with finite supply. Also, as we will see, there is little hope for fixed-parameter tractability for the number of agents alone. However, when parameterizing by the number of agents plus the number of (different) items, the problem becomes fixedparameter tractable. We first show the two hardness results.

Proposition 4. ENVY ELIMINATION BY ADDING GOODS is NP-hard even if there are three additional items, if the budget is unbounded, and the valuations are binary.

Proof. We reduce from the CLIQUE problem, where the task is to decide whether a given graph G = (V, E) contains a complete subgraph with a given number ℓof vertices. We have an agent av for each vertex v V , an agent ae for each edge e E, and an extra agent b. Initially, b holds an item that is approved by b and each edge agent ae, each vertex agent av holds an item that only av approves, and for each e = {u, v} E, the edge agent ae holds an item that only au and av approve. Thus, each edge agent ae envies b by one, and each vertex agent av values its own bundle as valuable as that of each incident edge agent, and more valuable by one than that of each non-incident edge agent. We have three

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25)

additional items r, r , r with #(r) = ℓ 2 , #(r ) = |E| ℓ 2 , and #(r ) = ℓ. All vertex agents av approve r and r , and all edge agents ae approve r and r . Clearly, the reduction can be computed in polynomial time. So let us prove its correctness. Suppose first that K V forms a clique of size ℓin G, and let Ek E be the set of ℓ 2 edges within that clique. Then we create an extension by allocating a copy of r to each av with v K, a copy of r to each ae with e EK, and a copy of r to ae with e / EK. Then the edge agents no longer envy b. Next, consider a vertex agent av and an edge agent ae. If e / EK, then the value of ae s bundle did not change for av, so there still is no envy. So suppose that e EK. If e is not incident to v, then av now values its bundle and that of ae equally. If e is incident to v, then v K, and av s valuation for its own bundle and ae s bundle increased by one. Thus, in all, this extension resolves envy. Suppose next that ρ resolves envy. As each edge agent ae envies b by one, we need to assign at least one item to each ae that ae approves. This only leaves the items r and r , and as #(r)+#(r ) = |E|, each edge must receive exactly one item. Let EK be the set of edges such that for each e Ek, agent ae receives r. Then each vertex agent av where v is incident to an edge e EK must receive a resource r , otherwise it envies ae. As #(r ) = ℓand |EK| = #(r) = ℓ 2 , the edges in EK must be incident to at most ℓvertices. This is only possible if these vertices form a clique of size ℓ, and EK are the edges within that clique.

Moreover, there is little hope for fixed-parameter tractability with the number of agents even if they all have identical valuations.

Proposition 5. ENVY ELIMINATION BY ADDING GOODS is W[1]-hard parameterized by |A|, even if all numbers in the input are encoded in unary, and all agents have identical valuations, even within the initial resource set.

Proof. We give a reduction from BIN PACKING parameterized by the number ℓof bins: Given integers u1, u2, . . . , un N, a number ℓof bins, and a bin size B, the task is to decide whether there is an assignment of the integers to the bins such that the sum of the integers in one bin is at most B. This problem is W[1]-hard even if all numbers are encoded in unary and if the sum of all integers equals ℓB [Jansen et al., 2013]; thus any solution must assign integers of value exactly B to each bin. Given a BIN PACKING instance, we construct an instance of ENVY ELIMINATION BY ADDING GOODS as follows. We have ℓ+ 1 agents a1, . . . , aℓ, b with identical valuations; we call the valuation function v. Initially, only b holds an item p with value v(p) = B. For each j [n], R< contains an item rj with value v(rj) = uj. Clearly, the construction can be computed in polynomial time. We next show the two instances to be equivalent. The BIN PACKING instance is a yes-instance if and only if there is an assignment π: [n] [ℓ] such that each bin receives integers of value exactly to B. Observe that the extension that allocates rj to aπ(j) for each j [n] assigns a set of items with value exactly B to each agent ai and thus resolves all envy with b. Indeed, an extension resolves envy if and

only if it assigns a set of value B to each ai; this proves the equivalence of the two instances.

We conclude this section with a result that holds for the bounded as well as for the unbounded variant of our problem. From Proposition 5 we can conclude that parameter number of agents is too small to hope for fixed-parameter tractability. Proposition 4 demonstrates the same for the number of (different) additional items. However, when these parameters are combined, the problem becomes fixed-parameter tractable. This follows from a simple ILP formulation combined with the algorithm by Eisenbrand and Weismantel [2020].

Observation 6. ENVY ELIMINATION BY ADDING GOODS is FPT when parameterized by |A| + |R|.

Proof. The ILP uses an integer variable 0 xr a #(r) for each agent a A and each item r R. Our formulation contains the following constraints: X

a A xr a #(r) for all r R (1)

va(σ(a))+ X

r R va(r)xr a va(σ(a ))+ X

r R va (r)xr a

for all a, a A. (2)

The first constraint ensures that we add at most #(r) copies of r R, while the second constraint ensures that the extended allocation is envy-free. If we are given an instance of the bounded variant, we add the constraint X

r R xr a k (3)

to ensure that the extension allocates at most k items. Fixed-parameter tractability now follows from the fact that our ILP contains O(|A| + |R|) variables and O(|A|2 + |R|)) constraints and from the result by Eisenbrand and Weismantel [2020] showing that solving ILPs is fixed-parameter tractable with respect to their number of constraints.

5 When the Budget is Bounded

Finally, we consider the case where we have a bound k on the size of the extension. We show that, even if the supply is not the bottleneck, there is little hope for the problem to be fixed-parameter tractable when parameterized by k.

Theorem 7. ENVY ELIMINATION BY ADDING GOODS with envy-freeness is W[1]-hard with respect to k even if restricted to binary valuations, if all supplies are k, and, initially, there is only one envious agent.

Proof. We give a reduction from INDEPENDENT SET parameterized by solution size ℓ, which, given a graph G = (V, E) and an integer ℓ, asks whether there is a set K V of at least ℓpairwise non-adjacent vertices. Given such an instance, we construct an equivalent instance of ENVY ELIMINATION BY ADDING GOODS as follows. We have one agent ae for each edge e E and one additional selection agent b. The set P contains mℓinitially assigned items (where m = |E|) of two different types t1 and t2. Each agent ae initially holds ℓ 1

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25)

items of type t1 and one item of type t2. Agent b approves items of both types and each agent ae only approves items of type t2. Note that initially only agent b is envious (as b does not hold any items). The set R contains one item rv for each vertex v V . The item rv is approved by agent b and all agents ae where e is incident to v in G. We complete the construction by setting k = ℓ. Clearly, the reduction can be computed in polynomial time. We next show the two instances to be equivalent. Assume first that there is an independent set K of size ℓin G. Then we create an extension that allocates one copy of each item in {rv | v K} to b. As b has positive value for all these items, b does not envy any other agent. Each agent ae evaluates the bundle of each agent ae (including themselves) with 1. However, since K is an independent set, agent b holds at most one item that ae approves. Thus, no agent envies any other agent and the constructed instance is a yes-instance of ENVY ELIMINATION BY ADDING GOODS. For the converse, let ρ be an envy-resolving extension of size ℓ. All of these ℓitems must be assigned to b as otherwise b envies all other agents. If ρ(b, ru) + ρ(b, rv) > 1 for any edge e = {u, v}, then ae will envy b, as it has positive value for both ru and rv, but only a value of 1 for its own bundle. Thus, the set of items allocated by ρ form an independent set of size ℓin G.

As the hardness results from Section 4 also hold when we have a size bound k, we cannot hope for fixed-parameter tractability for the number of (different) items. We are however able to show fixed-parameter tractability with respect to the sum over all item supplies. We remark that this algorithm implies that ENVY ELIMINATION BY ADDING GOODS is in XP with respect to k.

Theorem 8. ENVY ELIMINATION BY ADDING GOODS can be solved in O(|R|min{p,k} |A|2) time, where p = P r R #(r) is the sum of the finite supplies.

Proof. Our algorithm is based on a branching routine which is given an instance (P, R, #, A, v, σ, k) and an (initially empty) extension ρ that allocates items with finite supply, and proceeds as follows. If ρ resolves all envy, return yes. Otherwise, there exists at least one envious agent a A. For each r R with #(r) > 0 (if there is no such item or k = 0, return no), make a recursive call with input (P, R, # , A, v, σ, k 1) and ρ , where # is a copy of # but # (r) = #(r) 1 and ρ is a copy of ρ but ρ (a, r) = ρ(a, r)+1. Return yes if one of the calls returns yes, and no otherwise. Clearly, every extension ρ in any recursive call is valid, i.e., it allocates each item r R at most #(r) times and breaks as soon as k items have been allocated. Thus, if the algorithm computes an extension which is envy-resolving, then we have a yes-instance at hand. For the converse, let ρ be an envy-resolving extension of size at most k. For two extensions ρ and ρ we write ρ ρ if ρ(a, r) ρ (a, r) for all a A and r R. We prove that the algorithm returns yes by induction over the size k of ρ. For each k 0, we claim that there is a recursive call that is given an extension ρ of size k < k such that ρ ρ .

This statement is clearly true for k = 0. So suppose that the statement is true for some fixed k and let ρ ρ be the corresponding extension. If the algorithm returns yes within the current recursive call, then we are done. Note that specifically, the algorithm returns yes if ρ(a, r) = ρ (a, r) for all a A and r R, since ρ is envy-resolving. Suppose that the algorithm does not return yes within the current recursive call. Note that for each agent a, that is envious with respect to (σ, ρ), and thus particularly the agent that is chosen by the algorithm within our call, the solution ρ must assign at least one (additional) item from R to that agent; thus, ρ(a, r) < ρ (a, r) for some item r R. This also implies that #(r) > 0 in the current recursive call. Then, the algorithm makes a call that is given an extension ρ that is a copy of ρ, but ρ (a , r) = ρ(a , r) + 1. Note that ρ allocates k + 1 k finite supply items and ρ ρ , proving the induction, and thus the correctness of the algorithm. As for the running time, checking whether the current extension resolves envy takes O(|A|) time. In each recursive call, one item is assigned and k is decreased by one. Thus, the depth of the branching tree is at most min{p, k}. Moreover, as in each call, the algorithm makes at most |R| recursive calls, the overall running time is as claimed.

6 Conclusion We initiated the study of mitigating fairness of an initial allocation by adding goods, restricting ourselves to the notion of envy-freeness and additive valuations. In our parameterized complexity analysis, we leave open whether ENVY ELIMINATION BY ADDING GOODS is NP-hard or polynomial-time solvable for a constant number of agents. Further, can Theorem 8 be lifted to the setting where the budget is unlimited and there are both finite and infinite supplies? (The parameter would then become the sum of the finite supplies.) When adapting the branching routine to only assign finite supply items and calling the polynomial-time algorithm from Theorem 3 to decide whether the current allocation can be extended with the infinite supply items, one would need to derive a hint which agent is guaranteed to require an item with finite supply. Finally, does Proposition 4 also hold for two additional items? Our problem can also be studied for other fairness notions such as EF1 [Budish, 2010] or EFX [Caragiannis et al., 2019], but also the many fair share notions [Steinhaus, 1948; Budish, 2011; Babichenko et al., 2024]. As for EF1 and EFX, we believe that our hardness results can be easily transferred. Finally, investigating approximation guarantees, e.g. when minimizing the number of added items could be an intriguing research direction. Similarly, it seems attractive to minimize (absolute or relative) envy approximately in our setting. Since the latter approximation is known to be mostly intractable when allocations are computed from scratch [Lipton et al., 2004], it might be worth to combine this with parameterized approaches or structural restrictions.

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25)

Acknowledgements This research project started at the annual research retreat of the Algorithmics and Computational Complexity (AKT) group of TU Berlin, held in Darlingerode, Germany, September 17 22, 2023. Matthias Bentert acknowledges his support by the European Research Council (ERC) under the European Union s Horizon 2020 research and innovation programme (grant agreement No. 819416). Eva Deltl acknowledges her support by the Deutsche Forschungsgesellschaft (German Research Foundation, DFG), project COMSOC-MPMS, (grant agreement No. 465371386). Pallavi Jain acknowledges her support from SERB-SUPRA grant number SPR/2021/000860 and IITJ Seed Grant grant I/SEED/PJ/20210119. Robert Bredereck, Eva Deltl and Pallavi Jain were supported by a DSTDAAD travel grant (DAAD grant agreement No. 57683502).

References [Amanatidis et al., 2023] Georgios Amanatidis, Haris Aziz, Georgios Birmpas, Aris Filos-Ratsikas, Bo Li, Herv e Moulin, Alexandros A. Voudouris, and Xiaowei Wu. Fair division of indivisible goods: Recent progress and open questions. Artificial Intelligence, 322:103965, 2023. [Aziz et al., 2016] Haris Aziz, Ildik o Schlotter, and Toby Walsh. Control of fair division. In Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI), pages 67 73, 2016. [Aziz et al., 2019] Haris Aziz, P eter Bir o, J erˆome Lang, Julien Lesca, and J erˆome Monnot. Efficient reallocation under additive and responsive preferences. Theoretical Computer Science, 790:1 15, 2019. [Aziz, 2021] Haris Aziz. Achieving envy-freeness and equitability with monetary transfers. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), pages 5102 5109, 2021. [Babichenko et al., 2024] Yakov Babichenko, Michal Feldman, Ron Holzman, and Vishnu V. Narayan. Fair division via quantile shares. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC), pages 1235 1246. ACM, 2024. [Barman et al., 2022] Siddharth Barman, Anand Krishna, Yadati Narahari, and Soumyarup Sadhukhan. Achieving envy-freeness with limited subsidies under dichotomous valuations. In Proceedings of the 31st International Joint Conference on Artificial Intelligence (IJCAI), pages 60 66, 2022. [B ezout, 1779] Etienne B ezout. Th eorie g en erale des equations alg ebriques. Paris, Impr. de P.-D. Pierres, 1779. [Boehmer et al., 2024] Niclas Boehmer, Robert Bredereck, Klaus Heeger, Duˇsan Knop, and Junjie Luo. Multivariate algorithmics for eliminating envy by donating goods. Autonomous Agents and Multi-Agent Systems, 38(2):43, 2024. [Bredereck et al., 2023] Robert Bredereck, Andrzej Kaczmarczyk, Junjie Luo, Rolf Niedermeier, and Florian

Sachse. Improving resource allocations by sharing in pairs. Journal of Artificial Intelligence Research, 78:1069 1109, 2023. [Brustle et al., 2020] Johannes Brustle, Jack Dippel, Vishnu V. Narayan, Mashbat Suzuki, and Adrian Vetta. One dollar each eliminates envy. In Proceedings of the 21st ACM Conference on Economics and Computation (EC), pages 23 39. ACM, 2020. [Budish, 2010] Eric Budish. The combinatorial assignment problem: approximate competitive equilibrium from equal incomes. In Moshe Dror and Greys Sosic, editors, Proceedings of the Behavioral and Quantitative Game Theory - Conference on Future Directions (BQGT), page 74:1, 2010. [Budish, 2011] Eric Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, 119(6):1061 1103, 2011. [Caragiannis et al., 2019] Ioannis Caragiannis, David Kurokawa, Herv e Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang. The unreasonable fairness of maximum nash welfare. ACM Transactions on Economics and Computation, 7(3):12:1 12:32, 2019. [Chaudhury et al., 2021] Bhaskar Ray Chaudhury, Telikepalli Kavitha, Kurt Mehlhorn, and Alkmini Sgouritsa. A little charity guarantees almost envyfreeness. SIAM Journal on Computing, 50(4):1336 1358, 2021. [Cygan et al., 2015] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D aniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. [Dorn et al., 2021] Britta Dorn, Ronald de Haan, and Ildik o Schlotter. Obtaining a proportional allocation by deleting items. Algorithmica, 83(5):1559 1603, 2021. [Eisenbrand and Weismantel, 2020] Friedrich Eisenbrand and Robert Weismantel. Proximity results and faster algorithms for integer programming using the steinitz lemma. ACM Transactions on Algorithms, 16(1):5:1 5:14, 2020. [Gourv es et al., 2017] Laurent Gourv es, Julien Lesca, and Ana elle Wilczynski. Object allocation via swaps along a social network. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI), page 213 219, 2017. [Haake et al., 2002] Claus-Jochen Haake, Matthias G Raith, and Francis Edward Su. Bidding for envy-freeness: A procedural approach to n-player fair-division problems. Social Choice and Welfare, 19:723 749, 2002. [Halpern and Shah, 2019] Daniel Halpern and Nisarg Shah. Fair division with subsidy. In Proceedings of the 12th International Symposium on Algorithmic Game Theory (SAGT), pages 374 389, 2019. [Hoffman and Kruskal, 1956] Alan J. Hoffman and Joseph B. Kruskal. Integral boundary points of con-

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25)

vex polyhedra. Linear Inequalities and Related Systems, pages 223 246, 1956. [Jansen et al., 2013] Klaus Jansen, Stefan Kratsch, D aniel Marx, and Ildik o Schlotter. Bin packing with fixed number of bins revisited. Journal of Computer and System Sciences, 79(1):39 49, 2013. [Knuth, 1997] Donald E Knuth. The art of computer programming, Volume I: Fundamental Algorithms, 3rd Edition. Addison-Wesley, 1997. [Lipton et al., 2004] R. J. Lipton, E. Markakis, E. Mossel, and A. Saberi. On approximately fair allocations of indivisible goods. In Proceedings of the 5th ACM Conference on Electronic Commerce (EC), page 125 131. ACM, 2004. [Liu et al., 2024] Shengxin Liu, Xinhang Lu, Mashbat Suzuki, and Toby Walsh. Mixed fair division: A survey. Journal of Artificial Intelligence Research, 80:1373 1406, 2024. [Mishra et al., 2023] Shaily Mishra, Manisha Padala, and Sujit Gujar. Fair allocation of goods and chores - tutorial and survey of recent results. Co RR, abs/2307.10985, 2023. [Nguyen and Rothe, 2023] Trung Thanh Nguyen and J org Rothe. Complexity results and exact algorithms for fair division of indivisible items: A survey. In Proceedings of the 32nd International Joint Conference on Artificial Intelligence, (IJCAI), pages 6732 6740, 2023. [Prakash et al., 2025] Vishwa HV Prakash, Ayumi Igarashi, and Rohit Vaish. Fair and efficient completion of indivisible goods. In Proceedings of the 39th AAAI Conference on Artificial Intelligence (AAAI), pages 14045 14053, 2025. [Sandomirskiy and Segal-Halevi, 2022] Fedor Sandomirskiy and Erel Segal-Halevi. Efficient fair division with minimal sharing. Operations Research, 70(3):1762 1782, 2022. [Steinhaus, 1948] Hugo Steinhaus. The problem of fair division. Econometrica, 16:101 104, 1948. [Tamir, 1976] Arie Tamir. On totally unimodular matrices. Networks, 6(4):373 382, 1976.

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence (IJCAI-25)