Possible and Necessary Winners of Partial Tournaments

The strongest honest case is a continuous possible-ranked-pairs-winner problem for a high-multiplicity population of pairwise comparison events. I would use Theorem 14 as the lead anchor.

Theorem 14 states that \(PWRP\) is NP-complete. This result is proved in the paper, not cited from elsewhere. Its underlying problem is: given a partial \(n\)-weighted tournament \(G=(V,w)\), a distinguished alternative \(x\), and a fixed tie-breaking rule for equal edge weights, decide whether there exists a completion \(T\) of \(G\) such that \(x\) is the ranked-pairs winner. The paper proves NP-hardness by reducing from SAT. In its construction, a CNF formula produces an \(8\)-weighted partial tournament with heavy edges of weight \(8\), medium edges of weight \(6\), light edges of weight \(5\), and unresolved literal edges whose two directions initially have weight \(1\). The distinguished alternative \(d\) is a possible ranked-pairs winner exactly when the formula is satisfiable.

My mirror, which I would call \(\mathrm{RP\text{-}PossibleWinner}_{\infty}\), treats the population as a large collection of repeated pairwise comparison events. There are \(m\) alternatives \(C\), and \(M=\binom{m}{2}\) unordered candidate pairs. For each pair \(\{a,b\}\), the population contains mass \(q=1/M\) of comparison events. Some mass \(\ell_{ab}\) is already observed as \(a\) defeating \(b\), some mass \(\ell_{ba}\) is observed as \(b\) defeating \(a\), and the remaining mass \(r_{ab}=q-\ell_{ab}-\ell_{ba}\) is unresolved. Equivalently, the types are “an observed \(a\)-versus-\(b\) comparison won by \(a\),” “the same comparison won by \(b\),” and “an unresolved \(a\)-versus-\(b\) comparison.” All masses are rational and given in binary.

A completion chooses, for every pair, a real number \(z_{ab}\in[0,r_{ab}]\), interpreted as assigning \(z_{ab}\) of the unresolved mass to \(a\) and the remainder to \(b\). It therefore creates the weighted tournament \(W_z\) with \(W_z(a,b)=\ell_{ab}+z_{ab}\) and \(W_z(b,a)=\ell_{ba}+r_{ab}-z_{ab}\). Ranked pairs is then run on \(W_z\), using the paper’s fixed tie-breaking rule. The question is whether there exists a feasible vector \(z\) for which the target alternative \(c^\star\) is the unique ranked-pairs winner. A solution is simply such a completion \(z\), together with the resulting ranked-pairs order if a certificate is desired. The objective is feasibility, exactly as in the paper’s possible-winner problem; there is no added cost or campaign objective.

This has a credible high-multiplicity regime. Imagine a league with \(K\) essentially interchangeable match or assessment slots for every pair of teams. The population has \(N=KM\) events but only \(O(M)\) pair-and-status types, with \(K\) arbitrarily large. Replicating every integer weight in the paper’s construction by a factor \(K\) gives the same normalized masses and the same ranked-pairs comparisons. Thus the model is genuinely about mass rather than named individuals, while preserving the paper’s tournament-level information.

I expect this mirror to be Class B: hardness should transfer. Dividing an \(n\)-weighted tournament by \(n\) preserves every edge ordering, every cycle test, and therefore the ranked-pairs winner. More importantly, Theorem 14’s combinatorics live in the alternatives, clauses, literal gadgets, and directed cycles—not in the number of comparison events. Allowing divisible comparison mass does not obviously remove that structure. In the reduction, a winning completion must still provide, for every clause, a path of the form \(d\to \ell'\to \ell\to c\); the orientation of the unresolved literal pair encodes a truth assignment, and a ranked-pairs stack cannot consistently encode both complementary literals. The paper’s proof therefore appears close to extending to fractional weights, although a formal mirror theorem would need to establish that fractional values cannot create a spurious winning completion. That is the main technical obligation, not something Theorem 14 itself has already proved.

This mirror covers only the possible ranked-pairs-winner result. I would not claim that it mirrors the whole paper. In particular, I would avoid presenting Theorem 7 on the uncovered set as a second anchor: its unweighted tournament setting would require inventing a weighted uncovered-set semantics. Likewise, the polynomial Borda and maximin results are interesting possible algorithmic anchors, but they are weaker for the programme’s central question than this hardness result.

The mirror’s weakest point is that its agents are pairwise comparison events rather than voters with complete rankings. A distribution over ordinary ranking types determines pairwise margins jointly, whereas my model specifies pairwise masses independently. If a referee insists that every society must be a distribution over complete rankings, this becomes an extension rather than a direct mirror: the feasible completions would have to lie in the linear-ordering polytope, and some tournament completions used by Theorem 14 might disappear. The defence is that this paper explicitly studies tournament information independently of preference profiles and motivates it through sports competitions and other pairwise-comparison settings. At that level, repeated comparison events are exactly the paper’s population analogue.

The resulting programme would naturally ask whether \(\mathrm{RP\text{-}PossibleWinner}_{\infty}\) is NP-complete under rational masses, whether it has polynomial-bit rational witnesses, whether the continuous necessary-winner analogue inherits Theorem 15’s coNP-completeness, and how the answer changes when completions are required to arise from one coherent distribution over complete rankings.