1 Introduction↩︎

Fair division of resources among self-interested agents is a foundational problem in artificial intelligence and multi-agent systems [1], [2]. Among fairness criteria, envy-freeness (EF) is one of the most compelling: an allocation is envy-free if every agent weakly prefers their own bundle to that of any other agent. While EF allocations always exist for divisible goods [3], the indivisible setting is significantly more challenging—an EF allocation may not exist at all, and deciding whether one exists is computationally demanding in general.

Most work on envy-free allocation of indivisible goods either imposes special structural assumptions (e.g., identical valuations, binary preferences, two agents) or relaxes the fairness requirement to approximation notions such as EF1 [4], [5] (envy-freeness up to one item) or EFX [6], [7]. Exact EF for general additive valuations over indivisible goods is known to be computationally hard [8], and practical algorithms typically resort to exhaustive search, which is exponential in the number of agents.

In this paper we study a natural and practically motivated special case: items come in \(t\) types, and each agent has additive valuations that depend only on the type of an item rather than on individual items. This captures scenarios such as computing resource allocation across hardware tiers, food distribution by nutritional category, or budget allocation across departments. Crucially, our setting encompasses not only goods (positive valuations) but also chores (negative valuations) and mixed instances in which some item types are goods for certain agents and chores for others. The only constraint is we forbid agents with zero valuation vectors. The EF condition is uniform across all cases: every agent must weakly prefer their own bundle over anyone else’s. Despite the restriction to a fixed number of types, the problem remains non-trivial: the space of feasible allocations has size \(((m_1+1) \cdot\ldots \cdot (m_t+1))^n\), where \(m_i\) is the total number of items of type \(i\), rendering brute-force search infeasible for large inputs.

The number of types \(t\) turns out to be the key parameter governing tractability, and the known results reveal a striking complexity landscape.

For two types (\(t = 2\)), was shown that an EF allocation can be found in polynomial time. For many types (\(t = \Omega(m)\)), the problem is hard even for two agents: exact EF with two agents reduces to a variant of Subset Sum, and an ETH-based lower bound [9] implies that no \(2^{o(m)}\)-time algorithm exists. In particular, the gap between \(t=2\) and \(t=\Omega(m)\) cannot be closed without a breakthrough on ETH-hard problems.

The case \(t = 3\) studied in this paper lies between these two extremes and requires fundamentally new techniques. For the special case of a constant number of types, Maximum Nash Welfare allocations can be computed in polynomial time [10]; however, this does not yield exact EF algorithms, since MNW and EF are inequivalent for indivisible items.

1.0.0.1 Our contribution.

We present the first subexponential algorithm for exact envy-free allocation in the three-type setting, covering goods, chores, and mixed instances. The key insight is geometric: each agent’s valuation vector \(v_i \in \mathbb{R}^3\) defines a normal to a hyperplane, and a feasible allocation can be represented as a point in a convex polyhedron in \(\mathbb{R}^3\). The EF conditions \[\forall\, i,j \in N: \qquad \langle v_i,\, x_i - x_j \rangle \;\geq\; 0\] translate into a system of linear half-space constraints, so the set of all EF allocations forms a bounded convex polytope. We exploit this structure through two novel procedures: EnumerateSeparator: finds a small cycle separator of size at most \(\sqrt{8n}\) on the planar graph induced by the EF polytope; its existence is guaranteed by Miller’s classical planar cycle-separator theorem [11]. Divide: uses the spherical image of the separator to partition the remaining agents into two balanced groups \(L\) and \(R\), each of size at most \(\tfrac{11}{12}n\), such that any EF solutions for \(L\) and \(R\) can be merged into an EF solution for the whole.

Combining these in a divide-and-conquer scheme gives us the ConstructEF algorithm with time complexity \((n \cdot m)^{\mathcal{O}(\sqrt{n})}.\) We also consider an extended setting with fixed agents—agents whose allocations are predetermined as part of the input—and show that the algorithm extends naturally to this case.

1.0.0.2 Related work.

