| paper | d4-conf-ijcai-2015-0164 |
| 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}\)-complete under the stated promises. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given \(m=2^k\) candidates, a target \(c^\star\), and a distribution \(\mu\) over \(\tau\) supported complete rankings with binary rational masses, assume every candidate pair has a strict majority and the induced tournament makes \(c^\star\) a king with out-degree \(m/4\). Decide whether there is a balanced single-elimination seeding in which \(c^\star\) wins. The input is the ranking support and masses, with complexity measured in \(m\), \(\tau\), and their bit length \(L\).
Types are complete rankings of the candidates, each carrying mass \(\mu_t\). Candidates \(a,b\) are matched with \(a\) winning exactly when \(\sum_{t:a\succ_t b}\mu_t>1/2\); the decision variable is a discrete balanced bracket. The population is continuous, while the candidate set and bracket remain discrete.
The mirror covers Theorem 1’s king and out-degree hardness result. It leaves Theorems 2–7, Proposition 1, and Corollary 1 unmirrored, including the bribery, 3-king structural, stochastic choking, and exact counting results.
The strongest mirror is the paper’s voting interpretation of tournament fixing. Candidates are the tournament’s players; a large electorate supplies the pairwise match results. This continuizes the voter population, while leaving candidates, ballots, and the knockout bracket discrete.
A voter type is a complete ranking \(t\) of the candidate set \(C\). The society is a distribution \(\mu\) over the \(\tau\) supported rankings, with each \(\mu_t\) a binary rational fraction of the electorate. For candidates \(a,b\), \(a\) wins their pairwise match exactly when
\[
\sum_{t:\,a\succ_t b}\mu_t>\frac12.
\]
I would restrict instances to strict pairwise majorities, so these comparisons define a tournament. A plausible regime is an election with many voters but relatively few distinct ballots. Replicating every ballot type leaves \(\mu\) and the tournament unchanged while making the electorate arbitrarily large relative to \(\tau\).
The lead question is: given \(m=2^k\) candidates, such a society, and a target candidate \(c^\star\), does there exist a balanced single-elimination seeding in which \(c^\star\) wins every match and becomes champion? The promised version mirrors the paper’s king restriction: the majority tournament makes \(c^\star\) a king—within distance two of every candidate—and \(c^\star\) wins exactly \(m/4\) pairwise contests. A solution is a bracket, not a fractional outcome or a voter-transfer plan.
The anchor is Theorem 1, proved in this paper: TFP is NP-hard even when the player of interest is a king with out-degree \(|V|/4\). The paper starts from general TFP hardness cited to Aziz et al. (2014), then proves the restricted result by reduction. The majority-profile version should inherit this hardness: any tournament can be represented as the strict pairwise-majority relation of a polynomial-size profile of rankings, with rational masses. Applying that representation to the tournament produced by the theorem’s reduction gives a continuous-society instance with the same bracket answers. The mirror is therefore expected to be Class B, hardness transfers: the relevant combinatorics live in the candidate set and its agenda, not in the number of voters. The bracket is also a polynomial-size certificate, and pairwise majorities can be computed from the support, so the decision problem is in NP.
This is especially plausible because the authors explicitly present TFP as agenda control in a binary-cup election whose match outcomes come from pairwise majority preferences. They should recognize a distribution over voter rankings as a direct representation of that electorate. It also makes the high-multiplicity dictionary exact: a finite electorate with \(n_t\) voters of type \(t\) gives \(\mu_t=n_t/N\), and any rational \(\mu\) can be realized by clearing denominators. Ties and margin sensitivity are excluded from this anchor; they could motivate separate questions about how much voter mass must move between ranking types to change the target’s prospects.
The weakest point is that the theorem is proved for tournament graphs, not for electorate distributions. The hardness lift uses the standard construction realizing a tournament by a profile, which is not a result of this paper. And because TFP depends on the electorate only through its induced tournament, the continuous representation does not itself provide a new optimization algorithm. That limits the novelty of this mirror, but not its fit: the society is genuinely the continuous object, and the paper’s stated voting application is exactly where the authors are most likely to accept it.
The best objection is that the electorate is only a way to supply the tournament. Once the pairwise-majority relation is computed, the seeding question uses none of the voter masses: changing them without changing any majority changes nothing. That makes this a thin continuous mirror, with no obvious opening for the continuous-optimization tools that motivate ChoCo.
But that objection does not defeat the anchor. A distribution over complete rankings is a natural representation of the electorate in the paper’s own voting application, and every tournament can be realized by a polynomial-size strict-majority profile. Applying such a profile to the reduction in Theorem 1 preserves the king and out-degree conditions and the answer to the seeding question. Large electorates with repeated ballots are also a sensible high-multiplicity regime. The paper’s bracket and winner remain discrete, but the population supplying the match outcomes is the continuous object.
A richer question about how much voter mass must move to change the result would add a population-control objective, but that would be a different anchor. For Theorem 1’s direct mirror, the objection goes to how much new algorithmic structure the continuum contributes, not whether the mirror is well-posed or recognizable to the authors. I cannot honestly defeat this anchor, so the universal negative case is 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.