Answer: \(\mathrm{P}\): polynomial-time solvable
Theorem 9 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor any temporal fair division instance with identical days, it is possible to find an allocation that is SD- EF1 per day and SD-PROP1 overall in polynomial time. To achieve these guarantees, we use an algorithm that is almost identical to Algorithm 1, the algorithm which was used to achieve SD-EF1 per day and PROP1 overall in the general case, but with one major change.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational masses of complete agent types, k identical days with rational per-capita supplies of finitely many indivisible good categories, and type rankings/values respecting the identical-days condition, output a finite-support rational census x over integral bundle histories whose row masses equal the type masses and whose aggregate supplies equal the per-capita supplies, such that every supported pair of histories satisfies SD-EF1 on every day and every supported type-history satisfies the per-capita clone version of SD-PROP1 overall.
A society is given by its support: a list of \(\tau\) complete types with positive binary-rational masses \(p_i\), normalized by \(\sum_i p_i=1\). Here \(\tau\) is the support size, not the number of possible types.
There are \(m\geq1\) good categories, positive binary-rational per-capita supplies \(q_c\), and \(k\geq1\) identical days, with \(k\) encoded in unary. Type \(i\) has nonnegative rational additive values \(v_{ic}\), identical across days; copies of a category are interchangeable. Let \(H_i(c)=\{d:v_{id}\geq v_{ic}\}\); ties remain weak in all fairness comparisons.
An integral history is \(h\in\mathbb Z_{\geq0}^{k\times m}\). Output an explicitly listed, finite-support rational census \(x_{i,h}\geq0\) satisfying \(\sum_h x_{i,h}=p_i\) and \(\sum_{i,h}x_{i,h}h_{tc}=q_c\) for every day \(t\) and category \(c\).
Daily SD-EF1 means that for every ordered pair \((i,h),(j,h')\) with positive census mass and every day \(t\) on which \(h'_t\neq0\), there is a category \(a\) with \(h'_{ta}>0\) such that \(\sum_{d\in H_i(c)}h_{td}\geq\sum_{d\in H_i(c)}h'_{td}-\mathbf1_{\{a\in H_i(c)\}}\) for every category \(c\).
Overall per-capita clone SD-PROP1 means that for every supported \((i,h)\), there is one category \(a\) such that \(\sum_{t=1}^k\sum_{d\in H_i(c)}h_{td}+\mathbf1_{\{a\in H_i(c)\}}\geq\left\lceil k\sum_{d\in H_i(c)}q_d\right\rceil\) for every category \(c\). The added copy is outside the recipient's bundle in a sufficiently large finite clone realization, even if the recipient already owns copies of its category.
Is constructing such a census solvable in polynomial time in \(m,\tau,k,L\), where \(L\) is the total binary bit length of the rational input, or is it NP-hard?
For finite agents and explicitly listed goods on identical days, an allocation satisfying SD-EF1 daily and SD-PROP1 overall always exists and is computable in polynomial time. [Cookson, Ebadian, and Shah](https://arxiv.org/pdf/2410.23416).
No result settling this exact rational-mass census problem was located in the literature search.
The census can be constructed in polynomial time in \(m,\tau,k,L\). The construction uses cyclic round-robin orders whose starting points are evenly spaced across the days. A potentially large clone population is represented and processed through intervals of identical clones.
We prove the stronger guarantee that every supported \((i,h)\) satisfies
\(\displaystyle \sum_{t=1}^{k}\sum_{d\in H_i(c)}h_{td}\ \geq\ \left\lfloor k\sum_{d\in H_i(c)}q_d\right\rfloor\qquad\text{for every category }c.\)
Adding one copy of a most-preferred category therefore establishes the required overall SD-PROP1 condition.
The proof below is direct; it does not infer a compressed-input runtime from the cited [finite-agent theorem](https://arxiv.org/pdf/2410.23416).
For each category \(c\), define
\(\displaystyle B_c=\lfloor q_c\rfloor,\qquad r_c=q_c-B_c.\)
Thus \(0\leq r_c<1\). We first allocate the residual supplies \(r_c\), and then give every recipient \(B_c\) copies of category \(c\) on every day.
Write
\(\displaystyle R=\sum_{c=1}^{m}r_c<m.\)
Adding the same bundle to all recipients preserves daily SD comparisons: for any threshold set \(H_i(c)\), its contribution cancels when comparing two recipients.
For overall proportionality, if the residual history \(y\) satisfies
\(\displaystyle \sum_{t=1}^{k}\sum_{d\in H_i(c)}y_{td}\geq\left\lfloor k\sum_{d\in H_i(c)}r_d\right\rfloor,\)
then the full history \(h_{td}=B_d+y_{td}\) satisfies
\(\displaystyle \sum_{t=1}^{k}\sum_{d\in H_i(c)}h_{td} \geq k\sum_{d\in H_i(c)}B_d+ \left\lfloor k\sum_{d\in H_i(c)}r_d\right\rfloor = \left\lfloor k\sum_{d\in H_i(c)}q_d\right\rfloor. \)
The equality holds because \(k\sum_{d\in H_i(c)}B_d\) is an integer.
If \(R=0\), giving everyone the common bundle already establishes these guarantees. Henceforth suppose \(R>0\).
Let \(D\) be the product of the denominators of all input masses and supplies, and set
\(\displaystyle N=kD,\qquad n=N/k=D.\)
Then \(Np_i\), \(Nq_c\), and \(Nr_c\) are integers, and \(N\) is divisible by \(k\). Although \(N\) may be numerically large, its binary length is \(O(L+\log k)\).
Use clone labels \(a\in\{0,\ldots,N-1\}\). Put
\(\displaystyle A_0=0,\qquad A_i=N\sum_{j=1}^{i}p_j.\)
The clones of type \(i\) have labels in the integer interval \([A_{i-1},A_i)\). These intervals partition the clone population and contain exactly \(Np_i\) labels.
On every day, the residual stock of category \(c\) is
\(\displaystyle S_c=Nr_c,\)
and the total number of residual goods is
\(\displaystyle M=\sum_c S_c=NR.\)
Consequently,
\(\displaystyle \left\lceil M/N\right\rceil=\lceil R\rceil\leq m.\)
The allocation below therefore has at most \(m\) round-robin rounds per day.
Fix a deterministic category order for breaking valuation ties. All clones of a type use this same tie-breaking rule.
On day \(t\in\{1,\ldots,k\}\), define the offset
\(\displaystyle o_t=(t-1)n.\)
At pick index \(z\in\{0,\ldots,M-1\}\), the picking clone is
\(\displaystyle a_t(z)=(z-o_t)\bmod N.\)
That clone takes a copy of a highest-valued category with positive remaining stock.
Thus each complete round visits every clone once, in a fixed cyclic order for that day. The position of clone \(a\) within a round is
\(\displaystyle \rho_t(a)=(a+o_t)\bmod N.\)
Its pick indices are exactly
\(\displaystyle bN+\rho_t(a),\qquad b\in\mathbb Z_{\geq0},\quad bN+\rho_t(a)<M.\)
Denote its residual history by \(y_{a,tc}\). We next prove fairness for this finite allocation. Section 6 shows how to compute it without enumerating the clones or goods.
Fix a day \(t\), an evaluating clone \(a\) of type \(i\), and another clone \(a'\).
A basic property of greedy picking is the following: if clone \(a\) picks before a particular good is taken by another clone, that good is still available at \(a\)'s pick. Hence the good selected by \(a\) has value at least as large, according to type \(i\).
If \(a=a'\), the comparison is immediate. Otherwise their round positions differ.
For every pick made by \(a'\) in round \(b\), clone \(a\)'s pick in the same round exists and occurs earlier:
\(\displaystyle bN+\rho_t(a)<bN+\rho_t(a')<M.\)
Match each good taken by \(a'\) to the good taken by \(a\) in that round. The matched goods of \(a\) are distinct, and each is weakly preferred by type \(i\) to its matched good.
It follows that \(a\)'s residual bundle SD-dominates the entire residual bundle of \(a'\).
If \(a'\)'s residual bundle is nonempty, remove its first picked good. Every remaining good of \(a'\) was picked in a round \(b\geq1\).
Match that good to \(a\)'s pick in round \(b-1\). This pick exists and occurs earlier, since
\(\displaystyle (b-1)N+\rho_t(a)<bN+\rho_t(a')<M. \)
Again, the matched goods of \(a\) are distinct and weakly preferred by type \(i\).
Thus removing one good from \(a'\)'s residual bundle makes it SD-dominated by \(a\)'s residual bundle.
These matchings apply simultaneously to every weak threshold \(H_i(c)\): whenever a matched good of \(a'\) belongs to \(H_i(c)\), its matching good of \(a\) also belongs to that set.
After adding the common bundle, the same comparisons remain valid. If the target residual bundle is empty, the evaluating full bundle already SD-dominates the target full bundle; when the latter is nonempty, removing any of its goods preserves that dominance.
Therefore the full allocation is SD-EF1 on every day, with ties treated weakly as required.
Fix a clone \(a\) of type \(i\) and a threshold set \(H=H_i(c)\). Its residual stock on each day is
\(\displaystyle S_H=\sum_{d\in H}S_d=N\sum_{d\in H}r_d.\)
At every pick index \(z<S_H\), at least one residual good from \(H\) remains: only \(z\) goods in total have been removed, whereas initially \(H\) contained \(S_H\) goods.
Consequently, whenever clone \(a\) picks at such an index, it selects a category in \(H\). Indeed, its selected category is weakly preferred to an available category in \(H\), so it also belongs to \(H\).
We now count these early picks across all days.
Write
\(\displaystyle a=jn+\alpha,\qquad 0\leq\alpha<n.\)
Because the offsets are \(0,n,\ldots,(k-1)n\), the round positions of \(a\) across the days are precisely
\(\displaystyle \{\rho_t(a):1\leq t\leq k\}=\{\alpha,\alpha+n,\ldots,\alpha+(k-1)n\}.\)
Hence its pick indices across all days, before truncation at \(M\), are exactly
\(\displaystyle \alpha+\ell n,\qquad \ell\in\mathbb Z_{\geq0},\)
each occurring once. Since \(S_H\leq M\), every such index below \(S_H\) is an actual pick.
Write \(S_H=un+v\), where \(0\leq v<n\). For every \(\ell\in\{0,\ldots,u-1\}\),
\(\displaystyle \alpha+\ell n\leq(n-1)+(u-1)n=un-1<S_H.\)
Thus \(a\) has at least \(u\) early picks, all selecting goods in \(H\). Therefore
\(\displaystyle \sum_{t=1}^{k}\sum_{d\in H}y_{a,td} \geq u = \left\lfloor S_H/n\right\rfloor = \left\lfloor k\sum_{d\in H}r_d\right\rfloor. \)
Adding the common bundle yields the claimed stronger bound:
\(\displaystyle \sum_{t=1}^{k}\sum_{d\in H_i(c)}h_{a,td} \geq \left\lfloor k\sum_{d\in H_i(c)}q_d\right\rfloor. \)
Choose a most-preferred category \(c_i^\star\) for type \(i\). It belongs to every \(H_i(c)\). Since \(\lfloor w\rfloor+1\geq\lceil w\rceil\), adding one copy of \(c_i^\star\) establishes all the overall SD-PROP1 inequalities simultaneously.
The resulting census has denominator dividing \(N\). Each clone receives at most \(m\) residual goods per day, so its total number of category-\(c\) copies is at most \(k(B_c+m)\).
Replicate the resulting clone allocation by the integer factor
\(\displaystyle F=m+1+\sum_c B_c.\)
Because \(Nq_c\) is a positive integer,
\(\displaystyle kFNq_c\geq kF>k(B_c+m).\)
The enlarged realization therefore contains more category-\(c\) copies than any single recipient owns, for every category \(c\). In particular, a copy of \(c_i^\star\) exists outside each recipient's bundle. Replication preserves the census.
It remains to compress the greedy simulation.
Within one round on day \(t\), clone labels are traversed cyclically. Because each type occupies one consecutive label interval, this traversal splits into at most \(\tau+1\) runs. Within each run:
The final partial round has the same bound on its number of runs.
Suppose a run has \(u\) unprocessed labels, and its type's highest-valued available category \(c\) has remaining stock \(W_c\). The next
\(\displaystyle \ell=\min\{u,W_c\}\)
clones all select category \(c\). This follows because no other category's stock changes during those picks, and \(c\) remains available until its stock is exhausted.
Process those picks together. Record their day, category, and consecutive label interval, and subtract \(\ell\) from the stock.
Each operation ends either a type run or a category's stock. There are at most \(m(\tau+1)\) runs per day and at most \(m\) category exhaustions. Thus the total number \(T\) of recorded blocks satisfies
\(\displaystyle T\leq k\bigl(m(\tau+1)+m\bigr).\)
The required runs and their lengths are computed directly from the type boundaries and the cyclic offsets. No iteration over the \(N\) labels is needed.
Collect and sort:
Partition \([0,N)\) at these endpoints. On every resulting nonempty interval \(J=[u,v)\), all clones have the same type and the same history: membership in every recorded block is constant throughout \(J\).
For that type \(i\) and full history \(h\), assign mass
\(\displaystyle x_{i,h}=(v-u)/N.\)
Merge entries with equal pairs \((i,h)\) by adding their masses. The number of entries is at most \(\tau+2T\).
The type-mass equations hold because the intervals of type \(i\) together contain exactly \(Np_i\) labels:
\(\displaystyle \sum_h x_{i,h}=p_i.\)
Every day's greedy allocation consumes all \(S_c\) residual category-\(c\) goods. Therefore
\(\displaystyle \sum_{i,h}x_{i,h}h_{tc} = B_c+\frac{S_c}{N} = q_c. \)
Every supported history occurs among actual clones, so the fairness guarantees proved above hold for every required supported pair.
The construction uses exact arithmetic with polynomial-size integers:
Category choices require only exact comparisons of the input rational values. Sorting interval endpoints, constructing histories, and merging equal entries also take polynomial time. The algorithm processes \(k\) days, consistent with unary encoding of \(k\).
This proves a deterministic polynomial-time construction for the exact rational-mass census problem, including weak ties and the stated outside-copy interpretation.
⟨structured verdict parsed — rendered above⟩
The prover’s construction resolves the task. The finite allocation satisfies both fairness requirements, and the interval simulation produces an explicitly listed census in polynomial time. I found no major or minor issues.
For each category, \(B_c=\lfloor q_c\rfloor\) is a nonnegative integer and \(r_c=q_c-B_c\) satisfies \(0\leq r_c<1\). Consequently, \(R=\sum_c r_c<m\).
Giving everyone the same daily bundle preserves the residual SD-EF1 inequalities: its contribution to each threshold count cancels between the evaluating and target recipients. The overall floor identity is also correct because \(k\sum_{d\in H_i(c)}B_d\) is an integer.
The case \(R=0\) is handled correctly. All recipients have identical daily bundles, and their overall threshold counts equal the required benchmarks before any additional copy.
The product \(D\) of the input mass and supply denominators is a common multiple of those denominators. Thus \(Np_i\), \(Nq_c\), and \(Nr_c\) are integers for \(N=kD\).
The binary length of a product is bounded by the sum of its factors’ binary lengths, so the claimed \(O(L+\log k)\) bound for \(N\) is justified. The positive masses and normalization ensure that the integer type intervals partition all \(N\) clone labels and have the prescribed sizes.
The total residual stock is the integer \(M=NR\). Since \(R<m\), the number of complete or partial rounds is \(\lceil M/N\rceil\leq m\).
At index \(z\), the formula \(a_t(z)=(z-o_t)\bmod N\) visits each clone once per complete round. Its inverse position formula, \(\rho_t(a)=(a+o_t)\bmod N\), is correct.
The listed pick indices \(bN+\rho_t(a)<M\) therefore describe exactly the picks received by clone \(a\). Fixed tie-breaking makes the subsequent compressed simulation deterministic while preserving all weak valuation comparisons.
When the evaluating clone precedes the target within a round, every target pick has an existing earlier evaluating pick in that same round. When the evaluating clone follows the target, removing the target’s first pick permits matching each remaining target pick to the evaluating clone’s pick in the preceding round. The displayed inequalities establish both existence and precedence of those matched picks.
Each matching is injective. At the earlier pick, a copy of the category selected at the later target pick remains available. Greedy selection therefore gives the evaluating clone a weakly preferred good. This implication holds simultaneously for every weak threshold set, including tied valuations.
The self-comparison is immediate. The common bundle preserves the inequalities with the same removed residual good. If the target residual bundle is empty, the evaluating full bundle already dominates the target full bundle; if that target full bundle is nonempty, any of its goods can serve as the required removal. Thus the proof covers exactly the task’s nonempty-target condition.
For a fixed threshold set \(H\), at every index \(z<S_H\), fewer than \(S_H\) goods have been removed in total. Hence some good from \(H\) remains. A greedy pick by the evaluating type must then belong to \(H\), because membership in \(H\) is defined by a weak valuation threshold.
Writing \(a=jn+\alpha\) with \(0\leq\alpha<n\), the offsets permute the positions
\(\alpha,\alpha+n,\ldots,\alpha+(k-1)n\).
Across all days and rounds, these generate each index \(\alpha+\ell n\) exactly once. Since \(S_H\leq M\), every such index below \(S_H\) is an actual pick.
The division \(S_H=un+v\), with \(0\leq v<n\), gives at least \(u\) such picks. The calculation
\(u=\lfloor S_H/n\rfloor=\lfloor k\sum_{d\in H}r_d\rfloor\)
is correct. When \(u=0\), the claimed lower bound is simply nonnegativity, so there is no missing boundary case.
Adding the common bundle yields the asserted full-history floor bound. A most-preferred category belongs to every \(H_i(c)\), even with ties, and \(\lfloor w\rfloor+1\geq\lceil w\rceil\). Therefore one category supplies all required overall SD-PROP1 inequalities simultaneously.
Each clone receives at most \(m\) residual goods per day, so its total ownership of category \(c\) is bounded by \(k(B_c+m)\).
The proposed replication factor satisfies \(F>B_c+m\) for every category. Because \(Nq_c\) is a positive integer, the enlarged realization contains
\(kFNq_c\geq kF>k(B_c+m)\)
copies of category \(c\). Thus some copy lies outside any given recipient’s bundle.
Replicating recipients together with their allocations preserves the normalized census and all fairness comparisons. The argument meets the task’s stated interpretation of an outside copy.
A cyclic traversal of the consecutive type intervals has at most \(\tau+1\) runs with increasing, nonwrapping labels. The same bound applies to a partial traversal.
Within a run, the next \(\min\{u,W_c\}\) clones choose the same highest-priority available category: their preferences and tie-breaking agree, that category remains available throughout those picks, and other stocks do not change.
Each block ends a run or exhausts a category. There are at most \(m(\tau+1)\) runs and \(m\) category exhaustions per day, establishing the stated bound
\(T\leq k(m(\tau+1)+m)\).
Nothing in this simulation requires enumerating the numerically large clone population or stock.
Partitioning at all type boundaries and recorded block endpoints makes both type and block membership constant on every resulting interval. Consequently, every clone in an interval has the same complete history.
Assigning its normalized interval length as mass, and merging identical type-history pairs, gives the claimed support bound \(\tau+2T\). The type-mass equations follow from the sizes of the type intervals. Exact stock consumption gives every daily supply equation.
Every positive census entry represents actual clones. Therefore every ordered pair of supported entries inherits the daily comparisons already proved, and every supported entry inherits the overall guarantee.
Label endpoints and residual category stocks have polynomial binary length; \(M<mN\). Full history entries have polynomial binary length because they are bounded by \(B_c+m\). Output masses have denominator dividing \(N\).
The numbers of blocks, partition intervals, and output entries are polynomial. Explicitly constructing the \(k\times m\) histories, comparing rational valuations, sorting endpoints, and merging entries all require only polynomially many operations on polynomial-length data. Unary encoding of \(k\) supports the claimed dependence on the number of days.
The cited finite-agent theorem is not used as a premise, so no external theorem application remains to be verified.
No additional clarification is needed to verify the construction.
⟨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.