1 Introduction↩︎

Fair Division with indivisible items has attracted significant research interest in the recent years. This can be evidenced by the plethora of new results within the last decade, as exhibited in surveys such as [1], but also by the emergence of motivating applications, including course allocation algorithms [2], and food donation programs [3], among others. The main question in this context is to derive fair allocations of the available resources and several fairness criteria have been proposed, as a way to alleviate the fact that more traditional fairness notions, such as envy-freeness and proportionality fail to exist.

Among the various relaxations of envy-freeness that have been suggested, our work focuses on the well-known EF1 criterion (envy-freeness up to one good) defined by [2]. An allocation is said to be EF1 if for any pair of agents \(i, j\), for which agent \(i\) envies the bundle of agent \(j\), the envy is eliminated after the hypothetical removal of some item from the bundle of \(j\). This is a concept that can be easily satisfied whenever there are no further constraints on the allocation space. Namely, both a simple round-robin algorithm, as well as the envy cycle elimination algorithm by [4] are guaranteed to produce EF1 assignments.

The status regarding the existence of EF1 allocations however changes drastically when there are additional restrictions on the feasible assignments. Recently, there have been various works that study fair division problems under constraints [5], motivated by different application scenarios. Indicatively, some works examine the division of items into categories, with a constraint on the number of items of each category allocated to each agent [6]. In another model, the items form the vertices of a graph and each bundle must form a connected subgraph [7], [8]. We refer to our related work section for further exposition.

Our work focuses on yet another graph-theoretic model of constrained fair division that has been initiated recently, where the constraints are modeled via a conflict graph. More precisely, the items correspond to the vertex set of the conflict graph and a bundle is not allowed to contain two items that are connected with an edge. In other words, the bundles allocated to the \(n\) agents must constitute a \(n\)-coloring in the conflict graph (with each bundle being an independent set). This model turns out to impose severe limitations on the existence of fair allocations, if we want to allocate all items (i.e., have a complete allocation). Firstly, a complete allocation may simply not exist, even without imposing any fairness criterion. To circumvent this, the mild condition of \(\Delta<n\), where \(\Delta\) is the maximum degree of the graph does guarantee the existence of a complete allocation (since this is sufficient for the existence of a valid \(n\)-coloring). Even under this assumption, counterexamples for the existence of EF1 allocations have already been identified [9], [10]. We feel this naturally poses the question of understanding further or characterizing when is it possible to achieve EF1 or other fairness concepts under such constraints.

1.1 Our contribution↩︎

We are interested in the existence and efficient computation of complete, EF1 allocations in the presence of a conflict graph, when the agents have additive valuations. The main contribution of our work is that we explore the effect of the maximum degree of the conflict graph, \(\Delta\), on the existence of EF1 allocations. For the cases where we establish existence, we also describe efficient algorithms for computing such allocations. The techniques we use are based on leveraging results from matching theory such as Hall’s Theorem for perfect matchings or the structure of vertex sets that form violations to Hall’s theorem when no perfect matching exists. We derive our results by combining these techniques with algorithmic tools of fair division such as Round Robin and envy cycle elimination procedures.

We start in Section 3, where we deal with ordered valuations and the wider class of tiered valuations. Ordered valuations, where the agents agree on the ranking of all items w.r.t. their value has been extensively considered in fair division (e.g. [11]). Tiered valuations form a more natural superclass, where the items are grouped into tiers, and the agents agree on the ranking between the tiers even if they may not agree on the ranking of the items within each tier. We consider valuations with tiers of size \(n\), meaning that each tier (except maybe the last one) contains exactly \(n\) items (so that agents agree on which are the \(n\) most valuable items, then the next \(n\) most valuable and so on). For this valuation class we provide in Section 3.1 an algorithm that returns an EF1 allocation when the number of items, \(m\), is bounded as: \(m\leq n\left\lfloor \frac{n}{\Delta} \right\rfloor +n-\Delta\). We show that this result is tight, i.e., when \(m\) exceeds the above bound there may not exist EF1 allocations, and this is proved by extending the counterexample of Igarashi et al. [10]. To alleviate this negative fact when \(m> n\left\lfloor \frac{n}{\Delta} \right\rfloor +n-\Delta\), we provide a positive approximation result in Section 3.2. Namely, for \(\Delta\leq \frac{n}{2}\), and based on our previous algorithm, we provide an approximation algorithm obtaining a \((1-\frac{2}{r+1})\)-EF1 allocation where \(r=\left\lfloor \frac{n}{\Delta} \right\rfloor\). Observe that, the ratio of the algorithm approaches \(1\) as \(r\) becomes sufficient small and tends to \(0\).

