Achieving Envy-Freeness with Limited Subsidies under Dichotomous Valuations

1 Introduction

Discrete fair division is an extremely active field of work at the interface of mathematical economics and computer science [Brandt et al., 2016; Endriss, 2017]. This field addresses the problem of finding fair allocations of indivisible goods (i.e., resources that cannot be fractionally assigned) among agents with individual preferences. Solution concepts and algorithms developed here address several real-world settings, such as assignment of housing units [Benabbou et al., 2020; Deng et al., 2013], course allocation [Budish et al., 2017], and inheritance division; the widely-used platform spliddit.org [Goldman and Procaccia, 2015] provides fair-division methods for a range of other allocation problems.

The quintessential and classic [Foley, 1966; Varian, 1974] notion of fairness in mathematical economics is that of envyfreeness, which requires that each agent weakly prefers the bundle assigned to her over that of any other agent. However, in the case of indivisible goods, an envy-free allocation is not guaranteed to exist; consider the (ad nauseam) example of two agents and one good.

Motivated, in part, by such considerations, a notable thread of research in discrete fair division aims to achieve the ideal of envy-freeness with the use of subsidies [Halpern and Shah, 2019; Brustle et al., 2020; Goko et al., 2021; Caragiannis and Ioannidis, 2021]. The objective is to provide each agent i-in addition to a bundle-an appropriate subsidy pi such that envy-freeness is achieved overall. That is, the aim is to identify an allocation of the goods and subsidies such that each agent i's value for her bundle plus her subsidy, pi, is at least as large as i's value for any other agent j's bundle plus the subsidy pj .

The subsidy model can be alternatively viewed as a setting wherein we have a divisible good (money), along with the indivisible ones. The divisible good can be fractionally assigned among the agents towards achieving fair (envy-free) outcomes. A natural question in this context is to understand how much subsidy is required to eliminate all envy. This question was in fact addressed in the classic work of Maskin [1987] for the case of unit-demand agents. Considering a scaling, wherein each agent has value at most 1 for any good, Maskin showed that a total subsidy of (n-1) suffices; 1 throughout, n denotes the number of agents participating in the fair division exercise. This unit-demand setting is referred to as the rent division problem and has been studied over the past few decades; see, e.g., [Aziz, 2020] and references therein. Going beyond rent division, the above-mentioned results address settings in which agents' preferences span the subsets of the goods. In particular, the work of Halpern and Shah [2019] shows that, if the n agents have binary additive valuations, then envy-freeness can be achieved with a total subsidy of (n - 1). A similar result was obtained for binary submodular valuations by Goko et al. [2021].

The current work contributes to this line of work with a focus on valuations that have binary marginals. Specifically, we address fair division instances in which, for each agent i, the marginal value of any good g relative to any subset S is either zero or one, vi(S ∪ {g}) - vi(S) ∈ {0, 1}; here, set function vi denotes the valuation of agent i. Such set functions are referred to as dichotomous valuations and have received significant attention in various fair division settings, e.g., [Bogomolnaia et al., 2005; Bouveret and Lang, 2008; Kurokawa et al., 2018; Babaioff et al., 2021]. Indeed, dichotomous valuations-and restricted subclasses thereofmodel preferences in several application domains; see, e.g., [Roth et al., 2005; Deng et al., 2013; Benabbou et al., 2020].

1 Here, a valuation scaling is unavoidable, since the obtained guarantee is an absolute bound (on the total subsidy).

The following stylized example illustrates the applicability of dichotomous valuations and the use of subsidies: consider a scheduling setting in which time-slots (indivisible goods) have be to assigned among employees (agents) whose nonzero marginal values for the slots are the same; equivalently, the agents have binary marginals for the slots. An employee's preference on whether a time-slot can be utilized (i.e., the slot has a nonzero marginal value) could depend on multiple factors, such as contiguity of slots, shift rotations, and time of day. Still, given that the current work holds for general dichotomous valuations, 2 finding a fair allocation in such a scheduling setting falls under the purview of the current work. Also, in this context, subsidies can be viewed as bonuses paid to the employees.

