Approximation Algorithms for Campaign Management

The strongest positive case is a two-anchor mirror, led by the paper’s hardness result.

The natural regime is a large population of individuals who share a small number of complete behavioural types. In the campaign setting, a type consists of a ranking, the cost curve for moving the preferred candidate \(p\), and any other parameters used by the rule. The mass \(\mu_t\) of a type is the fraction of the population with that description. Campaign cost is proportional to the mass reached. This is particularly plausible here because the paper itself says that a “voter” may represent a group reached by the same promotional activity, and explicitly motivates weighted voters through groups of voters or search terms with identical treatment.

My lead anchor is Proposition 4.3, proved in this paper. It states that, for every rational \(\alpha<1\) and every \(K\), there is no polynomial-time \(K\)-approximation algorithm for weighted Copeland\({}^\alpha\)-microbribery unless \(\mathrm{P}=\mathrm{NP}\). The proof uses only three candidates and reduces from Partition. Thus the result is not merely a consequence of having many candidates: its hardness comes from binary voter weights and the requirement that an indivisible collection of weighted voters be split exactly.

The corresponding continuous problem is:

Continuous Copeland\({}^\alpha\)-microbribery. An instance consists of a finite candidate set \(C\), a preferred candidate \(p\), a finite set \(T\) of complete preference-table types, rational masses \(\mu_t\) summing to \(1\), and type-dependent pair-flip costs. A type is a complete antisymmetric pairwise-preference table together with its flip-cost function, so two agents are of the same type only when they are indistinguishable for the whole problem. A solution chooses nonnegative masses \(x_{t,t'}\) transferred from each initial type \(t\) to final type \(t'\). The transfer cost is \(\gamma(t,t')x_{t,t'}\), where \(\gamma(t,t')\) is the minimum cost of changing table \(t\) into \(t'\). The final population induces pairwise masses
\[ N_{\mu'}(a,b)=\sum_{t\in T}\mu'_t\,\mathbf 1[t:a\succ b], \]
and hence normalized Copeland\({}^\alpha\) scores. The task is to find a minimum-cost mass transfer making \(p\) a Copeland\({}^\alpha\)-winner.

This is the same microbribery question—same candidates, same pairwise operations, same costs, same winner condition—with voter multiplicity made divisible. For the three-candidate regime used in Proposition 4.3, the continuous problem is exactly solvable in polynomial time for explicit \(T\): enumerate the finitely many possible pairwise outcomes and solve the resulting transportation LPs.

The paper’s Partition reduction makes the point sharply. Its weighted voters aggregate into three continuous types of masses \(1/2,1/4,1/4\):
\[ a\succ b\succ p,\qquad p\succ a\succ b,\qquad p\succ b\succ a. \]
Only the \(a\)-versus-\(b\) relation in the first type may be flipped, at zero cost. In the discrete reduction, one must choose a subset of the weighted \(a\succ b\succ p\) voters whose weights sum to exactly half. In the continuous mirror, one simply transfers mass \(1/4\) of that type to \(b\succ a\succ p\). Then every pairwise contest ties, all candidates receive Copeland score \(2\alpha\), and \(p\) wins at cost \(0\). The Partition hardness therefore dissolves for exactly the reason continuization is supposed to expose: the combinatorics lived in indivisible population blocks, not in the agenda or the voting rule.

I would expect this mirror to be Class A in the anchored three-candidate regime. For unbounded \(m\), the complexity of continuous Copeland microbribery remains a worthwhile further question: the winner condition has disjunctive pairwise structure, and the type universe can be exponentially large. It is also worth asking precisely which restrictions restore hardness—indivisible blocs, fixed campaign charges, or constraints forbidding a type’s mass from splitting.

My second anchor is Corollary 3.6, also proved here. It states that, for every scoring rule \(\vec\alpha\), there is an algorithm \(\mathcal B^w\) which, given a weighted instance of weighted \(\mathcal R_{\vec\alpha}\)-shift-bribery, outputs a successful shift-action of cost at most \(2\opt(I)\) in time polynomial in \(|I|\) and \(|\vec\alpha|\). This is a direct algorithmic result for the paper’s central campaign-management problem.

The continuous counterpart is:

Continuous scoring-rule shift campaign. An instance consists of candidates \(C\), a target \(p\), a scoring vector \(\vec\alpha\), ranking types \(t\in T\) with rational masses \(\mu_t\), and nondecreasing per-unit cost curves \(\pi_t(k)\). If \(p\) is in position \(r_t\) in type \(t\), let \(y_{t,k}\) be the mass of that type shifted upward by exactly \(k\) positions, for \(0\le k<r_t\). The constraints are
\[ \sum_{k=0}^{r_t-1}y_{t,k}=\mu_t,\qquad y_{t,k}\ge0. \]
The objective is
\[ \min \sum_{t\in T}\sum_k \pi_t(k)y_{t,k}, \]
subject to \(p\) maximizing the aggregate scoring-rule score after the shifts. A solution is the mass-allocation matrix \(y\), together with the induced post-campaign society.

This is not a softened campaign problem: \(p\) is still the same target, only upward shifts are allowed, the same scoring vector is used, and the same type-specific prices apply. The sole relaxation is that a type’s mass may be divided among different shift amounts, which is precisely the continuous-population interpretation.

For an explicit support \(T\), this problem is an LP with \(O(|T|m)\) variables and linear winner constraints, so I expect an exact polynomial-time algorithm. It is therefore a particularly clean Class A mirror. If the ranking types and costs are supplied implicitly over all \(m!\) rankings, the natural next question is a pricing or separation problem; that is a genuine continuation of the paper’s computational question rather than an unrelated fractional-election model. The discrete algorithm of Corollary 3.6 then gives a useful downward bridge: rational masses can be rounded to a finite electorate, with approximation or additive-error guarantees depending on the denominator and the number of types.

This case deliberately does not claim to mirror every result in the paper. It covers Proposition 4.3 and Corollary 3.6 emphatically; I would not stretch it to the unnumbered possible-winner claim about swap bribery, or claim that all maximin and Copeland variants automatically inherit the same LP structure.

The weakest point is the lead anchor. Proposition 4.3 concerns microbribery in the paper’s irrational-voter model, and its reduction uses zero-cost flips and pairwise tables that need not come from transitive rankings. A referee might regard that as a technical model rather than a realistic campaign. Also, if the real-world action is a fixed indivisible advertising bloc, fractional transfer would be inappropriate. The answer is that the paper itself studies microbribery, explicitly allows weighted groups, and the continuous question preserves its complete type descriptions and operations; it changes only the granularity of the population. The scoring-rule shift mirror is consequently the more robust positive case, while the Proposition 4.3 mirror is valuable precisely because it shows a named hardness result whose population-integrality component disappears under continuization.