Eliminating Envy in Multigraphs Through Subsidy

1 Introduction

Fair allocation of indivisible resources is an active area of research in computer science, economics, and operations research. One of the most widely accepted fairness notions is envy-freeness (EF), which requires that no agent strictly prefers another agent's allocation over their own [Foley, 1967]. Unlike the case of divisible items, where EF allocations always exist [Brams and Taylor, 1995], an EF allocation is not guaranteed when the items are indivisible. Consider a simple example: allocating a single item between two agents, each valuing the item at $1. The agent who receives the item would inevitably be envied by the other. To maintain fairness, a compensation of $1 can be given to the agent who receives nothing. More generally, this motivates the compelling and practical research problem of understanding how much compensation (i.e., subsidy) is required to ensure envy-freeness among the agents. This problem has been widely studied in the literature. Halpern and Shah [2019] first proved that when agents have additive valuations and the marginal value of each good is at most 1, a total subsidy of m(n-1) is sufficient to find an EF allocation. This result was later improved to n - 1 by Brustle et al. [2020]. This bound is tight in the sense that there are instances that require at least n-1 subsidy in order to achieve EF.

In this paper, we study a graph orientation model first introduced by Christodoulou et al. [2023], which has since attracted considerable attention. Here, agents are the vertices in a multigraph and items are the edges so that each agent is only interested in the items incident to her. An allocation is said to be an orientation if every item is allocated to one of the two incident agents. Christodoulou et al. [2023] considered a relaxed definition of envy-freeness, envy-free up to any item (EFX), and proved that deciding the existence of an EFX orientation is NP-hard. An allocation is EFX if no agent envies another agent's bundle after (hypothetically) removing any item in it. There is a significant amount of follow-up work on the graph orientation problem, including characterizing the graph structures under which an EFX orientation exists [Zeng and Mehta, 2024; Blazej et al., 2025], designing approximation algorithms for EFX [Amanatidis et al., 2024; Kaviani et al., 2025], and exploring other (approximate) fairness notions [Deligkas et al., 2025; Christodoulou and Mastrakoulis, 2025]. However, it remains unclear howmuch subsidy is sufficient to ensure EF in the graph orientation model. In this work, we address the problem of bounding the worstcase subsidy required to ensure envy-freeness in the graph orientation model.

1.1 Our Problem

Let G V,E) be a multigraph, where V = {1, . . . , n} and E = {e1, . . . , em} are respectively the sets of vertices and edges with |V | = n and |E| = m. There may be multiple edges between any two agents; however, without loss of generality, we assume the absence of self-loops or singletons, as self-loops and singletons can only serve to reduce envy among agents. Let Ei,j denote the set of edges between i, j ∈ V , where Ei,j = Ej,i and Ei,j = ∅ if i, j are not adjacent in G. Let Ei = ⋃j∈V Ei,j be the set of edges incident to i ∈ V .

In the fair graph orientation model, each vertex i ∈ V corresponds to an agent, and each edge e ∈ E corresponds to a good (or item). We also denote the sets of agents and goods by N = V and M = E to be consistent with the literature on resource allocation, and thus we use agents and vertices, goods and edges, interchangeably. Each agent i has an additive valuation function vi(·) : 2M → R≥0 such that for any S ⊆ M, vi(S) = ∑e∈S vi({e}). For simplicity, denote vi({e}) by vi(e). In the orientation model, each agent i ∈ V is only interested in her incident goods Ei, which are also called i's relevant goods, and each good can only be allocated to one of the two incident agents. That is vi(e) = 0 for all e /∈ Ei, and a feasible allocation, called orientation, is an npartition A = (A1, . . . , An) of M such that Ai ⊆ Ei for all i. We normalize each valuation such that maxe∈M vi(e) = 1 for all i ∈ N.

With no subsidies, an allocation A is envy-free (EF) if no agent would prefer the bundles of others to her own bundle, i.e., vi(Ai) ≥ vi(Aj) for all i, j ∈ N. As mentioned, when items are indivisible, an EF allocation barely exists. To address this, we provide each agent i with an objective payment (i.e., money) pi ≥ 0, called subsidy, alongside their allocated goods. Let p = (p1, . . . , pn) be the subsidy vector, and denote by (A, p) the final outcome. Accordingly, an allocation with subsidy (A, p) is envy-free if for any i, j ∈ N, vi(Ai) + pi ≥ vi(Aj ) + pj .

To illustrate, let's consider the following example.