In Section 4 we move to general additive valuations. The setting here is much more restrictive, as we exhibit that even with identical valuations, an EF1 allocation may not exist when \(m> 2n - \Delta\). We therefore focus on understanding EF1 existence when \(m\leq 2n\), for which we provide an almost complete picture. Firstly, we combine the Round Robin algorithm with an appropriately constructed matching to derive an EF1 allocation when either \(m\leq 2n-\Delta\) or \(m\leq 2n\) and \(\Delta\leq\frac{n}{2}\). Our most technical result is that we extend this algorithm to attain EF1 when \(m\leq 2n\) and \(\Delta\leq \frac{2n}{3}\). As a complementary result, when \(\Delta>\frac{2n}{3}\), we can attain EF1, when \(m\leq 2n-\Delta+1\), and \(G\) does not have \(K_{\Delta,2n-2\Delta+1}\) as a subgraph. The last 2 results are obtained by a repeated application of matching algorithms, in combination with envy cycle removals.

1.2 Further related work↩︎

The model of fair division with a conflict graph, that we study here was first introduced by Chiarelli et al. [12], where they focus on a different objective, that of maximizing the lowest total profit of items allocated to any agent. The existence and computation of complete EF1 allocations under this model, which is also the focus of our work, was later studied by Hummel and Hetland [9], where they established both positive results for some special cases, as well as impossibility results for general additive valuations (e.g., non-existence when \(\Delta> n\) or when \(n\geq 4\) and with lower values of \(\Delta\)). In the same work they also considered the criteria of MMS and Maximum Nash Welfare under this setting. Igarashi et al. [10] proved that a maximal but not necessarily complete EF1 allocation always exists for two agents and any graph, when the agents have monotone valuations. Moreover, they showed NP-hardness results for finding maximal EF1 allocations for three or more agents. A special case of this problem, that corresponds to interval scheduling was considered by Li et al. [13] and Kumar et al. [14], under the fairness criteria of EF1 and MMS. Additionally, Kumar et al. [14] also considered the case where the items are chores. Finally, Yoneda and Yoneda [15] studied a setting where the conflict constraints are treated as "soft." In this scenario, allocating adjacent goods to the same agent is allowed and the objective is to find EF1 allocations with a small number of such conflict violations.

There have been several other models of fair division under constraints. Biswas et al. [16] considered a model where items are grouped into categories and each bundle needs to respect a bound on the items received from each category. Another graph-related model involves the allocation of connected bundles, where items are located again in a graph, as studied in [7], [8]. Other models concern constraints defined via matroids. For example, [6] considered a setting where the constraints are determined by laminar matroids. Furthermore, Gourves et al. [17] considered a model where the allocated items should form a base of a matroid. Additional results under matroid constraints regarding MMS and other criteria have also been obtained in [18], [19]. Yet another model focuses on the scenario where all agents should receive the same number of items (e.g. in assigning shifts) studied in [20] and more recently in [21], [22]. For an overview of problems involving constrained fair division we refer to the survey by Suksompong [5] or to the one by Biswas et al. [23].

When it comes to the unconstrained setting, there is an even bigger volume of research activity within the last decades. The lack of envy-free allocations led over the years to various new criteria including the one we study here, defined by [2], as well as the notions of EFX (envyfreeness up to any good) introduced in [18], [24], MMS defined by [2], and groupwise MMS considered in [25]. For an overview, we refer to the survey by [1].

2 Preliminaries↩︎

We consider a setting with \(n\) agents and \(m\) indivisible items to be allocated to the agents. We denote by \(N\) the set of agents and by \(M\) the set of items. Each agent \(i\in N\) has an additive valuation function \(v_i\) over the items so that for every \(S\subseteq M\), \(v_i(S)=\sum_{g\in S} v_i(\{g\})\) and \(v_i(\emptyset)=0\). For simplicity, we will use \(v_i(g)\) instead of \(v_i(\{g\})\), and we also assume that \(v_i(g)\geq 0\) for every \(g\in M\). We denote by \(V\) the set of valuation functions of the \(n\) agents, i.e., \(V=\{v_i\mid i\in N\}\).

A complete allocation, or simply an allocation, denoted by \(A=(A_1,A_2,\ldots\), \(A_n)\), is a partition of the items \(M\), where \(\bigcup_{i\in [n]}A_i=M\) and \(A_i\cap A_{i^{\prime}}=\emptyset\) for any \(i,i^{\prime}\in[n]\) with \(i\neq i^{\prime}\). The bundle \(A_i\) is the set of items assigned to agent \(i\). A partial allocation is an allocation over a strict subset of the set of items \(M\).

In the constrained setting we study, certain pairs of items are not allowed to be allocated to the same agent. These pairs are represented via an undirected conflict graph \(G=(M,E)\), where its vertices are the set of items i.e., \(V(G)=M\) and for every edge \((u,v)\in E\), the items \(u\) and \(v\) are conflicting and cannot be assigned to the same bundle. An allocation (complete or partial) is feasible if no bundle contains a pair of conflicting items. In other words, a feasible allocation forms a \(n\)-coloring of \(G\) and each bundle \(A_i\) is an independent set of \(G\). The question of interest in our work is to find feasible and complete allocations which also satisfy some fairness criteria.