Our Results. We prove that, under dichotomous valuations, there exists an allocation that achieves envy-freeness with a per-agent subsidy of either 0 or 1 (Theorem 4). Furthermore, such an envy-free solution can be computed efficiently in the standard value-oracle model. Our per-agent subsidy bound implies that, for dichotomous valuations, a total subsidy of at most (n - 1) suffices to realize envy-freeness. Indeed, this guarantee is tight: consider an instance with n agents and a single unit-valued good. In this instance, to achieve envy-freeness under any allocation, (n - 1) agents would each require a subsidy of 1.

Additional Related Work. As mentioned previously, Halpern and Shah [2019] showed that if the agents' valuations are binary additive, then envy-freeness can be achieved with a cumulative subsidy of (n - 1). The work of Goko et al. [2021] provides an analogous result for binary submodular valuations and further develops a strategy-proof mechanism for this setting. Note that binary additive and binary submodular functions constitute subclasses of dichotomous valuations.

Building upon [Halpern and Shah, 2019], Brustle et al. [2020] proved that a subsidy of at most 1 per agent suffices for additive valuations; this result is established under a standard scaling, wherein the value of any good across all agents is at most 1. Brustle et al. [2020] also obtained an O(n2 ) upper bound on the total required subsidy for general monotone valuations. The current work achieves a factor n improvement over this upper bound for dichotomous valuations in particular.

Caragiannis and Ioannidis [2021] study the problem of finding allocations that realize envy-freeness with as little subsidy as possible. Since this problem is NP-hard, they focus on approximation algorithms and, in particular, develop a fully polynomial-time approximation scheme for instances with a constant number of agents. Narayan et al. [2021] show that one can achieve envy-freeness with transfers, while incurring a constant-factor loss in Nash social welfare.

2 In particular, we do not require the dichotomous valuations to be additive, submodular, or even subadditive.

We note that the framework of subsidies complements discrete fair division results which strive towards existential guarantees by relaxing the envy-freeness criterion. Here, a well-studied solution concept (relaxation) is envy-freeness up to one good (EF1) [Budish, 2011]: an allocation is said to be EF1 iff each agent values her bundle at least as much as any other agent's bundle, up to the removal of some good from the other agent's bundle. EF1 allocations are known to exist under monotone valuations [Lipton et al., 2004].

2 Notation and Preliminaries

We study the problem of allocating m indivisible goods among n agents, with subsidies, in a fair manner. The cardinal preference of each agent i ∈ [n], over the subsets of goods, is specified via valuation vi : 2[m] → R+. Here, vi(S) ∈ R+ denotes the valuation that agent i has for a subset of goods S ⊆ [m]. We will throughout represent a discrete fair division instance via the tuple 〈[n], [m], {vi}ni=1 〉. Our algorithms work in the standard value-oracle model. That is, for each valuation vi, we only require an oracle that-when queried with a subset S ⊆ [m]-provides the value vi(S).

This work focuses on valuations that have binary marginals, i.e., for each agent i ∈ [n], the marginal value of including any good g ∈ [m] in any subset S ⊆ [m] is either zero or one: vi(S ∪ {g}) - vi(S) ∈ {0, 1}. We will refer to such set functions vis as dichotomous valuations. Note that a dichotomous valuation vi is monotone: vi(A) ≤ vi(B) for all subsets A ⊆ B ⊆ [m]. Also, we will assume that the agents' valuations satisfy vi(∅) = 0.

An allocation A = (A1, A2, . . . , An) is an ordered collection of n pairwise disjoint subsets, A1,A2, . . . ,An ⊆ [m], wherein the subset of goods Ai is assigned to agent i ∈ [n]. We refer to each such subset Ai as a bundle. Note that an allocation can be partial in the sense that ∪ni=1Ai ̸= [m]. For disambiguation, we will use the term complete allocation to denote allocations wherein all the goods have been assigned and, otherwise, use the term partial allocation. The social (utilitarian) welfare of an allocation A = (A1, . . . , An) is the sum of the values that it generates among the agents, ∑ni=1 vi(Ai).

