| paper | d4-conf-aaai-2017-0379 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
The weighted-report robust aggregation problem is a plausible continuous-population extension, and the paper's distortion witnesses can be expressed with rational masses. But every named result offered as an anchor is a distortion bound, which does not satisfy the required computational-result criterion. The paper states no named algorithmic or complexity result for computing from mass profiles, so bit (a) fails.
fails bit a — no named computational result to mirror
The proposed mirror covers the knapsack-vote distortion lower bound in Theorem 3.2 and the randomized-threshold distortion bounds in Theorems 3.5 and 3.6; it leaves the ranking results, experiments, and cognitive-load discussion aside.
The paper has no named theorem classifying a problem as polynomial-time solvable or NP-hard. Its strongest named computational results are distortion bounds. I would use those as anchors, without presenting them as running-time hardness results.
The mirror I believe in is a continuous electorate for the paper’s robust aggregation problem. Let \(A\) be \(m\) projects with rational costs \(c_a\), and let \(\mathcal F_c\) be the budget-feasible sets. A voter’s complete type is a normalized additive utility vector \(u\in\Delta(A)\), where \(u(S)=\sum_{a\in S}u(a)\). The underlying society is a unit-mass distribution \(\mu\) over such types. The aggregator sees only the mass \(\alpha_r\) of each reported vote \(r\), not the utilities that generated those reports. Thus the possible societies are those whose reports have masses \(\alpha\).
For a lottery \(q\) over \(\mathcal F_c\), write \(W_\mu(S)=\int u(S)\,d\mu(u)\). The paper’s objective carries over directly: minimize the worst-case ratio
\[
\sup_{\mu\text{ consistent with }\alpha}
\frac{\max_{S\in\mathcal F_c}W_\mu(S)}
{\mathbb E_{S\sim q}[W_\mu(S)]}.
\]
The instance gives the project costs and rational report masses; a solution is an outcome lottery, or a procedure that chooses that lottery from the observed masses. For a finite computational instance, the possible utility types can be a finite catalog; the lower-bound witnesses below use rational utilities. The report mass is the computation’s input because the paper’s motivating uncertainty is precisely that utilities are hidden.
Theorem 3.2 is the lead for the knapsack-vote version. It is proved in the paper: *the distortion associated with knapsack votes is \(\Omega(m)\).* The continuous question is: given costs and rational masses on reported knapsack bundles, find a lottery over feasible project sets minimizing worst-case distortion over all compatible utility societies. In the paper’s witness, all project costs equal the budget and the \(m\) singleton reports each have mass \(1/m\). The utility construction giving the lower bound works with those exact fractional masses; it needs no indivisible voter counts. Conversely, Observation 3.1 gives distortion at most \(m\) by choosing one project uniformly. So the continuous version has worst-case distortion \(\Theta(m)\). The obstruction is driven by the number of alternatives and survives continuization. In the programme’s terms, that is a B-like transfer of a performance lower bound, not a claim of NP-hardness.
The positive counterpart is Theorem 3.5, proved in the paper: *the distortion associated with randomized threshold approval votes is \(O(\log^2 m)\).* The continuous problem is to choose a distribution over thresholds and a map from each resulting approval-mass profile to a lottery over feasible sets, minimizing worst-case distortion over possible utility societies. Its solution is the threshold distribution and aggregation procedure. The paper’s construction uses utility and cost buckets and works with aggregate approval counts; replacing voter counts by masses preserves its inequalities. It is constructive and appears implementable in time polynomial in \(m\), the report support size, and the input bit length. I expect the stated approximation guarantee to be Class A: the continuous version retains the paper’s explicit mechanism.
Theorem 3.6 anchors the other side of that same threshold problem. Its statement is: *the distortion associated with randomized threshold approval votes is \(\Omega(\log m/\log\log m)\).* The proof is in the full version, as the paper says. The continuous question is the same threshold-design problem as for Theorem 3.5; here the requested solution is a lower-bound witness or proof that no threshold-and-aggregation procedure beats that distortion order. Finite voter constructions embed as rational mass profiles, so the lower bound persists. Again, this is an alternatives-driven performance obstruction, not a complexity-hardness result. Together these threshold anchors leave a gap between \(O(\log^2 m)\) and \(\Omega(\log m/\log\log m)\); closing it is a natural further question.
The population regime is municipal participatory budgeting: thousands of residents weighing in on a relatively small project slate. The paper reports 4,430 Boston voters and 10 projects; with 10 projects there are at most \(2^{10}\) distinct approval subsets, so the report profile necessarily contains repeated types. Masses express the natural questions—what share approves a project or submits a given feasible bundle—without tying control or welfare calculations to one-person increments.
The scope here is §3.1’s knapsack-vote distortion lower bound and §3.3’s randomized-threshold bounds. It does not cover the rankings-by-value results, the empirical welfare-ratio experiments, or the paper’s discussion of cognitive load. The randomized threshold is part of the paper’s elicitation method; the mirror still continuizes the electorate, not the outcomes or the time dimension.
My weakest point is the gap between a voter’s complete utility type and the vote mass the aggregator observes. The continuous society is a distribution over full utility types, but the input gives only its projection onto reported ballots; distortion then ranges over the compatible underlying societies. That uncertainty is faithful to the paper’s problem, but it is not literally a known mass vector over the latent utility types. If the programme requires the full utility-type distribution to be given to the algorithm, this mirror fails: revealing it would remove the paper’s central information problem. I think the authors would recognize the report-mass version because their own aggregation rules take reported profiles as input and their distortion objective ranges over the hidden utilities consistent with them.
The strongest objection is that none of these anchors is a computational result in ChoCo’s sense. Theorem 3.2 gives a distortion lower bound for knapsack votes; Theorems 3.5 and 3.6 bound the distortion of randomized threshold approval. They say how well information formats support welfare, not how hard it is to compute an outcome or what algorithms exist for a mass-encoded society. The paper does define a distortion-minimizing rule, but the proposed mirror’s task—compute that rule from rational report masses—is a new algorithmic problem, not what these theorems establish.
The best version of the proposed mirror is still easy to formulate: give the aggregator rational masses on reported ballots, then ask it to choose a lottery minimizing worst-case distortion over all compatible utility populations. The difficulty is that this input is a distribution over *reports*, not over complete voter types. Two residents submitting the same ballot can have different utilities, and those differences matter to welfare. If the input instead gives the distribution over complete utility types, the hidden-utility uncertainty that motivates distortion disappears. So the mirror must either leave ChoCo’s complete-type population model or change the paper’s information problem into a robust optimization problem over an ambiguity set.
For Theorem 3.2, the \(\Omega(m)\) witness carries over to fractional ballot masses, just as the uniform lottery still gives the \(m\) upper bound. That makes a continuous version of the distortion claim straightforward to state, but it does not create a computational question. For Theorems 3.5 and 3.6, the same issue applies: their threshold construction and lower-bound witnesses concern attainable distortion. A genuine computational mirror would ask how efficiently one can optimize over thresholds, feasible project sets, and lotteries from succinct mass input. That may be interesting, but its value needs a separate case; the distortion bounds do not supply it.
There is a real weakness in this negative case. Participatory budgeting has a credible high-multiplicity regime, and ballots over a small project slate have a natural mass interpretation. The authors could plausibly recognize the robust aggregation problem on weighted ballots as theirs. Thus the objection does not rule out a worthwhile continuous mirror altogether. It does show that these three theorems are weak anchors for ChoCo’s complexity programme: the natural mirror preserves their distortion statements, while the more computationally interesting version changes the paper’s central input model.
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.