Our analysis will make use of the maximum degree \(\Delta(G)\), of a vertex in \(G\). For brevity, we will denote the maximum degree by \(\Delta\), instead of \(\Delta(G)\). We also denote by \(N(v)\) the neighbor vertices of a vertex \(v\). For a subset of items \(S\subseteq V(G)\), we use \(N(S)\) for the vertices that are neighbors with at least one vertex belonging to \(S\) i.e., \(N(S)=\{u\in V \setminus S: (u,v)\in E \text{ for some } v\in S\}\). Given a partial allocation \(A=(A_1,A_2,\ldots,A_n)\), the items that have as neighbor in \(G\) an item allocated to agent \(i\) are the conflicting items of agent \(i\) w.r.t. \(A\), i.e., these are precisely the items of the set \(C_i(A)= N(A_i)\).

We define now an additional graph that will be helpful in formalizing some of our algorithms and their analysis. Given a partial allocation \(A\), and the set \(U\) of unallocated items in \(A\), the feasibility graph, denoted as \(F(A,U)\), is a bipartite graph where \(V(F(A,U))=N\cup U\) and \(E(F(A,U))=\{(i,g)\mid g\notin C_i(A)\}\). Hence, in \(F(A,U)\) each agent \(i\) is connected with the items \(g\in U\) such that \(A_i\cup \{g\}\) remains feasible.

In the sequel, we will often allocate items to agents based on matchings that we compute in the feasibility graph. For brevity we will be using the procedure below. In particular, given a partial allocation \(A\), and a subset \(R\) of edges of \(F(A,U)\) such that each \(g\in U\) belongs to at most one edge of \(R\), Procedure [allocating-edges] allocates for each \((i,g)\in R\) the item \(g\) to agent \(i\).

Beyond completeness and feasibility, we want allocations that also meet some fairness criterion. The fairness criterion in our work is envy-freeness up to one item (EF1). Given an allocation \(A\) we say that an agent \(i\) envies agent \(j\) if \(v_i(A_i)<v_i(A_j)\). An allocation is envy-free (EF) if no agent envies the bundle of some other agent i.e., \(v_i(A_i)\geq v_i(A_j)\) for every pair of agents \(i, j\in N\). Envy-freeness up to one item is a relaxation of envy-freeness where every agent \(i\) is not envious towards any other agent \(j\) after the hypothetical removal of some item from the bundle of \(j\). The formal definition of an EF1 allocation is following.

Similarly to the above definition, an allocation is said to be \(\alpha-\)EF1 if \(v_i(A_i)\geq \alpha v_i(A_j \setminus {g})\) for some \(g\in A_j\).

Due to the following known proposition, and since we ask for complete matchings, we only consider instances with \(\Delta<n\).

2.1 Definitions and tools from matching theory↩︎

Now, we present some preliminary concepts related to matchings, which will be used extensively in the following sections.

In a bipartite graph \(G = (X\cup Y,E)\) a perfect matching is a matching that matches every vertex in \(X\) to a unique vertex in \(Y\) and vice versa. For a perfect matching to exist in a bipartite graph, it is necessary that \(|X|=|Y|\). If \(|X|\leq |Y|\) we say that a matching saturates \(X\) if every vertex in \(X\) is matched to a distinct vertex in \(Y\). In the sequel, we will extensively use the graph theoretic version of Hall’s theorem as follows.

Clearly, when \(|X|=|Y|\) and Hall’s condition holds, the matching is perfect. In a bipartite graph \(G = (X\cup Y,E)\), we say that \((S,N(S))\) is a Hall violator if \(|S|>|N(S)|\). Finally, a known consequence of Hall’s Theorem is the following proposition. For the sake of completeness, we provide a proof in the Appendix.

3 Ordered Valuations and Beyond↩︎

We say that the agents have ordered valuations if there is an ordering of the items, say \(g_1,g_2,\ldots,g_m\), such that \(v_i(g_1)\geq v_i(g_2)\geq \ldots \geq v_i(g_m)\) for every \(i\in N.\) Ordered valuations are motivated by settings where there is a common perception for the ranking of the items, even if the agents do not agree about their precise value. The results we present in this section actually hold for a broader class, that we term valuations with tiers of size \(n\). Let \(k\) be the minimum integer such that \((k-1)n< m\leq kn\). When the agents have valuation with (common) tiers of size \(n\), the set of items \(M\) is partitioned into sets (tiers) \(M_1, M_2,\ldots,M_k\). The set \(M_1\) contains the top \(n\) most preferred items which are common to all agents, even though they may not agree on the ranking of these items. The set \(M_2\) contains the next \(n\) items, and so on. Only \(M_k\) may contain strictly less than \(n\) items. A formal definition follows.

