| paper | d4-conf-ecai-2016-0035 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Polynomial-time solvable in both UNI and NON for every fixed \(\ell\ge3\), in \(O(\tau mL^2)+(\tau m+(m+\tau)L)^{O(1)}\) bit operations, with an absolute exponent independent of \(\ell\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given candidates [0m\(C\), supported rankings [0m\(S\) with rational masses [0m\(\mu_t>0\) summing to [0m\(1\), a target [0m\(p\), a rational mass budget [0m\(\beta\), and fixed [0m\(\ell\ge3\), is there a transfer map [0m\(x_{t,r}\ge0\) from each source type [0m\(t\in S\) to rankings [0m\(r\ne t\) with [0m\(d_{\mathrm{KT}}(t,r)\le\ell\), such that [0m\(\sum_r x_{t,r}\le\mu_t\) for every [0m\(t\), total transferred mass is at most [0m\(\beta\), and the resulting society makes [0m\(p\) a Condorcet winner (UNI) or weak Condorcet winner (NON)?
Types are complete rankings with rational masses [0m\(\mu_t\). Decision variables [0m\(x_{t,r}\) transfer mass to KT-close rankings, with at most [0m\(\mu_t\) leaving each type and at most [0m\(\beta\) transferred overall; the objective is to make [0m\(p\) a Condorcet winner.
The fixed-[0m\(\ell\) mass instances appear already solvable by ChoCo's move-cost LP framework, so these anchors may add little technical novelty; the proponent does not address that specific prior result.
fatal: False
The mirror covers the constructive KT-distance Condorcet results of Theorem 4 at fixed [0m\(\ell\ge3\), including both winner conventions. It leaves Theorem 2's Borda results, destructive bribery, Copeland, Maximin, and all Hamming-distance results outside this anchor.
The strongest mirror is the paper’s constructive KT-distance bribery problem. It keeps each voter’s complete ranking, the Kendall–Tau restriction on how far that ranking may change, the target candidate, and the limit on how many voters may be bribed. It changes the electorate from counts of voters to masses of voters. That is a high-multiplicity relaxation of their problem, rather than a continuization of the outcome or of time.
A plausible regime is a very large membership vote or public consultation over a fixed slate, where many people use the same ranking and a campaign can reach a large bloc. For example, \(n\) could be in the hundreds of thousands while the number \(\tau\) of distinct rankings is in the hundreds or thousands. A type is a complete ranking; people of one type have the same available recastings and the same unit cost. The mass \(\mu_t\) of type \(t\) is its fraction of the population. This scenario requires repeated preference blocs, so it is not a claim about every election.
Here is the shared model for the two anchors below. For fixed \(\ell\), an instance gives candidates \(C\), a support \(S\) of \(\tau\) rankings, rational masses \(\mu_t>0\) summing to \(1\), a target \(p\), and a rational budget \(\beta\). For each \(t\in S\) and each different ranking \(r\) with \(d_{\mathrm{KT}}(t,r)\le\ell\), let \(x_{t,r}\) be the mass changed from \(t\) to \(r\). Require
\[
\sum_{r:\,d_{\mathrm{KT}}(t,r)\le\ell,\ r\ne t}x_{t,r}\le\mu_t
\quad(t\in S),
\qquad
\sum_{t\in S}\sum_{r:\,d_{\mathrm{KT}}(t,r)\le\ell,\ r\ne t}x_{t,r}\le\beta.
\]
The resulting society \(\nu\) keeps the unaltered mass of each type and adds and subtracts the transfers. A solution is such a transfer map for which \(p\) wins under the specified voting rule. In the constructive variants, \(p\) starts out not winning. The objective is to make \(p\) win using at most \(\beta\) of the population; equivalently, ask whether the minimum required mass is at most \(\beta\). The model preserves the paper’s distance restriction and voting rule while making the bribed population share the budgeted quantity.
My lead anchor is Theorem 4, an authors’ result. It states that \(C\)-KT\((\ell)\)-Condorcet-UNI and \(C\)-KT\((\ell)\)-Condorcet-NON are NP-hard for every \(\ell\ge3\). The paper gives X3C reductions for radius \(3\), X4C reductions for radius \(4\), and obtains the cases \(\ell\ge5\) from a reduction cited as Theorem 3.2 of [26]. The corresponding mirror is Fractional KT-Condorcet Bribery at radius \(\ell\): given the instance above and the initial-state condition, is there a feasible transfer map making \(p\) a Condorcet winner (UNI), or a weak Condorcet winner (NON), under the paper’s conventions? A prover receives the rankings, masses, budget, and target and must return the transfers or certify that none exist. I expect this fixed-radius mirror to be in Class A. Each final pairwise margin is linear in the transfers, so the winning requirements are linear inequalities. For UNI, strict inequalities can be tested by maximizing a common margin and checking whether it is positive.
The second anchor is Theorem 2, also a result of this paper. It states that \(C\)-KT\((\ell)\)-Borda-UNI and \(C\)-KT\((\ell)\)-Borda-NON are NP-hard for every \(\ell\ge3\). The supplied proof gives the radius-\(3\) X3C reduction; it omits some proof details for space. Its mirror is Fractional KT-Borda Bribery at radius \(\ell\), with the same instance and transfer constraints, asking whether the final Borda scores make \(p\) a winner. Here too, I expect the fixed-radius version to be in Class A: final Borda scores are linear in the transfers, and the winner conditions are score inequalities, strict in UNI and non-strict in NON.
For either mirror, a fixed KT radius gives only polynomially many reachable rankings per source type: every ranking within distance \(\ell\) can be reached by at most \(\ell\) adjacent swaps. Thus the transfer variables number at most \(\tau\sum_{j=1}^{\ell}(m-1)^j\), polynomial in \(m\) and \(\tau\) when \(\ell\) is fixed. The mass constraints and the Borda or Condorcet conditions form a rational linear program. The discrete reductions’ set-cover choices select whole votes; this relaxation permits fractions of each type’s mass to take different allowed rankings. That is precisely where their integrality-based obstruction may disappear.
These are continuous questions the authors should recognize: the ranking domain, local change restriction, target, and decision objective all remain theirs. The continuous quantity is the electorate and its bribery budget. The finite version embeds by restricting transfers to multiples of \(1/n\) and setting \(\beta=R/n\). The unrestricted mass version is a genuine relaxation, so I am not claiming it preserves every finite instance’s yes/no answer. Existing high-multiplicity election work would support the regime’s plausibility rather than collide with this mirror.
I would keep the claim narrow. These mirrors cover the paper’s constructive Kendall–Tau Borda and Condorcet results at fixed small radii. They do not cover its destructive results, Copeland or Maximin, or the Hamming-distance results. If \(\ell\) is part of the input rather than fixed, the reachable-ranking set may be exponential; a pricing algorithm or a hardness result would then be needed. Further questions are whether the variable-radius mirrors remain tractable, and what rounding or additive guarantees connect their fractional solutions back to finite elections.
The weakest point is that the regime needs many voters to share exact rankings, with the same unit-cost bribery options. That is credible for repeated preference blocs over a fixed slate, but not for every ranked election. And even in that regime, the relaxation can exploit fractional masses where a finite election must move whole voters. Those are real limits on how far the positive case goes; they do not, in my view, undermine the continuous-population question itself.
The strongest negative case is about incremental research value. Both proposed fixed-radius mirrors appear to be direct instances of a continuous bribery framework already developed in ChoCo’s 2026 case study.
For each initial ranking \(\sigma_i\), assign move cost \(0\) to leaving it unchanged, cost \(1\) to any different ranking within KT distance \(\ell\), and infinite cost to every other ranking. Then minimizing total move cost is exactly minimizing the mass bribed. For fixed \(\ell\), the allowed destinations per type are polynomially enumerable. The case study’s polynomial-time theorem covers Borda and Condorcet winner conditions when those destinations can be enumerated, and handles strict winners by maximizing a common slack. So Theorems 2 and 4’s proposed continuous mirrors do not seem to pose new fixed-radius algorithmic questions; their answers fit existing machinery directly. ([ChoCo’s move-cost model and theorem](https://arxiv.org/html/2608.25444v1), [case-study preprint](https://arxiv.org/abs/2608.25444))
That is a real reason to ask a prover for a sharper task: for example, make \(\ell\) part of the input and study the complexity border, where the set of reachable rankings may be exponential. The existing theorem is polynomial in the number of reachable destinations, so it does not settle that version.
But this does not support the universal claim that there is no worthwhile mirror. Under the programme’s own prior-art rule, an existing answer to a well-posed mirror changes what remains to prove; it does not make the question invalid. Nor can I honestly dismiss the population model: repeated ranking blocs, a mass budget, and local allowed recastings preserve the paper’s problem in a plausible high-multiplicity regime. The negative case is therefore limited to low novelty for these particular fixed-radius questions. I cannot defeat either anchor as a worthwhile continuous question, and the stronger variable-radius version remains open.
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.