| paper | Extending Tournament Solutions |
| authors | F. Brandt, Markus Brill, Paul Harrenstein |
| venue | AAAI 2014 |
| filed under | voting · tournaments |
| judged by | gpt-5.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{-complete}\), even with positive dyadic masses and \(\tau=O(m^2)\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 20
statement extracted from the paper’s text layer
Given a finite candidate set \(A\), a rational distribution \(\mu\) over complete ranking types, and a designated candidate \(x\), form the majority weak tournament \(W_\mu\); decide whether some orientation \(T\in[W_\mu]\) satisfies \(x\in BP(T)\).
A high-multiplicity electorate with ranking types \(t\), masses \(\mu_t\), and candidates \(A\); binary orientation choices for tied majority pairs; feasibility objective \(x\in BP(T)\).
It covers Proposition 20 and Corollary 2 in the computational-complexity section, but not the inheritance axioms, comparison results, polynomial cases, or the open conservative-extension problem for \([MC]\).
The strongest positive case is a continuous version of the paper’s conservative-extension winner problem, with the population—not the alternatives or outcomes—as the continuous object.
Take a finite candidate set \(A\), a finite-support distribution \(\mu\) over complete rankings \(t\in\mathcal T\), and a designated candidate \(x\). The mass \(\mu_t\) is the fraction of the electorate with ranking \(t\). Define the induced weak tournament \(W_\mu\) by
\[ a\succeq_\mu b \quad\Longleftrightarrow\quad \sum_{t:a\succ_t b}\mu_t \ge \sum_{t:b\succ_t a}\mu_t. \]
Thus \(a\sim_\mu b\) exactly when the two sides have equal population mass. The candidates remain discrete, as do the rankings and the final winner set; only the electorate is continuous.
The natural regime is a large electorate with relatively few repeated ranking types: for example, a national election with millions of voters but a modest support of recurring preference orders. Rational \(\mu\) is exactly the high-multiplicity representation of a finite profile: if \(\mu_t=n_t/N\), one can recover the finite electorate by taking \(n_t\) copies of type \(t\). Conversely, the continuous model forgets irrelevant voter identities and retains the type masses.
My lead anchor is Proposition 20: “Computing \([BP]\) is NP-complete.” This result is cited from Brill et al. (2016), rather than proved in the manuscript. Its underlying problem is: given a weak tournament \(W\), determine whether a candidate belongs to the conservative extension of the bipartisan set,
\[ [BP](W)=\bigcup_{T\in[W]}BP(T). \]
In other words, one asks whether some orientation of the tied comparisons makes the candidate a bipartisan-set winner.
The continuous mirror is:
\[ \textsc{Continuous-Conservative-Bipartisan-Winner}. \]
An instance consists of \(A\), a rational distribution \(\mu\) over complete ranking types, and a candidate \(x\). Construct \(W_\mu\). For every tied pair \(\{a,b\}\), choose one of \(a\succ b\) or \(b\succ a\), obtaining an orientation \(T\in[W_\mu]\). The question is whether there exists such an orientation with \(x\in BP(T)\). A solution is the orientation, together with a witness that \(x\) belongs to the bipartisan set of that orientation; the optimization objective is simply feasibility.
This is recognisably the paper’s problem: the paper explicitly motivates weak tournaments by preference profiles with majority ties, and defines the conservative extension as winners under possible orientations. The continuous population supplies those pairwise margins directly. It does not replace the bipartisan set by a fractional outcome or alter the conservative-extension semantics.
I expect this mirror to be Class B: hardness transfers. Standard weighted-majority constructions can represent any weak tournament by a rational distribution over complete rankings, with polynomially many ranking types. Therefore the NP-hard weak-tournament instances from Proposition 20 can be compiled into continuous societies. This does not claim that population continuity dissolves the hardness; it identifies the problem as one whose combinatorics live in the pairwise completion and tournament solution rather than in named voter multiplicity.
A second worthwhile anchor is Corollary 2: “Computing \([BA]\) is NP-complete.” This corollary is derived in the manuscript from Lemma 5, which proves that NP-completeness of winner determination for a tournament solution transfers to its conservative extension. The underlying Banks-winner hardness is cited from Woeginger (2003).
The corresponding problem is:
\[ \textsc{Continuous-Conservative-Banks-Winner}. \]
Given \(A\), rational ranking masses \(\mu\), and \(x\), compute whether
\[ x\in[BA](W_\mu) = \bigcup_{T\in[W_\mu]}BA(T). \]
Equivalently, choose orientations of all pairwise population ties and ask whether \(x\) is a Banks winner in at least one resulting tournament. Again, a solution is the successful orientation and its Banks-winner certificate. This is also expected to be Class B. In fact, the reduction is especially transparent on societies with no pairwise ties: then \(W_\mu\) is already a tournament, and \([BA](W_\mu)=BA(W_\mu)\). Thus the continuous problem contains the cited NP-hard tournament problem as a special case.
These mirrors cover only the paper’s computational Section 6—Proposition 20 and Corollary 2. They do not claim to continuize the axiomatic inheritance results, the comparisons with other extensions, or the open problem concerning \([MC]\).
The weakest point is that the continuous layer may look like a thin front end: both problems ultimately use only the induced weak tournament, not the full distribution \(\mu\). Moreover, the paper’s orientations need not correspond to perturbations of \(\mu\) by an actually realizable nearby ranking distribution. That is a genuine modelling choice. The present mirror deliberately adopts the paper’s own conservative-completion semantics; a stricter follow-up would ask for winners under only those orientations realizable by infinitesimal mass perturbations. That variant would be more distinctively continuous, but it would be a new problem rather than the cleanest mirror of the paper’s named results.
The strongest negative case is that both proposed mirrors put a continuous wrapper around a finite weak-tournament problem. Let \(\Phi(\mu)=W_\mu\) be the induced majority relation. Their decision predicates factor completely through \(\Phi\):
\[ x\in[BP](W_\mu) \quad\text{or}\quad x\in[BA](W_\mu). \]
Thus the distribution’s support, multiplicities, and all information beyond pairwise majority margins are discarded before the computation begins. With no majority ties, the conservative extension collapses to the ordinary tournament solution. With ties, the paper’s arbitrary orientations need not correspond to perturbations of any nearby population distribution. The McGarvey-style construction \(W\mapsto\mu\) proves only that weak tournaments can be encoded as profiles; it does not show that population continuity is doing mathematical work.
This is a legitimate criticism of the proponent’s particular formulation: it is a thin encoding rather than a population-sensitive computational problem. A stronger mirror would instead ask for the minimum mass transfer, under a ranking-distance cost, needed to make \(x\) a bipartisan or Banks winner:
\[ \min_{\nu} d(\mu,\nu) \quad\text{subject to}\quad x\in BP(W_\nu) \]
or \(x\in BA(W_\nu)\). But that introduces a new intervention or robustness problem absent from the paper. It is no longer the named possible-winner problem, and its value depends on modelling choices about distance, admissible perturbations, and tie handling.
That objection does not defeat Proposition 20, however. It is a named computational result, explicitly about winner determination for weak tournaments arising from majority ties. A rational distribution over ranking types is a sensible high-multiplicity representation of exactly that electorate, and the induced weak tournament is the paper’s own object. The fact that the answer depends only on the majority relation is not a fatal mismatch: majoritarian rules are designed to have precisely that dependence.
Corollary 2 survives for the same reason. Indeed, the no-tie subcase already embeds Banks-winner determination: a rational high-multiplicity society can induce any required tournament, and then \([BA](W_\mu)=BA(W_\mu)\). This makes the proposed mirror thin, but not ill-posed.
So the honest negative conclusion is limited. The proponent has not yet shown a rich or distinctly continuous algorithmic programme; their constructions are mostly encodings of existing tournament problems. But I cannot honestly defeat both anchors under the stated rules. Proposition 20 alone supplies a valid continuous-population mirror, and a mass-transfer or robustness refinement would make the population genuinely computationally active.
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.