Ordered valuations form a special case of the above definition, where the items belonging to the same tier \(M_j\) are also ranked in the same way by all agents. The following simple proposition holds for valuations with tiers of size \(n\) and thus also for ordered valuations.

3.1 EF1 via Tiered Matching↩︎

Our main result in this subsection is an algorithm that returns a complete EF1 allocation when the number of items is bounded by \(n\left\lfloor \frac{n}{\Delta} \right\rfloor +n-\Delta\).

Our proposed algorithm iteratively allocates the items to the agents via matchings (one per tier) in the feasibility graph. We briefly discuss first for how many agents an unallocated item is feasible with their bundles. For a partial allocation \(A\) and a set of unallocated items \(U\), an agent \(i\) is not connected with an item \(g\in U\) if some item which is a neighbor of \(g\) in the conflict graph belongs to \(A_i\), i.e., \(g\in C_i(A)\). Since the conflict graph \(G\) has maximum degree \(\Delta\), even if all of the at most \(\Delta\) neighbor items of \(g\) have already been given to \(\Delta\) different agents, there are at least \(n-\Delta\) agents whose bundle is feasible with item \(g\). Thus, every \(g\in U\) is connected with at least \(n-\Delta\) agents in \(F(A,U)\). We are now in a position to present the Tiered Matching Algorithm (Algorithm 1).

Because of Proposition [balanced95EF1], if in each round of Algorithm 1, the matching \(R\) is perfect (except the last one, where it needs to saturate \(M_k\)), then the resulting allocation is complete and EF1. In what follows, we prove that this condition holds when the number of items does not exceed \(n\left\lfloor \frac{n}{\Delta} \right\rfloor +n-\Delta\).

Igarashi et al. [10] have shown a counterexample to EF1 existence for any \(n\geq 4\) with identical additive valuations and \(m=n+2\). This is not in conflict with our results since the conflict graph in their example is \(K_{3,n-1}\) i.e., \(\Delta(K_{3,n-1})=n-1\). Indeed, for \(\Delta=n-1\), \(n\left\lfloor \frac{n}{\Delta} \right\rfloor=n\) and Theorem 2 guarantees that Algorithm 1 returns an EF1 allocation when \(m\leq n+n-\Delta=2n-(n-1)=n+1\). Therefore, since \(m=n+2\) in the counterexample by Igarashi et al. [10], this shows that our bound on \(m\), for which Algorithm 1 returns an EF1 allocation is tight. In the following proposition we extend the tightness of Algorithm 1 w.r.t. the number of items, for any \(\Delta>\frac{2}{3}n\). In fact, we strengthen this even further, and prove an impossibility result even for approximate EF1 allocations, beyond a certain constant ratio, when \(m\) exceeds the bound of Theorem 2.

Note that for the construction of Proposition [counter-example], we must have \(\Delta\geq \frac{2n+1}{3}\). Otherwise, if \(\Delta\leq\frac{2}{3}n\), then the degree of vertices in \(V_1\) would be \(2n-2\Delta+1\geq \frac{2}{3}n+1\) and the maximum degree of the conflict graph \(K_{\Delta,2n-2\Delta+1}\) would not be equal to \(\Delta\). Thus, the counterexample no longer holds when \(\Delta\leq\frac{2}{3}n\).

3.2 Approximation via Tiered Matching↩︎

Given the tightness of the previous result when \(\Delta > 2n/3\), in this subsection, we investigate further the behavior of Algorithm 1 when there is no restriction on the number of items and for lower values of \(\Delta\). More precisely, we explore the case where \(\Delta\leq\frac{n}{2}\) (with the agents still having valuations with tiers of size \(n\)). Note we can still run Algorithm 1, but for \(j>\left\lfloor \frac{n}{\Delta} \right\rfloor\), there is no guarantee that the matching \(R_j\) produced in line [matching-j] of Algorithm 1 will be perfect. If it is not perfect, this implies that there is a Hall violator \((S, N(S))\) in \(F(A,M_{j})\) where \(S\) is a subset of agents and \(|S|>|N(S)|\). Since every item has degree at least \(n-\Delta\) in \(F(A,M_{j})\), for every subset of agents with size \(\Delta+1\) or greater, each item is connected with at least one agent in the subset. Hence that would mean that \(|N(S)| = n \geq |S|\). Therefore, this implies that \(|S|\leq \Delta\). Consequently \(|N(S)|\leq \Delta-1\) and an agent \(i\) that is unmatched in \(R_j\) has at least \(n-(\Delta-1)=n-\Delta+1\) items of \(M_j\) in her conflict set. Let \(r=\left\lfloor \frac{n}{\Delta} \right\rfloor\) and \(l\) be the minimum integer such that \(m\leq lrn\). In this section, if \((l-1)rn<m<lrn\), by adding zero valued items (without conflicts) we assume that \(m=lrn\), so that Algorithm 1 will run for \(lr\) rounds.

