| paper | Discrete Budget Aggregation: Truthfulness and Proportionality |
| authors | Ulrike Schmidt-Kraepelin, Warut Suksompong, Markus Utke |
| venue | IJCAI 2025 |
| filed under | multiwinner · pb |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
The paper has no numbered result asserting the complexity or algorithmic status of a computational problem. Its proposed high-multiplicity extensions are sensible, but their meaningful incentive condition changes unilateral truthfulness into coalition truthfulness. Therefore bit (a) fails and the paper is red.
fails bit a — no named computational result to mirror
Positive-mass deviations do not preserve the paper's unilateral truthfulness, and cloning finite profiles does not make a cohort deviation equivalent to changing one voter.
fatal: True
The proposed mirror covers Theorems 4 and 5 as mass-based axiomatic impossibility questions; it leaves the paper's remaining mechanism, proportionality, and dictatorship results without a computational classification.
The strongest honest positive case is that the paper has a very natural population mirror, but it fails ChoCo’s named-computational-anchor gate.
The paper contains no theorem asserting NP-hardness, membership in \(\mathrm P\), fixed-parameter tractability, approximation complexity, or any comparable computational classification. Theorem 1 is a non-truthfulness result; Theorem 2 proves truthfulness of integral moving-phantom mechanisms; Proposition 1 proves an equivalence; Theorem 3 proves quota-proportionality; Theorems 4 and 5 prove mechanism impossibilities; Theorem 6 is cited from Aswal et al.; and Theorem 7 is a dictatorship characterization. The SAT computation behind Theorem 4 does not turn it into a complexity result. Thus there is no qualifying computational anchor, and strictly speaking no Class A/B/C verdict to attach to this paper.
The closest positive case is nevertheless quite credible. Consider participatory budgeting in a city with \(m\) projects and \(b\) indivisible standardized budget units, with a very large population of residents. A voter type is an integral ballot \(p\in I_b^m\); two residents have the same type when they have the same \(\ell_1\)-preferences over integral allocations. A society is a rational distribution \(\mu\) over \(T=I_b^m\), and the mechanism outputs \(a\in I_b^m\). For the paper’s critical parameters \(m=4,b=3\), there are only \(\tau=\binom{6}{3}=20\) possible types, while the number of residents can be enormous. This is a genuine high-multiplicity regime, and it keeps the paper’s central indivisible-output feature rather than confusing it with fractional outcome-space continuity.
My lead extension would be the following, based on Theorem 5, proved in this paper through the displayed proof sketch and the full version.
Continuum-EJR\({}^+\) Mechanism Existence. For fixed \(m=4\) and \(b=3\), does there exist a rule \(A:\Delta_{\mathbb Q}(I_b^m)\to I_b^m\) such that, for every rational society \(\mu\):
\[
\min_{p:\mu_p>0}p_j\le A(\mu)_j\le\max_{p:\mu_p>0}p_j
\]
for every alternative \(j\);
\[ p_j>A(\mu)_j \quad\text{and}\quad \sum_{k=1}^m\min(p_k,A(\mu)_k)<\ell; \]
This is recognizably the authors’ problem: the type, allocation, utility, proportionality threshold, and indivisibility are unchanged; only voter multiplicities become masses. The expected answer is “no,” with the obstruction transferring from Theorem 5. Its three-voter profile can be cloned into three large cohorts of equal mass, and the same range-respect/EJR\({}^+\)/truthfulness contradiction applies to a cohort deviation. This is therefore a finite obstruction surviving in the population mirror, not a continuum-specific hardness phenomenon.
The weaker secondary extension would replace EJR\({}^+\) by the mass form of JR and ask for an anonymous truthful rule. That mirrors Theorem 4, proved here using a SAT certificate for \(n=3,m=4,b=3\). Again, rational clone profiles make the translation exact. I would not elevate this above Theorem 5: the latter has the cleaner human-readable obstruction and does not require anonymity.
The weakest point is truthfulness. In the paper, truthfulness forbids a unilateral named voter from misreporting. In an atomless society, one individual has zero mass and cannot change the outcome, so literal truthfulness becomes vacuous. The formulation above therefore replaces individual deviations by positive-mass cohort deviations. That is an author-recognizable high-multiplicity extension, but it is not a purely literal mirror. Alternatively, one could retain unilateral truthfulness by requiring a clone-invariant rule to remain truthful under every finite rational representation \(\mu=n/N\), but that introduces a hidden finite-population scale.
So the positive conclusion is modest: the paper’s budget-aggregation model has an excellent high-multiplicity population interpretation, and Theorems 4 and 5 generate precise, plausible continuum extensions whose impossibilities should transfer. But because the paper has no named computational result, this is not a qualifying ChoCo mirror in the strict programme sense.
The decisive point is the one the proponent concedes: this paper has no qualifying computational anchor. Theorem 1 is a non-truthfulness result, Theorems 2 and 3 are mechanism constructions, Theorems 4 and 5 are axiomatic impossibilities, and Theorem 7 is a dictatorship characterization. The SAT computation behind Theorem 4 is merely a proof method for one fixed impossibility instance; it does not establish the complexity of a decision or optimization problem. Consequently, there is no Class A, B, or C result here for ChoCo to continuize.
The proposed mirror of Theorem 5 is nevertheless a coherent population model. Taking \(T=I_b^m\), replacing voter counts by \(\mu\), and retaining \(a\in I_b^m\) preserves the static notions of range-respect and EJR\({}^+\). I would not reject it merely because the outcome remains integral, or because the EJR\({}^+\) definition needs its natural mass formulation.
The failure is the proposed treatment of truthfulness. In the paper, voter \(1\) makes a unilateral deviation while the other two named voters remain fixed. In an atomless society, one voter has zero mass and cannot change \(\mu\), so unilateral truthfulness is vacuous. The proposed positive-mass deviation is meaningful, but it is a coalition or group-strategyproofness condition, not the paper’s truthfulness condition. Clearing denominators does not repair this: cloning each type preserves the profile and the static axioms, but changing an entire clone cohort is not the same as changing one clone.
There is no way around this by choosing a more sophisticated type space. If types include all utility-relevant information, the same trilemma remains: price-taking individual deviations are vacuous; finite-agent deviations retain a hidden population scale; positive-mass deviations change the strategic predicate. Requiring a projective family of finite mechanisms \(A_N\) that behaves consistently under cloning would be a new cross-population axiom, absent from the paper.
Thus Theorem 5 can yield an author-recognizable axiomatic extension, perhaps of the form
\[
A:\Delta_{\mathbb Q}(I_b^m)\to I_b^m,
\]
but the transferred result is still a finite impossibility certificate, not a computational landscape. To obtain computation one would have to invent a new problem—such as finding a rule satisfying mass-group truthfulness, or computing the smallest manipulative coalition. That could be worthwhile independently, but it is not a continuous mirror of Theorem 5 under ChoCo’s named-anchor rule.
The same objection defeats the proposed secondary mirror of Theorem 4. Anonymity and JR translate naturally to masses, but truthfulness does not. Moreover, the theorem’s SAT unsatisfiability for \(n=3,m=4,b=3\) is not a complexity result: it gives no complexity classification for mechanism existence as \(n,m,b\) vary. A mass version either changes unilateral truthfulness into group truthfulness or introduces the new requirement that all finite clone representations agree. In both cases, the central computational question has been manufactured rather than mirrored.
The natural high-multiplicity participatory-budgeting interpretation is therefore sensible; that is not the obstruction. The obstruction is that the paper studies axiomatic mechanism properties, and its only apparent continuous translations either preserve no nontrivial individual incentive notion or replace it with a new coalitional one. The honest negative verdict is consequently strong at ChoCo’s programme gate, though not an impossibility claim about the broader research area: a separate paper on continuous coalitional manipulation or mechanism synthesis might be valuable, but this paper does not supply the computational result that would make it its 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.