| paper | d4-conf-atal-2016-0089 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Polynomial-time constructible, in \(\mathrm{FP}\), including the entire encoded derivation. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given a finite alternative set \(C\) and a binary-rational distribution \(\mu\) over \(\tau\) complete rankings, construct a finite derivation of \(W(\mu)=\arg\max_{c\in C}\sum_t\mu_t s(t,c)\) from a rational-mass extension of \(J_B\). Intermediate profiles are finite nonzero rational measures over rankings, with the paper’s \(\mathrm{Elem}\), \(\mathrm{Cycl}\), \(\mathrm{Canc}\), and reinforcement axioms interpreted on those measures.
Types are complete rankings \(t\), with population masses \(\mu_t>0\) summing to \(1\). The certificate consists of intermediate rational-mass profiles, rational coefficients, and a finite sequence of \(J_B\) inference steps deriving the exact Borda winner set; the task is to produce any valid certificate.
The opponent points out that rational masses can be scaled to finite profiles and that the paper provides no evidence that mass-valued proof certificates are shorter or easier for users; this limits the claimed practical benefit, which the proponent also leaves as an open question.
fatal: False
The mirror covers Theorem 2’s construction of proofs for Borda winner sets. It does not cover Theorem 1’s completeness result, the general argumentation framework, or the applications to attacks between voting rules.
The strongest case is narrow: continuize the paper’s algorithm for explaining Borda winners, rather than trying to continuize its whole argumentation framework.
My anchor is Theorem 2 (Borda justification). Proved in this paper, it says that for every profile \(R^*\), Borda-expl computes a proof, grounded in the paper’s axiomatisation \(J_B\), of the exact winner set selected by Borda. The construction combines elementary profiles, whose winners are fixed by the Elem axiom, with cyclic profiles, whose full alternative set wins by Cycl. It then uses cancellation, reinforcement, subtraction, and simplification to derive the Borda winner set for the input profile. Theorem 2 asserts correctness of this algorithm; it does not state a polynomial-time bound or a complexity-class classification. Its proof uses Lemma 2, including Lemmas 1 and 3 attributed to Young (1974) and the paper’s own restricted-cycle construction in Lemma 4.
I would not use Theorem 1 as a second anchor: it establishes completeness of the proof system, not an algorithmic result. The paper gives no named hardness result to anchor, so Theorem 2 is the best available computational result.
Call the mirror Continuous Borda Explanation. An instance consists of a finite alternative set \(C\), and a list of \(\tau\) complete rankings \(t\) with binary-rational masses \(\mu_t>0\) summing to \(1\). Each ranking is a voter type: anyone with that ballot is identical for the purposes of Borda and the explanation. Mass \(\mu_t\) is the fraction of the electorate with ranking \(t\). The question is to produce a finite derivation of the exact Borda winner set
\[
W(\mu)=\arg\max_{c\in C}\sum_t \mu_t\,s(t,c)
\]
from a mass-valued version of \(J_B\). The solution is the proof certificate itself; this is a search problem, not an optimization problem.
For precision, intermediate proof claims can use any nonzero finite rational mass vector \(\nu\), interpreted after normalizing by its total mass. Extend the paper’s axioms to these weighted profiles: Elem applies to the two rankings in an elementary profile, Cycl to equal mass on the cyclic rotations, Canc to profiles with zero pairwise margins, and Reinf to addition of masses. Reinf-sub and Simp express subtraction and positive rescaling. The certificate records intermediate weighted profiles and rational coefficients directly; it need not expand them into a list of individual voters. This preserves the paper’s underlying task—explaining why Borda’s outcome follows from those axioms—rather than replacing it with merely calculating a winner.
A plausible regime is a large organization or online election on a fixed slate, where many people submit complete rankings but shared endorsements, party blocs, or standard ballot patterns leave only a moderate number of distinct rankings. Then the electorate size \(n\) can be enormous while \(\tau\) is comparatively small. Complete rankings are a credible type description because the paper’s Borda rule uses only rankings, and mass is a natural way to say “\(x\)% of voters submitted this ballot.” The society is what becomes continuous; alternatives and the winner set remain discrete.
I expect this mirror to be Class A, tractable. The paper’s construction uses at most \(m-1\) elementary profiles and \(O(m^2)\) cyclic profiles, and its key step is solving a rational linear system over \(O(m^2)\) margin coordinates. With a compressed certificate representation, the corresponding construction appears to take polynomial time in \(m\), \(\tau\), and the input bit length \(L\). That is an analysis of the proposed mirror, not a runtime theorem claimed by the paper. It also gives a natural next question: prove a bit-complexity and output-size bound for the mass-valued explanation algorithm, and determine whether the resulting proofs remain usable in the paper’s intended explanations to people.
The mirror covers only Theorem 2’s Borda-outcome justification. It does not claim a continuous result for the general framework, for attacks between rules, or for natural-language rendering.
The soft spot is that the paper defines profiles as finite electorates, and its axioms use operations such as adding profiles and repeating them an integer number of times. A rational-mass proof system is an extension that the authors did not state or prove. They might question whether derivations involving fractional intermediate populations count as the same kind of understandable argument they intend to generate. The case survives because the proof still explains the same Borda outcome from the same substantive axioms, while expressing the electorate in proportions—the natural high-multiplicity representation for this regime.
The only anchor is Theorem 2, and it is a genuine computational result: Borda-expl constructs a proof of the Borda winner set. I can’t dismiss it as purely axiomatic. Nor do the usual modelling objections work: complete rankings are natural types, voter identities are irrelevant, and mass-valued versions of the paper’s profile operations are plausible.
The strongest case against is that the proposed mirror may be a thin high-multiplicity implementation question. For any rational society \(\mu\), clearing denominators gives a finite profile with the same Borda outcome. The construction in the paper works with beta scores, pairwise margins, and auxiliary elementary and cyclic profiles; those calculations can be expressed using rational masses and then scaled to integer counts. So the mirror is coherent, but its continuous input appears to re-encode a profile for an algorithm the paper already gives. Theorem 2 supplies no running-time, space, or certificate-size bound, so the proponent’s proposed tractability result would be new analysis, not a complexity guarantee inherited from the theorem.
There is also a gap between that analysis and the paper’s user-facing aim. Masses make the input easy to describe in percentages, but the proof still uses constructed auxiliary profiles and axiom applications. The paper establishes neither that mass-valued certificates are shorter nor that they make the arguments easier for people to follow. Without evidence of that benefit, the proposed work risks answering a bit-complexity question while leaving the intended explanation problem unchanged.
That case is limited. A large consultation with recurring rankings is a credible setting, and a proof over ballot proportions fits it naturally. The exact correspondence with finite profiles is expected in ChoCo’s high-multiplicity programme, so it cannot by itself rule the mirror out. I see no fundamental obstruction that defeats every plausible version; my negative case rests on uncertain research value and user-facing benefit, not on the mirror being ill-posed. A reader who treats a well-posed high-multiplicity algorithm question as sufficient could reasonably accept this anchor.
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.