The following lemma shows a lower bound for the number of items each agent \(i\) has in her bundle \(A_i\) in an allocation \(A\) obtained by Algorithm 1. For every \(h\in [l]\) we denote by \(M^h\) the items of the first \(hr\) rounds i.e., \(M^h= \bigcup_{j=1}^{hr}M_j\).

Let \(U\) be the set of unallocated items after the execution of Algorithm 1. For every \(h\) such that \(2\leq h\leq l\), let \(U_h\) be the subset of \(U\) obtained from rounds \(j\) such that \(r(h-1)+1\leq j \leq rh\), i.e., \(U_h=(\bigcup_{r(h-1)+1}^{rh}M_j)\cap U\).

The next algorithm is based on obtaining first an allocation \(A\) by Algorithm 1 (which may not be complete) and then figuring out how to allocate the items of \(U\). For every \(U_h\), let \(N_h\) be the set of agents who have less items from \(M^h\) than the number of rounds \(rh\) so far. Algorithm 2 gives priority to the agents of \(N_h\) for the unallocated items of \(U_h\). Then, if there are still items in \(U_h\) and no such agent is feasible with some of them, these items are allocated to the other agents ensuring that every agent has at most \(h(r+1)-1\) items from \(M^h\) in her bundle.

By Lemmas [bound-un] and [unallocated] the best and the worst case for a bundle \(A_i\) of an agent \(i\) are as represented in Table 1. Observe that in \(A_b\) it holds that \(|M^h\cap A_b|=h(r+1)-1\) for every \(h\in [l]\). The additional items of \(A_b\) arise from the best possible rounds. For every \(h\geq 2\) there are two items of round \(M_{(h-1)r+1}\) in the bundle of \(A_b\). This implies that the next possible round that \(A_b\) may contain an extra item is \(M_{hr+1}\), where there is also one extra item, because of the inequality \(|M^h\cap A_b|\leq h(r+1)-1\) and so on. Respectively, for \(A_w\) it holds that \(|M^h\cap A_w|=h(r-1)+1\) for very \(h\in [l]\) and the lost items of \(A_w\) occur in the worst possible way satisfying the inequality \(|M^h\cap A_w|\geq h(r-1)+1\).

4 General Additive Valuations↩︎

In this section we consider general additive valuations. We know already from the previous section that for exact EF1 allocations, we need \(m\leq n\left\lfloor \frac{n}{\Delta} \right\rfloor +n-\Delta\). Here we restrict our study even further to the case of \(m\leq 2n\). To motivate this, recall that since \(\Delta < n\), Proposition [counter-example] already implies that even when the agents have identical additive valuations, if \(\Delta>\frac{2}{3}n\) and \(m>2n-\Delta\), an EF1 allocation may not exist. We therefore find it important to understand EF1 existence in the still non-trivial case when \(m\) is bounded by a small multiple of \(n\).

We first show that even for general additive valuations, an EF1 allocation can be computed when \(m \leq 2n-\Delta\). Recall that this is the tight bound in the number of items for EF1 allocations established in the previous section. In particular, Algorithm 3, which we analyze in the sequel, returns an EF1 allocation when \(m\leq 2n-\Delta\) or when \(\Delta\leq \frac{n}{2}\) and \(m\leq 2n\).

If \(m\geq 2n-\Delta+1\) and \(\Delta>\frac{n}{2}\), Algorithm 3 cannot work. In particular, there is no guarantee that a matching saturating every vertex of \(M_2\) in \(F(A,M_2)\) exists in line [RRline] of Algorithm 3 (a property that is used for the cases handled by the proof of Theorem [RR-Thm1]). To remedy this, we propose Algorithm 4, a technically more involved algorithm, as an extension of Algorithm 3, that returns an EF1 allocation when \(m\leq 2n\) and \(\Delta\leq\frac{2n}{3}\). This results in the following theorem, which is the main technical result of this section.

4.1 Prelims to Algorithm 4: Relevant definitions and procedures↩︎

Before presenting the pseudocode of Algorithm 4, we provide some necessary concepts.

In a bipartite graph \(G = (X\cup Y,E)\), if no matching exists that saturates all vertices of \(X\), then Hall’s condition of Theorem 1 is violated by at least one subset \(S\) and its neighborhood \(N(S)\). A Hall violator of maximum deficiency is a Hall violator \((S,N(S))\), where \(S\subseteq X\), that maximizes \(|S|-|N(S)|\). A Hall violator of maximum deficiency \((S,N(S))\) is maximal if for every Hall violator \((S^{\prime}, N(S^{\prime}))\) where \(S\subset S^{\prime}\) it holds that \(|S|-|N(S)|>|S^{\prime}|-|N(S^{\prime})|\). This implies that if \((S,N(S))\) is a Hall violator of maximum deficiency that is also maximal, then \(|X^{\prime}|< |N(X^{\prime})\cap (Y\setminus N(S))|\) for every \(X^{\prime}\subseteq X\setminus S\), otherwise \(S\) could be extended by \(X^{\prime}\) and would not be maximal.

