| paper | d4-conf-aaai-2021-0939 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 1
Given candidates \(C\), the set \(T\) of all rankings of \(C\), a rational initial distribution \(\mu\) supported on \(\tau\) types, a target candidate \(p\), a round count \(\ell\), and per-turn budgets \(b_1,b_2\), does the first campaigner have a history-dependent strategy of transfers \(x_{t,t'}\geq 0\) that guarantees \(p\) is the unique Borda winner against every legal adversarial response? In each turn, transfers must satisfy \(\sum_{t'}x_{t,t'}\leq\mu_t\) for each type \(t\), update the society by outflow and inflow, and have total Kendall-swap cost at most the acting campaigner’s budget.
A continuous population with mass \(\mu_t\) on each ranking type \(t\in T\), where each unit of mass has one integral ballot. Campaigners move mass between types at Kendall-distance cost, use per-capita budgets each turn, and alternate moves for \(\ell\) rounds; the first campaigner seeks to guarantee a unique Borda win for \(p\).
The mirror covers the basic fixed-budget, multi-round adversarial Borda campaign model, with all \(m!\) rankings available as types. It leaves the enriched models and the general Presburger minimization theorem as a standalone result outside its scope.
The strongest mirror is the paper’s basic adversarial Borda campaign game. It has the right structure: the paper already describes voters as a society vector grouped by type, and campaign actions as moves between types. Replacing integer voter counts and moves with fractions of the population and mass transfers preserves what the game asks: whether one campaigner can guarantee a win against every legal response.
Take \(C\) to be the candidates and \(T\) the complete set of campaign-relevant voter types. In the basic model, a type is a ranking; for an exact swap-bribery mirror, let \(T\) contain all rankings of \(C\), so \(q=|T|=m!\). The initial society is a rational distribution \(\mu\) over \(T\), with support size \(\tau\). A transfer \(x_{t,t'}\geq 0\) means that fraction \(x_{t,t'}\) of the type-\(t\) cohort changes its complete ballot to \(t'\). Each voter still has one integral ranking; only the cohort mass can be fractional. The resulting mass of type \(t\) is its starting mass minus outflow plus inflow, and total outflow from \(t\) cannot exceed its current mass. The transfer costs \(x_{t,t'}\) times the Kendall distance between the two rankings. Give each side a rational per-capita budget \(b\) per turn: in an electorate of \(n\) voters, this corresponds to a total budget of \(bn\) adjacent swaps.
Call this Continuous Multi-Party Campaigning. Its instance is \(C,T,\mu\), a preferred candidate \(p\), a number of rounds \(\ell\), and the per-turn budgets. In each round, the first campaigner chooses a legal transfer, then the adversary chooses any legal transfer in response; repeat for \(\ell\) rounds. The question is whether the first campaigner has a strategy, depending on the observed history, that guarantees \(p\) is the unique Borda winner. Equivalently, at the end, for every \(c\ne p\),
\[
\sum_{t\in T}\mu^{\mathrm{final}}_t\bigl(m-\operatorname{rank}(p,t)\bigr)
>
\sum_{t\in T}\mu^{\mathrm{final}}_t\bigl(m-\operatorname{rank}(c,t)\bigr).
\]
The answer yes or no is the decision solution; in a yes-instance, a strategy can also be recovered. This is the paper’s basic worst-case model: its other bribers can collude, so they can be represented by one adversary with their combined budget.
A plausible regime is a large electorate facing a small number of campaigns, where ballots and campaign-relevant attributes form a relatively small number \(\tau\) of large, indistinguishable cohorts. National campaigns are a natural example: the meaningful quantity is the share of voters with each ballot, and campaign budgets scale with population. A finite election with counts \(n_t\) gives \(\mu_t=n_t/n\); the continuous game relaxes its integer transfers to real transfers. This is a distinct problem from the paper’s integer society vectors, though plainly a high-multiplicity extension of the same model. The authors are likely to recognize it: the type-flow actions, costs, round order, adversarial objective, and Borda condition all remain in place.
My anchor is Theorem 1 (the supplied rendering points to it as Theorem~\(\ref{theorem:pafpt}\), but omits its displayed numeral), proved in this paper. It states that, given a Presburger-arithmetic formula \(\varphi(\mathbf{x})\) and any convex objective \(f:\mathbb{R}^d\to\mathbb{R}\), minimizing \(f\) over the integer assignments satisfying \(\varphi\) is fixed-parameter tractable parameterized by \(\mathcal{L}(\varphi)+\alpha(\varphi)\), where \(\mathcal{L}\) is formula length and \(\alpha\) is the largest coefficient. The paper uses this result to compute campaigning strategies by encoding the game in Presburger arithmetic. It does not prove a named hardness result for campaigning; this algorithmic theorem is the relevant named anchor.
For the continuous mirror, I expect Class A: tractable. The state updates, budget constraints, and terminal Borda inequalities are all linear in rational data. The alternating choices over \(\ell\) rounds give a quantified linear-real-arithmetic question with a number of variables and constraints depending on \(m,q,\ell\). Quantifier elimination or repeated parametric linear programming therefore looks like a credible route to an \(f(m,q,\ell)\operatorname{poly}(L)\) algorithm, with \(L\) the input bit length. For rankings, \(q=m!\), so this is a parameterized bound in \(m,\ell\), not a claim of a running time polynomial in the number of possible rankings. This is an expectation for the mirror, not a result established by the paper’s integer Presburger theorem.
The main limitation is that the initial support \(\tau\) alone may not describe all actions: campaigns can move voters to rankings absent from the initial election. Keeping those actions makes the mirror faithful, but the direct formulation has \(q=m!\) types and does not immediately yield an algorithm parameterized by \(\tau\) alone. A useful next question is whether the transfer choices admit an implicit pricing method that avoids enumerating every ranking. Other natural questions are the integrality gap between this game and the finite-voter game, and how the answer changes when the terminal condition allows ties or asks for a specified winning margin. My case covers the paper’s basic fixed-budget, multi-round Borda model; it does not claim to continuize all of its extensions.
The named anchor does not have a direct continuous counterpart. The paper’s theorem is about minimizing over integer assignments satisfying a Presburger formula; it is not a complexity result about elections or population size. Replacing counts with masses changes the arithmetic problem: congruences and integer quantifiers give way to real variables and quantified linear inequalities. So a result about the continuous campaign game would be a new game-solving result, not a continuization of that theorem.
That objection does not defeat the stronger mirror, though. A society with many voters sharing rankings is a sensible high-multiplicity regime, and the paper already represents voters as types and actions as moves between them. With rational type masses and per-capita budgets, the continuous game preserves the campaigners, move costs, order of play, and terminal Borda objective. Keeping all rankings in the type space makes the model faithful even when campaigns create types absent initially. Scaling budgets with population avoids the degeneration that would occur with fixed absolute budgets. These are natural modelling choices the authors could recognize.
The repaired mirror is also a real computational question: does one campaigner have a strategy that guarantees a unique Borda win against every legal continuous response? The paper’s integer Presburger theorem does not answer it, and the possibility that real quantifier elimination or another method handles it efficiently is a research direction, not a reason to dismiss the question. The paper’s existing aggregation by voter types is evidence that this population regime makes sense; it cannot count against the mirror.
The strongest case against is therefore narrow: the proponent has attached a new continuous game to a general-purpose integer-arithmetic theorem, rather than given a continuous version of the theorem itself. But that defeats the anchor’s claimed connection, not the underlying campaign mirror. I can’t honestly argue that no worthwhile mirror survives: the continuous population version of multi-round campaigning remains a plausible, recognizable problem. The universal negative case is weak.
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.