The quintessential notion of fairness is that of envyfreeness [Foley, 1966]. This notion is defined next for allocations of indivisible goods.

Definition 1. An allocation A = (A1, . . . ,An) is said to be envy-free (EF) iff vi(Ai) ≥ vi(Aj) for all agents i, j ∈ [n].

Since, in the context of indivisible goods, envy-free allocations are not guaranteed to exist, a realizable desideratum is to achieve envy-freeness with the use of subsidies. The objective here is to provide each agent i ∈ [n]-in addition to a bundle Ai-an appropriate subsidy pi ≥ 0 such that envy-freeness is achieved overall. We will write vector p = (p1, p2, . . . , pn) ∈ Rn+ to denote the subsidies assigned to the agents. Our overarching aim is to find a complete allocation A = (A1, . . . ,An) and a (bounded) subsidy vector p = (p1, . . . , pn) that ensure envy-freeness for each agent i, i.e., agent i's value for her bundle (Ai) plus her subsidy, pi, is at least as large as i's value for any other agent j's bundle (Aj) plus the subsidy pj. Formally, Definition 2 (Envy-Free Solution). An allocation A = (A1, . . . , An) and a subsidy vector p = (p1, . . . , pn) are said to constitute an envy-free solution, (A, p), iff vi(Ai) + pi ≥ vi(Aj) + pj for all agents i, j ∈ [n].

The term envy-freeable will be used to denote any allocation A for which there exists a subsidy vector p such that (A, p) is an envy-free solution. Also, we will throughout write M(p) to denote the set of agents that receive maximum subsidy under p = (p1, . . . , pn), i.e., M(p) := {i ∈ [n] | pi ≥ pj for all j ∈ [n]}.

2.1 Characterizing Envy-Freeable Allocations

The work of Halpern and Shah [2019] provides a useful characterization of envy-freeable allocations. 3 Using the characterization, one can determine (in polynomial time) whether or not a given allocation B is envy-freeable, i.e., whether B can be coupled with a subsidy vector q to realize an envy-free solution (B, q). Furthermore, for any envy-freeable allocation B, the characterization leads to a polynomial-time algorithm to compute a corresponding subsidy vector q.

The characterization is obtained by considering a directed graph that captures the envy among the agents. Specifically, for an allocation A = (A1, . . . , An), the envy-graph GA is a complete, weighted, directed graph wherein the vertices correspond to the agents and each directed edge (i, j) has weight wA(i, j) := vi(Aj) - vi(Ai). Note that the weight of the edge (i, j) is the envy that agent i has towards j, and the edge weights can be negative. The weight of any (directed) path P in the graph GA will be denoted by wA(P); in particular, wA(P) is the sum of the weights of the edges along the path, wA(P) = ∑(i,j)∈P wA(i, j).

To achieve envy-freeness in certain settings, we will have to reassign the bundles among the agents. In particular, for an allocation A = (A1, . . . ,An) and permutation σ ∈ Sn (over the n agents), write Aσ := (Aσ(1),Aσ(2), . . . ,Aσ(n)) to denote the allocation wherein each agent i ∈ [n] receives the bundle Aσ(i).

The theorem below states the characterization of envyfreeable allocations.

Theorem 1. [Halpern and Shah, 2019] For any allocation A = (A1, . . . , An), the following statements are equivalent:

• (i) A is envy-freeable.
• (ii) A maximizes the social welfare across all reassignments of its bundles among the agents. That is, for every permutation σ over [n], we have ∑ni=1 vi(Ai) ≥ ∑ni=1 vi(Aσ(i)).
• (iii) The envy-graph GA has no positive-weight cycles.

3 An analogous result was developed by Aragones [1995] in the context of fair rent division.

Condition (ii) of Theorem 1 implies that, starting with an arbitrary allocation B = (B1, . . . ,Bn), we can always find an envy-freeable allocation by reassigning the bundles Bis among the agents. In particular, if σ is any maximum-weight matching between the agents and the bundles, then Bσ is an envy-freeable allocation. Note that such a matching can be computed in polynomial-time.