We refer to a pair of items \(p = \{g^1,g^2\}\) as feasible if \((g^1,g^2)\) is not an edge of the conflict graph \(G\). Algorithm 4 is based on constructing the following type of matchings.

The set of feasible pairs of a 2-matching \(R\) is the set of pairs of items that matched to the same agent in \(R\).

Another graph that we make use of is the envy graph of an allocation \(A\). This is a directed graph, denoted by \(EG(A)\), where its vertex set is the set of agents and there is an arc \((i,j)\) from agent \(i\) to \(j\) whenever \(v_i(A_j)>v_i(A_i)\).

Within our algorithm, we make use of Procedure [envy-swap] stated below, which receives as input a partial allocation \(A\) and a bundle \(A_f\) that does not belong to any agent. The agents have the option to swap their bundle with \(A_f\), and when the procedure ends no agent envies the final remaining bundle, \(A_f\). We also ensure that \(EG(A)\) is acyclic at the end (due to the order of the swaps).

When each agent has 1 item in her bundle and a matching does not exist, the question is how can we handle the items of the Hall violator \(S\). Algorithm 4 creates pairs of items of \(S\) in a feasible manner and each agent has the choice to exchange her bundle with one of these pairs. This is repeated until either the unallocated items can be matched to the agents with a single item so far or no agent is willing to exchange her bundle with such a pair. In the latter case some agents will end up with 3 items in their bundle and others with 1.

4.2 Auxiliary graph and computing a feasible 2-matching↩︎

Before proving that Algorithm 4 returns an EF1 allocation, we describe how to identify a maximal Hall violator of maximum deficiency and we provide a procedure for the construction of the feasible \(2\)-matching in line [line:2-matching]. Both rely on the notion of an auxiliary graph, as defined below.

Note that the unmatched vertices in \(R\) are single-vertices strongly connected components in the auxiliary graph, since either they may only have ingoing edges (if they belong to \(N^{\prime}\)) or only outgoing (if they belong to \(M_2\)). These strongly connected components are regarded as trivial. The non-trivial strongly connected components are those that are induced by the matched vertices.

The structural existence of the maximal Hall violator of maximum deficiency follows from the classic Dulmage-Mendelsohn decomposition [27], and it can be efficiently computed using standard alternating path reachability [28]. For the sake of completeness, we provide a description of how the maximal Hall violator of maximum deficiency \((S,N(S))\) is decided. Firstly we construct \(F_R(A^{\prime},M_2)\) given a maximum size matching \(R\) in \(F(A^{\prime},M_2)\). Let \(T\) be the set that contains every \(g\in M_2\) such that there exists an \(i\in N^{\prime}\) which is unmatched in \(R\) and \(i\) is reachable from \(g\) in \(F_R(A^{\prime},M_2)\). A maximal Hall violator of maximum deficiency \((S,N(S))\) is the one where \(S=M_2\setminus T\) .

The DAG of the strongly connected components of a directed graph is formed by contracting each strongly connected component into a single vertex, preserving only the edges that connect different components.

Now we present Procedure [procedure322-matching] that decides a feasible 2-matching \(R^{\prime}\) w.r.t. \(S\) in \(F(A^{\prime},M_2)\). As part of the proof of Theorem [Thm32EF1] that follows in Section 4.3, it is shown in Lemma [claim1] that this procedure yields a feasible \(2\)-matching at each iteration of line [line:32Hall-violator] in Algorithm 4.

4.3 Proof sketch of Theorem [Thm32EF1]↩︎

We provide here the main skeleton of our proof. All missing proofs of subsequent lemmas and claims that we state and use here can be found in the Appendix.

Because of Theorem [RR-Thm1], we assume that \(\Delta>\frac{n}{2}\) and \(m>2n-\Delta\). If a matching \(R\) in line [line:matching] exists, Algorithm 4 does not enter the while loop in lines [while3-start]-[while3-end]. The returned allocation \(A\) is EF1. The rest of this part of the proof is as in Theorem [RR-Thm1]. Otherwise, there is a Hall violator \((S,N(S))\).

Since the maximum degree of \(G\) is \(\Delta\), every vertex of \(F(A,M_2)\) has degree at least \(n-\Delta\). For the Hall violator when Algorithm 4 enters the while loop in lines [while3-start]-[while3-end] for the first time, it holds that \(n-\Delta\leq |N(S)|<|S|\leq \Delta\).