Example 1. Assume n is even, and consider a simple graph with vertices {1, . . . , n}. For any i ∈ {1, . . . , n2 }, there exists an edge between vertices 2i -1 and 2i, and hence, in total n2 edges. Each edge is valued at 1 by both of its incident agents. We can allocate each edge to one of its incident agents and provide the other agent with a subsidy of 1. This results in an EF orientation with a total subsidy of n2 .

Next, assume n is odd, the simple graph contains a component consisting of a path of length 2, and n-3 2 components, each of which is a path with length 1. Each agent has a value of 1 for any of her incident edges. To obtain an EF orientation, we similarly allocate every edge to one incident agent such that no agent receives more than one edge, and provide each agent who has not received edges a subsidy of 1. The total subsidy is n-1 2 .

It is worth noting that, in Example 1, a total subsidy of less than ⌊ n2 ⌋ is insufficient to guarantee EF for any orientation. In other words, in the worst case, a total subsidy of ⌊ n2 ⌋ is necessary. This naturally leads to the question of whether this bound is also sufficient:

Is a total subsidy of ⌊ n2 ⌋ sufficient to ensure EF for all multigraphs?

The main contribution of the current paper is to answer the above question in the affirmative. Specifically, we present a polynomial-time algorithm that always computes an EF orientation with a total subsidy of at most ⌊ n2 ⌋. An overview of our algorithm is provided in Section 2, and a formal proof of our result is given in Section 3. We note that the normalization assumption maxe∈M vi(e) = 1 for all i ∈ N is essential for our result. If this assumption is relaxed to maxe∈M vi(e) ≤ 1, as in [Halpern and Shah, 2019; Brustle et al., 2020], the optimal subsidy bound remains n-1.

For example, consider a graph with a single edge valued at 1 by both of its incident agents, while all other agents correspond to singleton vertices. In this case, a subsidy of n - 1 is required: one incident agent receives the edge, and each of the remaining agents receives a unit subsidy.

1.2 RelatedWork

Since EF allocations may not exist, the majority of the literature is focused on its relaxations when subsidy is not allowed. Two widely adopted relaxations are envy-free up to one item (EF1) [Budish, 2011] and envy-free up to any item (EFX) [Caragiannis et al., 2019], which requires no agent strictly prefers another agent's bundle excluding one or any item. EF1 allocations always exist [Lipton et al., 2004] but the existence of EFX allocations is still unknown except for several special cases, e.g., [Plaut and Roughgarden, 2020; Chaudhury et al., 2024]. We refer to the recent surveys [Amanatidis et al., 2023; Liu et al., 2024] for a comprehensive overview of fair allocation. Below we restrict our focus on the graph orientation and fair division with subsidy.

Graph Orientation. Christodoulou et al. [2023] first introduced the graph model where vertices are agents and edges are items such that agents are only interested in their incident items. When agents have additive valuations, they proved that an EFX allocations when the items can be arbitrarily allocated always exists but an EFX orientation where items must be allocated to their incident agents may not exist. Zeng and Mehta [2024] identified a family of graphs in which EFX orientations exist. Kaviani et al. [2024] and Deligkas et al. [2025] repectively generalized the graph orientation problem. In the model of Kaviani et al. [2024], agents have (p, q)- bounded valuations, where each item has a non-zero marginal value for at most p agents, and any two agents share at most q common interested items. They proved that for (∞, 1)- bounded valuations, EF2X orientations always exist. In the model of Deligkas et al. [2025], every agent has a predetermined set of items and only receives items from this set. They proved that for monotone valuations, an EF1 allocation always exists. Zhou et al. [2024] extended the goods model in [Christodoulou et al., 2023] to mixed setting when the marginal value of each item can be positive or negative.

Fair Division with Subsidy. Caragiannis and Ioannidis [2021] first studied the computational complexity of using the minimum amount of subsidies to ensure envy-freeness. Halpern and Shah [2019] bounded the worst-case amount of subsidies for additive valuations, and Brustle et al. [2020] later improved the result in [Halpern and Shah, 2019]. There is a line of recent works focusing on the variants and generalizations of the standard setting. For example, Goko et al. [2024] considered the strategic behaviors when subsidy is used, and Aziz et al. [2024] considered weighted envyfreeness when the agents have different entitlements. Brustle et al. [2020] proved that for general monotone valuations an EF allocation always exists with a subsidy of 2(n - 1)2 , which was improved to n(n - 1)/2 in [Kawase et al., 2024]. It is worth noting that the tight bound for monotone valuations is still unknown [Liu et al., 2024], where the lower bound is n - 1. However, there have been improvements for certain special cases. Barman et al. [2022] and la Tour and Fujii [2025], respectively, improved the upper bounds to O(n) and O(n√n logn) for monotone valuations with binary marginal values and when the number of agents is a prime power. Choo et al. [2024] and Dai et al. [2024] respectively studied the envy-free house allocation with subsidies and its weighted variant. Wu et al. [2023; 2025b; 2025a] extended the subsidy model to the fair allocation of indivisible chores.

