| paper | d4-conf-aaai-2016-0081 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: polynomial-time solvable · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 2.1
statement extracted from the paper’s text layer
Given \(n=2^k\) candidates \(V\), a target \(K\), and a distribution \(\mu\) with binary-rational masses over \(\tau\) strict rankings of \(V\), orient each pair by its strict majority under \(\mu\). Let \(A\) be the candidates that beat \(K\), and \(B\) those that beat \(K\)'s opponents but lose to \(K\). If \(K\) is a king and \(B=H\mathbin{\dot\cup}I\mathbin{\dot\cup}J\) with \(|H|<|A|\), \(\mathrm{in}_A(i)\ge\log n\) for every \(i\in I\), and \(\mathrm{out}(j)\le|A|\) for every \(j\in J\), find a balanced seeding in which \(K\) wins. What is the running time in \(n,\tau,L\), where \(L\) is the mass bit length?
The agents are voters whose complete types are rankings of the finite candidate set \(V\), with masses \(\mu_t\). Their pairwise majority outcomes form the candidate tournament; the decision is a balanced bracket seeding, and the objective is to make \(K\) champion. Theorem 2.1's conditions are promises on that induced tournament.
The mirror covers Theorem 2.1's conditional seeding result. It does not continuize the other structural, tournament-solution, or random-tournament results.
The strongest mirror I see is a voter-population version of the paper’s structural seeding result. It is a credible regime for elections: many voters may share a relatively small number of complete rankings, while organizers choose a balanced knockout bracket among the candidates. The paper itself connects tournament graphs to pairwise preferences between alternatives, often generated from voter information, so this supplies a natural electorate behind its tournament input.
My lead anchor is Theorem 2.1, proved in this paper. It says: for a tournament \(T=(V,E)\) with \(n=|V|=2^k\), let \(K\) be a king, \(A=N_{\mathrm{out}}(K)\), and \(B=V\setminus(A\cup\{K\})\). If \(B\) can be partitioned into disjoint, possibly empty sets \(H,I,J\) such that \(|H|<|A|\), every \(i\in I\) has \(\mathrm{in}_A(i)\ge\log n\), and every \(j\in J\) has \(\mathrm{out}(j)\le |A|\), then \(K\) is an SE winner, and a winning seeding can be computed in polynomial time.
The continuous problem I would hand to a prover is Theorem-2.1 Continuous Electorate Seeding. An instance gives a candidate set \(V\) of size \(n=2^k\), a finite support of strict rankings \(T\) over \(V\), and positive binary-rational masses \(\mu_t\) summing to \(1\). Require that every pair has a strict majority: orient \(u\to w\) when the total mass of rankings preferring \(u\) to \(w\) exceeds \(1/2\). The instance also gives a target \(K\) and a partition \(H,I,J\) of the candidates that beat \(K\), satisfying Theorem 2.1’s conditions in this majority tournament. The task is to output a balanced bracket seeding in which \(K\) wins every match and becomes champion. The ranking types are complete voter types; their masses are electorate shares. A discrete electorate with \(N_t\) voters of type \(t\) is the special case \(\mu_t=N_t/N\). The theorem’s algorithm, preceded by computing the pairwise majorities, solves this promised search problem in time polynomial in \(n,\tau,L\), where \(\tau\) is the number of supported rankings and \(L\) their mass bit length.
This is a high-multiplicity scenario when, for example, a large electorate has millions of voters but only tens or hundreds of commonly occurring rankings. The bracket action and its objective remain exactly those of the paper: choose a seeding so the target candidate wins. The continuous object is the electorate’s distribution over rankings. The theorem’s counts concern candidates, as they do in the paper; the voter masses determine the pairwise tournament supplied to it. That makes the mirror modest, but recognizable: the paper presents tournament outcomes as pairwise preferences that can come from voters.
I expect this promised problem to be tractable: Theorem 2.1 gives the constructive algorithm. The broader question it raises is whether unrestricted Continuous Electorate Tournament Fixing—given \(\mu\) and \(K\), find a winning seeding if one exists—remains hard when parameterized by \(n,\tau,L\), and whether profile information yields useful polynomial-time conditions beyond those in the theorem. The introduction reports general TFP hardness via a cited result, but it is not a numbered result proved in this paper, so I do not use it as an anchor.
The soft spot is that the electorate distribution sits upstream: once its majority tournament is computed, the bracket problem is unchanged, and Theorem 2.1 uses no continuous-optimization machinery. An author could reasonably say that their result is about tournaments, with voter profiles only one way to produce them. I still think this is a plausible mirror because the paper explicitly offers that voter interpretation, and the electorate—not the bracket or outcome space—is the continuous population here.
The paper’s result that can honestly anchor the proposed mirror is Theorem 2.1. The NP-hardness mentioned in the introduction is attributed to earlier work, not proved here. Theorem 2.1 gives a polynomial-time seeding algorithm when the candidate tournament meets its stated conditions.
That makes the continuous-electorate version a thin lift of the theorem. Given voter types and rational masses, sum the masses to orient each candidate pair by strict majority, check the conditions, and run the paper’s algorithm. The algorithm never transfers voter mass or reasons about how many voters hold a type; after the pairwise tournament is computed, it uses only the candidates and their edges. The theorem’s thresholds, including \(\log n\), concern the number of candidates. The strongest skeptical reading is that the voter distribution is an alternative encoding of the tournament input, not a continuous version of the bracket problem.
There is a deeper mismatch if the population to continuize is taken to be the tournament’s players. A single-elimination bracket pairs named, indivisible players and outputs one champion. Replacing players with types and masses erases the identity the bracket tracks; in an atomless limit, a designated champion has zero mass. Keeping a singled-out target preserves the original finite-player problem rather than making its participants a continuous population.
That objection does not dispose of the better mirror, though: a large electorate with a small support of complete rankings, whose pairwise majorities determine the tournament. The paper explicitly connects tournaments to elections, so its authors could recognize this scenario. The unrestricted version—finding a winning seeding from such a distribution—also asks a real question about complexity in the support size and mass encoding. Theorem 2.1 does not answer that question. And the fact that its promised version reduces to the same tournament algorithm is not, under the programme’s rules, enough to rule out the mirror.
The skeptical case is therefore that the paper’s own contribution is about finite candidates, while the electorate interpretation adds a population layer the results do not use. But I cannot honestly defend the universal claim that no worthwhile mirror exists: the electorate version is plausible and recognizable, and the strongest objection shows that it is modest, not that it fails.
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.