| paper | d4-conf-atal-2011-0102 |
| 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: \(\mathrm{NP}\)-complete for every fixed \(d\geq1\), even with exactly three types of masses \(3/8,3/8,1/4\). For \(d=0\), a weak local winner always exists and can be constructed in time polynomial in \(m,\tau,L\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4
Input a set \(\mathcal{T}\u005c) of \(\tau\u005c) complete binary-valued CP-net types with total local preference tables and indegree at most a fixed constant, each assigned positive binary-rational mass \(\mu_t\u005c) summing to \(1\u005c). For neighboring assignments \(x,y\in\{0,1\}^n\u005c), let \(p_\mu(y,x)=\sum_{t\in\mathcal{T}:y\succ_t x}\mu_t\u005c). Decide whether there is an assignment \(x\in\{0,1\}^n\u005c) such that \(p_\mu(y,x)\le 1/2\u005c) for every one-variable neighbor \(y\u005c), and return a witness if one exists.
A society is a rational-mass distribution over exact CP-net types; a candidate is a Boolean assignment, and it is a wLCW when no one-variable neighbor is preferred to it by more than half the society. This is a decision-and-witness problem with no objective function.
The mirror covers Theorem 4's wLCW checking and existence question; it leaves final weak Condorcet winner filtering, the SAT translation bound, and the experimental runtime comparisons outside the anchor.
The strongest anchor is Theorem 4, proved in this paper. It says that when every CP-net has node indegree bounded by a constant, checking whether a given alternative is a weak local Condorcet winner (wLCW) is polynomial-time, while finding the set of wLCWs is NP-complete. The anchor is specifically about wLCWs in the graph of alternatives that differ on one variable; it is not a result about computing the paper’s final set of weak Condorcet winners.
A direct continuous version is Continuous wLCW Existence. An instance consists of \(n\) binary variables, a finite support \(\mathcal T\) of \(\tau\) possibly cyclic CP-nets with total local preference tables and indegree at most a fixed constant \(d\), and positive binary-rational masses \(\mu_t\) summing to \(1\). Each type \(t\) is the complete CP-net, including its dependency graph and every conditional preference table; \(\mu_t\) is the fraction of society with that exact CP-net. For alternatives \(o,o'\) that differ in one variable, define \(p_\mu(o,o')=\sum_{t:o\succ_t o'}\mu_t\). Each CP-net directly orders such neighboring alternatives through its CPT, so their preference masses sum to \(1\). The question is whether there is an \(o\in\{0,1\}^n\) such that, for every one-variable neighbor \(o'\), \(p_\mu(o',o)\le 1/2\). Return such an \(o\), or report that none exists. This is the existence-and-witness core of the paper’s “finding the set” result.
The population regime could be a large procurement consortium choosing a standard multi-attribute configuration—for example, a workstation with interdependent processor, operating-system, and security choices. Many participants could share one of a modest number of standardized role or department CP-net templates: perhaps hundreds of types among hundreds of thousands of participants. Bounded indegree fits templates in which each choice depends on only a few other attributes. That is a scenario-specific case for high multiplicity, rather than a claim that every CP-net electorate has few types.
This mirror preserves the theorem’s object and majority semantics. Replacing each discrete agent by mass \(1/m\), and grouping identical CP-nets, gives exactly the same local majority comparisons, including ties, and therefore exactly the same wLCWs. The weighted problem is also in NP: a proposed alternative can be checked against its \(n\) neighbors by querying the supported CPTs and summing rational masses. Theorem 4’s hardness transfers through the equal-mass encoding. I therefore expect Class B: the agenda’s Boolean assignment structure carries the hardness, so weighting the population does not remove it. This gives an exact high-multiplicity mirror, though not a new algorithmic gain.
The scope is deliberately narrow: it mirrors Theorem 4’s wLCW computation, not the paper’s full task of finding weak Condorcet winners. The authors should recognize it as a weighted-population version of their named intermediate problem, which their approach computes before filtering candidates. The paper itself says that this final filtering still has PSPACE-complete complexity; I do not treat that statement as a second anchor here.
The soft spot is that wLCWs are a candidate set, not necessarily the final winners, and the paper’s application may not have many people sharing identical complete CP-nets. Role-based templates make that regime plausible, but restrictive. Further questions include whether wLCW existence becomes tractable under restrictions on the support size \(\tau\) or the variable interaction structure, and what complexity the weighted final-winner filtering has under those same restrictions.
The best objection is that the proponent’s anchor is an intermediate object. A weak local Condorcet winner need only beat, or tie with, its one-variable neighbors in the majority-induced graph. It need not be a weak Condorcet winner in the paper’s original pairwise sense. The paper itself gives examples of that gap. A continuous version could therefore classify the SAT search space that MajCP uses, without answering the group’s actual question: which alternatives survive comparison against every other alternative? If the aim is to understand useful collective decisions, this is a thinner result than a mirror of the final winner problem.
That objection does not defeat the stronger version of the mirror. The authors explicitly define wLCWs, prove a complexity result about finding them, and use them as the first stage of their method. A society with rational masses over complete CP-net types gives a precise weighted version: for each neighboring pair, sum the mass preferring each direction; a candidate is a wLCW if no neighbor has a strict majority against it. Ties and incomparability have a direct interpretation, and no individual identity is needed. Large groups using a modest number of shared preference templates—for example, recurring roles in a consortium choosing a standard configuration—are restrictive but plausible. Neither the local nature of the result nor the fact that it is an intermediate stage makes the question incoherent.
The mirror also seems unlikely to yield the kind of tractability gain that motivates much of ChoCo. Its constraints are weighted majority thresholds over Boolean assignments, and the agenda still has \(2^n\) alternatives. Replicating each discrete voter in proportion to a rational mass gives the original problem as a special case, so the paper’s hardness does not disappear in the weighted setting. But that is a prediction about the answer, and the programme explicitly treats such a result as worthwhile. It is not a sound reason to reject the question.
The honest negative case is therefore weak. The wLCW mirror is narrow, and the paper’s most practically relevant task is finding actual Condorcet winners, not merely its local candidates. The proposed population regime may also require many people to share an entire CP-net, including its graph and conditional preference tables. Those points lower the likely payoff and limit the scenario; they do not rule out a sensible high-multiplicity model. I cannot make the universal claim that no worthwhile continuous mirror exists here: Theorem 4 survives as a well-posed, if specialized, 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.