d4-conf-aaai-2010-0205

Answer: Polynomial-time solvable: the exact minimum bribery cost is computable in time polynomial in $m,\tau,L$. · discrete side: hardness · adjudication: proved

The anchor — hardness

Every anchor argued

The continuous mirror question

Given $C$, a societal order $L$, a target $p$, and a rational distribution $\mu$ over supported types $t=(P_t,w_t,q_t)$, where $P_t$ is an $L$-single-peaked ranking and $w_t,q_t$ are positive integer vote weights and bribe prices, choose transfers $x_{t,Q}\ge 0$ to $L$-single-peaked rankings $Q$, preserving $\sum_Q x_{t,Q}=\mu_t$. Minimize $\sum_t q_t\sum_{Q\ne P_t}x_{t,Q}$ subject, for each $c\ne p$, to $\sum_t w_t\sum_Q x_{t,Q}(\mathbf{1}[p\succ_Q c]-\mathbf{1}[c\succ_Q p])\ge 0$. What is the complexity of computing this minimum in $m$, $\tau$, and the input bit lengths?

The model it lives in

A high-multiplicity weighted election with a finite distribution over complete voter types $(P_t,w_t,q_t)$; fractional mass may change its ranking while keeping its weight and price, and the objective is minimum per-capita bribery cost subject to $p$ becoming a weak Condorcet winner.

What the mirror covers

The mirror covers the single-peaked weighted priced weak-Condorcet bribery entry of Theorem 6; it leaves the other bribery variants and the paper’s winner, control, and manipulation results unaddressed.

The case FOR (proponent)

The strongest positive case I see is narrow: a continuous version of the weighted-$\$$ weak-Condorcet bribery problem in Theorem 6, which the paper proves. The theorem’s full classification is that, for single-peaked electorates, weak-Condorcet weighted-$\$$ bribery, negative weighted bribery, and negative weighted-$\$$ bribery are NP-complete; the other five combinations of weighting, prices, and the negative-bribery restriction are in P. Here “negative” means a bribed voter may not rank the target first afterward unless they already ranked it first. I use the weighted-$\$$ hardness entry as my anchor: bribed voters have indivisible voting weights and individual prices, and the question is whether the target can be made a weak-Condorcet winner within the price budget.

A plausible high-multiplicity setting is a large membership organization voting on proposals along one policy axis. Suppose there are hundreds of thousands of members, but only dozens of recurring combinations of strict ranking, voting weight, and standardized outreach price. Members in the same combination are indistinguishable for this problem; the number of agents $N$ is much larger than the number of supported types $\tau$. A campaign changes the ballots of some members while keeping every resulting ranking single-peaked on the same axis. That makes the population distribution continuous; it does not make the alternatives or voters’ rankings continuous.

Here is the mirror I would hand to a prover. Call it Single-Peaked Weighted-$\$$ Weak-Condorcet Mass Bribery. The input is a candidate set $C$, a societal order $L$, a target $p$, and a supported distribution $\mu$ over types $t=(P_t,w_t,q_t)$, where $P_t$ is an $L$-single-peaked ranking, $w_t$ is a positive integer voting weight, $q_t$ is a positive integer bribe price, and the binary-rational masses sum to one. There is also a per-capita budget $b$. A unit of mass is a fraction of the population, and changing its ranking leaves its weight and price unchanged.

For each supported type $t$ and each $L$-single-peaked ranking $Q$, let $x_{t,Q}$ be the mass moved from $P_t$ to $Q$. The question is whether there are nonnegative transfers that preserve every source type’s mass, cost at most $b$, and make $p$ a weak Condorcet winner. Equivalently, minimize the total price of changed mass,
\[ \min \sum_t q_t\sum_{Q\ne P_t}x_{t,Q}, \]
subject to $\sum_Q x_{t,Q}=\mu_t$ for every $t$, and, for every $c\ne p$,
\[ \sum_t w_t\sum_Q x_{t,Q} \bigl(\mathbf{1}[p\succ_Q c]-\mathbf{1}[c\succ_Q p]\bigr)\ge 0. \]
A solution is the transfer distribution $x$; the budget version asks whether its minimum cost is at most $b$. For a discrete election with $N$ voters, the corresponding input has $\mu_t=n_t/N$ and a total price budget $K$ becomes $b=K/N$. The continuous model lets a fraction of a repeated type be bribed, while each member represented by that mass still has their full weight $w_t$.

