| paper | d4-conf-aaai-2016-0571 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Propositions 3 and 4 establish separability properties, not computational claims. Observation 2 gives a computation bound, but the stated anchor rule excludes it by result type, leaving the otherwise credible weighted crowdsourcing question without a qualifying result to mirror.
fails bit a — no named computational result to mirror
The proposed extension covers computing a Ranked Agenda outcome on \(K\)-decomposable agendas; it leaves the paper's separability characterizations, counterexamples, and comparisons among rules untouched.
The best positive angle is the paper’s computation on small decomposable agendas, especially in its own crowdsourcing setting: a large pool of annotators labeling many independent tasks, with relatively few distinct complete judgment patterns. A type is one complete, consistent judgment set over all the tasks; its mass is the fraction of annotators with that pattern. For each issue \(\varphi\), its collective support is \(w_\mu(\varphi)=\sum_t\mu_t\mathbf{1}[\varphi\in J_t]\). This is a natural high-multiplicity version of the paper’s profiles.
There is a suitable underlying problem: given a constrained agenda \((\mathcal A,\Gamma)\), a rational distribution \(\mu\) over \(\tau\) complete consistent judgment types, and a decomposition into independent blocks with at most \(K\) atoms each, compute one outcome of the Ranked Agenda rule. Order agenda formulas by \(w_\mu\), allowing any order among ties, then scan in that order and accept a formula whenever adding it preserves consistency. The solution is a complete consistent judgment set generated by this procedure. The type masses are binary rationals, so the instance records \(\tau\), their bit length, the agenda, and \(K\). The target question is whether an outcome can be computed in time \(2^{O(K)}\operatorname{poly}(m,\tau,L)\).
That candidate is plausible as the authors’ problem: the paper explicitly motivates agenda separability with crowdsourced labeling, and Proposition 3 proves that the Ranked Agenda rule \(\mathcal R_{\mathrm{RA}}\) is agenda separable; Proposition 4 further proves it satisfies overlapping agenda separability. Both propositions are proved in the paper. They support the decomposition behind the candidate, though neither is a complexity result.
There is an important limit on the anchor. Observation 2, proved in the paper, says that if an agenda is \(K\)-decomposable and a rule satisfies agenda separability, its collective judgment sets can be computed in \(O(2^K n)\) time. The paper then says winner determination for these rules is \(\Theta^p_2\)-hard or even \(\Pi^p_2\)-hard, citing Lang and Slavkovik (2014) and Endriss and H. (2015). The observation is the closest computational result, but it is not one of the permitted anchor forms: it is not a numbered Theorem, Lemma, Corollary, or Proposition asserting a complexity classification. Propositions 3 and 4 assert separability properties, not computational complexity. So, under the specified anchor rule, this paper has no admissible named computational anchor. I would expect the proposed problem to be Class A for bounded \(K\), with further questions about exact dependence on \(K\), support compression, and whether hardness persists when agenda decomposition is unrestricted.
The weakest point is that the apparent tractability comes from agenda structure, not from replacing the population with a distribution: every rational \(\mu\) can be scaled to a finite profile, and the paper already gives a bound linear in \(n\) for the decomposable case. The continuous version would chiefly expose a support-and-bit-length question—whether the computation can depend on \(\tau\) instead of a potentially huge electorate size. That is a coherent mirror to ask about, but it is a modest positive case, and it cannot substitute for the missing eligible hardness or algorithmic anchor.
The strongest case against a mirror is that the paper’s named propositions are about rule properties, not the complexity of a computational problem. Propositions 1–5 establish agenda separability and overlapping agenda separability; none gives an algorithmic classification. Observation 2 is the closest computational anchor: it states an \(O(2^K n)\) bound for decomposable agendas. But it does not define or classify a complexity problem, and the hardness claims it mentions are attributed to other papers. Under the stated anchor standard, there is no result here for a continuous computational question to mirror.
The proponents’ stronger version of the mirror is sensible: a large crowdsourcing population could be represented by masses over complete judgment sets, or by per-block marginals, and the Ranked Agenda rule could aggregate the resulting fractional supports. Propositions 3 and 4 establish that the rule has the separability properties this computation would use. But those propositions remain axiomatic results. Replacing counts with rational masses in their proofs extends the property; it does not turn it into a computational result.
One could ask for an algorithm that returns a Ranked Agenda outcome from a rational type distribution in time depending on \(K\), \(\tau\), and the mass bit length \(L\). That is a coherent high-multiplicity problem, and the paper’s crowdsourcing motivation makes the population scenario credible. Yet it adds the distributional input model and the computational question that the paper itself does not study. Observation 2 supplies a finite-profile bound; deriving a bound in \(\tau\) and \(L\) would be a new result about that rule, not a mirror of a complexity result established here.
I would not argue that judgment aggregation lacks a plausible high-multiplicity regime, or that a weighted Ranked Agenda algorithm could not be worthwhile. The negative case is narrower: this paper offers no eligible named computational anchor, so that algorithmic project would be adjacent new work rather than a continuization of one of its computational results. If Observation 2 is accepted as sufficient despite the anchor standard, I do not have an honest scenario-based objection strong enough to defeat the crowdsourcing 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.