| paper | d4-conf-ijcai-2021-0778 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-complete · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 4.3
statement extracted from the paper’s text layer
Given a candidate set \(C\) with \(|C|=2^r\), a support \(T\) of \(\tau\) complete rankings with positive rational masses \(\mu_t\) summing to \(1\), and a target \(c^\star\), define \(a\succ_\mu b\) when \(\sum_{t:\,a\succ_t b}\mu_t>1/2\), restricting inputs to those with no tied pair. Is there a balanced binary bracket using each candidate once whose champion under \(\succ_\mu\) is \(c^\star\); if so, find one, with complexity measured in \(|C|\), \(\tau\), and mass bit length \(L\)?
Types are complete rankings of \(C\), and their rational mass distribution \(\mu\) induces a deterministic majority tournament. The decision variable is a balanced bracket, represented by assigning candidates to its leaves; feasibility means \(c^\star\) wins, and the computational task is to decide feasibility and output a bracket.
Covers finding a target-winning bracket when a rational mass distribution over rankings induces a strict-majority tournament; it leaves out the paper’s random-edge threshold guarantees, the \(k\)-king results, and the experiments.
The strongest mirror is the paper’s single-elimination winner problem. The authors explicitly describe tournaments in elections as pairwise majority comparisons, so a large electorate with repeated ranking types gives a natural continuous input to their underlying problem.
My anchor is Theorem 4.3, proved in this paper. It assumes \(n\) is a power of two and each edge of a generalized random tournament is oriented independently, with every orientation probability \(p_{i,j}\) in \([100\log n/n,\,1-100\log n/n]\). With high probability, every alternative can win a balanced single-elimination tournament under some bracket; moreover, a winning bracket for each alternative can be computed in polynomial time. The proof uses Lemma 4.2, which is cited from Vassilevska Williams (2010): in any tournament, every superking is a single-elimination winner, and a winning bracket for a superking can be found in polynomial time. Theorem 4.3 is the computational anchor; the paper’s related-work sentence reporting NP-hardness of deciding single-elimination winners is attributed to Aziz et al. and is not a numbered result of this paper, so I do not count it as another anchor.
Here is the continuous problem I would hand to a prover: Continuous-Majority SE-Winner. An instance consists of a candidate set \(C\) with \(|C|=n=2^r\), a finite support of \(\tau\) complete rankings of \(C\), positive rational masses \(\mu_t\) summing to \(1\), and a target \(c^\star\). Require every pair to have a strict majority: for \(a,b\in C\), set \(a\succ_\mu b\) when the total mass ranking \(a\) above \(b\) exceeds \(1/2\), and require this total not to equal \(1/2\). Ask whether there is a balanced binary bracket using each candidate once in which \(c^\star\) wins every match. A solution is such a bracket. The input is the supported mass list, with running time measured in \(n,\tau\), and the bit length \(L\); the bracket is the decision variable, and the objective is simply to find a winning one.
The regime is a large electorate whose members share a relatively small number of complete rankings: for example, voters repeatedly using a handful of ballot patterns in a committee that chooses a winner through a knockout agenda. The masses are population fractions, so voters cannot be changed one at a time. Scaling up the number of voters while preserving those fractions leaves the continuous instance unchanged. This seems like a question the authors would recognize: it keeps their candidate set, pairwise-majority tournament, target, and bracket-based winner condition. It changes how the tournament is supplied, from a list of edge outcomes to a distribution of voter types.
I expect the general problem to be hardness-transferring. The paper cites NP-hardness of single-elimination winner recognition from outside its own numbered results; standard majority-profile realizations let a tournament be represented by a polynomial-size electorate, and that profile can be encoded as rational masses. Thus the continuum does not erase the combinatorics of choosing a bracket. The hard part is in the number of alternatives and the agenda, not in tracking named voters. Useful follow-up questions include whether the problem is FPT in \(\tau\), how strict versus tied pairwise majorities affect it, and how much population mass must move between ranking types to make a target a winner.
The scope here is deliberately narrow: it mirrors Theorem 4.3’s underlying single-elimination winner task, not the paper’s \(k\)-king threshold results, random-tournament probability bounds, or experiments. The soft spot is that Theorem 4.3’s independent random-edge model does not follow from a single distribution over rankings; pairwise majority outcomes from shared rankings can be strongly dependent. So its high-probability guarantee and polynomial-time construction do not carry over as stated. The case for the mirror rests on the paper’s underlying problem being a natural computation on a continuous electorate, not on transferring that theorem’s random-model guarantee.
The strongest case against is that Theorem 4.3 is a guarantee about random tournaments, not a complexity classification for a problem on populations. Its edge orientations are independently randomized, with probabilities bounded in terms of the number of alternatives \(n\). The proposed Continuous-Majority SE-Winner instead takes a deterministic distribution over voter rankings, converts it to majority edges, and asks whether one target can win. That is a sensible question, but it drops the theorem’s probability model and its claim that all alternatives are winners with high probability. The NP-hardness cited for winner recognition is from outside this paper; Theorem 4.3 gives a polynomial-time bracket construction for typical random tournaments, not a worst-case complexity result for the population problem.
A more faithful attempt to preserve the theorem’s random model runs into a modeling gap. Sampling many voters from a distribution over rankings gives pairwise outcomes that depend on the same ballots, so the edge outcomes are generally correlated. As the electorate grows, nonzero pairwise margins settle into deterministic majority edges; exact ties create a different limiting issue. Neither reproduces the paper’s independent edge noise and its \(p\)-thresholds. One can manufacture a random electorate by first drawing a tournament and then realizing it as a majority relation, but that leaves the theorem’s tournament randomness in place; it does not explain it through a population model. Lemma 4.2 does not bridge this gap: it is a pointwise tournament result about superkings and bracket construction.
That objection does not defeat the proponent’s improved mirror. A large electorate with repeated ranking types choosing among candidates through pairwise majority and a knockout bracket is plausible, and target-winner recognition on its rational mass distribution is well-posed. The authors could reasonably recognize it as their underlying single-elimination-winner problem. The fact that the population affects the task only through the resulting majority tournament is not enough to dismiss it under the programme’s rules.
So the defensible negative claim is narrower: the proposed population problem does not mirror Theorem 4.3’s probabilistic contribution, and the paper itself establishes no complexity classification for that continuous-population problem. The universal claim that *no worthwhile continuous mirror exists* is weak: the direct majority-profile winner query survives, even if its connection to the paper’s main theorem is looser than the proponent suggests.
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.