2 Technical Overview

In this section, we present the definitions and techniques used to prove our main result. We discuss the challenges involved and outline the key ideas behind our algorithm.

2.1 Envy-freeable Orientations

Before describing our algorithm, it is important to note, as observed by Halpern and Shah [2019], that not every orientation can be made envy-free through the use of subsidies. For example, consider an instance with 2 agents and 2 edges between them such that v1(e1) = v2(e2) = 1 and v1(e2) = v2(e1) = 0. If we allocate {e2} to agent 1 and {e1} to agent 2, no matter how much we compensate each agent, the envy cannot be eliminated, since the subsidies are objective. Thus, Halpern and Shah [2019] introduced the notion of envy-freeable allocations, and characterized all envy-freeable allocations via envy graphs. Formally, an allocation A is said to be envy-freeable (EFable) if there exists a subsidy vector p = (p1, . . . , pn) such that (A, p) is EF. The envy graph DA for allocation A is a complete weighted directed graph with vertices N. For any pair of agents i, j ∈ N, the weight of arc i → j in DA is vi(Aj) - vi(Ai).

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

1. A is envy-freeable;
2. A maximizes the total value of agents among all reassignments of its bundles to agents, i.e., for every permutation π : N → N, ∑i∈N vi(Ai) ≥ ∑i∈N vi(Aπ(i));
3. DA contains no directed cycle with positive weight.

Given orientation A = (A1, . . . ,An), for any i, j ∈ N, denote Aji = Ai ∩Ei,j for ease of notation. The orientation is locally envy-freeable with respect to agents i, j if the partial allocation of Ei,j is envy-freeable, i.e., vi(Aji ) + vj(Aij ) ≥ vi(Aij ) + vj(Aji ). The orientation A is locally envy-freeable if for every pair of agents i, j, the partial allocation of Ei,j is envy-freeable.

2.2 Our Algorithm

Brustle et al. [2020] proposed the "Bounded-Subsidy Algorithm" that computes an EF allocation with subsidy at most n - 1 for the classical additive allocation setting, where each good may be assigned to any agent rather than being constrained by a graph orientation. However, this algorithm cannot achieve the bound of ⌊ n2 ⌋ in the context of orientation, even for simple graphs. Hence, one needs to derive a new method to achieve this bound.

Since every edge is only relevant to two agents, say i and j, another intuition is to find a proper way to allocate the edges between the two agents and compensate the one at a disadvantage. Two useful and commonly used rules are the RoundRobin algorithm shown in Algorithm 1 and the social utility maximizing algorithm shown in Algorithm 2. Although the other agents are not directly affected by the edges between i and j, they may feel envious of any subsidy provided. Furthermore, this independent procedure does not provide control over the total amount of subsidy given. Before moving on to our algorithm, it is worth noting that in the partial allocation returned by RoundRobin(i, j,Ei,j), the envy of one agent towards the other one is upper bounded by 1, the largest single-item value, although this allocation may not be locally envy-freeable. However, by Theorem 1, the partial allocation returned by MaxUtility(i, j, Ei,j) is always locally envyfreeable.

Algorithm 1 RoundRobin(i, j, S)

Input: Agents i, j and bundle S.

Output: A 2-partition (Bi, Bj) of S.

• 1: t ← i. {Round Robin starts with agent i}

• 2: while S ̸= ∅ do
• 3: e∗ ← argmaxe∈S vt(e), breaking ties arbitrarily when no explicit rule is specified;
• 4: Bt ←Bt ∪{e∗ }, S ←S \{e∗ }, and t ← {i, j}\{t};
• 5: end while

Algorithm 2 MaxUtility(i, j, S)

Input: Agents i, j and bundle S.

Output: A 2-partition (Bi, Bj) of S.

• 1: for e ∈ S do
• 2: t ← argmaxt∈{i,j} vt(e). If there is a tie, set t ← i;
• 3: Bt ←Bt ∪ {e};
• 4: end for