Envy-free allocation of indivisible goods has been studied extensively in the computational social choice community. Exact EF algorithms are known for two agents [12] and for special valuation structures [13]. For the general multi-agent case, the problem is \(\mathop{\mathrm{{\sf NP}}}\)-hard when an EF allocation may not exist [8]. The multi-type (also called multi-dimensional or categorised) setting was studied in [14], [15] but without subexponential guarantees. EF for chores and mixed manna has attracted significant recent attention [16]–[18]; to the best of our knowledge, no subexponential exact algorithm was previously known for any non-trivial multi-agent, multi-type variant of this problem, regardless of the sign of valuations.

1.0.0.3 Organization of the paper.

Section 2 introduces the formal model and notation. 3 presents our main algorithmic result (2) in the form of a recursive subexponential algorithm, explains the idea behind it, proves its correctness and running time bound. Subsequent sections (4, 5 and 6) are devoted to the proof of the main structural result (1) that our algorithm relies on.

2 Preliminaries and Notation↩︎

We consider a fair division problem with a finite set of agents and multiple types of indivisible goods.

2.0.0.1 Agents and goods.

Let \(N = \{1, \dots, n\}=[n]\) denote the set of all agents, \(M\) denote the set of all items and \(m = |M|\) is the total number of items. Let \(T = \{1,2,3\}\) denote the set of item types. For each type \(t \in T\), let \(m_t \in \mathbb{Z}_{\ge 0}\) be the total number of available items of type \(t\): \(m_1+m_2+m_3 = m\). In our algorithms, we will deal with subsets of goods, characterized by three non-negative integers \(k_i\le m_i\), for each \(i\in T\). We denote \(\mathbf{k} = (k_1, k_2, k_3)\).

2.0.0.2 Valuations.

Each agent \(i \in N\) has additive linear valuations over item types, represented by a vector \[{v}_i = (v_i(1), v_i(2), v_i(3)) \in \mathbb{R}_{\ge 0}^3.\] The only restriction we put on a vector \(v_i\) for each \(i\) is that \(v_i\) is non-degenerate, that is, \(v_i\neq(0,0,0)\). Given an allocation \(x_i \in \mathbb{Z}_{\ge 0}^3\), the utility of agent \(i\) is defined as \[u_i(x_i) = \sum_{t \in T} v_i(t)\cdot x_{i,t} = \langle v_i, x_i \rangle.\]

2.0.0.3 Allocations.

Let \(A \subseteq N\) be set of agents. An allocation for \(A\) is a collection \(X = (x_i)_{i \in A}\), where each \[x_i = (x_{i,1}, x_{i,2}, x_{i,3}) \in \mathbb{Z}_{\ge 0}^3\] specifies the number of items of each type assigned to agent \(i\). An allocation is feasible for \(\mathbf{k}\) if it satisfies the resource constraints, \(\sum_{i \in A} x_{i,t} = k_t\) for each \(t \in T\).

2.0.0.4 Envy-freeness.

An allocation \(X = (x_i)_{i \in A}\) is called envy-free (EF) if for any pair of agents \(i,j \in A\), \(u_i(x_i) \ge u_i(x_j)\).

2.0.0.5 Fixed agents.

In the extended setting, we are also given a subset of agents \(F \subseteq A\) whose allocations are fixed in advance. For each \(i \in F\), the vector \(x_i \in \mathbb{Z}_{\ge 0}^3\) is specified as a part of the input.

We denote the remaining agents by \(A_{\text{free}} = A \setminus F\). The goal is to compute allocations \(x_i\) for all \(i \in A_{\text{free}}\) such that the combined allocation over all agents \(A\) is feasible and envy-free.

We say that two partial allocations agree, if for each agent that is given a bundle in both allocations, this bundle is the same in both allocations for this agent.

2.0.0.6 Geometric interpretation.

We view each allocation vector \(x_i \in \mathbb{R}^3\) as a point in \(\mathbb{R}^3\), and each valuation vector \(v_i\) as a normal vector. The envy-freeness condition between agents \(i\) and \(j\) with bundles \(x_i\) and \(x_j\) respectively can be written as \[\langle v_i, x_i - x_j \rangle \ge 0.\] That is, \(x_i\) and \(v_i\) define a half-space for envy-free bundles \(x_j\) in \(\mathbb{R}^3\). Thus, the set of envy-free allocations can be interpreted as a region defined by linear constraints in \(\mathbb{R}^3\). This is also the reason why we forbid degenerate valuations: such valuations do not define half-spaces.

