| paper | d4-conf-aaai-2010-0095 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Deterministic polynomial-time solvable in \(m,\tau,L\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given \(2^r\) candidates, a target \(c^\star\), a fixed tie-breaking order, and a rational distribution \(\mu\) over strict rankings, orient each candidate pair toward its majority-preferred candidate, resolving ties by the order. If every candidate that defeats \(c^\star\) has outdegree at most \(c^\star\)’s outdegree, construct a balanced single-elimination bracket in which \(c^\star\) wins.
The society is a distribution \(\mu\) over ranking types, with \(\tau\) supported types and binary rational masses. The masses determine pairwise-majority outcomes; candidates and brackets remain discrete, and the output is a bracket rather than an optimized mass transfer.
Covers Theorem 3’s promised structural case for electorate-induced majority tournaments. It does not cover Theorem 1’s arbitrary missing-match graphs; Theorem 2 concerns complete binary arborescences, not this binomial-arborescence anchor.
The strongest mirror I believe is an electorate-level version of the paper’s cup-voting problem. The contestants remain discrete; the population being continuized is the electorate whose pairwise majorities decide the matches. That fits the paper’s voting interpretation directly: it describes candidates competing by majority comparisons along a binary voting tree.
Call the lead problem Dominating-Losers Continuous Agenda Bracketing. Its input is a candidate set \(C\) with \(|C|=2^r\), a support \(T\) of \(\tau\) strict rankings, rational masses \(\mu_t>0\) summing to \(1\), a fixed tie-breaking order, and a target candidate \(c^\star\). For each pair \(c,d\), orient the edge toward the candidate preferred by more than half the mass; use the tie-breaker on equal masses. Write \(d_\mu(c)\) for the number of candidates \(c\) defeats. The input is promised to satisfy
\[
d_\mu(d)\le d_\mu(c^\star)
\quad\text{for every }d\text{ that defeats }c^\star.
\]
The task is to produce a balanced single-elimination bracket, using every candidate once, in which \(c^\star\) wins. A solution is the bracket itself. A plausible regime is a large electorate with many repeated ballots: \(n\) voters but only \(\tau\ll n\) distinct rankings. Each ranking type is a complete preference description, and its mass is its fraction of the electorate.
The anchor is Theorem 3, proved in this paper: for a tournament graph \(G=(V,E)\), if every in-neighbor \(v\) of \(A\) has \(\deg_{\mathrm{out}}(v)\le \deg_{\mathrm{out}}(A)\), then a binomial spanning arborescence rooted at \(A\) can be constructed in polynomial time. The paper identifies that arborescence with a balanced single-elimination tournament won by \(A\). Applying the theorem to the tournament induced by \(\mu\) gives the promised bracket. Constructing the pairwise-majority graph takes polynomial time in \(m,\tau,L\), where \(L\) is the bit length of the masses, so this promised continuous problem is tractable in \(\mathrm{poly}(m,\tau,L)\).
This is a plausible analogue because the society is explicitly a distribution over voter types, while the question remains whether agenda control can make the target win. The distribution changes the pairwise outcomes; it does not fractionalize candidates or brackets. The result therefore mirrors a real constructive agenda-control theorem, though only on the stated structural regime.
My case covers Theorem 3, not the paper’s general NP-completeness result. Theorem 1 concerns arbitrary directed graphs where missing edges make some matches unavailable; a voter distribution with pairwise-majority comparisons instead induces a complete tournament. The paper itself says hardness for balanced tournament fixing on unweighted tournament graphs remains open, so I would not claim that Theorem 1 supplies a hardness anchor for this mirror.
The weak point is that this is a restricted tractable slice, and the algorithmic content comes from the theorem’s graph structure, not from continuous optimization. It establishes a sensible continuous-population input and a concrete constructive question, but does not settle unrestricted agenda control. The next questions are whether the unrestricted target-win problem on distributions \(\mu\) is tractable, and how the set of distributions supporting a winning bracket changes as \(\mu\) moves through the preference simplex.
The strongest case against is about payoff, not legitimacy. In the proposed Theorem 3 mirror, the ranking masses matter only through the signs of the pairwise majority margins
\[
\sum_{t\in T}\mu_t\bigl(\mathbf{1}[c\succ_t d]-\mathbf{1}[d\succ_t c]\bigr).
\]
Once those signs are known, the degree condition and the bracket construction are exactly the graph problem already solved in the paper. The continuous input adds a representation and preprocessing step; the algorithm does not optimize over population mass. That makes this a thin ChoCo contribution if the aim is to bring continuous optimization into reach. But it is only a case for prioritizing other papers: under the programme’s stated criteria, a tractable or already answered mirror is still a valid mirror.
The proposed Theorem 3 anchor itself survives scrutiny. Voter rankings are complete types, repeated ballots are a plausible high-multiplicity regime, and the electorate’s aggregate determines the match outcomes. The fact that candidates remain discrete does not invalidate population continuization. Nor can I dismiss the mirror because its bracket is unchanged by scaling the electorate: the distribution still determines which tournament the agenda designer faces.
A stronger mirror asks, for an unrestricted rational ranking distribution \(\mu\) and target \(c^\star\), whether any balanced bracket elects \(c^\star\). That is the paper’s tournament agenda-control problem on the majority tournament induced by \(\mu\), and the paper identifies this problem as open. The paper also gives a more direct hardness anchor: Theorem 2 proves NP-completeness for complete binary arborescences on tournament graphs. Any tournament can be realized as the pairwise-majority relation of a strict-ranking profile with polynomial support and rational masses, so that hardness carries to a continuous-electorate input. Theorem 3 then gives a tractable structural regime within this broader problem.
The arbitrary-digraph Theorem 1 is a weaker fit: voter majorities produce a complete tournament, so its missing-match restrictions need an additional model feature. Still, that does not affect the electorate mirrors of Theorems 2 and 3. My negative case is therefore weak: the mirror may offer little new continuous-optimization machinery, but I cannot make an honest case that no worthwhile continuous mirror exists.
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.