| paper | d4-journals-jair-2026-0011 |
| 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: \(\text{Polynomial-time solvable}\) · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 19
statement extracted from the paper’s text layer
For \(m\) divisible public items with feasible allocation set \(Z\), utility reports in the paper’s admissible class, and a population supported on at most \(\tau\) utility types with rational masses \(\mu_t\) satisfying \(N\mu_t\in\mathbb{Z}\), can one compute a randomized mechanism \(M_N\) in time polynomial in \(N,\tau,m,L\) that is asymptotically truthful under every one-resident report change of mass \(1/N\) and returns an asymptotic core allocation with high probability? Here, for true type \(t\), alternative report \(t'\), and other-resident mass vector \(\nu\), truthfulness compares \(\mathbb{E}[U_t(M_N(\nu+e_t/N))]\) with \((1-\epsilon_N)\mathbb{E}[U_t(M_N(\nu+e_{t'}/N))]-\delta_N\), where \(\epsilon_N,\delta_N\to0\). The core condition treats a coalition as masses \(a_t\in[0,\mu_t]\), with \(\alpha=\sum_t a_t>0\), and rules out allocations \(z'\in Z\) satisfying \(\alpha U_t(z')\ge(1+\eta_N)U_t(z)+\kappa_N\) for every participating type, with strict improvement on positive mass, where \(\eta_N,\kappa_N\to0\).
The society is a distribution \(\mu\) over complete utility types, with \(N\mu_t\) residents of type \(t\); all residents receive the common public allocation \(z\in Z\). The type-weighted Nash welfare objective is \(\sum_t\mu_t\log(U_t(z)+\upsilon_N)\), and a type-aggregated PPGA can maintain one local and dual state per type, weight aggregation by \(\mu_t\), and calibrate noise to the \(1/N\) effect of one report. Core coalitions are represented by submasses \(a_t\).
The proposed runtime is polynomial in \(N\), so expanding the mass input into \(N\) residents may suffice; it does not establish runtime polynomial in \(\tau\) and the bit length \(L\) of the masses. This leaves the promised computational gain from high multiplicity open.
fatal: False
The mirror covers Theorem 19’s combined asymptotic-truthfulness and high-probability asymptotic-core guarantees, drawing on Theorems 12 and 17. It leaves the exact-core characterization, detailed privacy and convergence lemmas, implementation, and empirical results outside the mirror.
The strongest honest positive case is the paper’s Theorem 19, proved here: “Algorithm 1 achieves asymptotic truthfulness and computes an asymptotic core solution with high probability in polynomial time.” Under the paper’s public-good model and assumptions, the theorem’s parameter choices include \(m=o(\sqrt n)\), \(K=\Theta(n)\), smoothing \(\upsilon=\Theta(1/\sqrt n)\), and truthfulness parameters \(\epsilon=\Theta(1/\log n)\), \(\delta=\Theta(1/\sqrt n)\). The output is an asymptotic core outcome with probability at least \(1-1/n-1/n^m\); the paper gives running time \(O(n^{2.75}\log(n)m\log(m))\). The excerpt gives no named hardness result, so this algorithmic theorem is the best anchor.
A plausible regime is municipal participatory budgeting with many residents and repeated preference profiles over a modest project list. Define a type \(t\) as a resident’s complete utility description over the projects; residents with the same type are identical for the utilities and strategic reports used by the problem. Let \(\mu_t\) be the fraction of residents of type \(t\). A city might have tens of thousands of residents but far fewer recurring preference profiles, so statements such as “\(18\%\) of residents value this bundle” are natural. The paper’s municipal setting and its election instances, with roughly \(10{,}000\)–\(96{,}000\) votes and \(13\)–\(134\) projects, support the scale of this scenario; it does not report the number of distinct profiles, so those experiments do not establish that \(\tau\) is small.
The mirror: High-Multiplicity Asymptotic Core Allocation. An instance has \(m\) public items, the paper’s feasible allocation set \(Z\), a finite set of utility types \(T\), and rational masses \(\mu_t\geq0\) summing to \(1\). Each type has a utility function \(U_t\) satisfying the paper’s assumptions. Include a population resolution \(N\) such that \(N\mu_t\) is integral. The decision variable is a randomized allocation \(M_N(\mu)\in Z\), obtained by an algorithm. Its fairness objective is the mass-weighted Nash welfare \(\sum_t\mu_t\log(U_t(z)+\upsilon_N)\); its action is the common public allocation \(z\). Divisibility and the capacity constraints stay as in the paper; continuity enters by representing the resident population with \(\mu\).
The requirements make the question operational. For any type \(t\), alternative report \(t'\), and fixed reports of the other \(N-1\) residents with mass vector \(\nu\), the mechanism must satisfy
\[
\mathbb E[U_t(M_N(\nu+e_t/N))]
\geq (1-\epsilon_N)\mathbb E[U_t(M_N(\nu+e_{t'}/N))]-\delta_N,
\]
where \(\epsilon_N,\delta_N\to0\). Its output must also be an asymptotic core outcome with high probability. For the paper’s core convention, a coalition of mass \(\alpha\) can block with allocation \(z'\) if its members’ utilities scaled by \(\alpha\) beat their utilities at \(z\). In the mass model, a coalition is specified by \(a_t\in[0,\mu_t]\), with \(\alpha=\sum_t a_t>0\); an approximate block requires \(\alpha U_t(z')\geq(1+\eta_N)U_t(z)+\kappa_N\) for each participating type, with strict improvement on positive mass. The computational task is to produce such a mechanism in time polynomial in the population resolution \(N\), the number of types \(\tau\), \(m\), and the input representation length.
I expect this mirror to be Class A: a type-weighted version of PPGA can aggregate repeated local updates, optimize the mass-weighted Nash welfare, and calibrate the noise to the \(1/N\) effect of one resident’s report. Theorem 19 already gives a polynomial-time, asymptotically truthful, high-probability core mechanism for the corresponding finite populations. A useful further question is whether the type-aggregated implementation can make the dependence on \(\tau\) explicit and avoid work proportional to every resident in each iteration.
The soft spot is that the continuous distribution \(\mu\) alone cannot express a unilateral resident’s report: in a literal continuum, one person has zero mass, making truthfulness vacuous. Keeping \(N\) as the resolution and requiring guarantees under \(1/N\) report changes handles that issue, but it means the mirror is an asymptotic family built around the continuum population, rather than a standalone incentive notion on \(\mu\) alone. That is still a credible mirror for this paper because its central guarantee is itself asymptotic in the number of residents.
The only computational anchor is Theorem 19. Its distinctive guarantee combines an asymptotic core outcome with asymptotic truthfulness. The strongest case against mirroring it is that these two parts behave differently when the population becomes continuous.
For an atomless society with distribution \(\mu\), changing one resident’s report changes no mass. Any mechanism that takes \(\mu\) as its input is therefore unaffected by that report; individual truthfulness becomes vacuous, and the paper’s differential privacy argument loses its individual-level sensitivity tradeoff. The core guarantee does have a natural mass version, but the theorem’s defining combination of fairness and incentives does not survive as a nontrivial claim in the limit.
The proposed resolution \(N\) restores that claim by letting one report change mass by \(1/N\). But the proposed running-time target, polynomial in \(N\), lets an algorithm expand the input into \(N\) residents, so it asks for little beyond the existing theorem. Compressing identical residents to \(\tau\) types can reduce the work within each PPGA iteration: identical types have identical local updates. Yet PPGA still uses \(K=\Theta(N)\) iterations. A meaningful high-multiplicity target would need to be polynomial in \(\tau\) and the bit length of the masses, rather than in \(N\). Theorem 19 does not establish that.
That is the best objection to the proponent’s particular mirror: its continuum version makes individual incentives vacuous, while its finite-resolution version has not stated a genuinely compressed complexity target. It does not defeat the stronger version, though. A type-compressed algorithm with nontrivial \(1/N\)-scale incentive guarantees and running time polynomial in the compressed input would be a well-posed computational question, and potentially a worthwhile one. The municipal participatory-budgeting setting makes repeated preference types plausible. I cannot honestly argue that no scenario or improved formulation survives; the negative case is weak against that stronger mirror.
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.