We now introduce the high-level ideas of our algorithm. Given an orientation instance G = (V,E) and agents' valuations vi(·)'s, our algorithm utilizes an auxiliary directed graph G′ = (V, E′ ) over the agents, called the reserve graph. The vertex set of G′ is identical to that of G. Each agent i selects, or reserves, one incident edge only for the purpose of constructing the auxiliary graph G′ : choose an edge e ∈ Ei such that vi(e) = 1; if there are multiple, we arbitrarily choose one. This selection is not an allocation, and the selected edge may or may not eventually be assigned to agent i. Suppose e ∈ Ei,j, then we create a directed edge j → i in E′ . The existence of such an edge follows from the normalization maxe∈Ei vi(e) = 1. If two agents i and j select edges in Ei,j, possibly the same edge, then both arcs i → j and j → i are created in E′ . Thus, the in-degree of each vertex is 1 in G′ , and the out-degree can be any number between 0 and n - 1. The intuition behind the reserve graph is that if agent i, who has neighbors j and k in G, eventually receives the edge of value 1 she selected between i and j, then i does not envy k provided that the edges Ei,k are allocated by RoundRobin(k, i, Ei,k). Recall that under RoundRobin(k, i,Ei,k), i's envy towards k is at most 1, which can be offset by the value of the reserved edge.

Denote by C = {C1, . . . , Ck} the set of weakly connected components in G′ , where each component is a maximal connected subgraph of G′ when edge directions are ignored. As each vertex has in-degree 1, each component is either a directed cycle or a set of trees rooted at vertices in a cycle. Our algorithm proceeds in two phases:

• In Phase 1, allocate edges between adjacent agents in G′ ;
• In Phase 2, allocate edges between non-adjacent agents in G′ .

Regarding Phase 1, based on the earlier intuition, if one component C does not contain a 2-cycle (a cycle with length 2), we can run RoundRobin(j, i,Ei,j) for all pairs of agents such that i → j in C. This results in a partial allocation that is EF and does not require any subsidy. However, when there is a 2-cycle f → g and g → f in C, the problem becomes tricky, as there are no additional reserved edges available to offset the mutual envy between f and g. In such cases, it is necessary to provide a subsidy to one of the agents, say f. While it is not hard to ensure that f's envy towards g remains within 1, the real challenge lies in managing the envy between f and her other neighbors, as well as the envy that propagates to their respective neighbors.

To resolve this issue, we introduce a diffusion subroutine as shown in Algorithm 5, which essentially distributes the subsidy of f to her descendants. Accordingly, we prove an important property that for each component C, the total required subsidy is upper bounded by the envy of f towards g (see Lemma 7), which is upper bounded by 1. In summary, the total subsidy is upper bounded by k, where k ≤ ⌊ n2 ⌋ is the number of components in G′ . This is the most technically complicated part of the algorithm. Note that this analysis matches Example 1, where the edges form ⌊ n2 ⌋ paths.

In Phase 2, we allocate the edges between non-adjacent agents in G′ . To address any resulting envy, we adjust the subsidies provided in Phase 1, potentially reducing the subsidy for certain agents as needed.

3 Main Result

In this section, we formally describe the algorithm and prove the following main result.

Theorem 2. For any multigraph with n agents, an EF orientation with a total subsidy of at most ⌊ n2 ⌋ can be computed in polynomial time.

3.1 The Algorithm

The main algorithm is shown in Algorithm 3, with two subroutines described in Algorithms 4 and 5. The algorithm first builds reserve graph G′ , and let C = {C1, . . . , Ck} be the k weakly connected components of G′ . For simplicity, we use (x)+ to denote max(x, 0).

Phase 1 (Lines 4-21). In this phase, we allocate items between agents adjacent in G′ . For a component C of G′ , if

Algorithm 3 Main Algorithm for Multigraph Orientations

Input: An instance G = (N, E) and valuation {vi}.

Output: An orientation A = (A1, . . . ,An) and payment p = (p1, . . . , pn).

• 1: For each i ∈ N, initialize Ai ← ∅, wi, ti, pi ← 0.
• 2: Create a reserve graph G′ as described in Section 2.2. % The in-degree of each vertex is 1 in G′ .
• 3: Let C = {C1, . . . ,Ck} be the k weakly connected components of G′ .
• % Phases 1: allocate items between adjacent agents in G′
• 4: for each C ∈ C do
• 5: if C has a directed cycle of length at least 3 then
• 6: for each arc i → j in C do
• 7: RoundRobin(j, i,Ei,j) = (Bj,Bi) and respectively allocate Bj and Bi to agents j and i.
• 8: end for
• 9: else