In every iteration of the while loop in lines [while3-start]-[while3-end], we consider the following four cases for the bundle \(A_f\) that is left unallocated by Envy Swap in line [line:32envy-swap]. We denote by \(M_s\) the set of items belonging to the agents of \(N(S)\) and by \(M_0\) the items belonging to the agents of \(N^{\prime}\setminus N(S)\). These cases are distinguished based on which agent held the bundle before Envy Swap. The cases are the following.

• \(A_f=\{g\}\), where \(g\in M_s\) and \(g\) is not feasible with any item of \(M_0\).

• \(A_f=\{g\}\), where \(g \in M_s\) and \(g\) is feasible with some item of \(M_0\).

• \(A_f=\{g\}\), where \(g\in M_0\).

• \(A_f=\{p_i\}\), where \(p_i\) is a feasible pair belonging to an agent \(i\in N\setminus N^{\prime}\).

Observe that in the first three cases the number of agents that are allocated a feasible pair is increased by \(1\) after the iteration. Moreover, in the first iteration \(A_f\) cannot fall into Case C4 since no agent is allocated a feasible pair so far.

To proceed with the proof, we first show that Algorithm 4 is well-defined and always terminates. This is established by Lemma [claim1] and Claims [claimcombined]-[claim4]. Lemma [claim1] establishes the existence of the 2-matching in each iteration.

Claim [claimcombined] esteblishes some structural properties of the auxiliary graph \(F(A^{\prime},M_2)\). Recall that \(B_s\) is the strongly connected component which is non-trivial sink in the DAG formed by the strongly connected components of \(F_R(A^{\prime},M_2)\).

The specific construction of the 2-matching, combined with the structure of the feasibility graph implied by the condition that \(\Delta \leq \frac{2n}{3}\), ensures the validity of the claims stated below. Claim [claim2] specifies the conditions under which Algorithm 4 exits the while loop in lines [while3-start]-[while3-end] and terminates.

Claim [claim3] shows that the items belonging to the agents of \(N^{\prime}\setminus N(S)\) is a subset of the respective items in the initial iteration.

The number of agents that have been already allocated a feasible pair is denoted by \(n_p\). i.e., \(n_p=|N\setminus N^{\prime}|\). Clearly the number of items that have been allocated to the agents of \(N\setminus N^{\prime}\) is \(2n_p\). Claim [claim4] is obtained almost directly by Claim [claim3].

The set of items belonging to the agents of \(N^{\prime}\setminus N(S)\) are connected in the conflict graph with every item belonging to \(S\) at some point during the execution of Algorithm 4. Thus, Claim [claim3] implies that the overall number of items which are elements of \(S\) at some iteration is at most \(\Delta\). Since \(\Delta\leq \frac{2n}{3}\), the number of feasible pairs that can be constructed is \(O(n^2)\). Moreover, observe that the value of any agent does not decrease during Algorithm 4 and in every iteration of the while loop at least one agent strictly increases her value. Consequently, in combination with Claim [claim4], after a polynomial number of iterations the deficiency \(|S|-|N(S)|\) would strictly decrease if Algorithm 4 re-enters the while loop. Thus, because of Claim [claim2], Algorithm 4 always terminates.

Having established the termination of the algorithm, we can now establish that it produces a desirable allocation.

Finally, we argue that Algorithm 4 runs in polynomial time. A maximal Hall violator of maximum deficiency and a feasible 2-matching can be computed in polynomial time (see Appendix 4.2). Since the initial deficiency \(|S|-|N(S)|\) is at most \(\Delta-(n-\Delta)\leq \frac{n}{3}\) and after a polynomial number of iterations the deficiency is strictly decreased, then the overall number of iterations that the while loop is executed is polynomial. This concludes the proof.

4.4 Further consequences of Algorithm 4↩︎

The following theorem shows that when \(\Delta> \frac{2n}{3}\) and \(m=2n-\Delta+1\), a necessary condition for the non-existence of EF1 allocations, even with additive valuations, is that \(K_{\Delta,2n-2\Delta+1}\) is subgraph of the conflict graph \(G\). Recall that \(K_{\Delta,2n-2\Delta+1}\) is the conflict graph of the counterexample in Proposition [counter-example] for every \(\Delta>\frac{2n}{3}\). The proof is similar to the one of Theorem [Thm32EF1] in a simplified manner and is provided in the Appendix.

5 Conclusions↩︎

We have studied the existence of complete EF1 allocations in constrained fair division with a conflict graph. Our main technical contribution is the use of matching theory (and especially Hall’s theorem) for establishing the existence and efficient computation of EF1 allocations for certain classes of valuation functions. The provided results demonstrate that the maximum degree of the conflict graph plays a crucial role in determining the existence of such fair allocations. An open question arising from our work is for which \(m\) an EF1 allocation is guaranteed in the case that \(\Delta\leq 2n/3\) and \(m>2n\). Moreover, developing more refined approximation algorithms is also an interesting direction for future work.

