Answer: polynomial-time solvable
Theorem 3.1 — class: algorithmic
Given a rational type distribution \(\mu\) over strict rankings of \(K\) item classes, a finite piecewise-constant schedule \(\sigma:[0,1]\to T\) with \(|\{s:\sigma(s)=t\}|=\mu_t\), and rational per-capita supplies \(b_j\) with \(\sum_j b_j=R\), compute the limiting bundle masses \(x_{t,\mathbf{k}}\). The schedule repeats for \(R\) rounds; in each finite approximation, \(q\mu_t\) agents of type \(t\) take turns in schedule order and each item class has \(qb_j\) indivisible copies. Each agent takes her highest-ranked class still available on her turn. Output the limiting mass of each type receiving each integral bundle \(\mathbf{k}\in\mathbb{N}^K\), using noiseless comparison oracles for the type rankings.
A society is given by its support: a list \(T\) of \(\tau\) strict-ranking types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings. There are \(m=K\geq1\) item classes; a noiseless unit-cost oracle answers comparisons between two classes for a specified type.
The schedule \(\sigma:[0,1)\to T\) is supplied as \(h\) consecutive half-open intervals with rational endpoints and type labels, satisfying \(\lambda(\sigma^{-1}(t))=\mu_t\), where \(\lambda\) is Lebesgue measure. Supplies \(b_j\geq0\) are binary rationals with \(\sum_{j=1}^{m}b_j=R\), for a positive integer \(R\) encoded in binary.
Let \(D\) be the least common multiple of all input rational denominators. For each positive multiple \(q\) of \(D\), agent \(a\in\{1,\ldots,q\}\) has type \(\sigma((a-1)/q)\); initially class \(j\) has \(qb_j\) copies. The same agents take turns in order \(1,\ldots,q\) for \(R\) rounds, retaining their bundles between rounds. Each turn takes one copy of the highest-ranked nonempty class; copies within a class are interchangeable.
For \(\mathbf{k}\in\mathbb{Z}_{\geq0}^{m}\) with \(\sum_j k_j=R\), define \(x_{t,\mathbf{k}}=\lim_{q\to\infty,\ D\mid q}q^{-1}|\{a:\sigma((a-1)/q)=t\text{ and agent }a\text{ receives bundle }\mathbf{k}\}|\). The computational output is the sparse list of positive masses, represented exactly as binary rationals, with bundle coordinates in binary; omitted masses are zero. Let \(L\) be the total bit length of the supplied numerical data and labels.
Is exact computation of these limiting bundle masses polynomial-time in \(m,\tau,h,L\), using noiseless comparison queries, or is it NP-hard?
For explicitly listed agents and distinct items, deterministic noiseless round-robin allocation is polynomial-time, with the stated bound \(O(nM\log(M/n))\) for \(n\) agents and \(M\) items; randomized comparison algorithms require \(\Omega(nM+M\log M)\) queries. [Source](https://arxiv.org/html/2404.19402v1).
No result settling this exact continuous problem was located in the literature search.
Theorem. The limiting bundle masses exist and can be computed exactly in time polynomial in \(m,\tau,h,L\), using \(O(\tau m\log(m+1))\) noiseless comparison queries. There are at most \(h+m\) positive output entries.
In fact, the normalized bundle masses are identical for every positive multiple \(q\) of \(D\). Thus no approximation or limit computation is needed.
Write the schedule endpoints as \(0=e_0<e_1<\cdots<e_h=1\), with type label \(t_i\) on \([e_{i-1},e_i)\). Empty intervals, if supplied, can first be discarded.
By the definition of \(D\), all \(De_i\) and \(Db_j\) are integers. Consider the specified allocation process with exactly \(D\) agents, and denote agent \(a\)'s final bundle by \(\mathbf{k}(a)\).
Replication lemma. For every positive integer \(z\), in the process with \(q=zD\) agents, the consecutive agents
\((a-1)z+1,\ldots,az\) all receive bundle \(\mathbf{k}(a)\).
Proof. Call these \(z\) agents the clone block of base agent \(a\). Their positions belong to
\([(a-1)/D,a/D)\). Since every schedule endpoint lies on the grid with spacing \(1/D\), this entire interval has the type of base agent \(a\).
Initially, every inventory in the clone process is \(z\) times the corresponding inventory in the base process. We induct over base turns, in their chronological order across all rounds.
Suppose the inventories have this scaling immediately before a base turn and its corresponding clone block. The base agent chooses some class \(j\) with a positive integer inventory \(c\). The clone process has \(zc\) copies of this class. All members of the clone block have the same strict ranking, and they can all choose \(j\): even if \(c=1\), the last copy is consumed only by the last clone. No more preferred class becomes available during the block.
After the block, class \(j\)'s inventory is \(z(c-1)\), and all other inventories retain the scaling. This establishes the induction. Each clone therefore makes the same choice as its base agent in every round. \(\square\)
Consequently, for every allowed \(q=zD\),
\( q^{-1}|\{a:\text{type}(a)=t,\ \text{bundle}(a)=\mathbf{k}\}| = D^{-1}|\{a\in\{1,\ldots,D\}:\text{type}(a)=t,\ \mathbf{k}(a)=\mathbf{k}\}|. \)
This proves both existence of the requested limits and their exact equality to the normalized \(D\)-agent allocation.
Although \(D\) may be exponentially large, the next algorithm never enumerates its agents.
Rescale the population coordinate to \([0,D)\). The schedule becomes \(h\) intervals with integer endpoints \(De_i\). Initially class \(j\) has the integer inventory \(B_j=Db_j\), and
\(\sum_j B_j=DR\).
Maintain:
Initially, this partition is the schedule partition, and every bundle is zero.
A partition interval \([u,v)\), with integer endpoints, represents exactly the agents whose zero-based positions are \(u,\ldots,v-1\). Thus its population mass is \((v-u)/D\).
At a round boundary, let \(A=\{j:S_j>0\}\). For each type \(t\), let \(c_t(A)\) be its highest-ranked class in \(A\). Define the integer demand vector
\( d_j(A)=\sum_{i:c_{t_i}(A)=j}D(e_i-e_{i-1}). \)
These demands satisfy \(\sum_jd_j(A)=D\).
Suppose \(r<R\). Define
\( N=\min_{j:d_j(A)>0}\left\lfloor S_j/d_j(A)\right\rfloor. \)
If \(N>0\), process \(N\) complete rounds simultaneously:
Batching lemma. This update exactly reproduces the next \(N\) rounds.
Proof. Prescribe that every agent of type \(t\) chooses \(c_t(A)\) in each of these rounds. The total prescribed consumption of class \(j\) is \(Nd_j(A)\), which is at most \(S_j\).
Induct over the prescribed turns. Immediately before any prescribed choice of class \(j\), fewer than \(Nd_j(A)\) prescribed copies of that class have been consumed. Hence at least one copy remains. Moreover, \(j\) was the agent's highest-ranked class in \(A\), while classes outside \(A\) had zero inventory and remain unavailable. Therefore the actual greedy choice is precisely the prescribed choice.
This proves every prescribed turn is executed, including cases where a class is exhausted before the end of the final batched round. \(\square\)
The batch cannot exceed the remaining number of rounds. Indeed, at a round boundary,
\( \sum_jS_j=D(R-r). \)
If \(N>R-r\), then \(S_j\geq Nd_j(A)\) for every demanded class, implying \(\sum_jS_j\geq ND>D(R-r)\), a contradiction.
If \(N=0\), process one round by scanning the \(h\) schedule intervals from left to right.
Within a schedule interval of type \(t\), let \(\ell\) be its unprocessed length. Choose the highest-ranked class \(j\) with \(S_j>0\), and set \(w=\min\{\ell,S_j\}\). The next \(w\) agents all choose \(j\). Decrease \(S_j\) by \(w\), and add one copy of class \(j\) to their bundles.
If these agents end inside a maintained partition interval, split that interval at the endpoint of the processed segment. Continue until the entire round has been processed.
All lengths and inventories are integers. Hence this operation implements exactly \(w\) consecutive turns, without enumerating those turns. Every segment ends either at a schedule endpoint or at a class exhaustion.
Exhaustion lemma. Every round processed with \(N=0\) exhausts at least one previously nonempty class.
Proof. The condition \(N=0\) implies that some demanded class \(j\) satisfies \(S_j<d_j(A)\).
If no class were exhausted during the round, the available set would remain \(A\), so every type would always choose \(c_t(A)\). Class \(j\) would then lose exactly \(d_j(A)\) copies, exceeding its inventory. This is impossible. \(\square\)
The scan can always complete: before the round there are \(D(R-r)\) copies in total, with \(R-r\geq1\), so at least \(D\) copies are available.
Every class is exhausted at most once. The exhaustion lemma therefore bounds the number of individually scanned rounds by \(m\).
There are also at most \(m+1\) positive batches. To see this, consider a nonterminal batch.
Different charges use disjoint class exhaustions. A possible terminal batch contributes at most one additional batch.
Each scanned round has at most \(h+m\) segments: schedule endpoints account for at most \(h\) segments, and internal exhaustions add at most \(m\). Consequently, the algorithm performs polynomially many interval operations, independent of the magnitudes of \(D\) and \(R\).
A batch does not split any partition interval, because all agents of a given type receive the same class in every batched round.
During a scanned round, a new partition boundary can occur only at a class exhaustion. There are at most \(m\) such events over the entire allocation. Starting from \(h\) schedule intervals, the final partition therefore has at most \(h+m\) intervals.
For each final interval \([u,v)\) carrying type \(t\) and bundle \(\mathbf{k}\), contribute \((v-u)/D\) to the output entry \((t,\mathbf{k})\). Combine entries with identical keys. This gives at most \(h+m\) positive entries.
These masses are exactly those proved in Section 1. Every bundle coordinate is a nonnegative integer, and every bundle has total size \(R\), since every represented agent receives exactly one copy per round.
For the arithmetic bound, \(D\) is at most the product of the input denominators, so its binary length is \(O(L)\). It can be computed by repeated greatest-common-divisor and least-common-multiple operations in polynomial time.
Throughout the algorithm:
Thus every stored integer has polynomial bit length. All updates use integer addition, subtraction, comparison, multiplication, or division with remainder. Together with the operation counts above, this proves polynomial bit complexity.
Finally, sort the \(m\) classes once for each of the \(\tau\) support types. This uses \(O(\tau m\log(m+1))\) noiseless comparison queries. All subsequent choices can be determined from those rankings.
The exact computation problem is polynomial-time solvable in \(m,\tau,h,L\). The proof handles both potentially exponential quantities: population size is compressed into intervals, and the number of rounds is compressed into batches. The limiting masses are already exact at every permitted population size.
⟨structured verdict parsed — rendered above⟩
The argument establishes the claimed polynomial-time result. I found no false step, unverified theorem application, or gap requiring additional mathematics.
Every schedule endpoint and initial supply becomes integral after multiplication by \(D\). Thus the process with \(D\) agents is well-defined.
For \(q=zD\), the clone block corresponding to base agent \(a\) lies entirely within the same schedule interval as that agent. Half-open endpoints cause no exception: a block beginning at a schedule boundary receives the label of the interval beginning there.
The inventory induction is correct. Immediately before a corresponding turn and clone block, the available classes coincide because their inventories differ by the positive factor \(z\). If the base agent selects class \(j\) with inventory \(c\geq1\), the clone block starts with \(zc\) copies. Before its final member acts, at least one copy remains. All clones therefore select \(j\), and the inventories again have the required scaling afterward.
The induction applies across round boundaries as well as within rounds. Consequently, each base agent’s final bundle is replicated exactly \(z\) times. The normalized masses are constant over every permitted population size, which proves the stated limits exist and equal the normalized \(D\)-agent masses.
Assessment: Correct.
The integer interval \([u,v)\) represents exactly \(v-u\) base agents. Starting with schedule boundaries preserves a common type on every maintained partition interval.
At any round boundary with \(r<R\), the residual total is \(D(R-r)>0\), so the available set \(A\) is nonempty. Strict rankings therefore give each type a unique choice \(c_t(A)\).
The demand formula counts all agents choosing each class under the fixed available set. Its coordinates are nonnegative integers and sum to \(D\). Hence at least one demand is positive, and the minimum defining \(N\) is well-defined.
Assessment: Correct, including zero-supply classes and zero-demand coordinates.
For every demanded class, the definition of \(N\) gives \(Nd_j(A)\leq S_j\).
The prescribed-turn induction correctly proves feasibility. Before a prescribed selection of class \(j\), fewer than its total prescribed selections have occurred, so its inventory is positive. No class outside the initial available set can become available, and no initially available class is preferred to the prescribed choice by that agent.
This also handles exhaustion during the final batched round: the induction guarantees that any class exhausted then has no remaining prescribed selection.
The bound \(N\leq R-r\) follows from summing the inventory inequalities over demanded classes and using the residual-total invariant. Inventories of undemanded classes are nonnegative, so they do not invalidate that comparison.
Assessment: Correct.
Within a constant-type schedule interval, the next \(w=\min\{\ell,S_j\}\) agents choose the same current favorite. Before the last of these turns, that class remains available, and no more-preferred class becomes available. The segment operation therefore exactly reproduces those turns.
Updating the bundles requires applying the increment across the maintained partition intervals intersecting the segment. Existing boundaries already separate any previously different bundles; only the segment endpoint can require a new boundary. This is a routine interval operation consistent with the stated representation.
“Process one round” implicitly advances the completed-round counter by one. Its omission as a separate update bullet does not create a mathematical gap.
The exhaustion lemma is valid: if no class disappeared during the scan, every agent would retain its initial choice, contradicting \(S_j<d_j(A)\) for a class witnessing \(N=0\).
The total-inventory argument also correctly ensures the scan finishes. Before any of the round’s \(D\) turns, at least one copy remains.
Assessment: Correct.
Classes never replenish, so there are at most \(m\) exhaustion events and therefore at most \(m\) scanned rounds.
The positive-batch argument is sound:
These charges cannot reuse an exhaustion: each charged event occurs before subsequent batches, and an exhausted class stays unavailable. A terminal batch adds at most one further batch.
A scanned round has at most \(h+m\) consumption segments. Updating a segment may cross existing partition boundaries, but the maintained partition also has polynomial size, as established below. Thus counting these additional interval operations does not undermine polynomial runtime.
Assessment: Correct.
Batches introduce no boundaries. A scanned segment ends at either an existing schedule boundary or an exhaustion location. Therefore only exhaustion locations can introduce new partition boundaries, and there are at most \(m\) of them over the entire execution.
The final partition consequently has at most \(h+m\) intervals. Each contributes one positive mass to one type-and-bundle key, and merging identical keys can only decrease the number of entries.
The output matches the base allocation, hence the limits established by replication. Every agent receives exactly \(R\) items, so every reported bundle satisfies the required coordinate-sum constraint.
The numerical bounds are correct. The bit length of \(D\) is bounded by the total bit length of the input denominators. Inventories bounded by \(DR\), coordinates bounded by \(R\), and masses with denominator \(D\) all have polynomial bit length. Exact integer arithmetic, rational normalization, and merging the polynomially many output keys therefore have polynomial bit complexity.
Finally, sorting each supplied strict ranking uses the stated \(O(\tau m\log(m+1))\) comparison bound. Subsequent choices require no further oracle queries.
Assessment: Correct.
The prover resolves the assigned continuous computation problem with an exact polynomial-time algorithm, a polynomial output-size bound, and a proof of existence of all requested limits. No additional clarification is needed for verification.
⟨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.