How Many Extra Cuts Make Fair Division Easy?

Suppose $n$ people must split a ribbon among $p$ groups so that every person agrees each group got exactly a $1/p$ share by their own measure. A classical topological theorem guarantees this is possible with $n(p-1)$ cuts. Finding those cuts, however, is provably hard. It is complete for complexity classes built on counting arguments: PPA for $p=2$, and PPA$_p$ (search problems whose solutions exist because of a counting argument modulo $p$) for general $p$. With very many cuts the problem is trivial: cut every homogeneous stretch of ribbon into $p$ equal pieces. With fewer cuts than the topological minimum, a solution may not exist at all.

The ribbon problem therefore carries a two-objective trade-off, number of cuts against worst-case unfairness. This proposal treats that trade-off curve as the primary object and asks where along it the computational difficulty lives. The tools come from multi-objective optimization: trade-off curves, approximate Pareto sets, and representative solutions. The anchor comes from topology: the $\mathbb{Z}_p$-STAR-TUCKER Lemma, a discrete lemma about labelings with $p$-fold rotational symmetry that pins down one hard point on that curve.

The core claim is that the known results describe only the two ends of this curve. Nobody has asked how fast hardness decays as cuts are added beyond $n(p-1)$. We conjecture a sharp threshold. Hardness survives $n(p-1)+r$ cuts for $r$ sublinear in $n$, and collapses to polynomial time once $r$ is a constant fraction of $n$ for bounded-complexity valuations. We will prove as much of this as we can, and measure the rest on instances generated by the hardness reductions themselves.

What is known and where the gap sits

The hard end is well mapped. Consensus halving is PPA-complete and The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich show that approximate two-way consensus with exactly $n$ cuts is PPA-complete. Consensus-Halving: Does It Ever Get Easier? keeps that hardness even when each agent's valuation is two uniform blocks. The same paper also supplies the only existing foothold on the "extra cuts" axis. For single-block valuations, exact halving is solvable by linear programming when $2n-\ell$ cuts are allowed, for constant $\ell$. That result motivates this proposal. It shows that cut budget and complexity interact. It also stops at single blocks, $p=2$, and one specific budget. The same paper proves that approximate consensus-$1/3$ division is PPAD-hard, so the $p\ge3$ regime is where the open problems concentrate.

A Topological Characterization of Modulo-p Arguments and Implications for Necklace Splitting supplies the method. It introduces the $\mathbb{Z}_p$-STAR-TUCKER Lemma, proves PPA$_p$-completeness of $p$-fold Tucker and Borsuk-Ulam variants, and places $p$-thief necklace splitting in PPA$_p$ without matching hardness. The Classes PPA-k: Existence from Arguments Modulo k gives the underlying class definitions. Two other results constrain the design. Constant Inapproximability for PPA indicates that hardness persists at constant error when the cut budget is exactly $n$. Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem shows that exact solutions are harder than approximate ones. We therefore study approximate solutions throughout and treat the exact case only at the easy end.

The multi-objective side supplies the lens but not the theorems. How Good is the Chord Algorithm? shows that approximating a convex trade-off curve with a weighted-sum oracle costs $\Theta(\log m + \log\log(1/\epsilon))$ in the worst case. Representative Solutions for Bi-Objective Optimisation computes small representative sets along a two-objective front with polynomially many solver calls. Our curve is two-objective, with cut count and unfairness, so these tools apply directly. One difference matters. Our front has only polynomially many points, because the cut count is an integer bounded by the instance description. The obstacle is therefore not the front's size, the usual worry in multi-objective optimization. It is the cost of each point. To our knowledge, no paper in the file studies a trade-off front whose points fall in different complexity classes.

Research Program

Write $\mathrm{Div}(n,p,c,\epsilon)$ for the problem of finding at most $c$ cuts and an assignment of pieces to $p$ groups so that every agent values every group within $\epsilon$ of $1/p$. The trade-off curve is the function $\epsilon^*(c)$, the least achievable unfairness at budget $c$. Topology gives $\epsilon^*(n(p-1))=0$. Breakpoint splitting gives exactness at $c$ proportional to the total number of valuation blocks. The program has three parts.

The first part is algorithmic and asks what extra cuts buy. The natural mechanism is dimension reduction. Extra cuts can be spent to satisfy some agents locally, which removes them from the symmetric search. That shrinks the dimension of the Tucker-type instance that path-following must solve. We will extend the single-block linear program to two-block valuations and to general $p$. We will then build a hybrid solver that spends $r$ surplus cuts on local fixes and runs $\mathbb{Z}_p$-Tucker path-following on the remaining $n-r'$ agents. The target theorem is a runtime exponential only in the residual dimension. If proved, it yields polynomial time for $r=\Omega(n)$ under bounded block counts.

The second part concerns hardness that survives surplus cuts. We will re-examine the two-block reduction of Filos-Ratsikas et al., built from equivariant arithmetic gates, and the $p$-fold constructions of the modulo-$p$ paper. The question is whether a solver given $n(p-1)+r$ cuts can exploit the surplus to bypass the gadgets. The natural route is padding: replicate the hard instance so that $r$ surplus cuts can only help a vanishing fraction of the copies. This gives hardness for $r=o(n)$ if the gadgets resist local repair. For $p=3$ the same question applies to the known PPAD-hardness of consensus-$1/3$ division: does it survive surplus cuts? A negative answer would be informative. It would mean that hardness sits only at the exact topological budget.

