| paper | d4-conf-aaai-2007-0111 |
| 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}\)-hard; more strongly, \(\Theta_2^p\)-hard and in \(\Sigma_2^p\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 7(i)
statement extracted from the paper’s text layer
Given \(m\) alternatives, a target \(a\), and \(\tau\) complete-ranking types with positive rational masses \(\mu_t\) summing to \(1\), define \(x \succ_\mu y\) when the total mass ranking \(x\) above \(y\) exceeds \(1/2\). Decide whether \(a\) belongs to some inclusion-minimal upward covering set of the resulting dominance relation; on yes-instances, such a set may be returned. Measure input size in \(m\), \(\tau\), and the masses’ bit length \(L\).
Types are complete rankings of the alternatives, each carrying rational mass \(\mu_t\). The induced majority relation determines the upward covering sets; the decision variables are the membership indicators of a candidate subset \(S\), which must satisfy internal and external stability and have no proper subset with those properties. There is no optimization objective: the question is existential membership in an inclusion-minimal set.
This mirrors Theorem 7(i) only. It leaves Theorem 7(ii–iii), the algorithms for bidirectional covering and the essential set, and the set-theoretic results unaddressed.
The lead mirror is Continuous Upward-Covering Membership. Let \(A\) be a set of \(m\) alternatives. An instance gives a target \(a\in A\) and a list of \(\tau\) complete rankings \(\pi_i\), each with positive rational mass \(\mu_i\), where \(\sum_i\mu_i=1\). Interpret \(\mu_i\) as the fraction of society with ranking \(\pi_i\), and define the pairwise-majority relation by
\[
x\succ_\mu y \quad\Longleftrightarrow\quad \sum_{i:\,x\succ_{\pi_i}y}\mu_i>\tfrac12.
\]
The question is whether \(a\) belongs to *some* inclusion-minimal upward covering set of \((A,\succ_\mu)\). Here a set \(S\subseteq A\) is an upward covering set when its upward uncovered set, computed within \(S\), is \(S\) itself, and every \(x\in A\setminus S\) is upward covered in \(S\cup\{x\}\); inclusion-minimal means no proper subset of \(S\) is also an upward covering set. A yes-instance can return such an \(S\). The input size is measured in \(m,\tau\), and the bit length \(L\) of the masses.
My anchor is Theorem 7(i) of this paper. It asserts that it is NP-hard to decide whether an alternative is contained in *some minimal upward covering set*. The paper presents this as its own result, saying it follows from reductions from satisfiability, though it omits the proof. The mirror asks the same membership question about the same covering sets; it changes the society’s input from a dominance graph to a distribution of voter types. The continuum here is the population of ranked voters, not a mixed strategy or a fractional outcome.
This has a plausible high-multiplicity regime: for example, a large election or consultation where many people share ballots, and the number of distinct rankings is small compared with the electorate. Each type is a complete ranking, and its mass is the share of people with that ranking. The paper itself motivates dominance by pairwise majority and cites McGarvey’s result that any asymmetric dominance relation can be realized by a profile of linear rankings. Thus a graph instance for Theorem 7(i) can be represented by a finite ranking profile, then converted into rational masses by aggregating identical rankings and dividing their counts by the total. The induced majority graph, and therefore every upward covering set, is preserved.
I expect hardness to transfer (Class B). The graph-to-profile construction is polynomial, and the resulting rational-mass instance has polynomial encoding size. So a polynomial-time algorithm for this mirror in \(m,\tau,L\) would solve the paper’s NP-hard problem. This is a meaningful boundary case for continuization: the hard combinatorics can lie in the alternatives and the dominance relation, rather than in tracking individual voters.
This mirror covers Theorem 7(i) only. The next questions are whether hardness persists when the induced majority relation must be a complete tournament, as with an odd electorate, and what changes for bounded support size \(\tau\). The weakest point is that the hardness transfer uses McGarvey realizations, which can produce artificial profiles with support growing polynomially in \(m\); it does not establish hardness for fixed \(\tau\) or for the most natural ballot distributions. Still, the population model is one the authors should recognize: it expresses their majority relation directly as shares of voters, while preserving the underlying problem exactly.
The strongest case against this mirror is that the population masses disappear after one preprocessing step. From \(\mu\), compute the pairwise-majority graph; the answer to membership in a minimal upward covering set depends only on that graph. Conversely, McGarvey’s construction realizes any dominance graph with a polynomial-size ranking profile, which can be encoded as rational masses. So Continuous Upward-Covering Membership is polynomial-time equivalent to the paper’s graph problem. It offers no apparent foothold for continuous optimization, and the paper’s mass input adds no structure once the graph is computed.
That makes it a weak candidate if the aim is to find a new algorithmic phenomenon. But it does not defeat the anchor. Theorem 7(i) is a named NP-hardness result, and the profile realization preserves the covering sets with polynomial encoding size. The proposal uses the population as the continuous object; the paper itself takes the dominance graph as input. Under the stated standard, an exact reduction and a Class B result count as a worthwhile mirror, even if the masses are only an encoding of the graph.
A more restricted mirror—say, for complete majority tournaments or bounded support \(\tau\)—could ask a sharper question, but Theorem 7(i) does not establish hardness there. A robustness question over changing \(\mu\) might make mass variation more central, but it would extend the paper’s result rather than mirror it. Neither alternative defeats the unrestricted mirror.
I can’t honestly make the requested universal case against this paper: the sole anchor raised survives. The best negative conclusion is limited to positioning—the mirror may yield less continuous-specific insight than a mass-sensitive optimization problem. That is not enough to reject it under ChoCo’s criteria.
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.