3 Algorithm↩︎

In this section, we describe the recursive algorithm \(\texttt{ConstructEF}\) for finding an envy-free allocation, assuming the existence of procedures \(\texttt{EnumerateSeparator}\) and \(\texttt{Divide}\). As announced in the introduction, these two procedures allow to fix a certain allocation and split the agents into two groups that are not very much different in size. We introduce their properties in the following technical result.

We will prove 1 later. Before that, we use it to prove the main result of this paper and present ConstructEF.

3.1 Description of ConstructEF↩︎

3.1.0.1 High-level idea.

The algorithm follows a divide-and-conquer paradigm. The key idea is to exploit the geometric structure of envy-free allocations. In particular, we assume that any feasible envy-free allocation induces a geometric object (a convex polyhedron). Its planar graph admits a small separator of size \(\mathcal{O}(\sqrt{n})\) (see 1).

The algorithm proceeds as follows:

• It tries to guess a small set of agents together with their allocation — \(X_S\).

• “Removing” \(X_S\) separates the remaining agents into the left part and the right part. \(L\) and \(R\) are formed as sets of the agents of the corresponding parts, together with the separator agent set \(S\) (so \(L\cap R=S\) and \(L\cup R=A\)).

• The algorithm tries every possible way to split the remaining items between the parts.

• For each such guess, the algorithm recursively constructs envy-free allocations on \(L\) and \(R\), treating \(X_S\) as a set of agents with fixed allocations. This way, the two independent solutions agree on \(S\).

• Finally, it combines the solutions if both recursive calls succeed.

Since the separator is small, the number of possibilities for \(X_S\) is subexponential. Since the separator is balanced, that is, splits the agents in not very small parts, the depth of the recursion is logarithmic in the number of agents. This leads to the overall subexponential running time.

3.1.0.2 Detailed description.

ConstructEF is present in the form of pseudocode in 2. It exactly implements the high-level idea above. The only technical addition is the recursion base: when \(A\) is small, the algorithm finds a solution by brute force (the ExhaustiveSearch procedure). Note that the algorithm keeps track of the fixed allocations \(X_F\), and these allocations are propagated in recursion and distributed between the two recursion parts together with the agents. We give description of this and another newly-introduced procedures below.

3.1.0.3 Exhaustive search.

For completeness, we present the \(\texttt{ExhaustiveSearch}\) procedure in 3 in the form of pseudocode. The idea is to enumerate all feasible allocations of items to agents in \(A\), respecting: (i) the fixed allocations \(X_F\), (ii) the total item counts \(\mathbf{k}\), and check the envy-freeness condition.

The procedure checks all feasible allocations consistent with the resource constraints and fixed agents. Since the search space is finite and all allocations are explicitly tested, it returns an envy-free allocation if one exists, and \(\bot\) otherwise. The number of allocations is bounded by \((k_1 \cdot k_2 \cdot k_3)^{|A \setminus F|}\), this determines the running time of the procedure. It is used by our main algorithm only in case \(|A|=\mathcal{O}(1)\), so any run of ExhaustiveSearch runs in time polynomial in \(m\).

3.1.0.4 Envy-freeness check.

IsEF is a polynomial-time procedure that evaluates whether a given (partial) allocation is envy-free and the constraints on the number of items are satisfied for each type.

3.2 Correctness and running time analysis↩︎

In what remains of this section, we prove that ConstructEF is correct and runs in time subexponential in \(n\). We start with proving the correctness.

3.2.0.1 Running time analysis.

We now analyze the running time of \(\texttt{ConstructEF}\), using the notion \(p = |A|\), \(K = (k_1+1) \cdot (k_2+1) \cdot (k_3+1)\). To proceed, we clarify what does “efficient” means in the statement of 1. First, \(\texttt{Divide}(A,X_S)\) runs in polynomial time, i.e. it takes \((pK)^{\mathcal{O}(1)}\) time. Second, \(\texttt{EnumerateSeparator}\) runs in time \((pK)^{d\sqrt{p}}\) for some universal constant \(d\ge 1\), given by the upper bound to the number of possible agent sets of size \(\mathcal{O}(\sqrt{p})\) and possible partial allocations.

