Answer: Polynomial-time solvable in \(O(L)\) bit operations. Feasible distributions with \(K\leq B\) exist exactly when \(B\geq1\); the optimum is always \(K=1\).
Theorem 6 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateLet N be a set of players whose valuation func- tions are piecewise constant with m steps. Assuming that the intersection property holds, there exists a poly(m, n) time allocation algorithm that is envy-free and cuts the cake in O(nm) locations.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a population scale \(N\), a finite support \(T\) of piecewise-constant valuation types on \([0,1]\), and rational masses \(\mu_t\) summing to \(1\), with the types satisfying the intersection property, choose finite-support distributions \(q_t\) over bundles that are finite unions of intervals. Require that every mass unit receives a whole bundle, that \(\sum_{t\in T}\mu_t q_t(\{P:x\in P\})=1/N\) almost everywhere, and that every type weakly prefers every bundle in its distribution’s support to every bundle in any type’s support. Find distributions minimizing \(K=\sum_{t\in T}\mu_t\sum_P q_t(P)k(P)\), where \(k(P)\) is the number of intervals in \(P\).
A society is given by its support: the list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\) summing to \(1\); \(\tau\) is the support size, not the number of possible types.
Input also includes a binary-encoded integer population scale \(N\geq2\) and a binary-rational threshold \(B\geq0\). No integrality condition is imposed on \(N\mu_t\).
Each type has a nonnegative piecewise-constant density \(\nu_t\), specified by at most \(m\) positive-length valuation intervals with disjoint interiors, positive rational heights and rational endpoints; it is zero elsewhere and satisfies \(\int_0^1\nu_t(x)\,dx=1\). At almost every point, some type has positive density. Write \(V_t(P)=\int_P\nu_t(x)\,dx\).
The intersection property requires that each specified valuation interval of type \(t\) overlaps in positive length exactly one specified valuation interval of every other type \(s\).
A bundle \(P\) is a nonempty finite union of positive-length intervals in \([0,1]\), considered modulo null sets; \(k(P)\) counts its interval components after merging adjacent intervals.
Choose a finite-support probability distribution \(q_t\) over bundles for each type, allowing real probabilities and endpoints. A fraction \(q_t(P)\) of type \(t\) receives the whole bundle \(P\).
Feasibility requires \(\sum_{t\in T}\mu_t\sum_{P\in\operatorname{supp}(q_t)}q_t(P)\mathbf{1}_P(x)=1/N\) almost everywhere and \(V_t(P)\geq V_t(Q)\) for every \(t,s\in T\), \(P\in\operatorname{supp}(q_t)\), and \(Q\in\operatorname{supp}(q_s)\).
Define \(K=\sum_{t\in T}\mu_t\sum_{P\in\operatorname{supp}(q_t)}q_t(P)k(P)\); let \(L\) be the total binary input length.
Is deciding whether feasible distributions with \(K\leq B\) exist solvable in polynomial time, or is it NP-hard? State running times in \(m,\tau,L,N\).
For a finite society of \(n\) agents satisfying the intersection property, an algorithm polynomial in \(m,n\) constructs an envy-free complete allocation using \(O(nm)\) cuts ([source](https://ojs.aaai.org/index.php/AAAI/article/view/10584)); this does not establish exact cut minimization.
No result settling this precise mass-distribution decision problem was located.
The decision problem is polynomial-time solvable: the answer is yes exactly when \(B\geq 1\). In fact, every permitted instance admits feasible distributions with \(K=1\).
The substantive point is that a partition into \(N\) connected intervals can always be paired with fractional assignments of types to their most preferred intervals, giving each interval total recipient mass \(1/N\). This uses the stated permission to assign the same bundle to fractions of several types. It holds without the intersection property.
Every allowed bundle is nonempty and has at least one interval component. Therefore every choice of distributions satisfies
\(K=\sum_{t\in T}\mu_t\sum_{P\in\operatorname{supp}(q_t)}q_t(P)k(P)\geq\sum_{t\in T}\mu_t\sum_{P\in\operatorname{supp}(q_t)}q_t(P)=1.\)
Consequently, \(B<1\) is impossible. It remains to prove that \(K=1\) is always achievable.
Let
\(\Delta_N=\{\ell\in\mathbb{R}_{\geq0}^{N}:\sum_{i=1}^{N}\ell_i=1\}.\)
For \(\ell\in\Delta_N\), define \(c_0=0\), \(c_i=\sum_{j=1}^{i}\ell_j\), and \(P_i(\ell)=[c_{i-1},c_i]\). These intervals partition the cake modulo endpoints. During the existence argument, we allow zero-length intervals; we will prove that the final partition has none.
For each type \(t\), write
\(v_{ti}(\ell)=V_t(P_i(\ell)).\)
Each function \(v_{ti}\) is continuous. Indeed, the cumulative valuation \(F_t(a)=\int_0^a\nu_t(x)\,dx\) is continuous, and
\(v_{ti}(\ell)=F_t(c_i)-F_t(c_{i-1}).\)
Nonnegativity and normalization give
\(v_{ti}(\ell)\geq0,\qquad \sum_{i=1}^{N}v_{ti}(\ell)=1.\)
In particular, the largest interval value for every type is at least \(1/N\). Thus a zero-length interval is never most preferred.
Define the set of most preferred indices by
\(A_t(\ell)=\{i:v_{ti}(\ell)=\max_{1\leq j\leq N}v_{tj}(\ell)\},\)
and the allowed probability vectors for type \(t\) by
\(C_t(\ell)=\{z\in\Delta_N:z_i=0\text{ whenever }i\notin A_t(\ell)\}.\)
This is a nonempty compact convex face of \(\Delta_N\). Its vectors assign positive probability only to most preferred intervals.
Define the possible aggregate recipient-mass vectors by
\(D(\ell)=\{\sum_{t\in T}\mu_t z_t:z_t\in C_t(\ell)\text{ for every }t\}.\)
Every vector in \(D(\ell)\) belongs to \(\Delta_N\), because the masses and each probability vector sum to \(1\).
We use the following finite-dimensional form of Kakutani’s fixed-point theorem: if \(S\) is a nonempty compact convex subset of a Euclidean space, and a correspondence \(\Phi:S\rightrightarrows S\) has a closed graph and nonempty compact convex values, then some \(s\in S\) satisfies \(s\in\Phi(s)\). This is Theorem 1 and its corollary in [Kakutani’s original paper](https://www.math.ucdavis.edu/~deloera/TEACHING/READINGSEMINAR/PAPERS/kakutanioriginal.pdf).
We first verify the required properties.
The correspondence \(C_t\) has a closed graph. Suppose \(\ell^{(r)}\to\ell\), \(z^{(r)}\to z\), and \(z^{(r)}\in C_t(\ell^{(r)})\). If \(z_i>0\), then \(z_i^{(r)}>0\) for all sufficiently large \(r\). Hence
\(v_{ti}(\ell^{(r)})\geq v_{tj}(\ell^{(r)})\)
for every \(j\). Continuity gives the same inequalities at \(\ell\), so \(i\in A_t(\ell)\). This proves \(z\in C_t(\ell)\).
The correspondence \(D\) has nonempty compact convex values and a closed graph. Nonemptiness follows from that of each \(C_t\). Compactness follows because \(D(\ell)\) is the continuous image of the finite product of the compact sets \(C_t(\ell)\). Convexity follows by taking convex combinations of the corresponding vectors for every type.
For closedness of the graph, suppose \(\ell^{(r)}\to\ell\), \(d^{(r)}\to d\), and \(d^{(r)}\in D(\ell^{(r)})\). Choose representations
\(d^{(r)}=\sum_t\mu_t z_t^{(r)},\qquad z_t^{(r)}\in C_t(\ell^{(r)}).\)
Compactness of the finite product \((\Delta_N)^\tau\) gives a subsequence along which every \(z_t^{(r)}\) converges to some \(z_t\). Closedness of the graphs of \(C_t\) gives \(z_t\in C_t(\ell)\). Taking limits yields \(d=\sum_t\mu_t z_t\), hence \(d\in D(\ell)\).
For \(d\in\Delta_N\), define
\(R(d)=\{\ell\in\Delta_N:\ell_i=0\text{ whenever }d_i>\min_j d_j\}.\)
Thus \(R(d)\) consists of length vectors supported on indices with minimum aggregate recipient mass. It is a nonempty compact convex face. Equivalently,
\(R(d)=\{\ell\in\Delta_N:\sum_i\ell_i d_i=\min_jd_j\}.\)
This equality also proves that \(R\) has a closed graph, since both sides depend continuously on \((\ell,d)\).
Now take \(S=\Delta_N\times\Delta_N\) and define
\(\Phi(\ell,d)=R(d)\times D(\ell).\)
The domain \(S\) is nonempty, compact, and convex. The preceding checks show that \(\Phi\) has nonempty compact convex values and a closed graph. Kakutani’s theorem therefore supplies \((\ell^*,d^*)\) with
\(\ell^*\in R(d^*),\qquad d^*\in D(\ell^*).\)
We next prove that every coordinate of \(\ell^*\) is positive. Suppose \(\ell_i^*=0\) for some \(i\). That interval has zero value for every type, whereas every type has a most preferred interval of positive value. Thus every vector in \(C_t(\ell^*)\) has coordinate \(i\) equal to zero, and consequently \(d_i^*=0\). Since \(d^*\) is nonnegative, its minimum coordinate is zero.
Membership \(\ell^*\in R(d^*)\) now implies that \(d_j^*=0\) whenever \(\ell_j^*>0\). For indices with \(\ell_j^*=0\), the preceding zero-length argument also gives \(d_j^*=0\). All coordinates of \(d^*\) would therefore vanish, contradicting \(d^*\in\Delta_N\).
Hence \(\ell_i^*>0\) for every \(i\). Membership in \(R(d^*)\) then forces every coordinate of \(d^*\) to equal its minimum. Since their sum is \(1\),
\(d_i^*=1/N\qquad\text{for every }i.\)
Because \(d^*\in D(\ell^*)\), choose vectors \(z_t\in C_t(\ell^*)\) such that
\(\sum_t\mu_t z_{ti}=1/N\qquad\text{for every }i.\)
Use the positive-length bundles \(P_i=P_i(\ell^*)\), and set \(q_t(P_i)=z_{ti}\), omitting zero-probability entries. Each distribution has finite support of size at most \(N\).
For almost every \(x\), exactly one interval \(P_i\) contains \(x\). Therefore
\(\sum_t\mu_t\sum_jq_t(P_j)\mathbf{1}_{P_j}(x)=\sum_t\mu_t z_{ti}=1/N.\)
This proves the required pointwise feasibility.
If \(P_i\) belongs to the support of \(q_t\), then \(z_t\in C_t(\ell^*)\) implies
\(V_t(P_i)=\max_jV_t(P_j).\)
Every bundle allocated to any type is one of the \(P_j\). Thus \(V_t(P_i)\geq V_t(Q)\) for every allocated bundle \(Q\), proving all the required envy inequalities, including those within a type.
Finally, each \(P_i\) has exactly one component. Hence
\(K=\sum_t\mu_t\sum_i z_{ti}=1.\)
Together with the lower bound, this proves that the optimum is exactly \(1\).
For the promised input class, accept exactly when \(B\geq1\). Comparing the binary-encoded numerator and denominator of \(B\), including reading the input, takes \(O(L)\) bit operations.
Thus the decision running time is \(O(L)\), with no additional dependence on \(m\), \(\tau\), or the numerical value of \(N\). In particular, expanding the population into \(N\) agents is unnecessary.
The fixed-point proof establishes existence; it does not assert an efficient algorithm for explicitly listing the distributions. That distinction does not affect this decision problem, whose answer is determined entirely by the threshold comparison.
⟨structured verdict parsed — rendered above⟩
The prover’s argument is correct and resolves the stated decision problem. It establishes that every permitted instance has feasible distributions with \(K=1\), and that no distributions can have \(K<1\). Thus acceptance is equivalent to \(B\geq1\).
I found no major or minor mathematical issues. The proof uses the task’s express permission to share a bundle among fractions of different types and to use real probabilities and endpoints.
Every allowed bundle has at least one interval component, so \(k(P)\geq1\). Each \(q_t\) is a probability distribution, and the type masses sum to \(1\). Consequently, the displayed calculation proving \(K\geq1\) is valid.
This covers arbitrary allowed bundles, not merely the connected bundles subsequently constructed.
The simplex \(\Delta_N\) correctly parameterizes ordered partitions into \(N\) intervals, temporarily allowing zero-length intervals.
The functions \(v_{ti}\) are continuous: the given densities are integrable, their cumulative valuations are continuous, and the partition endpoints depend continuously on \(\ell\).
The identities \(v_{ti}\geq0\) and \(\sum_i v_{ti}=1\) are correct. Shared endpoints have zero valuation and do not affect additivity. Therefore each type’s maximum interval value is at least \(1/N>0\), whereas every zero-length interval has value zero. The conclusion that zero-length intervals are never most preferred is valid, including on the boundary of the simplex.
Each \(C_t(\ell)\) is indeed a nonempty compact convex face: the finite set of interval values has a maximizer, and \(C_t(\ell)\) consists precisely of probability vectors supported on maximizers.
The closed-graph argument for \(C_t\) is sound. Whenever a limiting coordinate \(z_i\) is positive, that coordinate is eventually positive in the approximating vectors. The corresponding maximizing inequalities then pass to the limit by continuity. Coordinates equal to zero impose no additional condition.
The claims about \(D(\ell)\) are also justified:
For its closed graph, the simultaneous subsequence extraction is legitimate because the number of types is finite and \((\Delta_N)^\tau\) is compact. The closed graphs of the \(C_t\) and continuity of the weighted sum give the stated limiting representation.
The correspondence \(R(d)\) is a nonempty compact convex face. Its displayed equality characterization is correct: a convex combination of coordinates attains their minimum exactly when its positive weights occur only at minimum coordinates. The minimum of finitely many coordinates is continuous, so this characterization establishes the closed graph.
The theorem is stated precisely enough for this application. The cited original paper gives the closed-graph formulation and extends the theorem to arbitrary bounded closed convex sets in Euclidean space. [Kakutani, Theorem 1 and its corollary](https://www.math.ucdavis.edu/~deloera/TEACHING/READINGSEMINAR/PAPERS/kakutanioriginal.pdf).
All hypotheses are satisfied as written:
Although \(N\) is binary encoded and potentially large, it is finite for each instance. This suffices for the existence theorem; the proof does not claim to compute its fixed point efficiently.
The contradiction excluding zero coordinates of \(\ell^*\) is valid.
A zero-length interval receives zero probability from every type, hence has aggregate recipient mass zero. The minimum aggregate mass is therefore zero. Membership in \(R(d^*)\) forces every positive-length interval also to have aggregate mass zero. Every remaining zero-length interval already has aggregate mass zero. This would make \(d^*\) the zero vector, contradicting \(d^*\in\Delta_N\).
Thus every interval has positive length. Since \(\ell^*\) is supported on minimum-mass coordinates and every coordinate is positive, all coordinates of \(d^*\) are equal. Their sum is \(1\), giving exactly \(d_i^*=1/N\).
No integrality condition on \(N\mu_t\) is used.
The constructed \(q_t\) are probability distributions with finite support of size at most \(N\). Every used bundle is a permitted positive-length interval.
Outside the finitely many partition endpoints, exactly one bundle contains each point. The aggregate indicator sum consequently equals its recipient mass, \(1/N\), proving the required almost-everywhere coverage condition.
For every type \(t\), every bundle in its support maximizes that type’s valuation among all partition intervals. Every bundle allocated to any type belongs to that same collection. This proves the full quantified envy condition, including comparisons between bundles assigned within a type.
Each used bundle has one component, so the calculation \(K=1\) is correct.
The argument applies to the entire promised input class. Its independence from the intersection property is valid: proving the result for a broader class suffices.
The decision algorithm only compares \(B\) with \(1\). Under the stated binary-rational encoding, this takes \(O(L)\) bit operations, including reading the input, with no additional dependence on \(m\), \(\tau\), or the numerical value of \(N\).
The distinction between deciding existence and explicitly constructing the distributions is correctly maintained. The task asks for the former, so potentially large support descriptions do not invalidate the running-time claim.
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.