Complementing the characterization, Theorem 2 (below) identifies an efficient algorithm to compute a subsidy vector for any given envy-freeable allocation A. Here, ℓA(i) is used to denote the maximum weight of any path (in GA) which starts at i ∈ [n]. Since the envy-graph GA (for an envyfreeable allocation A) does not contain any positive-weight cycle (condition (iii) in Theorem 1), the weight ℓA(i) is welldefined and can be computed efficiently. In particular, we can apply the Floyd-Warshall algorithm, after negating the edge weights. The theorem asserts that providing a subsidy of ℓA(i), to each agent i, suffices to achieve envy-freeness.

Theorem 2. [Halpern and Shah, 2019] For any envyfreeable allocationA, a subsidy of p∗i := ℓA(i), for all agents i ∈ [n], realizes an envy-free solution (A, p∗ ); here subsidy vector p∗ = (p∗1 , . . . , p∗n ). Furthermore, for any other vector p = (p1, . . . , pn) ∈ Rn+, such that (A, p) is envy-free, we have p∗i ≤ pi for all i ∈ [n].

For any subsidy vector p = (p1, . . . , pn) and permutation σ over [n], let pσ = (pσ(1), pσ(2), . . . , pσ(n)) denote the subsidies obtained by reassigning according to σ, i.e., under pσ, agent i receives a subsidy pσ(i).

The following lemma shows that if reassigning bundles, according to some permutation σ, maintains envy-freeability, then, in fact, reassigning the subsidies-also according to σ-preserves envy-freeness. A proof of this lemma appears in the full version of this work [Barman et al., 2022].

Lemma 3. Let (A, p) be an envy-free solution and let σ be a permutation such that allocation B := Aσ is envy-freeable. Then, (B, pσ) is an envy-free solution as well.

3 Our Results

The next theorem is the main result of the current work and it shows that in any discrete fair division instance with dichotomous valuations there exists an envy-free solution with a subsidy of at most 1 per agent.

Theorem 4. For any discrete fair division instance 〈[n], [m], {vi}ni=1 〉 with dichotomous valuations, there exists an envy-free solution (A, p) such that p ∈ {0, 1}n . Furthermore, given value oracle access to the vis, such an envy-free solution, (A, p), can be computed in polynomial time.

This theorem implies that, to achieve envy-freeness under dichotomous valuations, the total required subsidy is at most (n - 1), i.e., ∑ni=1 pi ≤ n - 1. Note that the case in which pi = 1, for all agents i, can be addressed by giving each agent a subsidy of 0.

4 Finding Envy-Free Solutions for Dichotomous Valuations

For dichotomous valuations, our algorithm ALG (Algorithm 1) finds an envy-free solution (A, p) such that the subsidy vector p ∈ {0, 1}n . In particular, with iteration count t, the algorithm inductively maintains an envy-free solution (At , pt ) wherein At = (At1 , . . .Atn ) is a (partial) envyfreeable allocation and the subsidy vector pt ∈ {0, 1}n . In every iteration t, the algorithm selects an unallocated good g ∈ [m] \ (∪ni=1Ati ), includes it in one of the current bundles, At1 , . . . ,Atn , and possibly reassigns the bundles among the agents such that the updated allocation, At+1 , is also envyfreeable with subsidies in {0, 1}.

We note that a relatively simple case occurs if-in any iteration t and for an unallocated good g-there exists an agent k ∈ [n] such that (a) the marginal value of good g for agent k is equal to 1 (i.e., vk(Atk ∪{g})-vk(Atk ) = 1) and (b) agent k's subsidy (under pt = (pt1 , . . . , ptn )) is at least as large as that of any other agent (ptk ≥ ptj for all j). In such a case, the allocation At+1 obtained by assigning the good g to the agent k is envy-freeable, since the social welfare of At+1 is one more than the social welfare of At and this is the maximum possible among all the reassignments of the bundles in At+1 (see condition (ii) in Theorem 1). Furthermore, for the allocation At+1 , the accompanying subsidies remain in {0, 1}. This essentially follows from the facts that k was one of the most subsidized agents and, when we assign the good g to agent k, only the weights of the edges incident on k (in the updated envy graph) change. In particular, the weight of the edges going out of k necessarily decrease by 1 and for each incoming edge the weight increases by at most 1. 4 Using these observations one can show that the weights of all paths remain below 1 and, hence (via Theorem 2), the subsidies remain in {0, 1}.

