Approximate Envy-Freeness in Graphical Cake Cutting

The strongest positive case is a high-multiplicity, rational-clone mirror of Theorem 4.

The paper’s Theorem 4, proved here rather than cited, says that for a star graph with \(m\) edges and arbitrary agent valuations, a \((3+\epsilon)\)-EF connected allocation can be computed in time polynomial in \(n\), \(m\), and \(1/\epsilon\). This is a genuine computational anchor: it is an explicit approximation algorithm whose input population can naturally contain many repeated valuation types.

My mirror is Typed-Star-AEF\(_\infty\). An instance consists of a star graph \(G\), a finite set of valuation types \(T\), rational masses \(\mu_t\) summing to \(1\), and one normalized additive valuation \(v_t\) for each type. Valuations may be represented in the paper’s Robertson–Webb query model, or by rational piecewise-constant densities. For every integer \(N\) such that \(N\mu_t\in\mathbb Z\), form the finite clone instance \(I_N\) containing \(N\mu_t\) agents of type \(t\).

A solution is a uniform allocation procedure producing, for every such \(N\), a partition \(A^{(N)}\) of \(G\) into connected shares, one per clone. Its objective is the worst multiplicative envy ratio \(R_N=\max_{i,j}v_{\operatorname{type}(i)}(A_j^{(N)})/v_{\operatorname{type}(i)}(A_i^{(N)})\). The continuous question is: given \(\epsilon>0\), output a procedure for which \(R_N\le 3+\epsilon\) for every sufficiently large \(N\), or equivalently determine whether the asymptotic optimum \(\limsup_{N\to\infty}\min_A R_N\) is at most \(3+\epsilon\).

This is a direct high-multiplicity mirror at every finite realization: the graph, connectedness requirement, valuation semantics, and pairwise envy predicate are unchanged. Only the named population is replaced by its rational type histogram \(\mu\). A convincing regime is a large pool of road, railway, or cable-maintenance contractors operating on hub-and-branch networks. Contractors repeat a small number of complete profiles—same valuation densities, eligibility, and operating parameters—while \(N\) is very large relative to \(|T|\). The paper’s own maintenance interpretation makes this recognizable to the authors.

The inherited mirror is Class A: Theorem 4 already supplies the required family of allocations. The genuinely new ChoCo question is whether the family can be generated from the compressed input \((G,T,\mu)\) without expanding all \(N\) clones. The natural conjecture is still tractable: the four phases of the paper’s algorithm should admit mass-aware versions that process type masses and split clone classes symbolically. That is a real algorithmic question, not merely a relabeling.

A second, independently plausible anchor is Theorem 6, also proved here. It states that for arbitrary graphs and identical valuations, a \((2+\epsilon)\)-EF connected allocation is computable in polynomial time. Its mirror, Typed-Graphical-MEF\(_\infty\), takes a graph \(G\), one common valuation \(v\), and the high-multiplicity society \(\mu=(1)\). It asks for a uniform family of connected allocations to \(N\) identical clones with \(\limsup_N \max_i v(A_i)/\min_i v(A_i)\le 2+\epsilon\). Theorem 6 gives this family; Theorem 7 gives the stronger exact \(2\)-EF guarantee on stars. This is a weaker population mirror because there is only one type, but it is particularly author-recognizable: the paper explicitly motivates identical valuations by towns distributing street-maintenance responsibility among many contractors. Its expected classification is also Class A, with the paper’s minimum–maximum balancing procedure as the starting point.

I would not anchor on Theorem 3’s \(1/2\)-additive guarantee. With a fixed cake and \(N\to\infty\), individual utilities vanish, so a constant additive bound becomes increasingly weak. The multiplicative anchors are better because their ratios remain meaningful in the high-multiplicity limit.

The weakest point is that a literal atomless population cannot each receive a positive-length connected piece of one fixed finite cake. Replacing the problem by fractional type-level coverage would erase precisely the connectivity and individual-envy structure that makes the paper interesting. My mirror therefore uses the rational-clone limit rather than pretending that an uncountable family of positive bundles exists. That makes it an extension of the paper’s finite model rather than a brand-new continuum allocation theorem, but it preserves the original computational predicate exactly and gives a clear programme: characterize the asymptotic optimum, design a type-compressed algorithm, and establish rounding or clone-consistency bounds between the mass representation and finite allocations.