| paper | d4-conf-atal-2010-0132 |
| 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: Polynomial-time solvable · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 1(iii)
statement extracted from the paper’s text layer
Given a finite set C of m alternatives and a finite-support distribution μ over strict rankings of C, with binary-rational masses summing to 1 and strict majority comparisons for every pair, compute ∘TC of the induced majority tournament in time polynomial in m, τ, and L, where τ is the support size and L is the total bit length of the masses.
The society consists of ranking types t with masses μ_t. For each pair of alternatives, compare the mass ranking one above the other to induce the tournament; the output is the union of its inclusion-minimal TC-retentive sets. There is no intervention objective.
The mirror covers Theorem 1(iii) instantiated at S = TC and computing ∘TC from majority-profile masses; it leaves the broader inheritance results, the convergence hierarchy, and TEQ's complexity untouched.
My lead is Mass-\(\circ\)TC: compute the paper’s TC-retentive choice set from a society represented by voter-type masses.
Anchor — Theorem 1(iii), proved in this paper. For every proper tournament solution \(S\), \(\circ S\) is efficiently computable if and only if \(S\) is efficiently computable. The proof gives polynomial-time reductions in both directions for the ordinary explicit-tournament input. This is a tractability result, not a hardness result. I would apply it with \(S=\mathrm{TC}\), whose top cycle is polynomial-time computable.
The continuous problem is: given alternatives \(C\) and a finite-support distribution \(\mu\) over strict rankings of \(C\), with rational masses summing to \(1\), assume every pair has a strict majority comparison. Define \(a\succ_\mu b\) when more than half the mass ranks \(a\) above \(b\). Compute and return exactly
\[ \circ\mathrm{TC}(C,\succ_\mu), \]
the union of all inclusion-minimal TC-retentive sets of the induced tournament. A type is a complete ranking; its mass is the fraction of society with that ranking. There is no voter-level action or optimization objective in this problem: the decision is which alternatives to return. The expected result is tractability in \(\mathrm{poly}(m,\tau,L)\), where \(m=|C|\), \(\tau\) is the number of supported rankings, and \(L\) is the total bit length of their masses.
The population regime is a large election or platform electorate with many repeated ballot types: \(n\) is very large while \(\tau\ll n\). The mass representation treats “\(23\%\) rank \(a\) above \(b\)” as the direct input, rather than requiring the computation to depend on a named voter count. This is a plausible scenario for the paper’s problem: its introduction explicitly motivates tournaments through pairwise majority voting. The ranking distribution induces precisely the dominance relation on which its solution is computed.
The tractability claim follows by first calculating all pairwise majority comparisons and then applying Theorem 1(iii) to \(\mathrm{TC}\). The paper’s Theorem 4, proved here, supplies useful structural support: \(R_{\mathrm{TC}}\) is pairwise intersecting, so there is a unique minimal TC-retentive set. It is supporting evidence rather than a second computational anchor. Conversely, standard majority-profile constructions can represent any tournament using polynomially many ranking types, so this mass formulation does not discard tournament instances. The continuous computation is therefore polynomial when the tournament computation is polynomial, and the profile encoding preserves the underlying problem.
I would class this mirror as tractable. The scope is narrow: computing the TC-retentive choice set from a high-multiplicity electorate. It does not claim to mirror the paper’s convergence results or TEQ’s complexity. The introduction cites NP-hardness of TEQ from elsewhere, but that is not a numbered computational result proved in this paper, so I do not use it as an anchor. A natural follow-up is whether the corresponding mass-profile TEQ problem retains that hardness; since tournaments can be realized by compact majority profiles, I would expect hardness to transfer.
The weak point is that the mass profile collapses to an ordinary tournament before the choice set is computed. This is a faithful high-multiplicity representation of the paper’s majority-voting problem, but it does not expose new continuous optimization or show that population-driven hardness dissolves. It is a credible mirror of one computational result, though a modest example of what continuization can add.
The strongest case against this anchor is that its continuous input is redundant: a distribution over rankings is first compressed into a majority tournament, and \(\circ\mathrm{TC}\) depends only on that tournament. The paper’s Theorem 1(iii) already gives an algorithm for the relation-level problem; aggregating \(\tau\) rational masses into pairwise comparisons takes polynomial time in \(m,\tau,L\). So this mirror adds no population-sensitive structure or new optimization question. It is a modest high-multiplicity encoding of a problem the paper already solves on a more general input.
That makes it a weak ChoCo showcase, but it does not defeat the anchor under the stated standard. Large electorates with repeated ranking types are a sensible regime, and the distribution over complete rankings is a valid continuous society. The question of computing \(\circ\mathrm{TC}\) from that society is well-posed and computational, even if it factors through a tournament and has an immediate polynomial-time solution. The brief explicitly rules out treating a straightforward or unexciting answer as a reason the question is not worth asking.
A more population-sensitive extension could ask for the least mass reallocation needed to change the \(\circ\mathrm{TC}\) choice set. But that adds an intervention cost and objective absent from the paper; it is a new problem, not a stronger version of this anchor that rescues the negative case. I cannot honestly defeat the proposed \(\circ\mathrm{TC}\) mirror: its anchor survives, and the case against it rests only on its limited added value.
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.