Even if there does not exist an agent k that directly satisfies the above-mentioned conditions (a) and (b), we can still try to first reassign the current bundles (among the agents) and then look for such an agent. Specifically, the case detailed above continues to be relevant if there exists a permutation σ such that allocation B = Atσ is envy-freeable, 5 and, under B, there exists an agent κ that satisfies conditions (a) and (b). Encapsulating this case, 6 we will say that the current allocation At is extendable with good g, iff the desired permutation σ and agent κ exist; see Definition 3.

Section 4.1 develops a subroutine, EXTEND (Algorithm 2), that efficiently identifies whether the current allocation At is extendable. If the allocation is extendable, then the subroutine returns the relevant permutation σ and the agent κ. Using this subroutine, our algorithm ALG addresses the case of extendable solutions (in Lines 4 to 6). In particular, ALG allocates good g and updates the envy-free solution (At , pt ) to (At+1 , pt+1 ), while maintaining the invariant that the subsidies are either 0 or 1.

In the complementary case, wherein the current allocation At is not extendable, ALG (in Line 8) invokes the subroutine FINDSINK (detailed in Section 4.2). A key technical insight

4 Note that under dichotomous valuations the edge weights in the envy graph are integers.

5 Here, the envy-freeability of B ensures that the accompanying subsidies are still either 0 or 1; see Lemma 3.

6 Note that with σ as the identity permutation, one can capture the setting wherein a reassignment of the bundles is not required.

Algorithm 1 ALG

Input: Instance 〈[n], [m], {vi}i∈[n]〉 with value oracle access

to dichotomous valuations vis.

Output: Allocation A and subsidy vector p.

• 1: Initialize index t = 1 along with bundles At1 = . . . = Atn = ∅ and subsidies pt1 = . . . = ptn = 0. {Here, allocation At = (∅, . . . , ∅) and subsidy vector pt = (0, . . . , 0).}
• 2: while [m] \ (∪i∈[n]Ati ) ̸= ∅ do
• 3: Select any unallocated good g ∈ [m] \ (∪i∈[n]Ati ).
• 4: if (At , pt ) is extendable with good g then
• 5: (B1, . . . ,Bn) := Atσ .
• Set (σ, κ) := EXTEND(At , pt , g) and set allocation {(B1, . . . ,Bn) is obtained by reassigning bundles in At , according to permutation σ.}
• 6: Set allocation At+1 := (B1, . . . ,Bκ ∪ {g}, . . . , Bn).

