Answer: \(\text{Polynomial-time constructible and evaluable}\)
Theorem 4 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAssume that the agents have piecewise uniform valuation functions. Then Algorithm 1 is truthful, propor- tional, EF, and polynomial-time. Randomized Algorithms and Piecewise Linear Valuations In the previous section we saw that designing deterministic truthful and fair algorithms is not an easy task, even if the valuation functions of the agents are rather restricted. In this section we shall demonstrate that by allowing randomness we can obtain significantly more general results.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a binary-encoded population scale \(N\), rational masses \(\mu_t=k_t/N\) over \(\tau\) piecewise-uniform valuation types \(t\), and rational interval descriptions of each type’s reference set \(U_t\), does there exist a succinct mechanism, evaluable in time polynomial in \(\tau\), the description length \(L\), and \(\log N\), that assigns each of the \(N\) individuals a cake piece? The mechanism must produce a partition with free disposal for every report profile, satisfy proportionality and envy-freeness at truthful profiles, and be dominant-strategy truthful for every individual and every alternative piecewise-uniform report. Its representation must specify assignments by type and within-type rank, so a unilateral report change updates the corresponding type masses by \(1/N\).
The cake is \([0,1]\). A type \(t\) has a reference set \(U_t\), a finite union of intervals with binary rational endpoints and positive total length, and valuation \(V_t(X)=\operatorname{len}(X\cap U_t)/\operatorname{len}(U_t)\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational. Here \(N\geq1\) is a binary-encoded integer, \(\mu_t=k_t/N\), \(k_t\in\mathbb Z_{>0}\), and \(\sum_t k_t=N\); \(\tau\) is the support size, not the number of possible types.
Let \(m\) be the number of elementary intervals induced by all reported endpoints and \(L\) the total bit length of the support description. Individuals have a fixed public order; an individual’s within-type rank is its position among individuals currently reporting that type.
A deterministic mechanism without payments maps every report profile to pairwise disjoint cake pieces, each a finite union of intervals; unassigned cake may be discarded. Its succinct representation specifies a piece \(A_{t,r}\) for each type and rank \(1\leq r\leq k_t\), and evaluation returns that piece’s rational interval endpoints.
At every truthful profile, require \(V_i(A_i)\geq1/N\) and \(V_i(A_i)\geq V_i(A_j)\) for all individuals \(i,j\). Require dominant-strategy truthfulness against every alternative positive-length, rational-endpoint piecewise-uniform report, for arbitrary reports of the other individuals.
A deviation preserves the individual’s identity, decreases its old type’s mass by \(1/N\), increases its new type’s mass by \(1/N\), and recomputes ranks using the fixed public order; types may enter or leave the support.
Can such a mechanism’s allocation representation be constructed and evaluated uniformly in polynomial time in \(m,\tau,L,\log N\), or is constructing such succinct allocations NP-hard?
For explicitly listed individuals, a deterministic polynomial-time mechanism satisfying truthfulness, proportionality, and envy-freeness is known ([Chen–Lai–Parkes–Procaccia](https://procaccia.info/wp-content/uploads/2020/03/justruth.pdf)). Its stated complexity uses the explicit population input; no result settling the support-encoded construction question was located.
Such a mechanism can be constructed and evaluated uniformly in polynomial time in \(m,\tau,L,\log N\).
The construction compresses the minimum-ratio allocation structure of Mechanism 1 in [Chen–Lai–Parkes–Procaccia](https://procaccia.info/wp-content/uploads/2020/03/justruth.pdf). Below, I prove the compressed running-time bound and verify truthfulness directly, including deviations that change the support and within-type ranks.
Throughout, interval endpoints are immaterial to valuations. We use half-open allocation intervals and discard the endpoint \(1\), so pieces are literally pairwise disjoint.
At an intermediate stage, let \(T\) be the remaining types, with their original counts \(k_t\), and let \(X\) be the remaining cake. Define, for \(H\subseteq T\),
\[ k(H)=\sum_{t\in H}k_t, \qquad D_X(H)=X\cap\bigcup_{t\in H}U_t, \qquad d_X(H)=\operatorname{len}(D_X(H)). \]
The next allocation rate will be
\[ \lambda=\min_{\varnothing\ne H\subseteq T}\frac{d_X(H)}{k(H)}. \]
Here a rate means unnormalized cake length per individual.
Lemma 1. The same minimum is obtained by minimizing over all nonempty subsets of the remaining individuals. Moreover, the unique largest minimizing individual set consists of all copies of a set of types.
Proof. Given an individual set \(S\), add every remaining individual whose reported type occurs in \(S\). This leaves its desired union unchanged and weakly increases its cardinality. Consequently, its desired length divided by cardinality weakly decreases. Thus the individual and type minima coincide.
It remains to justify “unique largest.” The function \(d_X\) is submodular: for type sets \(A,B\),
\[ d_X(A\cup B)+d_X(A\cap B) \leq d_X(A)+d_X(B). \]
Indeed, the desired union of \(A\cup B\) is the union of their desired unions, whereas the desired union of \(A\cap B\) is contained in their intersection.
Set \(F(H)=d_X(H)-\lambda k(H)\), including \(F(\varnothing)=0\). By minimality of \(\lambda\), \(F(H)\geq0\) for every \(H\). If \(A,B\) minimize the ratio, submodularity gives
\[ 0\leq F(A\cup B)+F(A\cap B) \leq F(A)+F(B)=0. \]
Hence \(A\cup B\) also minimizes. Taking the union of all minimizers produces the unique largest minimizer.
The identical argument applies to individual sets. Completing any individual minimizer to whole types still gives a minimizer, by the first paragraph. Therefore the largest individual minimizer contains every copy of each type it contains. \(\square\)
We always select this unique largest minimizing block. This choice is essential to the truthfulness proof below.
Partition the cake at all reported endpoints and at \(0,1\). Write its positive-length elementary intervals as \(I_j=[a_j,b_j)\), with lengths \(\ell_j=b_j-a_j\). Membership in each reported reference set is constant inside each elementary interval.
The algorithm will remove only whole elementary intervals, so \(X\) remains a union of them.
Let \(K=k(T)\). For a rational \(c\in[0,2]\), construct a network with source \(s\), sink \(z\), one node per remaining type, and one node per remaining elementary interval:
Lemma 2. This network has a flow saturating every source edge if and only if \(c\leq\lambda\).
Proof. A cut consisting of the source alone has capacity \(Kc\leq2N<M\). Thus a minimum cut cannot cut any type-to-interval edge.
For a prescribed set \(H\) of type nodes on the source side, all intervals desired by \(H\) must also lie on that side. Putting any additional interval there increases the cut capacity. Therefore the minimum cut with type set \(H\) has capacity
\[ c\bigl(K-k(H)\bigr)+d_X(H). \]
By the max-flow min-cut theorem, a flow of value \(Kc\) exists exactly when every such cut has capacity at least \(Kc\). This is equivalent to
\[ d_X(H)\geq c\,k(H) \quad\text{for every }H\subseteq T, \]
which is equivalent to \(c\leq\lambda\). \(\square\)
The network has \(O(m+\tau)\) vertices and \(O(m\tau+m+\tau)\) edges. Its size is independent of the explicit population size.
Choose a common denominator \(Q\) for the input endpoints. For example, their denominators’ product suffices. Its binary length is \(O(L)\).
Every remaining desired union has length \(A/Q\) for an integer \(A\). Thus every candidate ratio has the form
\[ \frac{A}{Qh}, \qquad 1\leq h\leq N. \]
Two distinct candidate ratios differ by at least
\[ \left|\frac{A}{Qh}-\frac{B}{Qh'}\right| =\frac{|Ah'-Bh|}{Qhh'} \geq\frac{1}{QN^2}. \]
Use Lemma 2 to bisect an interval whose lower endpoint is feasible and upper endpoint is infeasible. Initially, \(0\) is feasible and \(2\) is infeasible, since the cake has length at most \(1\) and \(K\geq1\).
After \(O(\log Q+\log N)\) iterations, obtain endpoints \(c_-,c_+\) satisfying
\[ c_-\leq\lambda<c_+, \qquad c_+-c_-<\frac{1}{QN^2}. \]
A minimum cut at the infeasible value \(c_+\) supplies a nonempty type set \(H\) with
\[ \frac{d_X(H)}{k(H)}<c_+. \]
This ratio cannot exceed \(\lambda\): otherwise its separation from \(\lambda\) would be at least \(1/(QN^2)\). Therefore it equals \(\lambda\), determining the optimum exactly.
To obtain the largest minimizing block, compute a maximum flow at this exact \(\lambda\). In its residual graph, let \(Z\) be the vertices from which the sink cannot be reached. Then \(Z\) is the largest source side of a minimum cut:
Let \(B\) be the type nodes in \(Z\). The cut formula from Lemma 2 gives
\[ d_X(B)=\lambda k(B). \]
Every minimizing type set defines a minimum cut and is therefore contained in \(B\). Hence \(B\) is precisely the unique largest minimizing block. It is nonempty because a nonempty minimizer exists.
At each stage:
At least one type disappears at every stage, so there are at most \(\tau\) stages.
Let \(f_{jt}\) denote the flow from type \(t\in B\) to elementary interval \(I_j\). Every source edge is saturated, giving
\[ \sum_j f_{jt}=k_t\lambda. \]
The block sends total flow \(k(B)\lambda=d_X(B)\) into intervals whose total capacity is exactly \(d_X(B)\). Consequently, it fills every interval in \(D_X(B)\) completely.
Fix a deterministic ordering of the types, obtained from their canonical interval descriptions. Inside each such elementary interval, place the segments of lengths \(f_{jt}\) consecutively in this order. Let \(p_{jt}\) be the start of type \(t\)’s segment.
Divide that segment into \(k_t\) equal parts. Rank \(r\) receives
\[ \left[ p_{jt}+\frac{(r-1)f_{jt}}{k_t}, \; p_{jt}+\frac{rf_{jt}}{k_t} \right). \]
Its complete piece \(A_{t,r}\) is the union of these intervals over positive \(f_{jt}\). Every individual in the block therefore receives desired length exactly
\[ \sum_j\frac{f_{jt}}{k_t}=\lambda. \]
The representation stores the counts and the positive entries \((p_{jt},f_{jt})\). It specifies every type-and-rank piece without enumerating individuals. Evaluation requires at most \(m\) interval formulas.
Use a fixed ordering of network vertices and edges for all flow computations. Together with the unique largest block and the segment ordering, this defines a deterministic mechanism on every report profile.
The bisection performs \(O(L+\log N)\) flow computations per stage. Its rational capacities have polynomial bit length.
At the exact rate, write
\[ \lambda=\frac{A}{Qh}, \qquad h=k(B)\leq N. \]
All capacities are integer multiples of \(1/(Qh)\). An augmenting-path implementation starting at zero therefore returns flows with this denominator. Their bit lengths are \(O(L+\log N)\). The segment offsets have the same bound.
Dividing a segment among \(k_t\) ranks introduces a denominator dividing \(Qhk_t\leq QN^2\). Thus every returned endpoint also has bit length \(O(L+\log N)\).
For example, deterministic Edmonds–Karp gives a polynomial number of augmentations regardless of capacity magnitudes. Consequently, construction takes
\[ \operatorname{poly}(m,\tau,L,\log N) \]
time and space, and evaluation takes polynomial time in the same parameters. No operation iterates over \(N\) individuals.
First, allocation rates are nondecreasing.
Suppose block \(B\) receives rate \(\lambda\), and put \(X'=X\setminus D_X(B)\). For any nonempty set \(C\) of remaining types,
\[ d_X(B\cup C)=d_X(B)+d_{X'}(C). \]
Minimality of \(B\)’s ratio implies
\[ d_X(B)+d_{X'}(C) \geq\lambda\bigl(k(B)+k(C)\bigr). \]
Since \(d_X(B)=\lambda k(B)\), we obtain \(d_{X'}(C)\geq\lambda k(C)\). Therefore the next rate is at least \(\lambda\).
Now consider individual \(i\), allocated at rate \(q_i\). Its entire allocated length is desired.
An earlier individual \(j\) receives length at most \(q_i\), so
\[ \operatorname{len}(A_j\cap U_i)\leq\operatorname{len}(A_j)\leq q_i. \]
An individual allocated in the same block receives length \(q_i\), giving the same inequality. A later individual receives no positive-length portion of \(U_i\), because all remaining cake desired by \(i\) is removed when \(i\)’s block is allocated.
Thus \(i\) values its own piece at least as much as every other piece. This proves envy-freeness.
Every positively desired elementary interval is assigned to a type that desires it: an interval is removed at the first stage whose block desires it, and every reported type is eventually allocated. Hence all of \(U_i\) is assigned, up to endpoints. Envy-freeness then gives
\[ \operatorname{len}(U_i) =\sum_{j=1}^N\operatorname{len}(A_j\cap U_i) \leq Nq_i. \]
Dividing by \(\operatorname{len}(U_i)>0\) yields \(V_i(A_i)\geq1/N\).
Fix an individual \(i\), its true reference set \(U_i\), and arbitrary reports of all other individuals. Compare the run where \(i\) reports \(U_i\) with the run where it reports any allowed alternative \(U_i'\).
For this proof only, view the mechanism on the fixed set of individual identities. Lemma 1 shows that the compressed algorithm selects exactly the unique largest minimizing individual block.
Compare the runs while their selected blocks agree and exclude \(i\). At every such stage, the block’s reports are identical in both runs. Its entire desired union is therefore identical and is removed in both runs. Consequently, both runs reach the same remaining individual set and the same remaining cake \(X\).
Stop at the first stage where either the selected blocks differ or the truthful block contains \(i\). Such a stage exists because the truthful run eventually allocates \(i\).
Let \(B,\lambda\) be the truthful block and rate, and \(B',\lambda'\) the alternative block and rate at this common state.
The blocks differ at this stage. Since \(B\) excludes \(i\), its ratio is unchanged by the deviation. Therefore \(\lambda'\leq\lambda\).
I claim that \(i\in B'\). Otherwise, \(B'\)’s ratio would also be unchanged, giving \(\lambda'\geq\lambda\). Thus both rates would equal \(\lambda\). Then \(B'\) would be a truthful minimizer and \(B\) an alternative-profile minimizer. Largest-minimizer selection would imply both \(B'\subseteq B\) and \(B\subseteq B'\), contradicting their difference.
The deviation therefore allocates \(i\) immediately, with total length \(\lambda'\leq\lambda\). Its truly desired length is no greater than this total length. In the truthful run, \(i\) is allocated later at a rate at least \(\lambda\). The deviation cannot improve its utility.
Truthful reporting gives \(i\) desired length exactly \(\lambda\).
If \(\lambda'<\lambda\), the alternative block must contain \(i\): every set excluding \(i\) has unchanged ratio at least \(\lambda\). Hence \(i\)’s alternative piece has total length \(\lambda'<\lambda\), which cannot improve its utility.
It remains to consider \(\lambda'\geq\lambda\). Put
\[ D=X\cap\bigcup_{j\in B}U_j. \]
Here \(B\) is an individual set, so
\[ \operatorname{len}(D)=|B|\lambda. \]
For every \(j\in B\setminus\{i\}\), its report is unchanged. In the alternative run:
Their pieces are disjoint. The truly desired portion of \(i\)’s alternative piece is also contained in \(D\). Consequently,
\[ \operatorname{len}(A_i'\cap U_i) \leq |B|\lambda-(|B|-1)\lambda' \leq\lambda. \]
Again, the deviation cannot improve \(i\)’s utility.
These cases exhaust all possibilities. Dividing desired lengths by the fixed positive quantity \(\operatorname{len}(U_i)\) proves dominant-strategy truthfulness.
The argument tracks the same identity throughout. It places no restriction on the individual’s new type or rank, and allows types to enter or leave the support. The rank merely determines which geometric subsegments implement the guaranteed lengths.
The mechanism above satisfies deterministic dominant-strategy truthfulness, proportionality, and envy-freeness for the stated finite-population model. Its allocation representation and evaluator have uniform polynomial complexity in \(m,\tau,L,\log N\). This settles the support-encoded construction question affirmatively.
⟨structured verdict parsed — rendered above⟩
The prover’s output resolves the support-encoded construction question. The argument is correct: it gives a deterministic mechanism with a polynomial-size representation, polynomial-time construction and evaluation, and proves proportionality, envy-freeness, and dominant-strategy truthfulness. I found no major or minor mathematical issues requiring repair.
The output addresses the requested parameters \(m,\tau,L,\log N\), rather than claiming polynomial time in the explicit population size. It also addresses deviations that change support membership and within-type ranks.
The description of the underlying minimum-ratio allocation structure is consistent with [Chen–Lai–Parkes–Procaccia, Mechanism 1](https://procaccia.info/wp-content/uploads/2020/03/justruth.pdf). Crucially, the output independently establishes the compressed construction and its incentive properties; it does not assume that the cited explicit-population complexity bound settles the support-encoded question.
Verified.
Completing an individual subset to include every remaining individual of each represented type preserves its desired union and weakly increases its cardinality. The resulting ratio therefore cannot increase. Conversely, each type subset represents an individual subset containing all its copies. These two observations establish equality of the minima.
The stated submodularity inequality is correct. Subtracting the modular function \(\lambda k(H)\) preserves submodularity, and minimality gives \(F(H)\geq0\), including the empty set. The displayed inequality consequently establishes closure of minimizers under union. Since the family is finite, its union is the unique largest minimizer.
The same reasoning applies to individual subsets. Completing a minimizing subset still yields a minimizer, so the largest individual minimizer contains whole types.
This remains valid when an intermediate desired union has zero length: completing a zero-ratio minimizer preserves its minimum ratio.
Verified.
The source-only cut has capacity \(Kc\leq2N<M\). Thus no minimum cut crosses a type-to-interval edge.
For a fixed source-side type subset \(H\), the minimum-capacity placement of interval nodes includes exactly the intervals desired by \(H\). Elementary intervals have strictly positive length, so including additional interval nodes increases the capacity. The resulting cut capacity is correctly computed as
\(c(K-k(H))+d_X(H)\).
The application of the max-flow min-cut theorem is valid: the network is finite, capacities are nonnegative rationals, and \(Kc\) is the total source capacity. Requiring every cut to have capacity at least \(Kc\) is equivalent to the displayed inequalities for all \(H\), hence to \(c\leq\lambda\).
The stated vertex and edge bounds are correct and do not depend on enumerating individuals.
Verified.
The product of endpoint denominators is a valid common denominator \(Q\), with binary length \(O(L)\). Removing whole elementary intervals preserves the property that every desired-union length is an integer multiple of \(1/Q\).
For distinct candidate ratios, the numerator \(Ah'-Bh\) is a nonzero integer. Therefore the separation bound \(1/(QN^2)\) is correct.
The initial bisection bounds are valid: zero is feasible, whereas \(2\) is infeasible because total interval-to-sink capacity is at most \(1\) and \(K\geq1\). The stated number of iterations suffices.
At \(c_+\), an infeasible minimum cut supplies a nonempty subset with ratio below \(c_+\). That ratio is at least \(\lambda\) by definition. The separation bound and bracket width exclude any strictly larger candidate ratio, so the recovered value equals \(\lambda\).
The residual-graph characterization of the largest minimum-cut source side is also correct. Every minimum-cut source side has no outgoing positive-capacity residual edge and cannot contain a vertex with a residual path to the sink. Conversely, the stated set \(Z\) contains the source, excludes the sink, and has no outgoing positive-capacity residual edge.
Its type subset \(B\) is therefore a minimizer containing every other minimizing type subset. Nonemptiness follows from existence of a nonempty minimizer.
Verified.
At the exact rate, every source edge is saturated. Types in \(B\) send total flow \(k(B)\lambda=d_X(B)\), and all their outgoing flow enters intervals in \(D_X(B)\). Hence those intervals are completely filled by block flow. Flow belonging to types outside \(B\) cannot occupy any positive capacity there.
The consecutive segment placement and rank subdivision give each individual of type \(t\) length exactly \(\lambda\), entirely inside its reported reference set. Segments are disjoint within an elementary interval, and different elementary intervals and stages are disjoint. The half-open convention handles boundary intersections.
The representation stores segment data rather than individual pieces. Evaluation computes at most \(m\) intervals using the binary-encoded rank, so it does not enumerate the \(k_t\) individuals.
Fixed orderings together with a deterministic flow implementation specify a deterministic mechanism.
Verified.
At most \(\tau\) stages occur. Each stage uses \(O(L+\log N)\) feasibility tests on a network of polynomial size.
At the exact rate, capacities are integer multiples of \(1/(Qh)\), with \(h\leq N\). Starting an augmenting-path algorithm at zero preserves this denominator bound. Relevant capacities and flows have polynomial binary length.
Segment starts retain the stated denominator bound. Dividing a segment by \(k_t\) introduces at most the product denominator \(Qhk_t\leq QN^2\). Rank multiplication also uses only \(O(\log N)\)-bit integers.
Edmonds–Karp provides a polynomial number of augmentations independent of capacity magnitudes; exact rational arithmetic here has polynomial bit cost. Thus the claimed polynomial bounds for construction, storage, and evaluation follow.
Verified.
The identity relating \(d_X(B\cup C)\), \(d_X(B)\), and \(d_{X'}(C)\) is correct because \(X'\) removes precisely \(D_X(B)\). Applying minimum-ratio optimality proves that subsequent rates cannot decrease.
The envy comparison correctly covers all possibilities:
Every positively desired elementary interval is eventually assigned. Consequently, the proportionality calculation sums the entire length of \(U_i\) across the allocated pieces. Dividing by the explicitly positive normalization length is valid.
Verified.
The comparison fixes arbitrary reports of all other identities, as dominant-strategy truthfulness requires.
When the runs select the same block excluding \(i\), they remove the same desired union. Their geometric subdivisions may differ, but this does not affect the common remaining cake or remaining identities. The proof correctly needs only those common states.
Case 1. Because \(B\) excludes \(i\), its ratio is unchanged, giving \(\lambda'\leq\lambda\). If \(B'\) also excluded \(i\), its unchanged ratio would give the reverse inequality. At equal rates, largest-minimizer selection would force equality of the blocks, contradicting the stopping condition. Thus the deviator is allocated immediately, with total length no greater than its eventual truthful desired length.
Case 2, \(\lambda'<\lambda\). Any subset excluding \(i\) has an unchanged ratio at least \(\lambda\). Therefore \(B'\) must contain \(i\), and the deviating total length is strictly smaller than its truthful desired length.
Case 2, \(\lambda'\geq\lambda\). The other members of truthful block \(B\) remain unallocated at the common state. Their eventual alternative allocations lie inside \(D\) and each have length at least \(\lambda'\). The truly desired portion of \(i\)’s alternative allocation also lies inside \(D\). Disjointness therefore justifies the displayed capacity bound, which is at most \(\lambda\). This includes the singleton-block case.
Normalization uses the same true positive length in both runs. Support changes and rank changes do not invalidate any step, because the proof follows identities and uses allocation lengths and containment rather than rank-specific geometry.
The argument covers \(N=1\), a single support type, tied minimum ratios, disconnected reference sets, undesired cake, and deviations that introduce or eliminate a type. Endpoint differences have zero valuation and are handled explicitly.
No repair or additional mathematical 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.