| paper | d4-conf-aaai-2008-0033 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
parameterized→NP-hard discrete result → its continuous mirror
Answer: NP-hard: exact enumeration in time polynomial in \(m,\tau,L,a\) would imply \(\mathrm{P}=\mathrm{NP}\). Nevertheless, enumeration is possible in time \(2^k\operatorname{poly}(m,\tau,L,a)\), with individually extendible voter types and exact rational-mass arithmetic. · discrete side: parameterized · adjudication: proved
full proof & adversarial review →
Theorem 5
statement extracted from the paper’s text layer
Given \(p\) binary attributes with a supplied ordered partition \(A_1 > \cdots > A_q\), and a distribution over \(\tau\) types with positive binary-rational masses summing to \(1\), where each type specifies conditional preferences through a CP-net compatible with that partition and having a linear extension, compute the H-Schwartz winner set. At each attribute and setting of the other attributes, use weighted local majority, returning both values on an exact tie; form the induced graph as in the paper and return its Schwartz set.
The bundle space \(X=\{0,1\}^p\) stays discrete. The society is a finite-support distribution over complete conditional-preference types; the local majority correspondence uses their masses to build the paper’s induced graph, and the output is the set of H-Schwartz winning bundles. For rational masses, exact local tallying can operate on the \(\tau\) types, suggesting a weighted counterpart to Process 1’s output-sensitive bound in the number of winners, block-domain size, and local-rule evaluation cost.
The mirror covers H-Schwartz winner computation on profiles compatible with supplied ordered dependence blocks, corresponding to Theorem 5 and Process 1. It leaves the expressivity bound, local-to-global property results, and unrestricted profiles outside that structured setting.
The strongest positive case is a structured mirror of the paper’s H-Schwartz computation, not a claim that continuity makes the general problem easy.
My anchor is Theorem 5, an in-paper result. It says that if an \(n\)-vote profile \(P\) is compatible with an ordered partition \(A_1>\cdots>A_q\), and \(d_{\max}\) is the largest block’s domain size, then Process 1 computes all \(a\) H-Schwartz winners in time
\[
O\!\left(a p d_{\max}\bigl(np+t_{\max}(n)p+d_{\max}\bigr)\right),
\]
where \(p\) is the number of attributes and \(t_{\max}(n)\) is the time to apply a local rule to \(n\) inputs. This is output-sensitive: it is polynomial in the stated quantities, not an unconditional polynomial-time bound when the blocks or winner set are large. Theorem 4 supplies the correctness result for Process 1. The paper also discusses PSPACE-completeness results from prior work, but does not state them as numbered results, so they are not my anchor.
Here is the continuous question I would hand to a prover: Continuous H-Schwartz Winner Computation with Ordered Dependence Blocks. An instance has \(p\) binary attributes, a supplied partition \(A_1>\cdots>A_q\), and \(\tau\) voter types with positive binary-rational masses \(\mu_\theta\) summing to \(1\). A type is a complete conditional-preference table represented by a CP-net that has a linear extension and is compatible with the supplied partition. The task is to compute the set \(W\) of H-Schwartz winning bundles under weighted local majority. At each attribute and setting of the other attributes, mass greater than \(1/2\) favoring value \(1\) selects \(1\); mass less than \(1/2\) selects \(0\); an exact tie selects both. These local choices induce the directed graph as in the paper, and \(W\) is the union of its maximal mutually reachable sets with no incoming path from outside. There is no scalar objective: the solution is the winner correspondence itself.
This is the same choice problem the authors study. H-composition uses the voters’ local conditional preferences to build its graph, so replacing voter counts with masses preserves the rule’s meaning; the bundle space remains discrete. A plausible regime is a very large public consultation over linked policy choices: many residents share a small number of complete conditional-preference templates, issues fall into a common coarse sequence of blocks, and dependencies within a block may still be cyclic. The number of people \(N\) can greatly exceed the number of types \(\tau\). The type definition matters: people of one type agree on all conditional preferences the computation uses, rather than being grouped merely because their overall opinions look similar.
The expected direction for this mirror is tractable, output-sensitively, on the ordered-block slice. For rational masses, weighted local-rule evaluations operate on \(\tau\) types, with exact arithmetic polynomial in their encoding length \(L\). Theorem 5’s bound therefore has a natural weighted counterpart with \(n\) replaced by \(\tau\), and local-rule time replaced by its weighted evaluation time. If the largest block and the number of winners are polynomially bounded, this gives a polynomial-time computation in the encoded input size. The discrete bridge is exact: counts \(n_\theta\) correspond to \(\mu_\theta=n_\theta/n\), producing the same local choices and the same winner set. Conversely, rational masses can be scaled to integer counts. So the mirror is a high-multiplicity version of their problem, with compact mass encoding.
That exact embedding also limits the claim. The theorem does not cover arbitrary mixtures of incompatible dependence structures, and it does not show that continuization dissolves hardness. In the unrestricted mirror, any discrete hardness for the same winner problem transfers through \(\mu_\theta=n_\theta/n\). The further questions are whether the ordered-block condition can be weakened, how the output-sensitive bounds behave when blocks or winner sets grow, and whether the cited hardness boundary persists for compact mass inputs.
My weakest point is the structural promise: a common ordered block partition may fit staged policy decisions, but it excludes much of the paper’s general setting. The result also gives a high-multiplicity implementation of an existing structured algorithm, rather than a new tractability theorem for arbitrary populations. That is still a credible continuous mirror of Theorem 5 because it changes the population representation while preserving the authors’ winner rule and computational question.
The strongest case against this mirror is about its reach. Theorem 5’s bound depends on the number of winners \(a\), the largest block domain \(d_{\max}\), and the cost of applying local rules; it is not a polynomial-time guarantee in the full input size when those parameters grow. Replacing individual votes with \(\tau\) weighted types can reduce the cost of tallying local majorities, but it leaves the induced graph and the cost of enumerating its winners. So the mirror may amount to a weighted-input version of an existing, structurally restricted algorithm.
The proposed consultation scenario also asks residents to share complete conditional-preference tables, with dependencies compatible with the same ordered blocks. That is a demanding notion of “same type”: sharing views on current proposals is not enough if people disagree about preferences across counterfactual settings. The scenario is plausible for repeated machine agents or tightly templated policy decisions, but less persuasive for a broad human electorate. As the number of attributes grows, the tables can become large and types may fragment.
Neither point defeats the anchor under ChoCo’s stated standard. A parameterized result can be worth mirroring, and the exact grouping requirement is part of the high-multiplicity model rather than a defect in it. Scaling rational masses to integer counts gives the discrete bridge; compressing repeated types gives the continuous one. The unrestricted weighted H-Schwartz question is also well-posed, even if its answer were to follow from discrete hardness. That would be a result, not a reason the question should not be asked.
I therefore cannot make a convincing case that no worthwhile continuous mirror exists. The case against is that this particular mirror looks incremental and depends on a restrictive population regime. The proponent’s structured H-Schwartz computation remains a credible anchor, so a universal negative verdict would overstate the evidence.
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.