| paper | d4-conf-aaai-2008-0220 |
| 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}\text{-hard}\) · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 2
Given a candidate set \(C\), a finite-support rational distribution \(\mu\) over strict rankings of \(C\), with no pairwise-majority ties, and a target \(c^\star\), form \(T_\mu\) by setting \(a\succ_\mu b\) exactly when more than half the mass ranks \(a\) above \(b\). Decide whether \(c^\star\in\mathrm{TEQ}(T_\mu)\).
Voter types are strict rankings of \(C\), and \(\mu_t\) is each type’s fraction of the population. Pairwise strict majorities induce the tournament \(T_\mu\); the decision is whether the target \(c^\star\) belongs to its TEQ.
The mirror covers Theorem 2 on TEQ membership and Theorem 1 on Banks-set membership; it leaves out the heuristic TEQ algorithm and the monotonicity conjecture.
The cleanest mirror is a large electorate whose ranking ballots come in a small number of repeated types. Let \(C\) be the alternatives, let each type \(t\) be a strict ranking of \(C\), and let the society be a finite support distribution \(\mu\), with binary rational masses \(\mu_t>0\) summing to \(1\). For each pair \(a,b\), require that exactly one of \(a\) or \(b\) has more than half the mass ranking it above the other. These strict pairwise majorities define a tournament \(T_\mu\). The input is \((C,\mu,c^\star)\); the decision is whether the designated alternative \(c^\star\) belongs to a specified tournament solution of \(T_\mu\). There is no action or optimization objective: the answer is yes or no, as in the paper’s recognition problems.
This is a plausible electorate regime for both results: many voters share one of \(\tau\) ranking types, so the population can be far larger than the support. The paper itself says tournament dominance is commonly defined by pairwise majority voting. Moreover, every tournament can be realized as the strict majority relation of a finite profile with polynomially many ballots by the standard McGarvey construction. Turning that profile into rational type masses gives an exact society representation; repeating each ballot type arbitrarily many times makes the electorate large without increasing \(\tau\). Thus the society version still covers every input tournament in the paper.
My lead is continuous TEQ membership: given \((C,\mu,c^\star)\), decide whether \(c^\star\in\mathrm{TEQ}(T_\mu)\). The paper’s Theorem 2, proved there by a reduction from \(3\)-SAT, says that deciding whether a particular alternative belongs to the tournament equilibrium set of an input tournament is NP-hard. The reduction constructs a tournament in which the designated decision node belongs to TEQ exactly when the formula is satisfiable. The theorem does not claim membership in NP; the paper explicitly leaves open whether the problem could be harder. In the society version, the same tournament can be realized by rational ranking masses, so hardness transfers: this is Class B, with the reduction’s combinatorics in the number \(m\) of alternatives. The direct follow-up questions are how complexity behaves when parameterized by \(m\) or \(\tau\), and whether restrictions on the ballot types yield tractable cases. [The paper’s Theorem 2](https://arxiv.org/pdf/0711.2961)
A second substantial anchor is continuous Banks membership: given \((C,\mu,c^\star)\), decide whether \(c^\star\in BA(T_\mu)\). Theorem 1, also proved in the paper, says that membership in the Banks set of a tournament is NP-complete. The paper supplies an alternative proof using a \(3\)-SAT reduction: the designated alternative is in the Banks set exactly when the constructed formula is satisfiable. The NP witness is a transitive set with that alternative as its maximal element, maximal under inclusion. The paper notes that NP-completeness was previously shown by Woeginger; its contribution here is the alternative reduction. The society problem remains Class B by the same tournament-realization argument, and it retains the NP certificate. A natural further question is whether bounded support \(\tau\) changes the complexity. [The paper’s Theorem 1](https://arxiv.org/pdf/0711.2961)
I consider TEQ the lead because it is the paper’s main hardness result and the less settled complexity question; Banks is a useful companion with the stronger NP-completeness classification. These mirrors cover the two membership theorems, not the paper’s heuristic algorithm or the axiomatic question of TEQ monotonicity.
The soft spot is that the mass distribution matters only through the pairwise-majority signs: once \(T_\mu\) is formed, both problems discard the masses. This is a thin continuization, and it offers no obvious opening for continuous optimization technology. Still, it is a faithful population input to the paper’s actual tournament questions, not continuity of outcomes or noise over discrete profiles. I would expect the authors to recognize it as their membership problem posed from the majority electorate that their introduction already identifies as a standard source of tournaments.
The strongest case against is that the continuous input is immediately reduced to a binary tournament. Given ranking masses \(\mu\), sum the mass preferring \(a\) to \(b\) for each pair and retain only which side has the strict majority. Both Banks and TEQ membership then ignore the masses themselves. Within any region of the population simplex where all pairwise majority signs stay fixed, changing the society changes neither answer. The continuous variables provide no graded measure of support, and the paper’s results offer no obvious opening for continuous optimization tools.
That makes both proposed mirrors thin. For TEQ, the best mirror is still the direct one: given \(\mu\), form its strict-majority tournament and ask whether \(c^\star\) belongs to its TEQ. The paper’s NP-hardness reduction survives because every tournament can be realized by a polynomial-size majority profile, hence by rational ranking masses. The same holds for Banks membership, including its NP certificate. A richer, margin-sensitive version might use more of \(\mu\), but it would require extending the tournament solutions themselves and would no longer be the paper’s membership problem.
This is a reason to rank these mirrors below problems whose computational structure acts directly on masses. It is not, under the programme’s criteria, a reason to reject either one. The population is still the input, large electorates with repeated ranking types are a plausible regime, and the paper explicitly identifies pairwise majority as a common source of tournament dominance. Nor does the exact transfer make this an “already done continuously” collision: the paper’s input is a tournament, not a population distribution. High-multiplicity work, if relevant, would support the regime rather than count against it.
So I cannot honestly defeat either anchor. The best negative case is that the continuization adds little structure and may yield a short bridge back to the paper’s existing problems. But that attacks its likely novelty or payoff, not whether the continuous questions are sensible or worth asking. Under the stated rules, it is not strong enough to support the universal claim that no worthwhile mirror exists.
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.