| paper | Truthful Aggregation of Budget Proposals with Proportionality Guarantees |
| authors | Ioannis Caragiannis, George Christodoulou, Nicos Protopapas |
| venue | AAAI 2022 |
| filed under | multiwinner · pb |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | high |
| authors would recognise it | yes |
The paper’s numbered results are approximation guarantees, structural characterizations, and mechanism impossibility bounds; none asserts the complexity or solvability of a named computational problem. The proposed high-multiplicity loss-verification and phantom-design questions are coherent extensions, but they are new computational questions rather than mirrors of computational results in this paper. Therefore bit (a) fails even though a population analogue is plausible.
fails bit a — no named computational result to mirror
The proposed \(L_{\mathrm{PU}}(T)\) is a newly imposed menu-constrained verification problem, and the paper’s three-type reduction does not establish its computational complexity.
fatal: True
The proposed mirror covers population reinterpretations of Theorems 5 and 7, while leaving Theorem 6’s single-voter truthfulness lower bound and the paper’s other finite-profile structural results outside the computational formulation.
The strongest honest mirror is a population version of the paper’s mechanism-quality problem. The paper contains no named NP-hardness, P, W[1]-hardness, or FPT theorem, so this is not a direct complexity-class transfer. Its anchors are instead the proved approximation and impossibility theorems.
The mirror’s society is a distribution over ideal budget divisions. Fix \(m\), and let \(T=\{p^1,\ldots,p^\tau\}\subseteq\Delta_m\), where each \(p^r\) is a complete preference type: agents of that type have the same ideal division and the same \(\ell_1\) disutility. A society is \(\mu\in\Delta_\tau\), where \(\mu_r\) is the fraction of residents of type \(p^r\). Its proportional division is \(\bar p(\mu)=\sum_r\mu_rp^r\).
This is a plausible regime for a large municipal consultation with a small fixed project slate and standardized allocation proposals: millions of residents, but only a few recurring proposal templates used by neighborhoods, civic organizations, or resident cohorts. The exact finite-menu assumption is important: this is not claiming that every participatory-budgeting electorate has high multiplicity.
To define the population version of a moving-phantom mechanism, let \(\phi(u,t)\) be the continuum limit of the paper’s phantom functions \(y_k(t)\), with \(u\in[0,1]\) indexing phantom mass. For each \(t\), the phantom distribution is the pushforward of uniform mass on \([0,1]\) under \(u\mapsto\phi(u,t)\). In coordinate \(j\), combine this phantom distribution with the population distribution of reported coordinate values, \(\sum_r\mu_r\delta_{p^r_j}\), and take the inherited median. Choose \(t^\ast\) so that the resulting coordinates sum to \(1\). The outcome is \(F^\phi(\mu)\), and its loss is \(\ell^\phi(\mu)=\|F^\phi(\mu)-\bar p(\mu)\|_1\).
For rational \(\mu\), this is exactly the high-multiplicity limit of a finite profile containing \(N\mu_r\) copies of type \(p^r\). The mechanism is best understood as replication-stable: every finite approximation is one of the paper’s truthful moving-phantom mechanisms, using Theorem 1 of Freeman et al. The atomless limit should not be called individually truthful without this finite-replication interpretation, since a literally infinitesimal voter cannot affect the outcome.
My lead anchor is Theorem 5, proved in this paper: “The Piecewise Uniform mechanism is \((2/3+\epsilon)\)-approximate, for some \(\epsilon\le10^{-5}\).”
The corresponding problem is:
Given a finite rational peak menu \(T\subseteq\Delta_3\) and a rational threshold \(\alpha\), compute or decide the worst-case population loss
\[
L_{\mathrm{PU}}(T)=\sup_{\mu\in\Delta(T)}
\left\|F^{\mathrm{PU}}(\mu)-\sum_{p\in T}\mu_p p\right\|_1.
\]
A solution consists of either a maximizing mass vector \(\mu\) and its parameter \(t^\ast\), or an upper-bound certificate proving \(L_{\mathrm{PU}}(T)\le\alpha\). An additive-\(\eta\) version asks for \(L_{\mathrm{PU}}(T)\) within \(\eta\).
This is recognizably the same problem, not a tractable surrogate: the mechanism, strategic domain, proportional benchmark, and \(\ell_1\)-objective are unchanged. Only voter counts have become masses. Indeed, the paper’s own proof already normalizes the integer variables \(a_j,b_{j,k},C\) into \(\hat a_j,\hat b_{j,k},\hat C\). Those normalized variables are precisely population masses in the mirror. Theorem 4’s reduction to three-type profiles and the resulting finite collection of quadratic programs strongly suggest a Class A outcome for fixed \(m=3\) and piecewise-linear phantom systems. The paper’s \((2/3+\epsilon)\) guarantee should pass to rational high-multiplicity societies and, with an appropriate tie convention, to their limits.
The main follow-up questions are whether the continuous optimum is exactly \(2/3\), whether the computer-aided QPQC analysis can be replaced by a polynomial-time exact certificate, and what happens when \(m\) is part of the input rather than fixed at three.
A second useful anchor is Theorem 7, also proved here: “No moving phantom mechanism can achieve \(\ell_1\)-loss less than \(1-1/m\), for any \(m\ge2\).”
Its continuous problem is the corresponding minimax design problem. Given \(m\), a finite peak menu \(T\), and a description-length bound for piecewise-linear phantom flows, decide whether there exists a replication-stable moving-phantom mechanism \(\phi\) satisfying
\[
\sup_{\mu\in\Delta(T)}\ell^\phi(\mu)\le\alpha.
\]
A solution is the phantom flow together with a proof of the bound; a violating population \(\mu\) is a counterexample.
The theorem’s witness is already a high-multiplicity population. Take two types, \(e_1=(1,0,\ldots,0)\) and \(u=(1/m,\ldots,1/m)\), each with mass \(1/2\). The proportional division is \((1/2+1/(2m),1/(2m),\ldots,1/(2m))\), while the moving-phantom outcome is forced to be uniform under the inherited finite-median convention. The loss is therefore \(1-1/m\). This gives a particularly clean continuous boundary: for \(m=3\), the Piecewise Uniform mechanism’s \(2/3+\epsilon\) upper bound is essentially tight within the moving-phantom family.
For fixed \(m\) and finitely described phantom flows, I would expect the corresponding mass optimization to be tractable by order-pattern and quantile case analysis. The unrestricted mechanism-design problem, with variable \(m\) and arbitrary phantom functions, is a possible source of continuum-specific difficulty, but the paper does not establish such hardness.
I would not anchor on Theorem 6, despite its importance, because its lower bound is driven by a single voter’s strategic deviation. Under naive atomless continuization that deviation has zero mass and disappears. Recovering Theorem 6 would require a stronger positive-mass or coalition-deviation notion, which risks changing the authors’ question.
The weakest point is therefore twofold. First, these agents have ideal divisions rather than rankings over a fixed finite type set, so the natural unrestricted type space is \(\Delta_m\), not a finite \(T\). The finite-menu mirror is defensible for standardized civic proposals, and Theorem 7 even needs only two types, but it is not universal. Second, the paper provides approximation and impossibility results rather than the complexity results ChoCo ultimately seeks. Thus this paper does not by itself supply a Class A/B/C classification. It does, however, offer a credible continuous-population formulation whose main proof already operates on normalized masses, with a tractable-looking lead problem and a sharp impossibility boundary.
The strongest negative point is decisive under ChoCo’s stated scope: this paper has no named computational result to continuize. Theorem 5 and Theorem 7 are universal mechanism-quality and impossibility statements, not complexity or algorithmic theorems. They do not take a society as input and ask for bribery, control, campaigning, robustness, or any analogous computational task. The proposed problems \(L_{\mathrm{PU}}(T)\) and minimax phantom design are new problems, not continuous versions of computational results in the paper.
Theorem 5 is the better-looking anchor, but it does not survive that objection. For unrestricted peaks with \(m=3\), the paper’s own Theorem 4 reduces worst cases to three-type profiles described by a constant number of normalized variables. The \(a_j,b_{j,k},C\) variables have already been converted into masses in the proof. Thus the unrestricted continuous problem is essentially the paper’s existing constant-dimensional worst-case analysis rewritten geometrically; it is not a scalable high-multiplicity computational problem with a society supplied as an input.
The proposed finite-menu repair creates a different problem. If \(T\) is part of the input, the paper’s three-type reduction need not preserve \(T\): replacing a peak by a single-minded, double-minded, or fully satisfied report may produce a point outside the menu. Consequently, the \((2/3+\varepsilon)\) theorem gives no characterization of \(L_{\mathrm{PU}}(T)\). If \(T\) is fixed in advance, the resulting optimization again has no meaningful complexity landscape. If \(T\) varies, one has invented a menu-constrained verification problem whose computational content is not supplied by the paper.
There is also a deeper semantic loss. The paper is fundamentally about truthful mechanisms, where one named voter changes her report. In an atomless population, an individual has measure zero and cannot affect the outcome, so individual truthfulness becomes vacuous. Replication-stability preserves truthfulness for every finite approximation, but it does not produce a nonvacuous truthful mechanism on the continuum itself. The natural repair—allowing a positive-mass type or coalition to misreport—changes the strategic problem and requires a new coalition model. Theorem 6 illustrates exactly the feature that disappears: its lower bound is generated by one voter’s deviation.
Theorem 7 is an even weaker computational anchor. Its witness can indeed be read as a high-multiplicity society: half the population has peak \(e_1\), and half has the uniform peak \(u\), yielding loss \(1-1/m\). This is genuine evidence that a population interpretation is sensible; it would be wrong to object that the witness has only two types. But the theorem remains a universal lower bound, not an algorithmic problem. It asks neither what to compute from \(\mu\) nor how hard that computation is.
The proposed continuum minimax problem over phantom flows does not repair this. The finite definition permits a separate phantom system \(Y^{(n)}\) for every population size \(n\); it imposes no consistency condition producing a single flow \(\phi(u,t)\). Requiring replication-stability is therefore an additional modelling axiom. With arbitrary \(\phi\), there is no finite computational representation; with piecewise-linear or bounded-description \(\phi\), one has selected a new mechanism-design class not studied by Theorem 7. The two-type witness may survive either choice, but survival of a witness is not a complexity result.
I am not relying on the mistaken claims that fractional outcomes are already “continuous,” that high multiplicity is implausible, or that a bound passing unchanged would make the question uninteresting. A large municipal consultation with a small menu of recurring proposals is a credible high-multiplicity regime. The honest negative conclusion is narrower: this paper can support a useful side project in continuous mechanism verification or mechanism design, but neither proposed anchor supplies the computational population problem that ChoCo is meant to study. Under the programme’s remit, the mirror is therefore not worthwhile as a priority; the universal claim that no conceivable reformulation could ever be useful would be stronger than the evidence permits.
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.