I expect this problem to be tractable, in Class A terms. The winner constraints and budget are linear, so the formulation is an LP. Its potential obstacle is that there are exponentially many single-peaked destination rankings as $m$ grows. The algorithmic question is whether the LP’s dual pricing problem over those rankings can be solved in polynomial time in $m$, $\tau$, and the input bit lengths. Single-peaked structure gives reason to expect that it can. The discrete reduction’s partition choice over whole weighted, priced voters is exactly the kind of indivisibility that fractional mass may remove. That expectation is a research conjecture, not a result of this paper.

This mirror covers only the weighted-$\$$ weak-Condorcet bribery entry of Theorem 6. Further questions include whether the pricing oracle is polynomial, how the continuous optimum relates to the discrete optimum, and whether rounding yields an additive approximation for large finite electorates with moderate $\tau$.

The soft spot is that the paper’s hardness comes from a partition construction on indivisible voters, and such a construction may use many distinct weight-price combinations. If $\tau$ grows with $N$, the high-multiplicity regime offers less practical simplification; moreover, allowing fractional mass changes the unit of action that bribery normally treats as indivisible. The case rests on applications with genuinely repeated cohorts. In the membership scenario, identical rankings, weights, and prices are explicit parts of the model’s type, so fractional treatment of a cohort is a plausible population-level question rather than an averaging away of relevant differences.

The case AGAINST (opponent, writing after the proponent)

The strongest case against Theorem 6’s weighted-$\$$ weak-Condorcet anchor is that the discrete hardness is about choosing whole voters with different weights and prices. In a large organization with repeated voter types, bribing a fraction of a cohort is a reasonable population question, but it changes the indivisible selection problem that Theorem 6 classifies. In the most natural version of that story—ordinary members with one vote each—the weighted anchor disappears. Weighted votes fit more naturally in shareholder or proxy settings, where the people who cast the votes may be a small, individuated group.

That objection does not survive the better mirror. A large population can contain repeated cohorts with the same ranking, weight, and price; the cohort’s mass then captures exactly how much of that group can be persuaded. Weight and price are legitimate parts of the type. Fractional mass means targeting a fraction of many identical people, not part of one person. The paper’s axis and restriction on resulting ballots can also be preserved: for any societal order, a ranking with the target first can be single-peaked.

There is also already a close continuous result. A 2026 paper gives a polynomial-time algorithm for continuous Condorcet priced bribery. The weighted version can be expressed in that model: if type $i$ has population fraction $\mu_i$, vote weight $w_i$, and price $q_i$, let $W=\sum_i\mu_iw_i$, use transformed mass $\hat\mu_i=\mu_iw_i/W$, and charge $\hat q_i=q_iW/w_i$ per unit. Pairwise margins scale by $W$, while the bribery cost is preserved. The unrestricted continuous problem can send bribed mass to a target-first ranking, which is a legal single-peaked destination here. So this anchor appears to have a known continuous algorithmic answer already. ([Koutecký et al., *Continuous Computational Social Choice: A Case Study in Bribery*](https://arxiv.org/abs/2608.25444))

That makes the anchor weak as a source of new algorithmic work, but under ChoCo’s stated rule, an outside answer to a well-posed mirror does not make the mirror unworthy. I cannot honestly defeat this anchor: repeated weighted and priced voter types are a sensible high-multiplicity regime, and the mass version asks a coherent computational question. The negative case is therefore weak; the existing result tells the prover what to cite or adapt, rather than establishing that there is no worthwhile mirror.

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.

paper	d4-conf-aaai-2010-0205
authors	—
venue	?
filed under	unclassified
judged by	gpt-6-luna / xhigh (triple__luna__xhigh__c6r1)
judge confidence	high
authors would recognise it	yes