Answer: Polynomial-time solvable; a valid allocation always exists under the stated promises.
Theorem 12 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThere exists a polynomial-time algorithm that, on input any allocation instance with satiating subad- ditive goods, returns a PROP1 allocation.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite good types \(G\), household types \(T\), rational masses \(\mu_t\) summing to \(1\), rational per-capita supplies \(q_g\), and normalized nonnegative subadditive valuations \(u_t:\mathbb{Z}_{\ge 0}^{G}\to\mathbb{R}_{\ge 0}\), let \(\beta_t=\lim_{N\to\infty}u_t(Nq)/N\) along integers \(N\) for which \(Nq\) is integral. Find a finite-support rational allocation \(x_{t,b}\ge 0\) such that \(\sum_b x_{t,b}=\mu_t\), \(\sum_{t,b}x_{t,b}b_g=q_g\) for each \(g\), and every \(b\) with \(x_{t,b}>0\) satisfies \(u_t(b)\ge\beta_t\) or \(u_t(b+e_g)\ge\beta_t\) for some \(g\) with \(q_g>0\); or determine that no such allocation exists.
Let \(G\) be a finite set of good types, with \(m=|G|\), and let \(q\in\mathbb{Q}_{\ge0}^{G}\) be per-capita supplies. A society is given by its support: the list \(T\) of its \(\tau\) household types with positive binary-rational masses \(\mu_t\), summing to \(1\). Here \(\tau=|T|\) is the support size, not the number of possible types.
Each type has a valuation \(u_t:\mathbb{Z}_{\ge0}^{G}\to\mathbb{Q}_{\ge0}\), with \(u_t(0)=0\) and \(u_t(a+b)\le u_t(a)+u_t(b)\). Monotonicity is not required. Define \(\beta_t=\lim_{N\to\infty,\,Nq\in\mathbb{Z}_{\ge0}^{G}}u_t(Nq)/N\). Valuations are supplied by finite descriptions of exact evaluation routines and routines deciding \(u_t(b)\ge\beta_t\), all promised to run in polynomial time in description length and binary bundle length. Let \(L\) be the total input bit length; these properties are input promises.
An allocation is a finitely supported family \(x_{t,b}\in\mathbb{Q}_{\ge0}\), indexed by \(t\in T\) and \(b\in\mathbb{Z}_{\ge0}^{G}\), satisfying \(\sum_bx_{t,b}=\mu_t\) and \(\sum_{t,b}x_{t,b}b_g=q_g\). Every positively allocated bundle must satisfy \(u_t(b)\ge\beta_t\), or \(u_t(b+e_g)\ge\beta_t\) for some \(g\) with \(q_g>0\), where \(e_g\) is the unit vector. The extra copy is hypothetical and may have a type already present in \(b\); there is no removal alternative.
Is finding such an allocation, or determining that none exists, solvable in polynomial time in \(m,\tau,L\), or is this continuous allocation problem NP-hard?
For finitely many agents and individually listed goods, normalized nonnegative subadditive valuations admit a polynomial-time algorithm producing a complete PROP1 allocation, allowing either the bundle itself or the addition of one item held elsewhere to meet the proportional threshold. [Discrete result](https://ojs.aaai.org/index.php/AAAI/article/download/38704/42666)
No result settling this exact mass-allocation problem was located.
The problem is solvable in deterministic polynomial time under the stated promises. Moreover, a valid allocation always exists.
The algorithm uses only the promised threshold-comparison routines. It neither computes nor approximates the thresholds, which may be irrational.
The proof has two ingredients: subadditivity gives a separating linear functional for rejected bundles, and a compact construction produces a bundle distribution for any suitable signed linear functional.
Let \(G_+=\{g\in G:q_g>0\}\) and \(d=|G_+|\). Coordinates outside \(G_+\) must be zero in every positively allocated bundle, so we suppress them.
If \(d=0\), every threshold is zero and assigning the empty bundle to everyone solves the problem. Henceforth \(d\ge1\).
It suffices to solve the following problem separately for each type:
Given one valuation \(u\) and its threshold \(\beta\), construct a finitely supported rational probability distribution on acceptable bundles whose mean is \(q\).
Indeed, if \(r_{t,b}\) is such a distribution for type \(t\), then setting \(x_{t,b}=\mu_t r_{t,b}\) gives
\( \sum_b x_{t,b}=\mu_t \) and
\( \sum_{t,b}x_{t,b}b=\sum_t\mu_t q=q \).
Throughout the proof for one valuation, “acceptable” means that \(u(b)\ge\beta\), or that \(u(b+e_g)\ge\beta\) for some \(g\in G_+\).
Let \(N\) be the least common multiple of the denominators of the reduced coordinates of \(q\), and put \(Q=Nq\). Thus \(Q\in\mathbb Z_{>0}^{d}\). Both \(N\) and all coordinates of \(Q\) have bit length polynomial in \(L\), although their numerical values may be exponential.
Lemma 1. Every finitely supported rational probability distribution \((\lambda_b)\) with mean \(q\) satisfies
\( \beta\le\sum_b\lambda_b u(b) \).
Proof. The sequence \(a_k=u(kQ)\) is subadditive: \(a_{k+\ell}\le a_k+a_\ell\).
For completeness, fix \(h\ge1\) and write \(k=jh+s\), where \(0\le s<h\). Subadditivity gives \(a_k\le ja_h+a_s\), and consequently
\( \limsup_{k\to\infty}a_k/k\le a_h/h \).
The reverse lower bound by \(\inf_h a_h/h\) holds termwise. Therefore
\( \beta=\inf_{k\ge1}u(kQ)/(kN) \).
In particular, whenever \(Kq\) is integral,
\( \beta\le u(Kq)/K \).
Choose a positive integer \(K\) divisible by \(N\) and by the denominators of all \(\lambda_b\). Then
\( Kq=\sum_b(K\lambda_b)b \),
where all coefficients are nonnegative integers. Repeated subadditivity yields
\( u(Kq)\le\sum_b(K\lambda_b)u(b) \).
Dividing by \(K\) proves the lemma. \(\square\)
A useful implication is the following.
Corollary 2. If \(C\) is a finite collection of integer bundles with \(u(c)<\beta\) for every \(c\in C\), then \(q\notin\operatorname{conv}(C)\).
Proof. If \(q\) belonged to this convex hull, it would have a rational convex representation: the equations defining its convex representations have rational coefficients, and a nonempty such polytope has a rational vertex. Lemma 1 would then give
\( \beta\le\sum_{c\in C}\lambda_c u(c)<\beta \),
a contradiction. \(\square\)
We next prove a construction that is independent of \(u\).
Lemma 3. Given a rational vector \(p\in\mathbb Q^d\) with \(p\cdot q>0\), one can construct, in polynomial time, integer multiplicities \(a_b>0\) satisfying:
The running time is polynomial in \(d\), the binary encoding lengths of \(N,Q\), and the encoding length of \(p\).
Proof. Write \(\theta=p\cdot q>0\). Regard \(Q\) conceptually as an inventory to be partitioned into \(N\) bundles.
Reserve all copies of goods with nonpositive price for the final bundle. Order the positive-price good types arbitrarily. Construct the first \(N-1\) bundles as follows: take the longest prefix of the remaining positive-price inventory whose total price is strictly less than \(\theta\), and stop immediately before the next copy would bring the price to at least \(\theta\).
Each constructed bundle \(b\) therefore satisfies
\( p\cdot b<\theta \)
and
\( p\cdot(b+e_g)\ge\theta \)
for the next positive-price good \(g\).
We check that this stopping copy always exists. Let \(P\) be the total price of the initial positive-price inventory. Since the nonpositive-price inventory has nonpositive total price,
\( P\ge p\cdot Q=N\theta \).
After \(j\) ordinary bundles have been constructed, their total price is at most \(j\theta\), so the remaining positive-price inventory has price at least \((N-j)\theta\). Before constructing an ordinary bundle, \(j\le N-2\), and hence this remaining price is at least \(2\theta>\theta\). A crossing copy consequently exists.
Give all remaining copies, including the reserved inventory, to the final bundle \(R\). If the ordinary bundle prices are \(v_1,\ldots,v_{N-1}\), then
\( p\cdot R=N\theta-\sum_{j=1}^{N-1}v_j\ge\theta \).
For \(N>1\) this inequality is strict; for \(N=1\), equality holds.
It remains to implement the construction without iterating \(N\) times.
Suppose an ordinary bundle is about to start at a positive-price type \(g\), with \(r\ge1\) copies remaining. Set
\( k_g=\lceil\theta/p_g\rceil-1 \).
If \(k_g=0\), every remaining ordinary bundle can be empty: adding one copy of \(g\) reaches the threshold. Record their multiplicity in one operation.
If \(k_g>0\), and \(K\) ordinary bundles remain to be constructed, create
\( A=\min\{K,\lfloor(r-1)/k_g\rfloor\} \)
copies of the pure bundle \(k_g e_g\). These are exactly valid greedy bundles: each leaves a further copy of \(g\) available as its crossing copy.
If more ordinary bundles remain, the current block now has at most \(k_g\) copies. The next bundle consumes this block completely and proceeds through subsequent types until it encounters its crossing copy. At a partially filled bundle of price \(v<\theta\), the maximum number of copies of the current type that can be taken before crossing is
\( \lceil(\theta-v)/p_g\rceil-1 \).
Thus each block is processed by exact rational arithmetic and integer division.
There is at most one batch of pure bundles per positive-price type. Every mixed bundle exhausts at least one block, so there are at most \(d\) mixed bundles. Together with a possible empty-bundle batch and the final bundle, this gives at most \(2d+2\) recorded bundles.
All inventories, bundle coordinates, and multiplicities are bounded by \(Q\) or \(N\). The arithmetic and the number of operations are polynomial in the stated binary encoding lengths. \(\square\)
Negative coordinates of \(p\) are allowed in this lemma. This matters because monotonicity of \(u\) was not assumed.
Fix one valuation \(u\). First query the threshold routine at the empty bundle. Since \(u(0)=0\) and \(\beta\ge0\), a positive answer means \(\beta=0\). In that case every bundle is acceptable; use \(Q\) with probability \(1/N\) and the empty bundle with probability \((N-1)/N\).
Now suppose \(\beta>0\).
Define the finite bundle box
\( \mathcal Z=\prod_{g=1}^{d}\{0,\ldots,Q_g\} \),
and let \(\mathcal B\subseteq\mathcal Z\) be its unacceptable bundles. Equivalently, \(b\in\mathcal B\) precisely when
\( u(b)<\beta \)
and
\( u(b+e_g)<\beta \)
for every \(g\in G_+\).
Define
\( \mathcal C=\{0\}\cup\bigcup_{b\in\mathcal B}\bigl(\{b\}\cup\{b+e_g:g\in G_+\}\bigr) \).
Every member of \(\mathcal C\) has value strictly below \(\beta\). Corollary 2 gives
\( q\notin\operatorname{conv}(\mathcal C) \).
Since this convex hull is compact, there is a vector \(p\) such that
\( p\cdot(q-c)>0 \)
for every \(c\in\mathcal C\). In particular, because \(0\in\mathcal C\), we have \(p\cdot q>0\).
We need a quantitative margin that depends only on input coordinates, not on differences between utility values.
Put
\( M=\max_g Q_g \),
\( H=(N+1)(M+1) \),
\( \Delta=(d+1)!H^{d+1} \),
and
\( \eta=1/(4\Delta) \).
Every coordinate of every integer vector \(Q-Nc\), with \(c\in\mathcal C\), has absolute value at most \(H\).
Consider the auxiliary linear program maximizing \(\delta\), subject to
\( -1\le p_g\le1 \),
\( 0\le\delta\le1 \),
and
\( (Q-Nc)\cdot p\ge\delta \)
for every \(c\in\mathcal C\).
The strict separator above, after scaling, shows that its optimum \(\delta^*\) is positive. This is a bounded, nonempty polytope in \(d+1\) variables, so an optimum occurs at a vertex. At that vertex, \(d+1\) independent tight constraints determine the coordinates.
Their coefficients and right-hand sides are integers, and every matrix entry has absolute value at most \(H\). The determinant expansion bounds the absolute determinant by \(\Delta\). Cramer’s rule therefore gives
\( \delta^*\ge1/\Delta \):
its numerator is a positive integer and its denominator is at most \(\Delta\).
Consequently the polytope
\( \mathcal P=\{p\in[-1,1]^d:(Q-Nc)\cdot p\ge\eta\text{ for every }c\in\mathcal C\} \)
contains a ball of explicitly bounded radius. Indeed, halve an optimal price vector. Its coordinates then lie in \([-1/2,1/2]\), and every displayed margin is at least \(2\eta\). Since each constraint normal has Euclidean norm at most \(dH\), the ball of radius
\( r=\eta/(2dH) \)
around this halved vector lies inside \(\mathcal P\).
Also, \(\mathcal P\) lies inside the origin-centered ball of radius \(R=d\). The binary lengths of \(H,\Delta,\eta,r\), and hence \(\log(R/r)\), are polynomial in \(d,L\).
The auxiliary linear program is used only to prove this margin bound. Its exponentially many constraints are never enumerated.
Use the rational ellipsoid cutting procedure in dimension \(d\), starting with the radius-\(R\) ball.
The standard ellipsoid guarantee needed here is: for a fixed convex set contained in a known radius-\(R\) ball and containing a radius-\(r\) ball, one cannot supply a valid separating cut at every queried center for more than polynomially many iterations in \(d\) and \(\log(R/r)\). With rational cuts of polynomial encoding length, the rational implementation has polynomial bit complexity. This follows from the usual enclosing-volume argument and rational ellipsoid implementation. [Ellipsoid method reference](https://www.cs.princeton.edu/courses/archive/fall13/cos521/lecnotes/lec16.pdf).
At each queried rational vector \(p\), perform the following operations.
If \(p\notin[-1,1]^d\), return a violated box constraint. If \(p\cdot Q<\eta\), return the constraint \(p\cdot Q\ge\eta\). Each cut contains \(\mathcal P\), because \(0\in\mathcal C\).
Otherwise \(p\cdot q\ge\eta/N>0\). Apply Lemma 3, obtaining at most \(2d+2\) bundles with integer multiplicities.
Check every recorded bundle using the promised threshold routine, including its one-copy extensions when necessary. If every bundle is acceptable, return the distribution with probabilities \(a_b/N\).
Otherwise let \(b\) be an unacceptable recorded bundle. Lemma 3 provides a bundle \(c\) equal either to \(b\) or to \(b+e_g\), satisfying
\( p\cdot c\ge p\cdot q \).
Because \(b\) is unacceptable, this \(c\) belongs to \(\mathcal C\). Therefore
\( (Q-Nc)\cdot p\le0<\eta \).
Return the violated inequality
\( (Q-Nc)\cdot y\ge\eta \).
This halfspace contains all of \(\mathcal P\).
Thus every iteration either returns a verified acceptable distribution or returns a valid separating cut for the fixed polytope \(\mathcal P\).
The ball established in Section 4 prevents valid cuts from continuing beyond the polynomial ellipsoid iteration bound. Therefore the algorithm must return an acceptable distribution within polynomial time.
Notice that a successful query need not establish that its price vector belongs to \(\mathcal P\). This causes no difficulty: success directly returns a checked allocation. Until success, every returned cut is valid for \(\mathcal P\), which is all the volume argument requires.
Each ellipsoid iteration uses polynomially many arithmetic operations and at most \(O(d^2)\) threshold queries. Every queried bundle is either in \(\mathcal Z\) or is a one-copy extension of a bundle in \(\mathcal Z\), so its binary length is polynomial in \(L\).
For each household type \(t\), the algorithm returns integer multiplicities \(a_{t,b}\) with
\( \sum_b a_{t,b}=N \)
and
\( \sum_b a_{t,b}b=Q \).
Set
\( x_{t,b}=\mu_t a_{t,b}/N \).
Then
\( \sum_bx_{t,b}=\mu_t \)
and
\( \sum_{t,b}x_{t,b}b=\sum_t\mu_t Q/N=q \).
Every positively allocated bundle has been checked for the required acceptability condition.
The output has at most \(\tau(2d+2)\le\tau(2m+2)\) nonzero entries before merging duplicates. Bundle coordinates and allocation masses have polynomial binary encoding length. Running the construction separately for all supported types therefore takes polynomial time in \(m,\tau,L\).
This proves polynomial-time solvability and universal existence under exactly the stated assumptions, including nonmonotone valuations and the addition-only condition.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is verified: the argument establishes deterministic polynomial-time solvability and universal existence under the stated promises. I found no major or minor mathematical issues.
Suppressing coordinates with zero supply is valid: nonnegative allocation masses and nonnegative bundle coordinates force every positively allocated bundle to contain zero copies of those goods.
When all supplies vanish, normalization gives every threshold equal to zero, so allocating the empty bundle is valid.
For positive supply coordinates, the proposed per-type reduction preserves both type masses and aggregate supplies. It is sufficient to construct each type’s probability distribution with mean \(q\).
The denominator choice is also correct. The least common multiple \(N\) has polynomial binary length, and \(Q=Nq\) has positive integer coordinates of polynomial binary length. The construction never requires time polynomial in the numerical value of \(N\).
The sequence \(a_k=u(kQ)\) is subadditive. The remainder argument correctly establishes
\[
\lim_{k\to\infty}\frac{a_k}{k}=\inf_{h\ge1}\frac{a_h}{h}.
\]
Consequently, dividing by \(N\) gives the asserted characterization of \(\beta\).
Every positive integer \(K\) with integral \(Kq\) is divisible by \(N\), so the inequality involving \(u(Kq)/K\) follows from this characterization.
Choosing \(K\) divisible by the probability denominators makes the bundle multiplicities integral. Repeated subadditivity then proves the claimed inequality. No monotonicity assumption is used.
The convex-representation polytope has rational coefficients, is bounded, and is nonempty under the contradiction hypothesis. It therefore admits a rational vertex.
Lemma 1 applies to that rational representation. Because the support is finite and every represented value is strictly below \(\beta\), its weighted average is strictly below \(\beta\). The contradiction is valid.
Reserving goods with nonpositive prices is legitimate. Their total price is nonpositive, so the initial positive-price inventory has total price at least \(N\theta\).
Every ordinary bundle has price strictly below \(\theta\). Before any of the first \(N-1\) bundles is constructed, the remaining positive-price inventory has price at least \(2\theta\). Thus a crossing copy exists, and its good has positive supply.
The final bundle’s price follows from exact conservation of inventory:
\[
p\cdot R=N\theta-\sum_{j=1}^{N-1}v_j\ge\theta.
\]
The distinction between \(N=1\) and \(N>1\) is handled correctly.
The compression formulas also check out. For a positive price \(p_g\), the largest integer number of copies with price strictly below \(\theta\) is
\[
k_g=\left\lceil\frac{\theta}{p_g}\right\rceil-1.
\]
The batch bound using \(r-1\) ensures a crossing copy remains available for every recorded pure bundle. If ordinary bundles remain after the batch, at most \(k_g\) copies of that type remain, so consuming the block preserves the strict price inequality.
Every mixed bundle exhausts at least one block. Blocks are processed in order and never replenished, which validates the polynomial operation count and the stated support bound. The case \(k_g=0\) correctly produces an empty-bundle batch.
Rational division and ceiling operations have polynomial bit complexity in the stated input lengths, including when their numerical results are large.
Once the empty-bundle threshold query fails, \(\beta>0\). Thus every member of \(\mathcal C\), including zero, has value strictly below \(\beta\).
Corollary 2 applies because \(\mathcal C\) is finite. Strict separation of the point \(q\) from its compact convex hull yields precisely the inequalities stated. Including zero in \(\mathcal C\) ensures \(p\cdot q>0\), as required by Lemma 3.
One-copy extensions may lie outside \(\mathcal Z\); the definition of \(\mathcal C\) explicitly permits this. Their coordinates remain bounded by \(Q_g+1\).
The coordinate bound \(H\) covers all vectors \(Q-Nc\), including extensions.
The auxiliary linear program is bounded and feasible, and scaling a strict separator shows its optimum is positive. At an optimal vertex, an independent system of \(d+1\) active constraints has integer coefficients bounded in absolute value by \(H\).
The determinant expansion gives the stated bound \(\Delta\). Cramer’s rule then gives \(\delta^*\ge1/\Delta\): the relevant numerator is a nonzero integer.
Halving the optimal price vector leaves coordinate slack of at least \(1/2\) and constraint margins of at least \(2\eta\). The proposed radius \(r\) is small enough to preserve both the box constraints and all margin inequalities. The outer radius \(R=d\) covers the box for every \(d\ge1\).
All these parameters have polynomial binary length.
The invoked ellipsoid guarantee is applicable: \(\mathcal P\) is a fixed convex set, has a known containing ball, and contains a ball with the stated positive radius. The cited [ellipsoid notes](https://www.cs.princeton.edu/courses/archive/fall13/cos521/lecnotes/lec16.pdf) support the enclosing-volume argument; the rational implementation guarantee stated in the proof is the standard finite-precision version.
Both explicit constraint checks yield separating halfspaces containing \(\mathcal P\).
For an unacceptable recorded bundle, Lemma 3 supplies an appropriate \(c\), and unacceptability ensures \(c\in\mathcal C\). Hence
\[
(Q-Nc)\cdot p\le0<\eta,
\]
so the returned inequality strictly excludes the queried center and contains all of \(\mathcal P\). Its encoding length is polynomial.
The procedure need not certify membership in \(\mathcal P\) on success. Success independently certifies the desired allocation; every unsuccessful iteration supplies a valid cut for the same fixed set. This is sufficient for the ellipsoid termination argument.
Acceptability checks exactly match the addition-only condition, including hypothetical copies of already-present good types.
All queried bundles have polynomial binary length. The number of threshold queries per iteration is polynomial, and the promised routines therefore suffice.
The returned probabilities and the masses \(x_{t,b}=\mu_t a_{t,b}/N\) are rational with polynomial encoding length. Their sums and supply equations are correct. The support bound is polynomial in the actual society support size \(\tau\).
No unproved connection to the discrete PROP1 result is needed. The continuous problem is resolved directly.
No additional clarification or repair 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.