Our goal is to show that the overall running time is subexponential in the number of agents.

3.2.0.2 Recurrence for \(\texttt{ConstructEF}\).

Let \(T(p,\mathbf{k})\) denote the worst-case running time of \(\texttt{ConstructEF}\) on an instance with \(p\) agents and item quantity vector \(\mathbf{k}=(k_1,k_2,k_3)\). We prove by induction that \(T(p,\mathbf{k})\le (pK)^{c\sqrt{p}}\) for some constant \(c>d\) to be specified later. We naturally assume that \(T(p',\mathbf{k}')\le T(p,\mathbf{k})\) for any \(p'\le p\) and \(\mathbf{k}'\le \mathbf{k}\).

If \(p \le 1200\), the algorithm calls \(\texttt{ExhaustiveSearch}\). Since this bound is just a constant, we have \(T(p,\mathbf{k})=(pK)^{\mathcal{O}(1)}\) in this case.

Let us move on to \(p>1200\). For each candidate separator \(X_S\) (at most \((pK)^{d\sqrt{p}}\) choices), the algorithm:

• computes \((L,R)\gets \texttt{Divide}(A, X_S)\) in polynomial time;

• iterates over all vectors \(\mathbf{k}^L=(k_1^L,k_2^L,k_3^L)\) satisfying, for each \(t\in [3]\), \(k_t^S\le k_t^L \le k_t\).

The number of such vectors is at most \(K\). For each such choice, the algorithm makes two recursive calls, one on \(L\) and one on \(R\).

By the separator property, both sets \(L\) and \(R\) contain at most \(\alpha p\) agents for some constant \(\alpha<1\) (\(C_2\) in 1). Thus, \(|L| \le \alpha p\) and \(|R| \le \alpha p,\) and the recursive call on each of them runs in at most \(T(\alpha p, \mathbf{k})\) time. Then \[T(p,\mathbf{k}) \le (pK)^{d\sqrt{p}}\cdot K\cdot (T(\alpha p,\mathbf{k})+T(\alpha p,\mathbf{k})).\] Equivalently, we may write \[T(p,\mathbf{k}) \le (pK)^{d\sqrt{p}+2}\cdot T(\alpha p,\mathbf{k}).\] Using the bound on \(T(\alpha p, \mathbf{k})\) by induction, \[T(p,\mathbf{k}) \le (pK)^{d\sqrt{p}+2}\cdot (pK)^{c\sqrt{\alpha p}}=(pK)^{(d+c\sqrt{\alpha})\cdot \sqrt{p}+2}.\] It suffices to use that \[(d+c\sqrt{\alpha})\cdot \sqrt{p}+2\le c\sqrt{p},\] so choose any \(c\) satisfying \[2\le (c(1-\sqrt{\alpha})-d)\cdot \sqrt{1200}\] to complete the proof of \(T(p,\boldsymbol{k})\le (pK)^{\mathcal{O}(\sqrt{p})}\).

3.2.0.3 Summing up.

The discussion above leads to the following theorem, which is the main result of the paper.

4 Enumerating Balanced Separators↩︎

The rest of the work is devoted to the proof of 1, that comes in several sections. In this section, we introduce and study the EnumerateSeparator procedure.

As noted in the overview, any EF allocation can be represented as a convex polyhedron \(P\) in \(\mathbb{R}^3\), and the graph of \(P\) is planar. The procedure EnumerateSeparator enumerates candidate \((S, X_S)\), where \(X_S\) is a vector of separator agents with a partial allocation for it, such that the cycle \(C\) induced by \(X_S\) on \(P\) is a valid planar cycle separator and \(S\) is set of unique agents, presented in \(X_S\). If an EF allocation exists, the correct separator is guaranteed to be yielded at some point during enumeration. The pseudocode is present in 4.

We move on to the discussion and formal analysis of how the procedure works and theoretical facts it relies on.

