| paper | d4-conf-aaai-2016-0133 |
| 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: \(\mathrm{NP}\text{-complete}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 8
statement extracted from the paper’s text layer
Given a partial tournament \(P\) on candidates \(C\) and a target \(c^\star\), does there exist a rational distribution \(\mu\) over strict rankings of \(C\) such that every specified pairwise direction in \(P\) agrees with its margin under \(\mu\), every unspecified pair has nonzero margin, and \(c^\star\in\mathrm{BP}(T_\mu)\), where \(T_\mu\) orients each pair by the sign of its margin?
Types are strict rankings \(t\) of \(C\); masses \(\mu_t\ge 0\) sum to \(1\) and represent population fractions. The decision variables are the masses, constrained by the specified margin signs and nonzero margins on unspecified pairs; the question is feasibility and bipartisan-set membership, with no cost objective.
The input is a partial tournament rather than a known society μ, so the population masses serve as witnesses to possible completions instead of describing a starting population whose changes are computed.
fatal: False
The mirror covers Theorems 8 and 9, the possible and necessary bipartisan-set winner results. It leaves aside the general matrix-game and weak-tournament results, as well as the mixed-integer programming formulation and experiments.
The strongest mirror is on the bipartisan set (BP) side, with Theorem 8 as the lead. The paper proves Theorem 8: given an incomplete tournament and a distinguished vertex, deciding whether *some completion* makes that vertex a BP winner is NP-complete. It proves this in the paper, by reduction from 3SAT. Theorem 9, also proved here, says that deciding whether the vertex is a BP winner in *every completion* is coNP-complete. These are the possible and necessary winner questions, respectively; in a tournament game, BP is the support of its unique equilibrium.
Here is a continuous-population version of each question. Let \(C\) be the candidates, and let a type \(t\) be a strict ranking of \(C\). A society is a distribution \(\mu\) over rankings: \(\mu_t\) is the fraction of voters with type \(t\). For each pair \(a,b\), define the pairwise margin
\[
\Delta_{ab}(\mu)=\sum_{t:\,a\succ_t b}\mu_t-\sum_{t:\,b\succ_t a}\mu_t.
\]
The input is a partial tournament \(P\), recording some known pairwise majority directions, and a target \(c^\star\). Let \(\mathcal U(P)\) be the set of rational societies whose margins agree with every direction specified in \(P\), and are nonzero for every unspecified pair. Each such society induces a completed tournament \(T_\mu\) by orienting each pair according to the sign of its margin.
Continuous Possible BP Winner asks whether there exists \(\mu\in\mathcal U(P)\) with \(c^\star\in\mathrm{BP}(T_\mu)\). A yes-solution is a society distribution witnessing that membership.
Continuous Necessary BP Winner asks whether \(c^\star\in\mathrm{BP}(T_\mu)\) for every \(\mu\in\mathcal U(P)\). A counterexample distribution witnesses a no-answer.
These questions preserve the paper’s BP winner query. The key is that every tournament completion can be realized by a rational ranking distribution. For each oriented pair, take two rankings that agree on that pair and cancel each other’s margins on all other pairs. Combining the two-ranking constructions for all pairs realizes any tournament, with support at most \(2\binom{|C|}{2}\). Conversely, any \(\mu\in\mathcal U(P)\) induces a tournament completion of \(P\). Thus the possible and necessary continuous questions range over exactly the same tournaments as Theorems 8 and 9. The population constraints add coherence through a common distribution over rankings, but that coherence does not remove any tournament completion.
The regime is a large electorate with recurring ballot types: voters share complete rankings, and the unknown information concerns some pairwise majority outcomes. Each realizing distribution has support \(\tau=O(m^2)\), where \(m=|C|\); replicating its ballots leaves the proportions and support unchanged while making the electorate arbitrarily large relative to \(\tau\). The type captures everything this problem uses about a voter—their ranking. There is no numerical optimization objective in the paper’s query, so the continuous decision is feasibility or universal membership, not a newly invented cost minimization.
The expected classification is Class B: hardness transfers. Theorem 8’s mirror remains NP-complete; Theorem 9’s remains coNP-complete. Their reductions encode 3SAT in the tournament structure over alternatives, not in the number of voters. Replacing edge completions with mass distributions over rankings therefore does not dissolve the hardness. The article’s own motivation makes this especially plausible: it connects BP winner questions to partial information about voters’ preferences.
The natural follow-up questions are whether either problem becomes tractable when parameterized by support size \(\tau\), and whether the hardness persists when all majority margins must have a specified positive gap. A separate, more intervention-focused extension would start from a known society \(\mu\) and ask for the minimum mass transfer between ranking types needed to make a candidate a BP winner; that would connect more directly to continuous bribery, but it is not what these theorems establish.
The soft spot is the information model. The input is a partial tournament, hence a *family* of compatible societies, rather than one fully specified distribution \(\mu\). That is faithful to the paper’s possible/necessary winner setting and its discussion of incomplete preference information, but it is the point a referee would need to accept. If a ChoCo mirror must start from one known society and alter its masses, these two questions are not that mirror.
The strongest case against the proposed mirror is that its “society” is only a witness for the paper’s existing completion problem. Theorems 8 and 9 ask whether some or every completion of a partial tournament puts the target in the bipartisan set. The proposed continuous versions quantify over societies whose pairwise margins realize those completions. But every tournament completion can be realized by a rational distribution over rankings, with support \(O(m^2)\); and any fully specified society determines one tournament, whose bipartisan set is computable in polynomial time. So the population adds no constraint to the partial-tournament query, and no computation on a given population: it repackages the same alternatives-level uncertainty as a distributional witness.
That is a real weakness in this particular formulation, but it is not enough to reject the mirror. An unchanged answer or hardness driven by alternatives is not a valid objection under the programme’s criteria. Nor does the paper’s existing high-multiplicity interpretation count against it. The authors explicitly connect the problem to incomplete voter information, and large electorates with recurring ranking types are a plausible regime.
A stronger mirror would start from a known society \(\mu\) over rankings and ask for the minimum mass transfer, at a stated per-unit cost such as Kendall–\(\tau\), that makes a target a bipartisan-set winner. This gives the population a substantive role: the ranking masses and transfer costs jointly determine which majority directions can change and at what cost. It also fits the paper’s limited-control setting and its social-choice application. Ties could be handled with the weak-tournament essential set or a specified margin gap; that is a natural model choice, not a reason to discard the question.
I can’t honestly defeat that stronger mirror on the material given. It changes the paper’s query from choosing arbitrary payoff completions to changing a voter population, so it is not what Theorems 8 and 9 establish. But it is a plausible continuous computational problem that the authors could recognize, and it is enough to make the universal negative case weak.
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.