Almost envy-free allocations with connected bundles

The strongest honest positive case is a two-anchor case. The lead is the paper’s cited hardness anchor; the paper’s strongest in-house computational anchor is Theorem 4.3.

The continuous model I would use throughout is this. Let \(G=(V,E)\), let \(\mathcal C(G)\) be its connected vertex sets, and let \(T=\{1,\ldots,\tau\}\) be complete valuation types. Type \(t\) has a monotone valuation \(u_t:\mathcal C(G)\to\mathbb Q_{\ge0}\), and occupies mass \(\mu_t\), where \(\sum_t\mu_t=1\). There is also a per-capita supply \(q_v\) of copies of each item-location \(v\). An allocation is a family \(x_{t,B}\ge0\), where \(x_{t,B}\) is the mass of type \(t\) receiving the integral connected bundle \(B\), satisfying

\[ \sum_{B\in\mathcal C(G)}x_{t,B}=\mu_t \]

and

\[ \sum_t\sum_{B\ni v}x_{t,B}=q_v \]

for every \(v\). Thus only population mass is fractional: every individual still receives an integral connected bundle. With rational data, multiplying by a common denominator gives a finite high-multiplicity instance with repeated agents and repeated item copies.

For a bundle \(B\), write \(u_t^-(B)\) for its value after removing the best admissible outer item, as in the paper. The natural continuous EF1 condition is that, whenever \(x_{t,B}>0\) and \(B'\) is occupied by positive mass,

\[ u_t(B)\ge u_t^-(B'). \]

This says that every individual of type \(t\) is EF1 relative to every bundle actually received by someone. It is the direct mass version of the paper’s underlying problem, not cake-cutting or fractional allocation of an individual bundle.

My lead anchor is the result cited in the conclusion as “Theorem 2” of Deligkas, Eiben, Ganian, Hamm, and Ordyniak. The paper states that deciding whether an EF1 allocation exists on a given graph is NP-hard; the hardness already holds when the graph is a star and the agents have binary additive valuations. This result is cited from elsewhere, not proved in the paper.

The corresponding problem is Continuous Connected-EF1 Feasibility:

Given a graph \(G\), binary additive valuation types \(u_t(B)=\sum_{v\in B}a_{t,v}\) with \(a_{t,v}\in\{0,1\}\), rational type masses \(\mu\), and rational per-capita item supplies \(q\), decide whether there exists an \(x\) satisfying the supply equations and the continuous EF1 condition above.

The regime is plausible: a large population consists of recurring cohorts with identical approval patterns for connected facilities, plots, or time blocks on a hub-and-spoke network. The number of people can be enormous while the number of valuation types remains modest. A finite instance with \(n\) agents and one copy of each item is recovered by setting \(\mu_t=n_t/n\) and \(q_v=1/n\).

I expect the unrestricted version to be Class B: hardness should largely survive because the cited reduction’s combinatorics live in the graph and the connected-bundle choices, not in the names of individual agents. The genuinely interesting question is whether hardness survives when \(\tau\ll n\). The cited theorem does not establish that compressed-type claim, so this is a research conjecture rather than a transferred theorem.

My second anchor is Theorem 4.3, proved in this paper. It states that, on a path with three agents and arbitrary monotone valuations, the discrete moving-knife protocol finds a connected EF1 allocation in \(O(m)\) time. The result includes the full algorithmic claim: the procedure terminates, returns EF1, and runs linearly in the number \(m\) of items, using lumpy ties and median lumpy ties.

Its continuous mirror is Continuous Three-Type Path-EF1:

Given a path \(P=(v_1,\ldots,v_m)\), three monotone valuation types \(u_1,u_2,u_3\) over intervals, rational masses \(\mu_1,\mu_2,\mu_3\), and rational per-capita item supplies \(q_v\), find a mass allocation \(x_{t,B}\) in which every individual receives an integral interval and the continuous EF1 inequalities hold.

The authors should recognise this as their problem: the path, connected bundles, monotone valuations, EF1 notion, and moving-knife order are unchanged. Only the population is replaced by repeated valuation types, with aggregate assignment mass recorded by \(x\). I would expect this fixed-three-type path problem to be Class A, probably via a finite support lemma followed by a sweep or flow computation. The ordered path and the paper’s lumpy-tie machinery provide exactly the structure one would hope to exploit. That expectation is not proved by Theorem 4.3: once a type may split across several intervals, the support condition becomes a new issue.

This mirror generates several worthwhile questions: whether the \(O(m)\) bound survives; whether arbitrary \(\tau\) admits an algorithm polynomial in \((m,\tau,L)\); whether the paper’s EF2 Theorem 5.4 has a continuum analogue for arbitrary \(\tau\); and whether finite high-multiplicity solutions can be rounded with controlled loss.

I would not anchor on Theorems 5.4 or 6.2, despite their importance, because they are existence theorems rather than named complexity classifications. Nor would I claim that the paper already contains a continuous algorithm. Its contribution is discrete, although it explicitly imports ideas from cake-cutting.

The weakest point is the population-copy construction itself. Splitting a type’s mass among several bundles can create feasible continuous allocations with no exact finite EF1 counterpart, and the cited NP-hardness reduction may depend on having many distinct valuation types. Thus hardness transfer is secure only as an expectation in the unrestricted model. The positive case nevertheless survives: the model is a genuine high-multiplicity version of the paper’s connected EF1 problem, preserves integral bundles, has a realistic repeated-cohort interpretation, and exposes two concrete computational questions rather than merely replacing \(n\) by a probability distribution.