10:

Suppose agents f, g are the (only) two agents such that arcs f → g and g → f exist in C, and then execute RoundRobin(g, f, Ef,g). If the resulting partial allocation is not locally EFable, swap their partial bundles restricted to Ef,g.

if both f and g are envy-free when restricted to the

• 11: allocation of Ef,g then
• 12: for i = f, g do 13:

Start from i and form an out-tree (excluding {f, g} \ {i}) with root i. Recursively execute Subroutine1 to allocate items between each node and its children, proceeding level by level down the tree until reaching the leaves.

• 14: end for
• 15: else
• 16: Suppose that agent g does not envy f when restricted to the allocation of Ef,g;
• 17: Start from f and form an out-tree (excluding g) with root f. Recursively use Subroutine2 to allocate items between each node and its children, proceeding level by level down the tree until

reaching the leaves.

• 18: Start from g and form an out-tree (excluding g) with root g. Recursively use Subroutine1 to allocate items between each node and its children, proceeding level by level down the tree until

reaching the leaves.

• 19: end if
• 20: end if
• 21: end for
• % Phases 2: allocate items between non-adjacent agents
• 22: For each i ∈ N, pi ← ti.
• 23: for each set of edges Ei,j not allocated do
• 24: Execute RoundRobin(j, i,Ei,j). If the resulting partial allocation is not locally EFable when restricted to Ei,j , swap their partial bundles restricted to Ei,j .
• 25: Let j be the agent such that vj(Aij ) ≥ vj(Aji )
• 26: if vi(Aij ) +pj > vi(Ai) + pi then
• 27: pj ← (vi(Ai) + pi - vi(Aij ))+.
• 28: end if
• 29: end for

the directed cycle has length at least 3, use RoundRobin (see Algorithm 1) to allocate items between each pair of adjacent agents i, j in C. In particular, if i → j exists, let j pick first in RoundRobin, and if j → i exists, let i pick first.

For the other case where C has a directed cycle with length 2 or a directed 2-cycle, suppose that both arcs f → g and g → f exist. First, allocate Ef,g through RoundRobin. If the resulting allocation is not locally EFable with respect to f, g, then swap the bundles (Line 10) to ensure local EFability. Next, form out-trees of f and g (see Figure 1 for an illustration) and proceed with the allocation of each out-tree from the corresponding root to depth-1 vertices first. Here, the depth of a vertex is measured from the root of the corresponding out-tree: the root has depth 0, and the depth-1 vertices are exactly the children/out-neighbors of the root in that out-tree.

Suppose that the algorithm visits f, of whom the set of out-neighbors is Ch(f) (excluding g) in the out-tree. For each j ∈ Ch(f), items in Ef,j are allocated based on either Subroutine1 or Subroutine2, depending on the allocations of Ef,g (Lines 11-18). The idea of Subroutine1 is to allocate items in a round robin manner, while that of Subroutine2 is relatively more complicated and will be explained later. These two subroutines are formally described in Algorithms 4 and 5. After allocating items between f and its depth-1 vertices, i.e., the children/out-neighbors of f in the out-tree, the algorithm visits each depth-1 vertex in the out-tree of f, and allocates items between these vertices and their adjacent depth-2 vertices, following the same rule used for allocating items incident to f. Repeat the process until the leaves (vertices with out-degree 0) are reached. This allocation rule also applies to the vertices in the out-tree of g. At the completion of this phase, items between agents adjacent in G′ have been allocated.

Phase 2 (Lines 21-29). Allocate items between agents not adjacent in G′ . For each pair of i, j that are adjacent in G but not in G′ , items Ei,j are currently unallocated. Allocate Ei,j through subroutine RoundRobin. If the resulting partial allocation is not locally EFable with respect to i, j, then swap their bundles restricted to Ei,j. Finally, Lines 26 and 27 adjust the payment to ensure that no envy is created between i, j.

Next, we introduce the Subroutine1 and Subroutine2, which allocate items between agents within the same component of reserve graph G′ .

Subroutine1. It takes an agent i as an input and allocate items between i and her out-neighbors in G′ . In particular, for each out-neighbor j, allocate items in Ei,j through RoundRobin and let j pick first. This subroutine is formally introduced in Algorithm 4.

