Answer: Polynomial-time solvable.
Lemma A.1 — class: other
Given a cake \(C=[0,1]\), a finite set of \(\tau\) piecewise-uniform valuation types with rational interval endpoints, and positive binary-rational masses \(\mu_t\) summing to \(1\), compute the CC-PUV-style allocation. In each round, with active types \(A\) and available intervals \(X\), choose a nonempty \(U\subseteq A\) minimizing \(\rho(U,X)=\frac{\sum_{I\in D(U,X)}|I|}{\sum_{t\in U}\mu_t}\). For \(r=\rho(U,X)\), find a rational flow that assigns only desired intervals to types in \(U\), gives each type \(t\in U\) aggregate cake measure \(r\mu_t\), and then removes \(U\) and \(D(U,X)\) before the next round. Determine whether this can be done exactly in time polynomial in \(\tau\), the number of intervals per type, and the input bit length.
A society is given by its support: a list of \(\tau\geq1\) valuation types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) counts listed types, not all possible types.
The cake is \(C=[0,1]\). Type \(t\) specifies a positive-length union \(B_t\) of at most \(\ell\) disjoint intervals with binary-rational endpoints and has normalized density \(v_t(x)=1/|B_t|\) on \(B_t\), zero elsewhere. Endpoints have measure zero.
Let \(W\) be the positive-length elementary intervals induced by all support endpoints and \(0,1\), let \(m=|W|\), and let \(L\) be the total input bit length. For \(X\subseteq W\), define \(D(U,X)=\{I\in X:I\subseteq B_t\text{ for some }t\in U\}\).
Start with \(A=\{1,\ldots,\tau\}\) and \(X=W\). Each round chooses a nonempty \(U\subseteq A\) minimizing \(\rho(U,X)=\bigl(\sum_{I\in D(U,X)}|I|\bigr)/\bigl(\sum_{t\in U}\mu_t\bigr)\), and sets \(r=\rho(U,X)\).
Allocate rational lengths \(f_{I,t}\geq0\) satisfying \(f_{I,t}=0\) unless \(I\subseteq B_t\), \(\sum_{t\in U}f_{I,t}=|I|\) for every \(I\in D(U,X)\), and \(\sum_{I\in D(U,X)}f_{I,t}=r\mu_t\) for every \(t\in U\). Realize these lengths as disjoint rational-endpoint subintervals.
Replace \(A\) by \(A\setminus U\) and \(X\) by \(X\setminus D(U,X)\), without renormalizing masses, until \(A=\varnothing\). Any minimizing subset and feasible allocation are permitted; cake desired by no type is discarded. The output consists of the selected subsets and allocations in all rounds.
Can this exact allocation problem be solved in time polynomial in \(m,\tau,\ell,L\), or is it NP-hard?
For finitely many equal-weight agents, flow feasibility at a common quota \(c\geq0\) is equivalent to every nonempty subset having average demand at least \(c\); the resulting recursive allocation is polynomial-time computable ([Chen et al.](https://procaccia.info/wp-content/uploads/2020/03/justruth.pdf)).
Variable-claim CCEA and polynomial-time variable-claim market allocations are nearby results ([Aziz and Ye](https://arxiv.org/html/1307.2908)); no source verified here explicitly settles the exact weighted round-sequence problem above.
The problem is polynomial-time solvable in \(m,\tau,\ell,L\). We prove this by giving a flow algorithm that finds an exact minimizing subset in every round and produces rational allocations of polynomial bit length.
The argument extends the flow method in [Chen et al., Sections 3.3–3.4](https://procaccia.info/wp-content/uploads/2020/03/justruth.pdf). The weighted minimization and bit-complexity arguments below are proved directly.
Let \(Q\) be the product of the denominators of all input interval endpoints, and let \(H\) be the product of the denominators of all input masses. These integers have bit length \(O(L)\), even when “binary-rational” means arbitrary rationals represented in binary.
For each elementary interval \(I\in W\) and each type \(t\), write
\( \displaystyle |I|=\frac{a_I}{Q},\qquad \mu_t=\frac{b_t}{H}, \)
where \(a_I,b_t\) are positive integers. Since the elementary intervals partition the cake up to endpoints and the masses sum to one,
\( \displaystyle \sum_{I\in W}a_I=Q,\qquad \sum_{t=1}^{\tau}b_t=H. \)
Fix a round with nonempty active set \(A\) and remaining intervals \(X\). Define
\( \displaystyle \mu(U)=\sum_{t\in U}\mu_t,\qquad d_X(U)=\sum_{I\in D(U,X)}|I|. \)
For nonempty \(U\subseteq A\), set
\( \displaystyle a_U=\sum_{I\in D(U,X)}a_I,\qquad b_U=\sum_{t\in U}b_t. \)
Then
\( \displaystyle \rho(U,X)=\frac{H a_U}{Q b_U},\qquad 0\leq a_U\leq Q,\qquad 1\leq b_U\leq H. \)
Put \(K=QH\). Every possible ratio, in every round, therefore has reduced numerator and denominator at most \(K\).
Consequently, any two distinct possible ratios differ by at least \(1/K^2\). Indeed, if they are \(p/q\) and \(p'/q'\) in reduced form, then
\( \displaystyle \left|\frac pq-\frac{p'}{q'}\right|=\frac{|pq'-p'q|}{qq'}\geq\frac1{K^2}, \)
because the nonzero integer numerator has absolute value at least one.
This separation bound will let us extract an exact minimizer using only polynomially many flow computations.
For a rational \(c\in[0,H+1]\), construct a directed network with source \(s\), sink \(z\), a vertex for each \(t\in A\), and a vertex for each \(I\in X\). Its arcs and capacities are:
Let \(F(c)\) denote its maximum-flow value.
Lemma. The following conditions are equivalent:
\( \displaystyle F(c)=c\mu(A), \)
and
\( \displaystyle d_X(U)\geq c\mu(U)\quad\text{for every nonempty }U\subseteq A. \)
Proof. The cut whose source side consists only of \(s\) has capacity \(c\mu(A)\leq H+1<M\). Thus no minimum cut crosses an arc of capacity \(M\).
For any minimum cut, let \(U\subseteq A\) and \(Y\subseteq X\) be its type vertices and interval vertices on the source side. Since no incidence arc crosses the cut, \(Y\supseteq D(U,X)\). Its capacity is therefore at least
\( \displaystyle c\mu(A\setminus U)+d_X(U). \)
Conversely, for every \(U\subseteq A\), the source side
\( \displaystyle \{s\}\cup U\cup D(U,X) \)
defines a cut of exactly that capacity. With the conventions \(\mu(\varnothing)=d_X(\varnothing)=0\), the minimum-cut value is consequently
\( \displaystyle c\mu(A)+\min_{U\subseteq A}\bigl(d_X(U)-c\mu(U)\bigr). \)
The minimum in this expression is at most zero, because the empty subset gives zero. By the max-flow/min-cut theorem, \(F(c)=c\mu(A)\) precisely when every term is nonnegative. This is the stated condition. \(\square\)
Define the exact minimum ratio
\( \displaystyle r_*=\min_{\varnothing\neq U\subseteq A}\rho(U,X). \)
The lemma proves that
\( \displaystyle F(c)=c\mu(A)\quad\Longleftrightarrow\quad c\leq r_*. \)
Moreover,
\( \displaystyle 0\leq r_*\leq\frac{d_X(A)}{\mu(A)}\leq H, \)
because \(d_X(A)\leq1\) and \(\mu(A)\geq1/H\).
Start with the feasible lower bound \(l=0\) and the infeasible upper bound \(h=H+1\). Repeatedly test \(c=(l+h)/2\) using the flow criterion:
The invariant is
\( \displaystyle l\leq r_*<h. \)
Stop after enough iterations that
\( \displaystyle h-l<\frac1{K^2}. \)
Starting from width \(H+1\), this requires only
\( \displaystyle O\bigl(\log(H+1)+\log K\bigr)=O(L) \)
iterations.
Now compute a minimum cut at \(c=h\), and let \(U\) be its source-side type vertices. Since \(h>r_*\), its capacity is strictly less than \(h\mu(A)\).
No capacity-\(M\) arc crosses this cut. Its source-side interval set is exactly \(D(U,X)\): any additional interval vertex could be moved to the sink side, decreasing the cut capacity by its strictly positive length without introducing an incidence arc across the cut.
Thus the strict cut inequality is
\( \displaystyle h\mu(A\setminus U)+d_X(U)<h\mu(A), \)
or equivalently,
\( \displaystyle d_X(U)<h\mu(U). \)
This also shows that \(U\neq\varnothing\). Hence
\( \displaystyle r_*\leq\rho(U,X)<h. \)
Suppose \(\rho(U,X)>r_*\). Both quantities are possible subset ratios, so the separation bound gives
\( \displaystyle \rho(U,X)-r_*\geq\frac1{K^2}. \)
But the maintained bounds give
\( \displaystyle \rho(U,X)-r_*<h-r_*\leq h-l<\frac1{K^2}, \)
a contradiction. Therefore
\( \displaystyle \rho(U,X)=r_*. \)
We have found an exact nonempty minimizing subset. This extraction works for any minimum cut at the final upper bound; no particular tie-breaking rule is needed.
Let \(U\) be the selected minimizer, put \(r=\rho(U,X)\), and write \(D=D(U,X)\).
Construct the same network using only types in \(U\), intervals in \(D\), and quota \(c=r\). For every nonempty \(S\subseteq U\),
\( \displaystyle d_X(S)\geq r\mu(S), \)
by minimality of \(U\). Also \(D(S,X)\subseteq D\), so restricting the interval set to \(D\) preserves every such demand length. The weighted flow criterion therefore gives a flow of value \(r\mu(U)\).
By the definition of \(r\),
\( \displaystyle r\mu(U)=d_X(U)=\sum_{I\in D}|I|. \)
This value equals both the sum of the source-arc capacities and the sum of the sink-arc capacities. Consequently, every source arc and every sink arc is saturated.
For \(I\in D\) and \(t\in U\), define \(f_{I,t}\) as the flow on \(t\to I\), taking it to be zero when that arc is absent. Conservation and saturation give
\( \displaystyle \sum_{I\in D}f_{I,t}=r\mu_t\quad(t\in U), \)
and
\( \displaystyle \sum_{t\in U}f_{I,t}=|I|\quad(I\in D). \)
An incidence arc exists only when \(I\subseteq B_t\), so all required allocation constraints hold.
For each \(I\in D\), order the types in \(U\) and lay out consecutive pieces of lengths \(f_{I,t}\) from its left endpoint. These pieces fill \(I\), with disjoint interiors. A consistent half-open endpoint convention makes them disjoint; endpoint choices do not affect any valuation.
If \(r=0\), then \(d_X(U)=0\), and positivity of elementary-interval lengths implies \(D=\varnothing\). The zero allocation satisfies the same constraints.
Each network has at most \(m+\tau+2\) vertices and \(m\tau+m+\tau\) arcs.
After \(j\) bisection iterations, every tested quota has a denominator dividing \(2^j\). All capacities can therefore be scaled to integers using the common denominator
\( \displaystyle 2^jHQ. \)
Since \(j=O(L)\) and \(Q,H\) have \(O(L)\) bits, the resulting integer capacities also have \(O(L)\) bits. An integer max-flow algorithm with a polynomial bound independent of capacity magnitudes, such as Edmonds–Karp, computes the flow and a minimum cut in polynomial bit time.
For the selected subset \(U\),
\( \displaystyle r=\frac{H a_U}{Q b_U},\qquad r\mu_t=\frac{a_Ub_t}{Qb_U}. \)
Thus all allocation-network capacities become integers when multiplied by
\( \displaystyle \Delta=Qb_U\leq QH. \)
Computing an integral maximum flow in this scaled network gives each allocation length in the form
\( \displaystyle f_{I,t}=\frac{k_{I,t}}{\Delta},\qquad 0\leq k_{I,t}\leq\Delta. \)
These numbers have \(O(L)\) bits. Original interval endpoints have denominators dividing \(Q\), and \(Q\) divides \(\Delta\). Therefore the cut points formed by adding allocation lengths also have \(O(L)\)-bit representations.
After producing the allocation, update exactly as specified:
\( \displaystyle A\leftarrow A\setminus U,\qquad X\leftarrow X\setminus D(U,X). \)
The original masses remain unchanged. The preceding arguments apply to every residual pair \(A,X\), so correctness follows inductively through all rounds.
Every round removes at least one type, giving at most \(\tau\) rounds. Each round uses \(O(L)\) flow tests, one final minimum-cut computation, and one allocation-flow computation.
Every elementary interval is allocated in at most one round and contributes at most \(\tau\) positive pieces. Thus there are at most \(m\tau\) output pieces, each with polynomial bit length. Zero entries can be specified implicitly.
Finally, sorting endpoints and computing all incidences \(I\subseteq B_t\) require polynomial time in \(m,\tau,\ell,L\), using exact rational comparisons.
Hence the algorithm computes a permitted complete round sequence and its exact rational allocations in time polynomial in \(m,\tau,\ell,L\).
⟨structured verdict parsed — rendered above⟩
The prover’s claim is correct: the argument establishes an exact polynomial-time algorithm for the specified weighted round sequence. No major or minor mathematical gaps were found.
The definitions of \(Q\) and \(H\) are valid for binary-encoded rational inputs. The bit length of a product is bounded by the sum of the bit lengths of its factors, so both integers have \(O(L)\) bits.
Every elementary-interval endpoint has denominator dividing \(Q\). Therefore each positive interval length can be expressed as \(a_I/Q\) with a positive integer \(a_I\). The identities
\[
\sum_{I\in W}a_I=Q,\qquad \sum_t b_t=H
\]
follow from the partition of the unit cake and the normalization of the masses.
For every nonempty active subset, \(b_U\geq1\), including when its remaining demand is zero. Thus the displayed expression
\[
\rho(U,X)=\frac{Ha_U}{Qb_U}
\]
is well defined. Its unreduced numerator and denominator are at most \(QH\), so reduction preserves those bounds. The zero ratio also satisfies the stated bound, with reduced representation \(0/1\).
The separation calculation is correct: two distinct rational numbers whose reduced denominators are at most \(K\) differ by at least \(1/K^2\). This bound applies uniformly to every residual round.
Finding: Correct.
All capacities are nonnegative rationals, and the network is finite. The max-flow/min-cut theorem therefore applies.
The source-only cut has capacity at most \(H+1\), strictly smaller than \(M=H+3\). Consequently, no minimum cut can cross an incidence arc of capacity \(M\).
If a minimum cut has source-side type set \(U\), its source-side interval set must contain \(D(U,X)\). Its capacity is consequently at least
\[
c\mu(A\setminus U)+d_X(U).
\]
Conversely, the specified source side \(\{s\}\cup U\cup D(U,X)\) crosses no incidence arc and has exactly that capacity. These two directions justify the minimum-cut formula, including the empty-subset convention.
Since the empty subset contributes zero, the formula gives precisely the claimed equivalence between full source-capacity flow and all weighted demand inequalities.
The bound \(r_*\leq H\) is also correct: the active set is nonempty, its mass is at least \(1/H\), and its remaining demand is at most one.
Finding: Correct; the criterion covers unequal masses and zero remaining demand.
The initial lower bound is feasible, and the initial upper bound is strictly infeasible. The flow criterion preserves
\[
l\leq r_*<h
\]
through every bisection step, including when a tested quota equals \(r_*\).
The interval width halves at each iteration. Achieving width strictly below \(1/K^2\) therefore requires \(O(L)\) iterations.
At the final upper bound, infeasibility implies that every minimum cut has capacity strictly below \(h\mu(A)\). The argument that its interval set equals \(D(U,X)\) is valid: an additional source-side interval has positive sink-arc capacity, and moving it to the sink side creates no crossing incidence arc from a source-side type.
The resulting strict inequality forces \(U\) to be nonempty and gives
\[
r_*\leq\rho(U,X)<h.
\]
If its ratio exceeded \(r_*\), the separation bound would contradict the final interval width. Thus the extracted subset is an exact minimizer.
This reasoning does not depend on a particular minimum-cut tie-breaking rule.
Finding: Correct; bisection locates an exact minimizing subset despite using only feasibility tests.
For every nonempty \(S\subseteq U\), minimality supplies the required weighted demand inequality. Moreover, restricting the interval vertices to \(D(U,X)\) does not remove any interval desired by \(S\). The flow criterion therefore applies to the restricted network.
The required maximum-flow value equals both the total source capacity and the total sink capacity. Because each individual arc carries at most its capacity, equality of these totals forces every source and sink arc to be saturated. Conservation then gives exactly the two allocation equalities required by the task.
The incidence restriction ensures that positive allocation lengths occur only on desired intervals.
Consecutive pieces realize the lengths with rational endpoints. The stated half-open convention handles disjointness, consistently with the task’s measure-zero treatment of endpoints.
The zero-ratio case is explicitly and correctly handled: positive elementary-interval lengths force \(D(U,X)=\varnothing\), and the zero allocation satisfies the constraints.
Finding: Correct.
After \(j\) bisection steps, every tested quota has denominator dividing \(2^j\). Multiplication by \(2^jHQ\) makes all capacities integral. Both the scaling factor and the scaled capacities have \(O(L)\) bits because \(j=O(L)\).
The cited algorithmic property of Edmonds–Karp is applicable: its number of augmentations is polynomial in the network size independently of capacity magnitudes. With polynomial-length integer capacities, its arithmetic operations also take polynomial bit time. Exact feasibility comparisons and minimum-cut extraction are therefore justified.
For the allocation network, the calculation
\[
r\mu_t=\frac{a_Ub_t}{Qb_U}
\]
is correct. Scaling by \(\Delta=Qb_U\) makes every capacity integral. An integral maximum flow therefore yields allocation lengths with denominator \(\Delta\).
Each allocation length is at most its interval’s length, hence at most one, which validates \(k_{I,t}\leq\Delta\). Original endpoints also have denominators dividing \(\Delta\), so cumulative cut points retain \(O(L)\)-bit representations.
The network-size bounds and the polynomial preprocessing claim are valid. Interval incidences can be determined by exact comparisons with the listed component intervals.
Finding: Correct.
Every round removes a nonempty set of types, so there are at most \(\tau\) rounds. The proof applies to arbitrary residual pairs \(A,X\), retaining the original masses; it requires no renormalization or additional invariant.
Each elementary interval is allocated at most once. The bound of \(m\tau\) output pieces is therefore valid, and the selected subsets also have polynomial total representation size. Undesired intervals may remain after all types have been removed, exactly as permitted by the task.
The algorithm consequently produces a complete permitted sequence of exact minimizers and feasible rational allocations.
Finding: The target is fully resolved. No repair or additional clarification is required.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.