Beyond the open questions that follow directly from our results, there are other important research avenues as well. The maximum degree \(\Delta\) provides only partial information about the conflict graph. Focusing on this parameter allows us to establish a robust worst-case analysis. However, a graph with a small number of vertices of degree \(\Delta\) may differ significantly in the conflicts it generates. Investigating how other structural properties, such as the average degree or vertex connectivity could affect and strengthen the fairness guarantees (maybe in combination with \(\Delta\)) is an appealing direction for future work. Furthermore, our work has focused only on the EF1 criterion, which is already quite challenging, but several other fairness notions can also be explored. There has been some progress on this front (e.g., for the MMS criterion in [9]), but we are still far from having a more complete understanding on which notions are more amenable under this constrained model.

Appendix

6 Missing Parts from Section 2↩︎

6.1 Proof of Proposition [Hall-Cor]↩︎

7 Missing Parts from Section 4↩︎

7.1 Missing parts from Proof of Theorem [Thm32EF1]↩︎

When Algorithm 4 entered the while loop for the first time it holds that \(n_p=0\). Recall that \(n_p=|N\setminus N^{\prime}|\) i.e. the number of agents that have already been allocated a feasible pair and they are not in \(F(A^{\prime},M_2)\). We prove Lemma [claim1] and Claims [claim2], [claim3], and [claim4] by induction in the iterations of the while loop in lines [while3-start]-[while3-end] of Algorithm 4. Additionally, we state and prove Claim [claimcombined] which establishes some structural properties of the feasibility graph in each iteration that are necessary in the proofs of the other claims. We show them in a unified manner for the first and the next iterations. We assume that all of them hold after several iterations and we prove that they also hold in the next one. For the first iteration, which serves as the basis of the induction, we have \(n_p=0\) and the only difference in the proof of them is that \(A_f\) returned by Envy Swap cannot fall into Case C4 in the first iteration since no agent is allocated a feasible pair so far.

Before proving Lemma [claim1] and Claims [claimcombined], [claim2], [claim3], and [claim4] , we provide a description of \(F(A^{\prime},M_2)\) after several iterations of the while loop. In \(F(A^{\prime},M_2)\) each part has \(n-n_p\) vertices. Since the maximum degree in the conflict graph is \(\Delta\), every vertex in \(F(A^{\prime},M_2)\) has degree at least \(n-\Delta-n_p\). If there is no matching in \(F(A^{\prime},M_2)\), for the Hall violator it holds \(n-\Delta-n_p\leq |N(S)|<|S|\). Moreover, because Claim [claim2] holds in the previous iterations, the items of \(M_0\) are connected in the conflict graph with the items of \(M_p\). Thus, \(|S|\leq \Delta-2n_p\) and \(|N(S)|<\Delta-2n_p\) and \(|N^{\prime}\setminus N(S)|>n-n_p-(\Delta-2n_p)=n-\Delta+n_p.\) Recall that \(M_s\) is the items belonging to the agents of \(N(S)\) and \(M_0\) those to the agents of \(N^{\prime}\setminus N(S)\). Every item of \(S\) is feasible with at least \(n-\Delta-n_p\) items of \(M_s\) and each item of \(M_0\) is feasible with at least \(n-\Delta+n_p\) of \(M_2\setminus S\) since it has \(2n_p\) conflicts with the items of \(M_p\).

Since in \(F(A^{\prime},M_2)\) each part has \(n-n_p\) vertices and \(n-\Delta-n_p\leq |N(S)|<|S|\leq \Delta-2n_p\), let \(|S|=n-\Delta-n_p+r+k\) and \(|N(S)|=n-\Delta-n_p+r\) for some \(r\geq 0\) and \(k\geq 1\).

In the proof of the Lemma [claim1] and Claims [claimcombined], [claim2], [claim3], and [claim4], because in the Envy Swap the agents that will remain in \(F(A^{\prime},M_2)\) may have swap their bundles in the Envy Swap, we may consider that in \(F(A^{\prime},M_2)\) the vertices of the one part is not the agents \(i\in N^{\prime}\) but their respective items \(M_s\cup M_0\). Equivalently to this notation, if \(A_i=\{g_i\}\) and \((i,g^{\prime})\in R^{\prime}\) for some agent \(i\in N^{\prime}\), we consider that \((g_i,g)\in R^{\prime}\).

The proofs of Claims [claim2] and [claim3] rely on the construction of the \(2\)-matching \(R^{\prime}\) and we shall utilize the auxiliary graph \(F_{R^{\prime}}(A^{\prime}, M_2)\) obtained by orienting the edges of \(F(A^{\prime}, M_2)\) as previously described or by reversing the direction of the edges of the matching \(R_2\) of Procedure [procedure322-matching] in \(F_{R}(A^{\prime}, M_2)\).

References↩︎