| paper | Truth-Tracking via Approval Voting: Size Matters |
| authors | Tahar Allouche, Jérôme Lang, Florian Yger |
| venue | AAAI 2022 |
| filed under | voting · rationalization |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c22r1) |
| judge confidence | high |
| authors would recognise it | yes |
The paper contains no numbered theorem asserting hardness, polynomial-time solvability, approximation, or parameterized tractability. Its Theorem 2 has a direct and sensible continuous population restatement, but that does not create the required computational anchor. Therefore bit (a) fails and the grade is red.
fails bit a — no named computational result to mirror
The paper has no named computational result to mirror; the proposed continuous weighted-score computation is a new computational framing rather than a result asserted by the paper.
fatal: True
The proposed mirror covers only Theorem 2's weighted approval characterization; Proposition 1, Theorems 3 and 4, and the empirical results remain structural, statistical, or experimental.
The paper has no named computational-complexity result: Proposition 1 and Theorems 2–4 are structural or statistical, and none states NP-hardness, membership in \( \mathrm{P} \), parameterized tractability, or similar. So there is no honest hardness anchor to claim. The strongest positive case is a prospective computational mirror of its central aggregation theorem.
The natural regime is large-scale crowdsourcing or collective annotation. Fix a small label set \(X\), such as the six animal or texture labels and eight language labels used in the paper, and imagine thousands of similarly trained annotators answering the same kind of question. A type is an approval ballot \(A\subset X\), together with the common noise model assumed by the paper. In the anonymous model, \(A\) is enough: agents with the same ballot are indistinguishable because they share the same \(d\) and common \(\phi\). The mass \(\mu_A\) is the fraction of annotators submitting \(A\). Thus \(n_A/n\) in a finite crowd becomes \(\mu_A\). There are at most \(2^m-2\) proper nonempty ballot types, while the population can be arbitrarily large; in the paper’s \(m=6\) and \(m=8\) datasets this means at most \(62\) and \(254\) possible types.
My lead anchor is Theorem 2, proved in this paper. It says that, for \(n\ge3\), the maximum-likelihood estimator is a size-decreasing approval rule exactly when \( \Delta\psi_d(j)=\psi_d(0,j)-\psi_d(1,j) \) is decreasing. This is unusually well suited to continuization because the theorem already reduces the individual-voter likelihood to an additive score.
The corresponding problem is:
Continuous Anonymous Approval Truth Tracking. An instance consists of alternatives \(X=\{a_1,\ldots,a_m\}\), a finite list of ballot types \(A\in\mathcal S\subseteq 2^X\setminus\{\varnothing,X\}\), rational masses \(\mu_A\ge0\) summing to \(1\), and a rational neutral-noise table giving \(w_k=\Delta\psi_d(k)\), with \(w_k>w_{k+1}\) whenever Theorem 2 requires size decrease. The decision variable is a single alternative \(a\), interpreted as the estimated ground truth. Its objective is to maximize the population score \(S_\mu(a)=\sum_{A\in\mathcal S:a\in A}\mu_Aw_{|A|}\). A solution is any \(a\in\arg\max_{b\in X}S_\mu(b)\), with all tied maximizers returned if ties matter.
This is not a weakened version of the paper’s question. If a finite profile has \(n_A\) voters of type \(A\), then setting \(\mu_A=n_A/n\) gives \(nS_\mu(a)\) equal to the paper’s discrete weighted-approval likelihood score, up to a candidate-independent term. The ballot format, hidden single-alternative truth, Mallows-style noise, and maximum-likelihood objective are unchanged. Only the representation of the population changes from multiplicities \(n_A\) to proportions \(\mu_A\).
I would expect this mirror to be Class A. With the distinct types listed explicitly, compute all \(m\) scores in time polynomial in \(m\), \(|\mathcal S|\), and the encoding length of the masses and weights. The paper’s Examples 3 and 4 become immediate instances: Jaccard noise gives \(w_k=1/k\), while Hamming/Condorcet noise gives constant weights. The continuous version removes dependence on the potentially enormous total number of annotators, while preserving dependence on the number of distinct voter types.
Theorem 4, also proved here, strengthens the plausibility of this regime even though I would not use it as a second anchor. Under the independent Condorcet model, the population mean ballot size is \( \sum_A\mu_A|A|=(m-1)-(m-2)p \). Thus the paper already contains the exact statistic that becomes a continuous population observable. A natural follow-on is to recover a common precision \(p\) from the mass distribution and then apply continuous maximum-likelihood truth tracking. Theorem 3 similarly suggests a heterogeneous extension in which voter types are pairs \((A,\phi)\), with mass over both reports and reliability levels.
The same mirror also generates genuinely computational ChoCo questions. Given a target \(a^\star\), a cost \(c(A,B)\) for converting ballot type \(A\) into \(B\), and a population \(\mu\), one can ask for the minimum-cost mass transfer making \(a^\star\) a maximizer of \(S_{\mu'}\). The transfer variables \(x_{A,B}\) and the winner constraints are linear, so this becomes a finite LP. One can also ask for minimum mass whose removal changes the estimated truth, or for approximation when \(\mu\) is known only through samples.
The weakest point is that this particular mirror is almost too tractable. With an explicit list of ballot types, the winner computation is just a weighted scan, so it does not expose the exponential-variable pricing phenomena that make some continuized voting problems theoretically deep. Also, the lead mirror relies on the anonymous model: if two annotators submit the same \(A\) but have different reliabilities, the complete type must be \((A,\phi)\), and Theorem 2 no longer applies directly. Finally, the paper itself offers no computational hardness result, so this case cannot claim that discrete complexity dissolves; it can only argue that the paper’s central maximum-likelihood problem has a faithful, well-defined, and polynomially solvable continuous population form.
The negative case starts before modelling: this paper has no named computational result to mirror. Proposition 1 and Theorems 2–4 are structural, probabilistic, and statistical statements. None gives a complexity classification, an algorithmic theorem, an approximation guarantee, or a parameterized result. Under the programme’s screening rule, that is decisive. Turning a characterization of a voting rule into a new optimization problem does not retroactively make the source paper computational.
Theorem 2 does admit a perfectly sensible high-multiplicity interpretation, but it is only a representation change. In a large crowdsourcing population, ballot \(A\) can be a type and \(\mu_A\) its mass; this is a legitimate regime, and it would be wrong to object that voters with the same ballot are somehow improperly merged. Yet the resulting estimator is simply
\[ S_\mu(a)=\sum_{A\ni a}\mu_A\,\Delta\psi_d(|A|). \]
Computing its maximizer is the same weighted score calculation already implicit in the paper. Clearing denominators recovers the finite profile exactly, including score comparisons and ties. With sparse support, the computation takes time polynomial in the number of listed ballot types and \(m\); with the full \(2^m-2\) table, the input is already exponential and a linear scan is still the natural baseline. There is no separation problem, hidden optimization structure, or complexity phenomenon left for continuization to expose.
That is not merely the objection that “continuization does not help.” A dull Class-A answer would still count if it were the computational content of a named result. Here the computational question has been manufactured around a theorem that never asks one. If evaluating every social-choice rule on a rational mass vector were enough, every axiomatic or statistical characterization would automatically qualify as a ChoCo anchor, defeating the programme’s named-result discipline.
Trying to make the Theorem 2 mirror more ambitious only moves it away from the paper. If the distribution \(\mu\) is given implicitly by a sampler, density, or probabilistic program, then computing \(S_\mu(a)\) becomes an expectation-estimation or succinct-representation problem. Its difficulty comes from the access model for \(\mu\), not from replacing voters by mass. If \(\mu\) is unknown and must be inferred from samples, the question is statistical estimation and confidence, whereas the paper’s estimator takes the observed profile as input. Neither variant is a direct continuous mirror.
The proposed intervention extensions have the same problem. Adding costs \(c(A,B)\) and asking for the minimum mass transfer making \(a^\star\) win does produce a linear programme:
\[ \min \sum_{A,B}c(A,B)x_{A,B} \]
subject to mass-conservation constraints and linear winner inequalities. But this is a new bribery or control problem. The paper contains no intervention operation, cost model, robustness objective, or computational claim about any of them. With an explicitly listed support it is an ordinary finite LP; with arbitrary costs, the cost representation itself carries the complexity; with a compact edit metric, one gets a new structured optimization problem whose difficulty is not supplied by the paper. The same is true of minimum winner-changing deletion. These could be worthwhile ChoCo projects in their own right, but they cannot rescue this paper as a source of a continuous computational mirror. Otherwise one could manufacture an anchor for any voting rule by appending bribery.
Theorem 4 is even less promising. The identity
\[ \mathbb{E}_p[|A_i|]=(m-1)-(m-2)p \]
says that a population mean ballot size estimates a common precision parameter by a closed-form arithmetic operation. Replacing the empirical mean by \(\sum_A\mu_A|A|\) is exactly the law-of-large-numbers version of that observation. It neither poses nor solves a computational problem. Under heterogeneous reliabilities, the mean identifies at most an aggregate statistic and is insufficient to recover the individual likelihood weights required by the Condorcet rule. Making \(p\) or \(\phi\) part of the type either makes the information explicit or creates a latent-variable inference problem absent from the theorem.
Theorem 3 has the same defect. Its contribution is an analytic sufficient condition ensuring that expected ballot size increases with a noise parameter. A mass distribution over \((A,\phi)\) can average that statement, but averaging a monotonicity theorem is not a computational continuization. If \(\phi\) is observed, the resulting likelihood score is another weighted scan. If \(\phi\) is hidden, the task becomes reliability-distribution learning, with a new information model and new identifiability questions. Neither produces a computational mirror of Theorem 3.
The crowdsourcing story is therefore a genuine high-multiplicity setting, but that concession weakens rather than strengthens the proposed case. It shows that the population regime is sensible; it does not show that this paper contains a computational object whose population version deserves a place in the complexity landscape. The strongest honest conclusion is not that approval populations can never support useful continuous social-choice research. It is that this particular paper supplies no named computational anchor, and every more ambitious anchor proposed for it is either a weighted restatement of the estimator or a newly invented learning, intervention, or robustness problem. On the programme’s terms, that is a strong negative verdict.
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.