| paper | d4-conf-aaai-2021-1239 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\Sigma_2^P\)-complete, hence NP-hard, even when \(m=2\) and \(\tau=2\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 6
statement extracted from the paper’s text layer
Given alternatives \(X\), ranking types \(T=\mathcal{L}(X)\), a target rational society \(\mu^\star\), a desired outcome \(X^\star\), and a finite quantifier-free corpus \(A\) of grounded outcome constraints at listed rational societies \(\mu_j\), does there exist \(A_N\subseteq A\) and an explanation \(A_E\) consisting of instances of \(A_N\) such that \(A_N\) is satisfied by some population rule \(F:\Delta(T)\to 2^X\setminus\{\varnothing\}\), every rule satisfying \(A_E\) selects exactly \(X^\star\) at \(\mu^\star\), and no proper subset of \(A_E\) forces that outcome?
A society is a rational distribution \(\mu\) over ranking types, given by its positive-mass support. The decision variables are the normative basis and explanation; their constraints concern population rules \(F:\Delta(T)\to 2^X\setminus\{\varnothing\}\) at finitely many listed societies. The model imposes no topological continuity condition on \(F\).
The hardness may chiefly reflect Boolean choices over a finite list of independently constrained outcomes, with society masses serving as labels rather than driving the computation.
fatal: False
The mirror covers the quantifier-free hardness results, Theorems 3 and 6. It does not establish analogues of the full-language results, Propositions 4 and 7 or Theorems 5 and 8, or the paper's restricted-language observations.
The strongest mirror is a narrow one: the paper’s explicit, quantifier-free justification problems. Its Theorems 3 and 6 are hardness anchors, and their reductions use outcomes at named profiles rather than the identities of the voters or detailed properties of their rankings. That makes those results unusually well suited to a high-multiplicity translation.
Let \(X\) be a finite set of alternatives and \(T=\mathcal L(X)\) the set of complete rankings. A society is a rational distribution \(\mu\in\Delta(T)\), specified by its positive-mass types and binary rational masses. A population rule is a map \(F:\Delta(T)\to 2^X\setminus\{\varnothing\}\). There is no topological continuity requirement on \(F\): the continuous object is the population composition it receives.
For the mirror problems, a scenario gives a target society \(\mu^\star\), a desired winner set \(X^\star\), and a finite corpus \(A\) of quantifier-free Boolean formulas over grounded outcome atoms \(o(x,\mu_j)\). Each named society \(\mu_j\) is part of the input, with its support and masses explicitly listed. Write \(\mathcal I_\Delta(B)\) for the population rules satisfying every formula in \(B\). A pair \((A_N,A_E)\) is a justification when \(A_N\subseteq A\), \(A_E\) consists of instances of \(A_N\), \(\mathcal I_\Delta(A_N)\ne\varnothing\), every rule in \(\mathcal I_\Delta(A_E)\) selects exactly \(X^\star\) at \(\mu^\star\), and no proper subset of \(A_E\) forces that outcome. In this grounded fragment, the formulas are already concrete instances.
The regime is a large membership organization or electorate with many people but only a few stable ranking types. Its decision rule is meant to respond to type proportions, and the justification explains a winner at one composition using concrete normative constraints about that and other named compositions. For example, with three alternatives there are six possible rankings; the hard instances can use just two of them. If there are \(s\) named societies, choose distinct masses \(\mu_j(t_1)=(2j+1)/2^{s+2}\) and \(\mu_j(t_2)=1-\mu_j(t_1)\), for \(1\le j\le s\). These societies have support size \(\tau=2\), yet each requires at least \(2^{s+2}\) voters for an exact finite realization. Thus the number of people can be exponentially larger than the number of types and the written instance.
The lead anchor is Theorem 6, proved in this paper: when the corpus is quantifier-free, EXISTS-JUST is \(\Sigma_2^P\)-complete. Its input is a voting scenario and a quantifier-free corpus; it asks whether there are a normative basis and an explanation satisfying adequacy, relevance, nontriviality, and the full minimal-explanation condition just stated. The paper proves the result by reducing from \(\exists\forall\)-3SAT. The corresponding continuous problem, Continuous EXISTS-JUST, has input \((\mu^\star,X^\star,A)\) as above and asks for such a pair \((A_N,A_E)\). I expect it to be \(\Sigma_2^P\)-complete. In the hardness construction, each profile constant used to encode a Boolean variable can be replaced by a distinct rational society \(\mu_j\). The construction constrains only outcomes at those named points, so any assignment of outcomes there extends to a rule on the rest of the simplex. The upper-bound reasoning also remains finite: only the named societies matter to the grounded formulas. This is my lead mirror because it preserves the paper’s central task of finding a minimally sufficient explanation.
A second, separate anchor is Theorem 3, also proved here: with a quantifier-free corpus, CHECK-JUST is DP-complete. This problem is given a scenario, corpus, and candidate pair \((A_N,A_E)\), and asks whether that pair is a valid justification—meaning, in particular, that its basis is allowed and nontrivial, its explanation is a relevant instance, all rules satisfying the explanation select \(X^\star\) at the target, and every proper subset fails to force \(X^\star\). Its continuous counterpart, Continuous CHECK-JUST, replaces the target profile by \(\mu^\star\) and the rules by population rules on \(\Delta(T)\); it asks whether the submitted pair satisfies those same conditions. I also expect DP-completeness. The paper’s hardness construction again uses outcome constraints at named profiles, which can be placed at distinct rational mass points, while the finite-witness checks extend to the full population domain because the grounded corpus mentions only finitely many societies.
Both mirrors therefore look like hardness transfers: the finite-profile instances used in the reductions remain available as rational societies, and the hard choices in the reductions concern which constraints and outcomes to use. No tractability gain follows merely from expressing those instances as type masses. Useful next questions would be whether hardness persists for recognizable axiom families such as Pareto or neutrality, and how these problems behave when parameterized by the number of named societies, \(\tau\), or \(m\).
The weakest point is the gap between formal fidelity and applied plausibility. These anchors concern arbitrary grounded constraints; the hard formulas can encode Boolean choices and need not resemble a compelling real-world normative corpus. Also, the paper permits rules over individually described profiles, whereas this mirror deliberately studies rules that see only the aggregate distribution. That is a natural regime for large elections with interchangeable ranking types, and the reductions’ outcome-only constraints survive it, but it does not cover every rule or axiom the paper allows. I would not claim the paper’s succinct-language results, Theorems 5 and 8, carry over: their quantification over finite profiles has not been shown to translate faithfully into quantification over population distributions.
The best case against has to concede that this paper has real computational anchors: Theorems 6 and 3 give \(\Sigma_2^P\)-completeness for finding a justification and DP-completeness for checking one in the quantifier-free fragment. Nor is there an obvious identity objection: large electorates with repeated ranking types are plausible. The problem is that the proposed mirrors make population composition do almost no work.
For both theorems, the proponent’s continuous model gives a rule arbitrary values at a finite list of named societies \(\mu_j\). The hard choices are then Boolean choices about \(F(\mu_j)\), linked by the corpus formulas. Values at all other points of \(\Delta(T)\) can be filled in arbitrarily. So the continuous task is, in substance, a constraint problem over a list of output cells; the masses merely distinguish those cells. In the proposed example, \(s\) distinct cells use fractions with denominator \(2^{s+2}\), making each society require exponentially many voters. That establishes high multiplicity, but also shows how little the population contributes: the precise ratios function as labels for the Boolean variables. Replacing them with arbitrary names would leave the constraint problem intact.
That is the same objection to both anchors. Theorem 6’s search for a minimal explanation and Theorem 3’s verification task both survive as formal questions about rules on a finite set of population points. But this does not yet make them worthwhile *continuous-population* mirrors. The paper’s voting rules range over profiles, including profiles that a population rule identifies whenever they have the same type proportions. Moving to \(F:\Delta(T)\to 2^X\setminus\{\varnothing\}\) therefore imposes an anonymity and aggregation semantics on the rule. The selected reductions may avoid collisions between profile constants and thus fit that quotient; that is evidence for a possible mirror, not evidence that the continuous population drives the result.
A more substantive mirror would state normative principles directly over populations—for example, relate outcomes across compositions or quantify over all type distributions. But that needs a finite language and representation for those principles, plus a precise account of how they induce constraints on population rules. The paper’s theorems do not supply that model: its quantifiers range over finite agents and profiles. Developing the population-level semantics could be worthwhile, but it would be new work rather than a direct continuization of these results.
So the negative case is strongest as a challenge to the claimed value of the two mirrors, not as proof that no mirror exists. Under the broad criterion that a rational population point may replace a profile constant, both anchors remain viable. I cannot honestly claim the paper has no worthwhile continuous mirror in any scenario; the strongest concern is that the proposed versions continuize the labels of a justification problem more than they continuize its population.
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.