| paper | d4-journals-jair-2021-0057 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Corollary 4.5
statement extracted from the paper’s text layer
Given a Boolean integrity constraint \(\varphi\) with feasible type set \(X_\varphi=\operatorname{Mod}(\varphi)\), decide whether there are maps \(g_j:\mathbb{Q}\cap[0,1]\to\{0,1\}\), one for each issue \(j\), with \(g_j(0)=0\) and \(g_j(1)=1\), such that for every finitely supported distribution \(\mu\) over \(X_\varphi\) with rational masses, the judgment vector \((g_j(\sum_{x\in X_\varphi:x_j=1}\mu_x))_{j=1}^m\) belongs to \(X_\varphi\).
A population is a distribution \(\mu\) over complete feasible judgment types in \(X_\varphi\). Each issue's collective judgment depends only on its yes-share, through a common response map across all rational population shares; the output must remain feasible for every such society.
A single map on shares must agree across electorate sizes, while the paper requires an anonymous rule at one finite arity; the proponent acknowledges this added condition but cannot establish that the authors would accept it.
fatal: False
The mirror covers the anonymous-aggregator decision problem for Boolean domains given by integrity constraints, anchored in part (A) of Corollary 4.5; it leaves the agenda results, non-Boolean results, and other aggregator classes aside.
The strongest mirror I believe is for the paper’s anonymous Boolean aggregation result. Consider a large electorate repeatedly deciding a fixed agenda of \(m\) issues under an integrity constraint \(\varphi\). A voter’s type is a complete feasible judgment vector \(x\in X_\varphi=\operatorname{Mod}(\varphi)\). In a plausible high-multiplicity regime, the electorate has \(N\) people but only \(\tau\) distinct judgment types, with \(N\gg\tau\); the meaningful quantities are the fractions holding each type. That fits the paper’s model: voters with the same complete judgment vector are indistinguishable for the problem.
My anchor is Corollary 4.5(A), proved in this paper from Corollary 4.4 and Theorem 4.2. It says that, given a Boolean integrity constraint \(\varphi\), deciding whether \(X_\varphi\) admits an anonymous aggregator is in \(\Sigma^P_2\cap\Pi^P_2\) and is coNP-hard. Here an anonymous aggregator is a conservative, issue-by-issue aggregation rule of some finite arity whose output is unchanged by permuting the voters. The bounds do not establish completeness. The paper imports the equivalence between anonymity and local possibility from earlier work; it establishes the complexity bounds here.
A continuous version would ask the same kind of existence question for population shares. Its instance is \(\varphi\), describing the allowable voter types; the societies it must handle are all finitely supported distributions \(\mu\) over \(X_\varphi\) with binary-rational masses. For each issue \(j\), let
\[
p_j(\mu)=\sum_{x\in X_\varphi:\,x_j=1}\mu_x
\]
be the fraction supporting “yes.” A solution is a tuple of share-response maps \(g_j:[0,1]\to\{0,1\}\) such that \(g_j(0)=0\), \(g_j(1)=1\), and, for every such society,
\[
\bigl(g_1(p_1(\mu)),\ldots,g_m(p_m(\mu))\bigr)\in X_\varphi.
\]
This is a population-responsive, anonymous rule: it sees fractions rather than voter identities, uses each issue’s marginal share separately, and must still return a logically feasible collective judgment. The “solution” is the maps and a proof that they satisfy the condition for every \(\mu\). There is no optimization objective in the paper’s problem, so none is added here.
I would provisionally expect this mirror to be Class C, with continuum-specific obstructions. The maps must work consistently across every rational mass profile, with no fixed electorate size or denominator. A finite anonymous aggregator only has to work for one arity; its values on that electorate’s count grid need not extend to one rule on all shares. Establishing whether the continuous problem has a finite witness or normal form is therefore part of the problem, not something the anchor settles. The corollary’s coNP-hardness does not by itself transfer to this stronger question.
The mirror covers only anonymous aggregation for Boolean domains, particularly the integrity-constraint setting. It does not claim to continuize the paper’s non-Boolean results, its agenda results, or its other aggregator classes. The main weakness is that passing from finite anonymous operations to a single share map imposes cross-denominator consistency that the authors did not require. They may accept the question as a continuous analogue of their anonymous-aggregation problem, while insisting that this extra requirement makes it a stricter problem. The case survives because anonymous aggregators already operate on voter histograms; normalized histograms are precisely population shares. The key follow-up questions are whether a continuous share rule implies a finite local possibility witness, whether such a witness can be extended to all rational shares, and whether continuous rules admit a finite description suitable for complexity analysis.
The strongest objection is a mismatch between anonymity and continuity across population sizes. Corollary 4.5(A) is a genuine computational result: given an integrity constraint, the paper bounds the complexity of deciding whether its domain admits an anonymous aggregator. And a large electorate with many voters sharing the same feasible judgment vector is a credible high-multiplicity regime. Neither the absence of a computational result nor the absence of repeated types is a sound objection here.
For a fixed electorate size \(n\), an anonymous aggregator on issue \(j\) is a function of the number \(k\) of yes votes, so it is defined on the grid \(k/n\). Anonymity requires invariance under permuting voters; it does not require the same response at \(k/n\) and \(k'/n'\) when those fractions are equal. The proposed \(g_j(p)\) imposes that extra cross-size consistency. It is a natural requirement if the society is represented only by its distribution, but it makes the mirror a scale-invariant version of anonymous aggregation, not a direct lift of the paper’s result.
That distinction survives the better formulation. Keep a separate response rule for each \(n\), and the proposal falls back to the finite-arity setting rather than asking a continuous question. Require one rule on shares, and the new cross-size condition becomes part of the problem. The paper’s complexity bounds establish nothing about that condition, and the map is specified over all rational shares rather than by a finite witness the paper’s algorithmic framework can directly manipulate.
This is a real reservation, but it does not defeat the mirror. Deciding whether a finite domain admits such a share-based rule is still a well-posed computational question, and finding a finite characterization would itself be legitimate work. The type space and large-population scenario are sensible; high-multiplicity work, where it exists, supports that judgment. I do not see an honest argument that no continuous mirror is worthwhile in any scenario. The negative case is weak: it identifies an added scale-invariance requirement, but cannot show that the resulting question falls outside what the authors would recognize as their problem.
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.