Bounding planes. To handle our convex polyhedron properly, we require that it is bounded. Note that any bundle point \(x_i\) lies in a cube with extremal points \((0,0,0)\) and \((k_1,k_2,k_3)\). We call the halfspace sequence \((\{x \geq 0\}, \{y \geq 0\}, \{z \geq 0\}, \{x\leq k_1\}, \{y \leq k_2\}, \{z \leq k_3\})\) the bounding planes vector. These planes are used to complete set of agents planes, so the “envy-freeness polyhedron” is always bounded. They can appear as a part of the separator; that is why \(S\) is a suset of \(A\) plus \(6\) additional imaginary “agents”.

4.0.0.1 Description of CheckAllocation.

The predicate \(\texttt{CheckAllocation}(X_S, \mathbf{k})\) verifies whether \(X_S\) can serve as a valid separator in some EF allocation. \(X_S\) represents vector of planes, forming separator edges an vertices.

Note that here \(X_S\) technically is a sequence of planes and points, and not just a partial allocation as we treated is in previous sections. This is only a minor technical detail used by EnumerateSeparator and Divide. \(\texttt{CheckAllocation}\) works as follows.

First, it checks that \(X_S\) respects the item counts: \(\sum_{i \in S\cap A} (X_S)_{i} \leq \mathbf{k}\). If this fails, it returns False. We also check consistency here, if \(i\) presented in \(X_S\) in tuple \((i, (x_{i,1}, x_{i,2}, x_{i,3}))\) any other appearance in vector should happen with exactly same item allocation. Otherwise we return False.

Next, for each agent with allocation \((i, (x_{i,1}, x_{i,2}, x_{i,3})) = (X_S)_i\), it constructs the hyperplane with normal \(v_i\) (the valuation vector of \(i^\text{th}\) agent in \(A\)) passing through the point \((x_{i,1}, x_{i,2}, x_{i,3})\). If \(i > |A|\) we take element with index \(i-6\) in bounding planes vector and ignore the point itself.

For each \(i\) we take hyperplane \(H_i\) constructed in step above. Now we have sequence \(V\), which contains \(4\ell + 1\) hyperplanes. Let us split first \(4\ell\) hyperplanes into \(\ell\) groups, each one formed of 4 consecutive elements. For each group, the four corresponding hyperplanes are intersected; if the intersection is not a single point, the check fails.

The resulting \(\ell\) intersection points are connected in their natural order to form a candidate cycle \(C\) (a closed polygonal chain in 3D space). If \(C\) is not a simple polyline, the check fails.

Let \(P'\) be the convex polyhedron formed by all hyperplanes \(\{H_i\}_{i \leq 4\ell + 1}\). The check then verifies that: every vertex of \(C\) is a vertex of \(P'\); every edge of \(C\) is either an edge of \(P'\) or a diagonal of a face of \(P'\); all \(\ell\) hyperplanes appear as faces of \(P'\); and each face of \(P'\) contains at most one diagonal of \(C\). Finally, it checks that the hyperplane \(H_{4\ell+1}\) (last plane in \(V\)) contains no vertex of \(C\). \(C\) is called separator cycle for \(X_S\). If all checks pass, \(\texttt{CheckAllocation}\) returns True.

4.0.0.2 Correctness.

Correctness proof in this section relies on a classical theorem, established in [11].

Now we can formulate the correctness lemma, which further explains why point 2 of 1 holds.

4.0.0.3 Running time.

We move on to giving an upper bound to the running time. We follow the same \(p, K\) notation as before.

To summarize, we note that point [prop:size] of 1 follows from 2; and EnumerateSeparator runs efficiently (in subexponential time).

5 Dividing the Agents↩︎

In this section we describe the Divide procedure, which takes the separator \(X_S\) (as a sequence of hyperplanes) produced by EnumerateSeparator and partitions the remaining agents into two balanced groups. The construction relies on the notion of the spherical image of a convex polyhedron and certain of its structural properties.

We will use the following property of spherical images.

5.0.0.1 High-level idea.

The high-level idea of Divide is to take the output of EnumerateSeparator in the form of a convex polyhedron and a closed polyline, construct the spherical image \(\Gamma\) of the polyline and split the agents according to their valuation point placement relative to \(\Gamma\) as a spherical curve.

5.0.0.2 Construction of \(\Gamma\).

