| paper | d4-conf-atal-2021-0177 |
| 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 · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 2
Given finitely many demand-menu types \(T\), rational masses \(\mu_t>0\) summing to \(1\), a per-capita budget \(b>0\), and explicit menus \(D_t\) of positive rational demands with each demand at most \(b\) and \(v(D_t)>b\), let \(d_t^*=\max D_t\) and \(q_0=b\min_{t\in T}\rho_1(d_t^*/b)\). Compute masses \(x_{t,S}\ge 0\) assigned to integral bundles \(S\subseteq D_t\), such that \(\sum_{S\subseteq D_t}x_{t,S}=\mu_t\), \(\sum_{t\in T}\sum_{S\subseteq D_t}x_{t,S}v(S)\le b\), and \(x_{t,S}>0\) only if \(v(S)\ge q_0\).
A continuum of users with complete demand-menu types \(t\), mass \(\mu_t\), and an integral bundle \(S\subseteq D_t\) for each user. The common supply is \(b\) per unit of population, so total spending is at most \(b\); the task is to construct a mass allocation guaranteeing every user utility at least \(q_0=b\min_t\rho_1(d_t^*/b)\).
Theorem 2 is a one-agent packing guarantee, so after scaling the common budget per capita the type masses do not couple decisions and the algorithm applies independently to each menu.
fatal: False
The mirror covers Theorem 2's constructive guarantee across menu types and uses Theorem 1's characterization of \(\rho_1\) to set the threshold; it leaves the exact two-agent characterization, the multi-agent accuracy bound, and strategic reporting aside.
The strongest honest anchor is Theorem 2, proved in this paper. The paper gives no numbered hardness result for its common-budget problem; its discussion of hardness in §1.1 concerns related indivisible-goods allocation. Theorem 2 is therefore the relevant constructive anchor.
Theorem 2 assumes one agent, budget \(B\), and positive demands \(D\) with each demand at most \(B\) and \(v(D)>B\). Let \(d^*=\max D\) and \(\gamma_1(d^*,B)=\rho_1(d^*/B)B\). It says that a polynomial-time algorithm constructs a subset \(S\subseteq D\) such that \(\gamma_1(d^*,B)\le v(S)\le B-E(d^*,B)\), where \(E\) is at least the applicable bound below:
Here \(\rho_1(\alpha)\), characterized by the paper’s Theorem 1 (also proved here), equals \(\frac{k-1+\alpha}{k}\) when \(\alpha\in(\frac1{k+1},\frac1k]\). The algorithmic claim is a worst-case guarantee with a budget-saving bound; it does not solve the exact max-min problem for every instance.
A continuous mirror is the Continuous Common-Budget Guarantee problem. Its instance is a finite support \(T\) of \(\tau\) demand-menu types, with rational masses \(\mu_t>0\) summing to \(1\), and a per-unit-of-population budget \(b>0\). Each type \(t\) has an explicit finite menu \(D_t\) of positive rational demands, with every demand at most \(b\) and \(v(D_t)>b\). Write \(d_t^*=\max D_t\) and set \(q_0=b\min_{t\in T}\rho_1(d_t^*/b)\).
The question is to output an allocation of the population mass to integral bundles: variables \(x_{t,S}\ge0\) for \(S\subseteq D_t\), with \(\sum_{S\subseteq D_t}x_{t,S}=\mu_t\), total spending \(\sum_{t,S}x_{t,S}v(S)\le b\), and \(x_{t,S}=0\) whenever \(v(S)<q_0\). A unit of mass represents an individual, so each individual still receives a whole subset of their demands. The solution must give every individual utility at least \(q_0\).
Theorem 2 solves this guarantee problem type by type: for each \(t\), apply it with budget \(b\) to find \(S_t\) with \(b\rho_1(d_t^*/b)\le v(S_t)\le b\), then set \(x_{t,S_t}=\mu_t\). The total spend is at most \(\sum_t\mu_t b=b\), and everyone gets at least \(q_0\). This gives a polynomial-time construction in the explicit menu sizes and rational input length.
A credible regime is a large shared-storage service whose capacity scales with enrollment: many accounts have one of a small number of recurring request-menu profiles, and each profile’s users are indistinguishable for this funding decision. For \(N\) users, the pool has capacity \(Nb\); after normalizing population mass to \(1\), its capacity is \(b\). This makes the population, rather than the outcome space, the continuous object. Menu types, masses, integral requests, common capacity, and worst-off individual utility all retain recognizable roles from the paper.
For the stated guarantee problem, I expect tractability. The mirror covers Theorem 2’s constructive worst-case guarantee, not the paper’s exact two-agent characterization, the multi-agent accuracy bound, or its other algorithms. A further question is the exact continuous max-min optimum \(q^*\). That version appears to retain subset-sum hardness even with one menu type: since utility equals spending, a threshold \(q\) is feasible under budget \(b\) exactly when some subset has value in \([q,b]\). The continuous population can mix integral bundles, but if every used bundle costs more than \(b\), its average cost also exceeds \(b\). Thus this exact-optimization question is a natural hardness-transfer boundary, rather than a benefit established by Theorem 2.
The weakness is that the anchor itself is a one-agent guarantee. Applying it to each type is a sound high-multiplicity construction, but it does not use fractional mass to improve the guarantee, and it does not make the exact optimum easier. The case is consequently narrow: a credible continuous version of a named constructive result, with a clear boundary at exact optimization.
The best case against this anchor is that Theorem 2 is a one-agent packing guarantee, not a result about competition among a population. Its algorithm takes one menu and one budget; the population mass never enters. In the proposed mirror, each type gets the same per-person budget \(b\), and Theorem 2 is run independently on each menu. The masses \(\mu_t\) matter only to verify that the resulting bundles fit the aggregate budget. So the continuous formulation adds bookkeeping, but no population-level computational problem.
The stronger version—maximize the least utility across a distribution of menu types—does couple types through the budget. But preserving the paper’s individual fairness objective means every positive-mass type must receive bundles worth at least \(q\). Since utility equals spending, the cheapest way to do that for type \(t\) is its least-cost subset worth at least \(q\). The resulting feasibility test is a weighted sum of menu-by-menu subset choices. Allowing mass to mix across bundles does not smooth an individual’s utility: if some positive mass receives less than \(q\), the least-funded-agent guarantee fails. Using average type utility instead would change the objective.
That is a real limitation on the case *against*, not a decisive objection to the mirror. A large service with recurring request menus and capacity scaled with enrollment is plausible; menus can be complete types, and every person can still receive an integral bundle. Theorem 2 then gives a valid per-type guarantee. Theorem 1’s characterization transfers in the same way. I cannot honestly rule out that scenario or claim the mirror is ill-posed.
So the negative case is weak. The anchor is narrow and its continuous guarantee follows immediately by applying the paper’s one-agent result to each type, but that does not defeat it under the programme’s standard. There is no “already continuous” collision or other solid ground here. A careful reader could reasonably let this anchor survive.
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.