Algorithm 4 Subroutine1(i)

Input: An agent i.

• 1: Ch(i) ← the set of i's out-neighbors in G′ , excluding i's in-neighbor if applicable.
• 2: for each j ∈ Ch(i) do
• 3: Let RoundRobin(j, i,Ei,j) = (Bj,Bi) and allocate respectively Bj and Bi to agents j and i;
• 4: end for

Subroutine2. It also takes an agent i as an input and allocate items between i and her out-neighbors in G′ , with a rule different from Subroutine1. Let Ch(i) be the set of outneighbors of i in G′ and s be the in-neighbor of i. According to the main algorithm, when Subroutine2 visits i, items in Ei,s have already been allocated.

When visiting i, the subroutine first updates wi based on the allocation Ei,s and ts (Line 4). Note that ts was determined when Subroutine2 visits s. The intuition behind wi is that if agent i receives subsidy wi and agent s receives subsidy ts, then agent i does not envy agent s when restricted to Ei,s. Then for each j ∈ Ch(i), compute the pre-assignments of Ei,j through RoundRobin (Lines 5-7). In Line 8, by the pre-assignments, we find the agent k, and define R ⊆ Ch(i) based on the sum of agent k's value in the pre-assignments and tk (Line 9). For agent j ∈ R, we compute another preassignment of Ei,j through MaxUtility.

Next, classify agents in R into Q′1 ,Q1,Q2,Q3 based on wi and the envy of j towards i in the pre-assignment determined by MaxUtility. Then allocate items between i and these agents (Lines 13-25). The items between i and agents in Ch(i) \R are allocated in Lines 30-34. Finally, we update ti in Line 35. Note that in later rounds, ti will be used to update wj for every out-neighbour j of i. As we will see, both wi and ti serve as the upper bounds of the final payment for agent i, and moreover, ti ≤ wi.

Figure 2 illustrates the classification of Ch(i), and the allocation algorithms used between i and agents in each group. Note that we process Q4 differently from other groups using RoundRobin, where we additionally swap the bundles between i and the agent in Q4 returned by RoundRobin.

Remark that for each i, wi (Line 4 of Subroutine2) is updated before allocating the items between i and i's outneighbors while ti is updated after all items between i and i's out-neighbors are allocated. Both wi and ti will be updated (at most) once during the process.

3.2 Proof of Theorem 2

In this section, we show that Algorithm 3 computes an envyfree orientation and payment (A, p) with ∑i∈N pi ≤ ⌊ n2 ⌋.

Algorithm 5 Subroutine2(i)

Input: An agent i.

• 1: Initialize R,Q1,Q′1 ,Q2,Q3,Q4,Q5 ← ∅ and k ← 0.
• 2: s ← the in-neighbor of i in G′ .
• 3: Ch(i) ← the set of i's out-neighbor in G′ , excluding s (if applicable).
• 4: Define wi := (ts + vi(Ais ) - vi(Asi ))+.
• 5: for every j ∈ Ch(i) do
• 6: Let RoundRobin(j, i,Ei,j) = (T i j , T j i ) where T j i and T i j respectively are the bundles for agent i and j. When the underlying agent has value 1 for multiple items, the agent always selects the item resulting in the edge in G′ .

7: end for

• 8: T i s ← Ais and k ← arg maxj∈Ch(i)∪{s}(vi(T i j ) + tj ) % Here tj = 0 for all j ∈ Ch(i).
• 9: for j ∈ Ch(i) with vi(Ei,j) < vi(T ik ) + tk do
• 10: Let MaxUtility(j, i,Ei,j) = (Si j , Sj i ) where Sj i and Si j respectively are bundles corresponding to agents i and j.
• 11: R←R∪ {j}.
• 12: end for

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

• 13: for j ∈ Rwith 0 ≤ vj(Sj i ) - vj(Si j ) ≤ wi do
• 14: if Q1 = ∅ then
• 15: Q1 ←Q1∪{j}, Aj ←Aj ∪Si j , and Ai ←Ai∪Sj i .
• 16: else
• 17: Q′1 ←Q′1 ∪{j},Aj ←Aj ∪T i j , and Ai ← Ai ∪T j i .
• 18: end if
• 19: end for

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

• 20: for j ∈ Rwith wi < vj(Sj i ) - vj(Si j ) do
• 21: Q2 ←Q2 ∪ {j}, Aj ←Aj ∪ T i
• 22: end for
• j , and Ai ← Ai ∪ T j i .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

