| paper | d4-conf-atal-2010-0265 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: The decision problem is \(\mathrm{NP}\)-complete, and finding any maximizer is \(\mathrm{NP}\)-hard, even with support size \(\tau=1\) and mass \(1\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 8
statement extracted from the paper’s text layer
Given \(p\) binary issues, an explicitly represented finite support of CP-net types \(N\), binary-rational masses \(\mu_N>0\) summing to \(1\), and a rational cutoff \(b\), decide whether some \(d\in\{0,1\}^p\) satisfies \(F^{(1)}_\mu(d)\ge b\), where \(F^{(1)}_\mu(d)=\sum_N\mu_N N_1(d,N)\) and \(N_1(d,N)=|\{i: N\text{ prefers }d_i\text{ to }\bar d_i\text{ in context }d_{-i}\}|\). The optimization version asks for a maximizer of \(F^{(1)}_\mu\).
A society is a finite distribution \(\mu\) over explicitly represented CP-net types for \(p\) binary issues. The decision variable is the collective outcome \(d\in\{0,1\}^p\); its score is the mass-weighted threshold-one consistency \(F^{(1)}_\mu(d)=\sum_N\mu_N N_1(d,N)\), and the task is to decide whether the score reaches \(b\) or find a maximizing outcome.
The mirror covers the binary-domain threshold-one hardness in Theorem 8 and the threshold-\(p\) algorithm in Proposition 1. It leaves the paper's representation characterizations, sequential-rule impossibility results, and other thresholds unmirrored.
The strongest mirror is a mass-weighted version of the paper’s threshold-one MLE winner determination. It keeps the paper’s binary policy outcomes, CP-net reports, and maximum-likelihood rule intact; the population becomes the continuous object.
Lead anchor — Theorem 8, proved in this paper. For binary multi-issue domains, under a distance-based threshold noise model \(\pi_{1,q}\) with \(q>\tfrac12\), the paper proves that finding an MLE winner is NP-hard. More precisely, deciding whether a profile \(P\) contains an alternative \(d\) with \(N_1(d,P)\ge T\) is NP-complete. Here \(N_1(d,P)\) sums, over the CP-nets in the profile, how many issues have a local preference favoring \(d_i\) over its opposite when the other issues are set as in \(d_{-i}\). The paper proves this by reducing from MAX2SAT.
Here is the continuous problem I would hand to a prover: Continuous Threshold-One CP-Net MLE Winner Determination. An instance has \(p\) binary issues and a finite list of CP-net types \(N\), each with a positive binary-rational mass \(\mu_N\), where \(\sum_N\mu_N=1\). It also has a rational threshold \(b\). Define
\[
F^{(1)}_\mu(d)=\sum_N\mu_N N_1(d,N),
\]
where \(N_1(d,N)\) counts the issues \(i\) for which type \(N\)’s local preference under context \(d_{-i}\) favors \(d_i\). The decision question is whether some \(d\in\{0,1\}^p\) has \(F^{(1)}_\mu(d)\ge b\); the optimization version asks for every maximizer of \(F^{(1)}_\mu\).
This is the normalized expected log-likelihood objective for the paper’s threshold-one model, up to a positive factor independent of \(d\). If an ordinary profile has \(n_N\) reports of type \(N\), set \(\mu_N=n_N/n\). Then \(F^{(1)}_\mu(d)=N_1(d,P)/n\). Thus the discrete instances in Theorem 8 are special cases of this continuous problem, with \(b=T/n\); the reduction’s rational masses and threshold have polynomial-size encodings. I expect hardness transfers (Class B). The reduction’s combinatorics live in the issue assignment and MAX2SAT clauses, not in finely targeting individual voters.
A plausible regime is a large consultation on a package of binary policy decisions. Many residents or stakeholders use the same complete conditional-preference template: for each issue, their local preference is fixed for each relevant setting of the other issues. The type is that whole CP-net, and its mass is the share of the population using it. One can have millions of participants but tens or hundreds of recurring templates. The paper’s hardness construction uses only sparse CP-nets, so this scenario need not rely on huge individual preference tables. Replicating the construction’s types scales the population without changing the normalized instance.
Second anchor — Proposition 1, proved in this paper. For the threshold-\(p\) model, where \(p\) is the number of issues, Algorithm 1 computes the MLE winner set in polynomial time and outputs it compactly. This is an algorithmic result rather than a hardness anchor, but it gives a useful contrast within the same continuous-population model.
The corresponding question is Continuous Threshold-\(p\) CP-Net MLE Winner Determination, with the same binary-rational distribution over CP-net types. For each issue \(i\) and value \(v\), sum \(\mu_N\) times the number of contexts in \(N\)’s conditional preference table where \(v\) is preferred to its opposite. Let \(W_i\) be the value or values with the larger total. The requested solution is the full winner set \(\prod_i W_i\), represented by the \(p\) sets \(W_i\). Proposition 1’s counting argument extends directly: replace counts of CP-nets by rationally weighted counts of their explicit table entries. I expect tractability (Class A), polynomial in the encoded CP-nets and mass bit lengths. The next questions are whether intermediate thresholds \(1<k<p\) are hard or tractable, and whether the threshold-one hardness persists under bounds on support size \(\tau\) or other structural restrictions.
The authors would likely recognize both as continuous versions of their problems: the paper itself defines aggregation over profiles of CP-net reports and studies MLE winner determination for these threshold models. In the mirror, each CP-net type’s mass replaces its fraction of the profile; the collective outcome remains one binary vector. This covers the paper’s binary-domain, distance-based threshold winner-determination results at thresholds \(1\) and \(p\). It does not mirror the representation characterizations or impossibility results in the earlier sections.
The soft spot is that exact repetition of a full CP-net is a demanding assumption, and these mirrors do not promise that continuous optimization will dissolve the threshold-one hardness. The lead mirror is a direct high-multiplicity formulation of the paper’s own computational problem; its value is to make the type support and mass encoding explicit and to ask how complexity changes with them. The positive tractable result at threshold \(p\) shows that this same population model also preserves a meaningful algorithmic boundary.
The strongest case against is that these are unusually thin continuizations. Both replace counts of reported CP-nets with rational weights in an additive score. At threshold \(1\), the proposed objective is exactly the paper’s objective divided by the number of voters on every empirical profile. At threshold \(p\), the paper’s per-issue counting algorithm simply becomes per-issue weighted summation. Neither mirror brings the population-allocation variables or continuous-optimization machinery that motivate much of ChoCo. The proponent also has not established that people commonly share an entire CP-net: a type fixes preferences across all issue contexts, including contexts a voter may never encounter. In many populations, the support size could grow almost as fast as the population.
Those points argue that these mirrors may be low priority. They do not defeat the stronger versions. A large consultation or membership decision over a binary policy package could have many participants represented by recurring, sparse conditional-preference templates. That makes the full CP-net a meaningful type; high multiplicity does not require the number of types to stay constant. Theorem 8’s reduction already uses polynomial-size CP-nets, with support growing with the MAX2SAT instance. Replicating each type yields many people per type while preserving the same rational mass objective. The resulting hardness transfer is exactly the kind of Class B boundary the programme allows; its being direct is not a reason to reject the question.
The threshold-\(p\) mirror also survives, though it is less compelling: its continuous algorithm is a straightforward weighted extension of Proposition 1. The paper’s probability model is not itself a continuous-population treatment, and neither mirror depends on individual identities or loses its objective as agents become infinitesimal. I cannot honestly defeat either anchor under the stated rules. The anti-case supports caution about novelty and priority, but the universal claim that no scenario yields a worthwhile continuous mirror is too strong.
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.