| paper | d4-conf-atal-2018-0209 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Polynomial-time solvable in \(O(\tau L^2+\tau mL)\) time. · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a finite alternative set \(S\), a current Reality \(R\in S\), an agenda order, and a society represented by \(\tau\) strict rankings \(t\) with positive rational masses \(\mu_t\) summing to \(1\), with no ties in the majority comparisons used, compute the winner returned by Algorithm 1: form \(S_R=\{s\in S\setminus\{R\}:\sum_{t:s\succ_t R}\mu_t>1/2\}\), run the agenda on \(S_R\) starting with \(R\), and return the final alternative if it wins every required comparison, or \(R\) otherwise.
A one-election society at a fixed Reality, with each type a strict ranking over \(S\) and its mass the share of voters holding that ranking. The agenda, majority comparisons, and elected state remain those of the paper; only voter counts are represented by rational type masses.
Theorem 1 certifies the agenda’s voting property but states no complexity bound; the polynomial analysis of the mass-based input is supplied by the mirror, as the proponent acknowledges.
fatal: False
The mirror covers Theorem 1’s conservative agenda result. It leaves the preference-domain properties, action plans and strategic game, and applications aside.
The strongest case is a narrow algorithmic mirror of Theorem 1, proved in this paper. The paper gives no named hardness or complexity-class result. Theorem 1’s full claim is that Algorithm 1 satisfies the Conservative Reality-aware Condorcet criterion, and that the modifications in Remark 7 yield algorithms satisfying the further criteria discussed in Section 4.1. In concrete terms, Algorithm 1 elects the Condorcet winner among the alternatives that beat Reality, if one exists; otherwise it elects Reality. The variants implement the corresponding permissive and preference-over-Reality criteria. I would use only the conservative result as an anchor.
Call the mirror Continuous Conservative Reality-Aware Agenda Winner. An instance consists of a finite set of alternatives \(S\), a current Reality \(R\in S\), an order \(\pi\) for the agenda, and a society given by \(\tau\) strict rankings \(t\) over \(S\), each with a positive binary-rational mass \(\mu_t\), where \(\sum_t\mu_t=1\). For this one-election problem, a type is the ranking supplied to the social choice function at the given Reality. Assume no pairwise comparison used by the agenda is tied at exactly half the mass; the paper does not specify how the algorithm handles tied votes.
For each \(s\ne R\), compute whether more than half the society ranks \(s\) above \(R\), and let \(S_R\) be the set of such alternatives. If \(S_R\) is empty, return \(R\). Otherwise, run the paper’s amendment agenda on \(S_R\), starting with \(R\) and using \(\pi\). Then check the agenda’s final alternative against every member of \(S_R\) it has not already faced. Return that alternative if it beats them all; otherwise return \(R\). The solution is the elected state \(w\in S\). There is no optimization objective: the decision variable is the winner selected by the rule.
A plausible regime is a large municipality choosing among a small slate of policy states, such as hospital locations or legislative drafts. Many residents can share a ranking of those states relative to the present policy, so the population may be large while \(\tau\) stays moderate. The input masses represent shares of residents, not fractional policy outcomes. That is a natural high-multiplicity version of the paper’s election: for an electorate with \(n_t\) voters of ranking \(t\), set \(\mu_t=n_t/n\), and every majority comparison has the same result. Conversely, any rational mass profile can be realized by a finite electorate after scaling its denominators.
The authors should recognize this as their problem: the alternatives, Reality, majority comparisons, agenda and elected state all remain as in their model. Only the electorate’s representation changes from voter counts to type masses. Theorem 1 gives the mirror its anchor-level correctness claim: it selects a viable Condorcet winner when one exists and retains Reality otherwise. For this input format, the procedure is tractable: pairwise mass totals and agenda steps can be computed with a number of rational operations polynomial in \(|S|\), \(\tau\), and the input bit length \(L\). That complexity bound follows directly from the algorithm; the paper does not state it as a complexity theorem.
I expect this mirror to be tractable. A further question is the complexity of choosing an agenda order to obtain a desired outcome. A richer repeated-election question would give each type rankings contingent on Reality and update the society’s preferences as Reality changes. Those are extensions: Theorem 1 anchors the single-election agenda, not the full action-plan problem.
The mirror covers Theorem 1’s conservative agenda result, not the paper’s preference-domain axioms, strategic game, or applications. Its weakest point is that the anchor proves an axiomatic property of an algorithm, not a complexity classification. The continuous version is also a direct weighted-majority computation, so its computational interest is mainly as a high-multiplicity formulation. There is a further interpretive edge: Remark 8 describes Reality as changing during the agenda, while the formal RASCF input supplies a ranking profile for a given Reality. The formulation above follows that single-election input; a version that re-evaluates preferences after each intermediate change would need its own model and correctness result.
The proponent’s sole anchor is Theorem 1, but it proves that Algorithm 1 satisfies a voting criterion; it does not establish a complexity result. The paper gives no theorem about the running time, hardness, or parameterized complexity of a computational problem. Its other formal results are also about axioms and preference domains. Since ChoCo’s target is the computational landscape, there is no such result here to continue.
The municipality scenario is credible, and the best version of the proposed mirror would represent each ranking type by its population share and compute the agenda winner from weighted pairwise votes. But that defines a sensible high-multiplicity election problem; it does not turn Theorem 1 into a complexity result. The claimed bound in \(|S|,\tau,L\) is a new analysis of that encoding, not a complexity claim made by the paper. A richer model with types specifying preferences at every possible Reality would better fit the action-plan discussion, but questions about reachability or strategic influence under that model would likewise be new questions, not mirrors of a result in this paper.
This is the strongest negative case for the paper as written. It is weaker as a universal claim: the high-multiplicity regime is plausible, and a well-chosen new computational question about action plans or influence might be worthwhile. I can’t honestly rule those out. They do not, however, rescue the proposed Theorem 1 mirror as a ChoCo complexity contribution.
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.