| paper | d4-conf-aaai-2026-2745 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable; a valid allocation always exists under the stated promises. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 12
statement extracted from the paper’s text layer
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.
A population is represented by type masses \(\mu_t\). The decision variables \(x_{t,b}\) assign mass to integral bundles \(b\), with aggregate quantities matching per-capita supplies \(q_g\). Every bundle used by type \(t\) must meet its PROP1 threshold \(\beta_t\), either directly or after adding one available unit.
For bounded or saturating valuations, the limiting threshold can be zero and make PROP1 vacuous; for nontrivial instances, the unbounded bundle domain and unspecified valuation-access model leave the computational formulation incomplete.
fatal: False
The mirror covers Theorem 12's computation of PROP1 allocations for satiating subadditive valuations. It leaves the EF1 implications, Round-Robin results, and Nash-welfare and Pareto-efficiency results outside its scope.
The lead mirror I believe is a large allocation of standardized relief goods to households. There are many households, but only a modest number of complete valuation types: households of a type value every bundle in the same way, including any satiation or negative marginal effects. The number of households is much larger than the number of types. The catalogue of goods is fixed, while the supply of each kind grows with the population. That fits settings where goods arrive in large lots and people have recurring, similar needs.
My anchor is Theorem 12, proved in this paper. It says that for any allocation instance with satiating subadditive goods, there is a polynomial-time algorithm that returns a PROP1 allocation. Here the goods are indivisible; each agent’s valuation is normalized, nonnegative on every bundle, subadditive, and may be nonmonotone. The result is an algorithmic one, not a hardness result. The paper’s supplied text gives no comparable hardness anchor, so this is the strongest result to build on.
Here is a continuous problem that preserves the individual fairness question. Let \(G\) be a finite catalogue of good types and \(T\) a finite set of household types. The input gives rational type masses \(\mu_t\), summing to one, and rational per-capita supplies \(q_g\). A type \(t\) has a valuation \(u_t(b)\) for every integral bundle \(b\in\mathbb Z_{\ge0}^{G}\). Assume these valuations are normalized, nonnegative, subadditive over bundles, and may have negative marginal values. Type is a complete description: households of type \(t\) share the same valuation.
Let \(\beta_t\) be type \(t\)’s per-capita value for the entire stock in the corresponding replicated finite instances: \(\beta_t=\lim_{N\to\infty}u_t(Nq)/N\), along population sizes for which the quantities are integral. The limit exists for subadditive valuations along such a scaling sequence. The question, Continuous PROP1 Allocation for Satiating Subadditive Types, is: can we produce a finite-support list of rational masses \(x_{t,b}\ge0\) such that
\[
\sum_b x_{t,b}=\mu_t,\qquad
\sum_{t,b}x_{t,b}b_g=q_g\quad\text{for every }g,
\]
and every bundle \(b\) receiving positive mass from type \(t\) satisfies
\[
u_t(b)\ge\beta_t
\quad\text{or}\quad
u_t(b+e_g)\ge\beta_t\text{ for some }g\text{ with }q_g>0?
\]
Here \(e_g\) adds one indivisible unit of good type \(g\). The masses describe which fraction of each type receives each bundle; they are not lotteries that give an individual a fractional bundle. Each household gets an integral bundle, and the aggregate allocation and supplies are fractional.
There is no welfare objective in the paper’s theorem, so this is a constructive feasibility problem: find such an allocation, or establish that none exists. It mirrors PROP1’s “proportionality up to one good” condition while taking the per-capita proportionality threshold from the growing finite instances. Replicated copies of a good type are interchangeable; the mirror therefore narrows the goods model, but keeps the fairness condition and indivisibility for every household.
I expect a Class A result. With a finite bundle catalogue, the problem is a linear feasibility program over the variables \(x_{t,b}\). For the unbounded integral-bundle version above, the key question is pricing: can one efficiently find a fair bundle that optimizes a linear cost for a given type? That is the continuous algorithmic problem to solve, and a natural place to use column generation. Further questions are whether a fair allocation always exists for every coherent rational scaling, whether the pricing step is polynomial under a stated valuation-access model, and how to round a continuous allocation back to finite populations while preserving PROP1.
The mirror covers Theorem 12; it does not claim to continuize the paper’s EF1 implications, Round-Robin results, or Nash-welfare and Pareto-efficiency results. Its weakest point is the passage from distinct goods and finitely many named agents to interchangeable good copies and an atomless population. Theorem 12’s polynomial runtime applies to finite instances, and the reproduced paper text does not specify a valuation encoding. It therefore does not itself prove a polynomial-time algorithm for this limit problem. Still, the mirror keeps each household’s bundle integral, retains the paper’s satiating subadditive valuations and one-good fairness test, and gives a concrete high-multiplicity regime for asking whether its algorithmic result survives.
The only serious anchor is Theorem 12: it is a named polynomial-time result, and its subject is computational. So the negative case cannot start by claiming there is nothing to mirror.
Its best attack is on whether the theorem’s broad valuation class survives the proposed scaling with a meaningful fairness condition. In a replicated instance with \(N\) households and per-capita stock \(q\), the PROP1 threshold for type \(t\) becomes \(u_t(Nq)/N\). For natural saturating valuations such as \(u_t(S)=\min\{1,|S|\}\), this tends to zero. Since valuations are nonnegative, every bundle then passes the proposed condition. That part of Theorem 12’s domain yields no substantive continuous fairness problem.
Restricting attention to types with positive limiting value avoids that degeneration, but brings a different gap. The continuous allocation must balance mass over integral bundles, while the bundle size has no uniform bound: arbitrarily small mass could receive arbitrarily many units. Theorem 12’s finite algorithm does not supply a finite bundle catalogue, a compactness guarantee, or a pricing model for this limit problem. Adding a bundle cap would make the model finite and define a configuration LP, but then the computational question depends on the added cap and on how valuations are represented. The theorem itself does not identify the relevant separation problem.
That is a substantial objection to this particular formulation: its broadest valuation class often collapses in the limit, while the nontrivial remainder needs extra modeling choices before its complexity question is defined. But it does not defeat the best mirror. Large cohorts with repeated valuation types and per-capita supplies are credible, and a positive-slope class of valuations could support a well-posed continuous allocation problem. Theorem 12’s item-transfer algorithm does not settle that problem.
So I would argue against prioritizing the proponent’s mirror as currently specified, but I cannot honestly defend the universal claim that no worthwhile mirror exists. The proposed mirror has real gaps; the case against the anchor itself remains weak.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.