The third part characterizes the front empirically. For small instances we compute $\epsilon^*(c)$ exactly and record the solver effort at each budget. We then test whether effort peaks at $c=n(p-1)$ and decays with a measurable profile. This measured profile is what the theory should explain.

Baselines

The naive reference point is breakpoint splitting. It cuts every homogeneous block into $p$ equal parts, which is exact, runs in linear time, and uses a number of cuts proportional to the total block count. Any method that claims to beat it must reach $\epsilon^*$ within a small tolerance at substantially fewer cuts. Beside it we run the greedy procedure and the $2n-\ell$ linear program from Consensus-Halving: Does It Ever Get Easier? on the single-block instances where they apply. They are the only existing polynomial-time methods that use surplus cuts.

The strongest general competitor for computing the whole front is exact enumeration with the $\epsilon$-constraint method. This means one mixed-integer program per cut budget, minimizing unfairness, which is exact on piecewise-constant valuations. We pair it with the RepSet procedure of Representative Solutions for Bi-Objective Optimisation, adapted to our two objectives. That paper reports RepSet finding 5 representative solutions in 460 seconds, against over 13,500 seconds for full $\epsilon$-constraint enumeration, on 2000-variable set covering. That figure comes from a different benchmark and serves only as a sanity reference for the machinery. We found no reported result on Lacuna for empirical runtimes or trade-off curves of consensus division under a varying cut budget, so all numbers on our instances will be new.

All methods get the same instances, the same MILP solver, the same wall-clock limit per budget point, and the same parameter-tuning budget. Beating the enumeration baseline means reaching the same $\epsilon^*$ values within tolerance at every budget, in less total time or with fewer solver calls. On reduction-generated instances the hybrid solver has no competitor with a guarantee. There, beating the baselines means solving budgets $n(p-1)+r$ that the MILP cannot finish.

The key ablation removes the dimension-reduction step. The same Tucker path-following runs on all $n$ agents, and surplus cuts are placed arbitrarily. If this ablation performs as well as the full hybrid solver, the claimed mechanism is not doing the work.

Why not just…?

Why not just combine the two known endpoints and call the curve understood? The endpoints, PPA$_p$ at $n(p-1)$ cuts and trivial at linear-in-blocks cuts, say nothing about the interior. The only interior data point is the single-block $2n-\ell$ result. That result already shows the interior is not a simple function of the endpoints: single-block halving is easy at $2n-\ell$ cuts, while two-block halving is hard at $n$ cuts. Part two's padding question and part three's effort profile settle whether the interior is a sharp threshold or a gradual decay.

Why not just compute the front with a MILP solver and skip the theory? For small $n$ this is exactly what part three does, and it is a real competitor for practical instance sizes. It cannot distinguish "hard because the solver is weak" from "hard because the problem is PPA$_p$-hard at that budget". It will also time out on reduction-generated instances whose size grows with the Tucker dimension. We use it to generate conjectures and as a baseline, not as the answer.

Why not just do smoothed analysis of consensus halving, following Improved Smoothed Analysis of Multiobjective Optimization? We considered this and rejected it for approximate solutions. Perturbing valuations by $\delta$ turns an $\epsilon$-solution of the perturbed instance into an $(\epsilon+\delta)$-solution of the original. Constant inapproximability for PPA therefore implies smoothed hardness almost immediately. The cut budget is the axis along which hardness can genuinely change.

Why not just stay at $p=2$ with Borsuk-Ulam and Tucker? For two groups, the surplus-cut question reduces to extending the single-block linear program. The open problems sit at $p\ge3$: consensus-$1/3$ division is PPAD-hard, and the hardness of $p$-thief necklace splitting is unresolved. Only the $\mathbb{Z}_p$-STAR-TUCKER machinery supplies both a PPA$_p$ membership argument and a path-following algorithm at $p\ge3$.

Proposed Experiments

We generate single-block and two-block piecewise-uniform valuations, matching the instance classes in Consensus-Halving: Does It Ever Get Easier?, for $n$ from 5 to 40 and $p\in\{2,3,5\}$. We also implement the reduction from small Tucker and $\mathbb{Z}_p$-Tucker instances to consensus division, producing structured hard instances. For every instance and every budget from $n(p-1)-2$ up to the breakpoint-splitting count, we record $\epsilon^*(c)$ from exact MILP, the time and solver calls for each baseline, and the hybrid solver's path length.

The first decisive check is whether, on reduction-generated instances, MILP effort peaks at $c=n(p-1)$. The second is whether effort falls sharply once $r$ reaches a constant fraction of $n$, or only gradually. Random instances serve as a control. If they show no peak, hardness is specific to structured instances, and the theory must target the reductions. The third check is the ablation: whether dimension reduction explains any speedup the hybrid solver shows over plain path-following. The theoretical deliverable is a robust-hardness theorem for $r=o(n)$ surplus cuts or a proof that the gadgets break, together with a polynomial algorithm for $r=\Omega(n)$ in the two-block case. Either outcome locates hardness on the trade-off curve more precisely than the current endpoint results.