• 23: for j ∈ R but does not satisfy the conditions of Line 13 or 20 do
• 24: Q3 ←Q3 ∪ {j}, Aj ←Aj ∪Si j , and Ai ← Ai ∪ Sj i .
• 25: end for

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

• 26: for j /∈ R do
• 27: Aj ←Aj ∪ T i j and Ai ←Ai ∪ T j i .
• 28: end for
• 29: S ← {j ∈ Ch(i) and j /∈ R : vi(Aij ) + vj(Aji ) > vi(Ai) + vj (Aij )}.
• 30: if S ̸= ∅ then
• 31: q ← argmaxj∈S vi(Aij ) and break ties arbitrarily. Let Q4 ← {q}.
• 32: Swap Aqi and Aiq and update Ai,Aq.
• 33: end if

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

• 34: Define Q5 := Ch(i) \ (Q′1 ∪Q1 ∪Q2 ∪Q3 ∪Q4).

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

• 35: Update ti ← (vi(Aik ) + tk - vi(Ai))+.

Due to space limitations, the detailed proofs of several lemmas are omitted. We begin with observations and propositions regarding Algorithm 3 and subroutines.

Observation 3. In the returned allocation A, for a pair of agents i and j adjacent in G, bundles Aji and Aij are determined by either RoundRobin or MaxUtility.

If the allocation of Ei,j is determined by RoundRobin, then the envy of any of these two agents towards the other is at most 1.

Proposition 4. For i, j adjacent in G, suppose RoundRobin(j, i,Ei,j) = (Bj,Bi), then vj(Bj) ≥ vj(Bi) and vi(Bj) - vi(Bi) ≤ 1 hold. If respectively assigning Bj and Bi to agents j and i does not result in a locally EFable allocation, then vj(Bj) - vj(Bi) ≤ 1.

Proof. For the first part of the statement, since agent j picks first, she does not envy agent i, i.e., vj(Bj) ≥ vj(Bi). For agent i, as RoundRobin presents an EF1 allocation and the maximum marginal value of an item is at most 1, we have vi(Bj ) - vi(Bi) ≤ 1.

For the second part of the statement, if allocating Bj (resp., Bi) to j (resp., i) is not locally envy-freeable, then vi(Bj) + vj(Bi) > vi(Bi) + vj(Bj), implying vj(Bj) - vj(Bi) < vi(Bj ) - vi(Bi) ≤ 1.

The tie-break rule in MaxUtility favors one agent when some item is equally valued, and we call this agent the favored agent. If the allocation of Ei,j is determined by MaxUtility and the favored agent values some item in Ei,j at 1, then the favored agent receives a value of at least 1 from items Ei,j. The following proposition directly follows from the rule of MaxUtility.

Proposition 5. For i, j adjacent in G, suppose MaxUtility(j, i,Ei,j) = (Bj,Bi). If there exists an item e ∈ Ei,j with vj(e) = 1, then vj(Bj) ≥ 1.

Next, we present bounds of wi, ti (after updating) if i is visited by Subroutine2.

Proposition 6. For an agent i, if the items between i and i's out-neighbors in G′ are allocated by Subroutine2, then i has an in-neighbor s in G′ . Moreover, vi(Asi ) + wi ≥ 1 holds, and after updating ti in Line 35 of Subroutine2, ti ≤ wi.

Proof. The fact that i has an in-neighbor s in G′ directly follows from the construction of the reserve graph. Since arc s → i exists in G′ , according to Line 2 of Algorithm 3, there exists e ∈ Es,i such that vi(e) = 1. Thus, max(vi(Asi ), vi(Ais )) ≥ 1 holds as {Asi , Ais } is a 2-partition of Es,i. Then we have

where the first inequality transition is due to ts ≥ 0.

For the bound between ti and wi, if ti = 0, then ti ≤ wi holds, as wi ≥ 0. For the case where ti > 0, we have ti = tk + vi(Aik ) - vi(Ai) for some k belonging to Ch(i) ∪ {s}; recall that Ch(i) is the set of out-neighbors (excluding s if applicable) of i in G′ . If k = s, then since Asi ⊆ Ai and ts, Ais are identical in Lines 4 and 35 of Subroutine2, we have ti ≤ wi. If k ̸= s, at the moment when computing ti in Line 35, tk = 0. By k ̸= s, we have Aki ∪ Asi ⊆ Ai and the following holds,