{Good g is included in agent κ's bundle Bκ.}

• 7: else
• 8: Let agent s := FINDSINK(At , pt , g).
• 9: Set allocationAt+1 := (At1 , . . . ,Ats ∪{g}, . . . ,Atn ). {Good g is included in agent s's bundle Ats .}
• 10: end if
• 11: Compute subsidy vector pt+1 for the allocation At+1 . {We will prove that, in all cases, At+1 is envy-freeable and invoke Theorem 2 to compute the subsidies.}
• 12: Update t ← t +1.
• 13: end while
• 14: return allocation At = (At1 , . . . ,Atn ) and subsidy vector pt = (pt1 , . . . , ptn ).

here is that, under dichotomous valuations and for an allocation At that is not extendable with a good g, there necessarily exists an agent s such that assigning g to s maintains the subsidies in {0, 1}. The subroutine FINDSINK directly finds such an agent by trying to assign g to different agents iteratively and checking whether subsidies remain in {0, 1}. It is relevant to note that, while the subroutine is simple in design, its analysis requires intricate existential arguments. In particular, Section 4.2 establishes that FINDSINK finds such an agent s ∈ [n] in polynomial time and, hence, provides a constructive proof of existence of the desired agent s.

Therefore, in every possible case, our algorithm ALG assigns a good and updates the allocation, all the while maintaining the invariant that the allocation in hand is envyfreeable and requires subsidies that are either 0 or 1.

For the analysis of the algorithm, we will use the following two propositions, which hold for dichotomous valuations. The proofs of the propositions appear in the full version of this paper [Barman et al., 2022].

Proposition 5. Let Y = (Y1, . . . , Yn) be an envy-freeable (partial) allocation. Also, assume that, for an agent x ∈ [n] and an unallocated good g, we have vx(Yx∪{g})-vx(Yx) = 1. Then, the allocation (Y1, . . . , Yx ∪ {g}, . . . , Yn) is envyfreeable as well.

Proposition 6. For any envy-freeable allocation Y = (Y1, . . . , Yn), any agent x, and any (unallocated) good g, let allocation Z := (Y1, . . . , Yx ∪ {g}, . . . , Yn). Then, in the envy graph GZ, the weights of all the edges-except the ones incident on x-are the same as in GY, i.e., for all edges (i, j), with i, j ∈ [n] \ {x}, we have wZ(i, j) = wY(i, j). Furthermore, the weights of edges (x, j) going out of x satisfy wZ(x, j) ≤ wY(x, j), and the weights of edges (i, x) coming into x satisfy wZ (i, x) ≤ wY (i, x) + 1.

For allocation Z := (Y1, . . . , Yx ∪ {g}, . . . , Yn), Proposition 6 implies that the weight of any path 7 P in the envy graph GZ is at most one more than the weight of P in the envy graph GY , i.e., wZ (P ) ≤ wY (P ) + 1.

4.1 Extendable Solutions

As mentioned previously, a relevant case for our algorithm occurs when, for an unallocated good g, there exists an agent κ such that (a) the marginal value of good g for agent κ is equal to one and (b) agent κ is one of the most subsidized agents. The notion of extendability (defined below) generalizes this case. Recall that M(p)-for any subsidy vector p = (p1, . . . , pn)-denotes the set of the most subsidized agents, M(p) := {i ∈ [n] | pi ≥ pj for all j ∈ [n]}.

Definition 3 (Extendable Solutions). An envy-free solution (A, p) is said to be extendable with good g ∈ [m]\(∪i∈[n]Ai ) iff there exists a permutation σ (over [n]) such that:

• (i) Allocation B := Aσ and subsidy vector q := pσ constitute an envy-free solution (B, q), and
• (ii) There exists an agent κ ∈ M(q) with the property that vκ(Bκ ∪ {g}) - vκ(Bκ) = 1.

The following lemma shows that, for an extendable solution (A, p), we can allocate the good g and still maintain peragent subsidy to be either 0 or 1.

Lemma 7. In a fair division instance with dichotomous valuations, let (A, p) be an envy-free solution extendable with good g and permutation σ. Also, assume that the subsidies p ∈ {0, 1}n . Then, the allocation (B1, . . . ,Bκ ∪ {g}, . . . ,Bn) is also envy-freeable with a subsidy of either 0 or 1 for each agent. Here, allocation (B1, . . . ,Bn) := Aσ and κ is the agent identified in the extendability criteria (Definition 3).

The proof of Lemma 7 appears in the full version of this work [Barman et al., 2022].

The following lemma shows that the subroutine EXTEND efficiently identifies whether a given solution (A, p) is extendable, i.e., the subroutine efficiently tests whether Definition 3 holds, or not. See the full version of this paper for the proof of the lemma [Barman et al., 2022].

Lemma 8. In a fair division instance with dichotomous valuations, let (A, p) be an envy-free solution.

• If (A, p) is extendable with good g ∈ [m] \ (∪ni=1Ai), then the EXTEND subroutine returns a permutation σ and an agent κ that satisfy the extendability criteria (Definition 3).

7 Note that, by definition, a path joins distinct vertices.

Algorithm 2 EXTEND

Input: Instance 〈[n], [m], {vi}i∈[n]〉, an envy-free solution (A, p), and a good g ∈ [m].

Output: A permutation and an agent that extend the input (A, p) with good g, or return that it is not extendable.

• 1: for each k ∈ [n] and ℓ ∈ M(p) with the property that vk(Aℓ ∪ {g}) - vk(Aℓ) = 1 do
• 2: Consider a complete bipartite graph H between sets [n] \ {k} and [n] \ {ℓ}. For each edge (i, j) in H set the weight to be vi(Aj).
• 3: Compute a maximum-weight matching ρ in H.
• 4: Set ρ(k) = ℓ. {ρ is a permutation over [n].}
• 5: If ∑ni=1 vi(Aρ(i)) ≥ ∑ni=1 vi(Ai), then return (ρ, k).
• 6: end for
• 7: return "(A, p) is not extendable with good g."
• Otherwise, if (A, p) is not extendable with good g, then subroutine EXTEND correctly reports as such.

4.2 Non-Extendable Solutions

This section addresses the case wherein the maintained allocation is not extendable. The subroutine FINDSINK takes as input an envy-free solution (A, p)-with subsidy vector p ∈ {0, 1}n-and a good g. The subroutine tentatively assigns the good to one agent at a time and checks if the subsidies remain in {0, 1}. We will show that if the input (A, p) is not extendable, then FINDSINK necessarily succeeds in finding such an agent (Lemmas 10 and 11).

Algorithm 3 FINDSINK

Input: Instance 〈[n], [m], {vi}i∈[n]〉, an envy-free solution (A, p), and a good g ∈ [m].

Output: An agent s.

• 1: Select an arbitrary agent s ∈ M(p) and set allocation X = (A1, A2, . . . , As ∪ {g}, . . . , An). {We will show that-for non-extendable inputsallocation X is envy-freeable.}
• 2: Compute the subsidy vector (ϕ1, . . . , ϕn) for allocation X . {See Theorem 2.}
• 3: while there exists an agent j with subsidy ϕj ≥ 2 do
• 4: Update s ← j and update X = (A1,A2, . . . ,As ∪ {g}, . . . , An).
• 5: Compute the subsidy vector (ϕ1, . . . , ϕn) for allocation X .
• 6: end while
• 7: return agent s.

The lemma below shows that all the agents s considered by FINDSINK are among the most subsidized ones, under p, and the considered allocations X := (A1, . . . , As ∪{g}, . . . , An) are envy-freeable. Note that, throughout the execution of the subroutine, (A, p) remains unchanged.

Lemma 9. In a fair division instance with dichotomous valuations, let (A, p) be an envy-free solution with subsidies p ∈ {0, 1}n . If input (A, p) is not extendable with the given good g, then each agent s considered in FINDSINK (Line 4) belongs to the set M(p) and each considered allocation X := (A1, . . . , As ∪ {g}, . . . , An) is envy-freeable.

The proof of the Lemma 9 appears in the full version [Barman et al., 2022].

The next lemma is a key technical result for FINDSINK. It shows that the subroutine terminates in polynomial time, when the input (A, p) is not extendable. The proof of this lemma entails intricate existential arguments; we defer the proof to the full version of this paper [Barman et al., 2022].

Lemma 10. In a fair division instance with dichotomous valuations, let (A, p) be an envy-free solution with subsidies p ∈ {0, 1}n . Also, assume that (A, p) is not extendable with good g. Then, given (A, p) and g as input, the subroutine FINDSINK terminates in polynomial time.

The subroutine FINDSINK is designed to terminate only when it has identified an agent s to whom we can assign the good g and maintain the subsidies to be in {0, 1}. The next lemma formalizes this observation.

Lemma 11. In a fair division instance with dichotomous valuations, let (A, p) be an envy-free solution with p ∈ {0, 1}n . Also, assume that (A, p) is not extendable with good g and let s ∈ [n] be the agent returned by FINDSINK (given (A, p) and g as input). Then, the allocation (A1, . . . , As ∪{g}, . . . , An) is envy-freeable with a subsidy of either 0 or 1 for each agent.

Proof. Since s is one of the agents selected in FINDSINK, Lemma 9 implies that the allocation (A1, . . . ,As ∪ {g}, . . . ,An) is envy-freeable. Furthermore, the termination condition of the while-loop in FINDSINK (Line 3) ensures that, for the allocation (A1, . . . ,As ∪ {g}, . . . ,An), the required subsidies are less than 2. Since the subsidies are nonnegative integers (for dichotomous valuations), they are either 0 or 1. This completes the proof.

4.3 Proof of Theorem 4

In this section, we will prove Theorem 4 by establishing that the solution returned by ALG (Algorithm 1) is envy-free and requires, for each agent, a subsidy of either 0 or 1.

Theorem 4. For any discrete fair division instance 〈[n], [m], {vi}ni=1 〉 with dichotomous valuations, there exists an envy-free solution (A, p) such that p ∈ {0, 1}n . Furthermore, given value oracle access to the vis, such an envy-free solution, (A, p), can be computed in polynomial time.

Proof. We will show that, with iteration counter t ≥ 1, the algorithm inductively maintains an envy-free solution (At , pt ) wherein At = (At1 , . . .Atn ) is a (partial) envy-freeable allocation and the subsidy vector pt ∈ {0, 1}n . The initialization in Line 1 of ALG ensures that this property holds for t = 1, since the empty allocation A1 is envy-freeable with zero subsidies.

Next, consider any iteration t ≥ 1 of the while-loop (Line 2) in ALG and let g be the good selected in Line 3. For the current solution (At , pt ), there are two complementary and exhaustive cases:

Case I: (At , pt ) is extendable with good g. Here, Lemma 8 implies that the permutation σ and the agent κ returned by the EXTEND subroutine satisfy the extendability criteria. Hence, by Lemma 7, we get that assigning g to agent κ's bundle-as in Lines 5 and 6-leads to an envy-free solution (At+1 , pt+1 ) with pt+1 ∈ {0, 1}n .

Case II: (At , pt ) is not extendable with good g. This case will be correctly identified in ALG (Lemma 8) and the algorithm will then invoke the FINDSINK subroutine (Line 8). The subroutine in turn will find (in polynomial time) an agent s ∈ [n] (Lemma 10) such that assigning the good g to agent s-as in Line 9-provides an envy-free solution (At+1 , pt+1 ) with pt+1 ∈ {0, 1}n (Lemma 11).

Therefore, in both cases, the updated solution (At+1 , pt+1 ) is envy-free with pt+1 ∈ {0, 1}n . This, overall, shows that the returned solution (A, p) satisfies the desired properties.

Furthermore, note that the subroutines EXTEND and FINDSINK run in polynomial time, and only require value queries. This establishes the efficiency of ALG and completes the proof.

5 Conclusion and FutureWork

We prove that, under dichotomous valuations, envy-freeness can always be achieved with a subsidy of at most 1 per agent. This bound is tight and our proof is constructive. Specifically, our algorithm assigns the goods iteratively while maintaining envy-freeness, with bounded subsidies.

Even though, at a high level, our algorithmmight seem like a refinement of the method used for finding EF1 allocations [Lipton et al., 2004], the two approaches are distinct. In particular, the current algorithm resolves positive-weight cycles (in the envy graph) and, by contrast, finding EF1 allocations (under monotone valuations) entails resolution of top trading cycles [Lipton et al., 2004]. We can, in fact, construct an instance wherein a specific execution of the developed algorithm returns an allocation that is not EF1; see the full version for details [Barman et al., 2022]. Hence, extending the current work to additionally obtain the EF1 guarantee is a relevant direction of future work. Another interesting direction would be to obtain tight subsidy bounds for general monotone valuations.

Acknowledgements

Siddharth Barman gratefully acknowledges the support of a Microsoft Research Lab (India) grant and an SERB Core research grant (CRG/2021/006165).