Recall that EnumerateSeparator yields a set of hyperplanes whose intersection defines a convex polyhedron \(P'\), and produces a cycle on the graph of \(P'\) that serves as a separator. We construct a corresponding curve \(\Gamma\) on \(\mathbb{S}\) as follows.

1. Let \(P'\) be the convex polyhedron formed by the hyperplanes fixed in EnumerateSeparator.

2. Compute the spherical image \(s(P')\). By Theorem 4, the image \(s(v)\) of each vertex \(v\) of \(P'\) is a convex spherical polygon, and the image \(s(e)\) of each edge \(e\) of the separator cycle is either a geodesic arc (if \(e\) is an edge of \(P'\)) or a single point (if \(e\) is a face diagonal, in which case \(s(e) = s(f)\) for the face \(f\) containing \(e\)).

3. For each edge \(e\) of the separator cycle : if \(s(e)\) is an arc, take its midpoint; if \(s(e)\) is a point, take that point. Connect the resulting points in the cyclic order inherited from the separator cycle to obtain the polyline \(\Gamma\) (see Figure 5).

4. The curve \(\Gamma\) divides \(\mathbb{S}\) into two open regions. For each agent \(i \in A \setminus S\), place its preference vector \(u_i\) (the \(i\)-th row of \(U\)) on \(\mathbb{S}\) and assign agent \(i\) to \(L\) or \(R\) according to which region contains \(u_i\).

5.0.0.3 Correctness.

We show that any convex polyhedron (the complete solution) that extends \(P'\) (partial allocation given by the separator) agrees with the division of the agents. First, split algorithm is correct, since Lemma 4 holds, so \(\Gamma\) divides \(\mathbb{S}\) into two open regions by Jordan curve theorem. Next, by Lemma 5 we can see that if we build \(\Gamma\) on spherical image of any complete solution, we will get exactly same split, since \(\Gamma\) and spherical images of agents planes does not change.

5.0.0.4 Balancedness.

By Lemma 4 and the Jordan curve theorem, \(\Gamma\) divides \(\mathbb{S}\) into exactly two open regions. By Theorem 4, each face of \(s(P)\) corresponds to a vertex of \(P\) and hence to an agent in \(A\). Since the separator cycle is produced by Miller’s theorem (Theorem 3), both regions contain at least \(\frac{1}{3}|A|\) faces of \(s(P)\).

By Euler’s formula \(V - E + F = 2\), together with \(E \geq \frac{3}{2}F\) (every face has at least 3 edges, every edge borders exactly 2 faces), we obtain \(V \geq \frac{1}{2}F\). Hence each region contains at least \(\frac{1}{2} \cdot \frac{1}{3}|A| = \frac{|A|}{6}\) free agents (agents in \(A\setminus S\)), giving \(|L \setminus S|,\; |R \setminus S| \;\geq\; \frac{|A|}{6} - |S| \geq \frac{|A|}{12},\) so \(|L|, |R| \leq\frac{11}{12}|A|.\) This unequality establishes the balancedness constant \(C_2 = \frac{11}{12}\) in 1. \(\frac{|A|}{6} - |S| \geq \frac{|A|}{12}\) is satisfied since if we run Divide, number of agents is over 1200 and \(|S| \leq \sqrt{8n} \leq \frac{1}{12}n\). The point [prop:balance] of 1 follows immediately from the above reasoning.

6 Merging Solutions from Two Parts↩︎

In this section we prove that once Divide has partitioned the agents into two groups and independent EF allocations have been found for each part, their union is an EF allocation.

6.0.0.1 Setup.

Let \(L\) and \(R\) be the two parts produced by Divide, with \(L \cap R = S\) where \(S\) is the separator set. Let \(X_L\) and \(X_R\) be EF allocations for \(L\) and \(R\) respectively, where in each case the agents in \(S\) are treated as fixed with allocation \(X_S\). Define \(X = X_L \cup X_R\).

6.0.0.2 Main argument.

We show that \(X\) is envy-free for all of \(A\). Suppose for contradiction that \(X\) is not EF. Then there exist agents \(a_L \in L \setminus S\) and \(a_R \in R \setminus S\) such that \(a_L\) envies \(a_R\) under \(X\).

Consider the convex polyhedron \(P'\) formed by the hyperplanes of \(S\) together with the hyperplanes \(H_L\) and \(H_R\) corresponding to \(a_L\) and \(a_R\) respectively. Assuming for now that \(P'\) is non-degenerate (no two hyperplanes coincide), we can form its spherical image \(s(P')\).

By the construction in Divide, the curve \(\Gamma = s(C)\) is a simple closed curve on \(\mathbb{S}\) that separates \(s(H_L)\) from \(s(H_R)\). By Lemma 5, no edge of \(s(P')\) crosses \(\Gamma\) except for images of edges of \(C\), so \(a_L\) and \(a_R\) are not adjacent in \(P'\). It follows that every face of \(P'\) adjacent to \(H_R\) is a face of some agent in \(S\), and each such face lies on the correct side of \(H_L\). Therefore every point in the face corresponding to \(a_R\) is not envied by \(a_L\), contradicting the assumption.

It remains to show that \(P'\) is always non-degenerate, i.e.that \(H_L\) and \(H_R\) cannot simultaneously make \(P'\) singular. Recall that EnumerateSeparator yields, as its last element, a hyperplane \(H_F\) that contains no vertex of the separator cycle \(C\) (last condition of CheckAllocation). This hyperplane \(H_F\) lies strictly on one side of \(C\): for one of the two parts, say \(L\), it lies on the same side as the non-separator faces of \(X_L\); for the other part \(R\), it lies on the opposite side.

Consequently, in the allocation \(X_L\) all faces lie on the same side of \(C\) as \(H_F\), while in \(X_R\) all faces lie on the opposite side. When we form the polyhedron determined by \(S\) alone, the faces \(H_L\) and \(H_R\) therefore lie on opposite sides of \(C\). Adding both \(H_L\) and \(H_R\) simultaneously cannot make \(P'\) singular, since any singularity would require them to be on the same side, which is impossible.

We proved that \(X = X_L \cup X_R\) is an EF allocation for all of \(A\), so the last point (point [prop:merge]) of 1 holds. This completes the proof of Theorem 1.

7 Conclusion↩︎

In this work, we presented a subexponential algorithm for finding an envy-free allocation of indivisible items among \(n\) agents when items come in three distinct types. The algorithm handles goods, chores, and mixed instances uniformly: agents may assign positive, negative, or mixed valuations to item types, and the EF guarantee holds in all cases. Correctness is established via a geometric representation of EF allocations as bounded convex polyhedra in \(\mathbb{R}^3\), combined with a divide-and-conquer decomposition based on Miller’s planar cycle-separator theorem. We also extended the result to the setting with fixed agents, where a subset of allocations is given as part of the input.

The present paper closes the open case \(t = 3\), reducing the complexity from brute-force exponential to subexponential, and fits into a broader complexity picture parameterised by the number of types: polynomial at \(t = 2\), subexponential at \(t = 3\), and \(2^{\Omega(m)}\)-hard under ETH for \(t = \Omega(m)\).

7.0.0.1 Open problems and future directions.

The most natural open question is whether our result generalises to an arbitrary number of item types. We conjecture that for any fixed number of types \(t\), there exists an algorithm with time complexity \[(nm)^{\mathcal{O}\left(n^{1 - \frac{1}{t-1}}\right)}.\] Proving this conjecture for general \(t\) would likely require a higher-dimensional analogue of the planar separator technique, possibly drawing on separator theorems for \(d\)-dimensional polytopes or higher-genus surfaces.

Beyond the complexity question, several directions remain open.

• Tightness. Is the exponent \(\sqrt{n}\) optimal for \(t = 3\), or can it be improved? A matching lower bound under standard complexity assumptions would strengthen the result.

• Approximate fairness. Can the geometric approach be adapted to compute EF1 or EFX allocations more efficiently than existing combinatorial methods, in particular for chores and mixed instances where EFX existence is still open?

• Item-specific perturbations. What happens when agents have valuations that are not purely type-based, but include item-specific additive perturbations? The convex-polyhedron representation breaks down in this setting, and new geometric tools would be needed.

8 Acknowledgments↩︎

This work was supported by the Ministry of Economic Development of the Russian Federation (IGK 000000C313925P4C0002), agreement №139-15-2025-010

References↩︎