The first inequality comes from tk = 0 and Aki ∪ Asi ⊆ Ai. For the second one, since k ∈ Q4 ∪ Q5 (k is used to define R and k /∈ R, so k ∈ Ch(i) \ R = Q4 ∪ Q5), then Aki and Aik are determined by RoundRobin(k, i, Ei,k). Based on Proposition 4, vi(Aik ) - vi(Aki ) ≤ 1. The third one is due to vi(Asi ) + wi ≥ 1.

We now present a crucial lemma for bounding the total required subsidy. Recall that Ch(i) denotes out-neighbors of i in G′ , excluding i's in-neighbor if applicable.

Lemma 7. If the items between i and Ch(i) are allocated by Subroutine2, then at termination of Algorithm 3, it holds that ti + ∑j∈Ch(i) wj ≤ wi.

To prove this lemma, we establish key properties guaranteed by Subroutine2 for Ch(i).

Lemma 8. For each weakly connected component C in G′ , let NC be the set of vertices in C. Then it holds that ∑j∈NC tj ≤ 1 at termination of Algorithm 3.

Proof. If items between adjacent agents in C are all allocated by Subroutine1, then for each j ∈ Nc, tj = 0 holds at termination of Algorithm 3. Thus, we can focus on the case where some items between adjacent agents in C are allocated by Subroutine2. Then there must be a directed 2-cycle in C, and suppose that the 2-cycle is formed by f, g. Moreover, there must be envy between f, g when restricted to Ef,g. Without loss of generality, assume that f envies g when restricted to Ef,g. Therefore, items between adjacent agents in the outtree with root f are allocated by Subroutine2.

Let Nf denote the set of vertices in the out-tree with root f (and hence g /∈ Nf ). By Lemma 7, for each j ∈ Nf , it holds that tj ≤ wj - ∑ℓ∈Ch(j) wℓ. Then we have

In the proof of Lemma 7 (which can be found in the full version), we have proved that wf ≤ 1 if the items between adjacent agents in the out-tree with root f are allocated by Subroutine2. Therefore, ∑j∈NC tj ≤ 1 holds.

At the termination of Algorithm 3, each agent j receives bundle Aj and payment pj. As pj is never increased during Phase 2 of Algorithm 3, we have pj ≤ tj for every j. Thus, ∑j∈N pj ≤ ∑j∈N tj. As each vertex has in-degree 1 in G′ , there are at most ⌊ n2 ⌋ weakly connected components. By Lemma 8, for each such component C in G′ , ∑j∈NC tj ≤ 1, where NC is the set of vertices in C. Thus, we have ∑j∈N tj ≤ ⌊ n2 ⌋, which implies ∑j∈N pj ≤ ⌊ n2 ⌋. The remaining task is to prove that the returned allocation with payment (A, p) is indeed envy-free.

Lemma 9. At the moment right before Phase 2, no agent envies their out- and in-neighbours in G′ if ti is the payment to agent i.

Lemma 10. At the termination of Algorithm 3, the allocation with payment (A, p) is envy-free.

Combining the above lemmas, Theorem 2 is proved.

4 Conclusion

In this paper, we study the problem of achieving envyfreeness with subsidy in the graph orientation model. For multigraphs, we prove that a subsidy of ⌊ n2 ⌋ is necessary and sufficient in the worst case. Our proof is constructive; we design a polynomial-time algorithm that ensures the required subsidy does not exceed ⌊ n2 ⌋. The bound cannot be improved even for simple graphs.

Our work also opens up several intriguing directions for future research. For example, in this paper, we assume additive valuations; exploring more general valuation functions would be a natural extension. As mentioned earlier, the tight bound for general monotone valuations is still unknown [Liu et al., 2024], where the upper and lower bounds are 12 n(n - 1) and n - 1 [Brustle et al., 2020; Kawase et al., 2024]. For monotone valuations with binary marginal values, it is proved in [Barman et al., 2022] that Θ(n) is necessary and sufficient. It is interesting to see if Θ(n) is enough for orientation models. Additionally, beyond graphs, it would be valuable to extend this study to other (p, q)-bounded valuation settings, where each item may be relevant to more than two agents.

Acknowledgments

Bo Li is supported in part by the Guangdong Basic and Applied Basic Research Foundation (Grant No. 2024A1515011524) and the Hong Kong SAR Research Grants Council (Grant No. PolyU 15210025). The author names are ordered alphabetically, and Shiji Xing is the corresponding author.