Approximation Algorithms for Campaign Management (d4-conf-wine-2010-0014)

Given \(m=3\) candidates, a target \(p\), an explicit finite set \(T\) of complete antisymmetric preference-table and cost types, rational masses \(\mu_t\) with \(\sum_t\mu_t=1\), and pair-flip costs, choose nonnegative transfers \(x_{t,u}\) from initial type \(t\) to final type \(u\) minimizing \(\sum_{t,u}\gamma(t,u)x_{t,u}\), subject to mass conservation and \(p\) being a \(\mathrm{Copeland}^{\alpha}\)-winner of the final profile \(N_{\mu'}(a,b)=\sum_t\mu'_t\mathbf{1}[t:a\succ b]\).

Let \(C=\{p,a,b\}\), \(m=3\), and fix rational \(\alpha\in[0,1)\). A preference table assigns exactly one orientation to each unordered pair of distinct candidates; cycles are allowed. Let \(U\) contain all such tables.
A society is given by its support \(T\): the list of \(\tau\) types with positive binary-rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible types. Each type contains an initial table \(q_t\) and symmetric pair-flip costs \(\delta_t(c,d)\in\mathbb Z_{\ge0}\cup\{+\infty\}\), with \(\delta_t(c,c)=0\); finite costs are encoded in binary.
Mass may split among final tables, retaining its original cost type. Choose \(x_{t,u}\in\mathbb R_{\ge0}\) with \(\sum_{u\in U}x_{t,u}=\mu_t\). Define \(\gamma(t,u)=\sum_{\{c,d\}:q_t(c,d)\ne u(c,d)}\delta_t(c,d)\), counting each unordered pair once; require \(x_{t,u}=0\) whenever \(\gamma(t,u)=+\infty\).
The final pairwise support is \(N_x(c,d)=\sum_{t\in T,u\in U}x_{t,u}\mathbf1[u:c\succ d]\). Apply standard \(\mathrm{Copeland}^{\alpha}\) using these supports, with exact pairwise ties and the nonunique-winner convention. A transfer is successful when \(p\) is among the maximum-score candidates; its cost is \(\sum_{t,u:\gamma(t,u)<+\infty}\gamma(t,u)x_{t,u}\).
Let \(\mathrm{OPT}\) be the infimum of successful transfer costs. Infeasibility must be reported; on feasible instances a multiplicative approximation returns a successful transfer of cost at most \(K\mathrm{OPT}\), including when \(\mathrm{OPT}=0\). State running times in \(m,\tau,L\), where \(L\) is the total input bit length.

For each fixed rational \(\alpha\in[0,1)\), does this continuous problem admit a polynomial-time \(K\)-approximation for some finite constant \(K\ge1\), or is it inapproximable within every such \(K\) unless \(\mathrm P=\mathrm{NP}\)?

Discrete weighted microbribery admits no polynomial-time approximation within any finite constant factor unless \(\mathrm P=\mathrm{NP}\), even with three candidates and zero or forbidden flip costs ([source](https://arxiv.org/pdf/1004.0334)). No result settling this precise divisible-mass version was located in the literature searches.

Conclusion

For every fixed rational \(\alpha\in[0,1)\), no finite-factor multiplicative approximation exists under the stated definition, regardless of running time. A feasible instance can have \(\mathrm{OPT}=0\) without admitting any successful transfer of cost zero.

This settles the question as written. To address the intended computational issue as well, I prove that feasibility, the exact infimum, and attainment are polynomial-time computable for \(\mspace{1mu}m=3\). Moreover, on instances where a zero infimum is attained, a polynomial-time \(K\)-approximation exists for every fixed rational \(K>1\).

1. A zero infimum that is not attained

Fix any \(\alpha\in[0,1)\). Take two types, each of mass \(1/2\), with initial tables given by the linear orders

\[ q_1:\ p\succ a\succ b, \qquad q_2:\ a\succ b\succ p. \]

For both types, set every distinct-pair flip cost to \(1\). Thus all costs are finite and strictly positive.

Initially,

\[ N(p,a)=\frac12,\qquad N(p,b)=\frac12,\qquad N(a,b)=1. \]

Consequently, the Copeland scores are

\[ s(p)=2\alpha,\qquad s(a)=1+\alpha,\qquad s(b)=\alpha. \]

Because \(1+\alpha>2\alpha\) for \(\alpha<1\), the initial society is unsuccessful.

Let \(u\) be the cyclic table with orientations \(p\succ a\), \(a\succ b\), and \(b\succ p\). It differs from \(q_2\) only on \(\{p,a\}\), so \(\gamma(2,u)=1\).

For any \(0<\varepsilon\le 1/2\), choose

\[ x_{1,q_1}=\frac12,\qquad x_{2,q_2}=\frac12-\varepsilon,\qquad x_{2,u}=\varepsilon, \]

with every other entry zero. This is a permitted transfer of cost \(\varepsilon\), and its supports satisfy

\[ N_x(p,a)=\frac12+\varepsilon,\qquad N_x(p,b)=\frac12,\qquad N_x(a,b)=1. \]

Its scores therefore are

\[ s_x(p)=1+\alpha,\qquad s_x(a)=1,\qquad s_x(b)=\alpha. \]

Hence \(p\) is a nonunique winner, including when \(\alpha=0\).

Successful costs approach zero, and all costs are nonnegative. Thus \(\mathrm{OPT}=0\).

However, every table different from its type’s initial table has cost at least \(1\). A zero-cost transfer must therefore leave every type entirely at its initial table. We already proved that this society is unsuccessful. Thus no successful zero-cost transfer exists.

For any finite \(K\), the required bound would be \(\operatorname{cost}(x)\le K\mathrm{OPT}=0\), which is impossible. Reporting infeasibility would also be incorrect, since the instance is feasible.

2. The divisible problem nevertheless has a polynomial-time infimum algorithm

The preceding obstruction concerns attainment. The underlying continuous optimization can be solved by a finite collection of rational linear programs.

I give the construction for general \(m\) to make the parameter dependence explicit. Put \(d=\binom m2\). Since cycles are allowed, there are \(2^d\) tables.

For each type, define its allowed destinations by

\[ A_t=\{u\in U:\gamma(t,u)<+\infty\}. \]

Use variables \(x_{t,u}\) only for \(u\in A_t\), and let \(P\) be the polytope specified by

\[ x_{t,u}\ge0,\qquad \sum_{u\in A_t}x_{t,u}=\mu_t. \]

Each initial table belongs to \(A_t\), so \(P\) is nonempty. It is closed and bounded because \(0\le x_{t,u}\le\mu_t\).

Write the cost as the linear function

\[ c(x)=\sum_t\sum_{u\in A_t}\gamma(t,u)x_{t,u}. \]

Fix an ordering of each unordered candidate pair \(e=\{c,d\}\), and define its margin by

\[ M_e(x)=N_x(c,d)-N_x(d,c). \]

These margins are linear functions of \(x\).

Outcome patterns and strict feasibility

An outcome pattern is a vector \(\sigma\in\{-1,0,1\}^d\), prescribing a negative margin, a tie, or a positive margin for each pair. Its Copeland scores depend only on \(\sigma\) and the fixed \(\alpha\). Enumerate all patterns and retain those in which \(p\) has maximum score.

For a retained pattern, its actual realization set is

\[ S_\sigma= \{x\in P: M_e(x)=0\text{ if }\sigma_e=0,\ \sigma_eM_e(x)>0\text{ otherwise}\}. \]

To decide whether \(S_\sigma\) is nonempty, maximize a common slack \(h\), subject to

\[ x\in P,\qquad 0\le h\le1, \]

\[ M_e(x)=0\quad(\sigma_e=0),\qquad \sigma_eM_e(x)\ge h\quad(\sigma_e\ne0). \]

The pattern is realizable exactly when this LP is feasible and its optimum is positive.

Indeed, positive slack realizes the prescribed strict inequalities. Conversely, any realization has a positive minimum among its finitely many strict margins, giving a feasible positive slack. If the pattern has no strict comparisons, any feasible realization allows \(h=1\).

This decides successful-transfer feasibility and produces a rational witness \(z_\sigma\in S_\sigma\) for every realizable winning pattern.

Computing the infimum without assuming attainment

For a realizable pattern, replace strict inequalities by weak ones:

\[ Q_\sigma= \{x\in P: M_e(x)=0\text{ if }\sigma_e=0,\ \sigma_eM_e(x)\ge0\text{ otherwise}\}. \]

Because \(Q_\sigma\) is nonempty and compact, the rational LP

\[ v_\sigma=\min_{x\in Q_\sigma}c(x) \]

has a minimizer \(x_\sigma^0\).

I claim that \(v_\sigma=\inf_{x\in S_\sigma}c(x)\). The inclusion \(S_\sigma\subseteq Q_\sigma\) gives one inequality. For the other, use the strict witness \(z_\sigma\). For every \(0<\lambda\le1\), set

\[ x_\lambda=(1-\lambda)x_\sigma^0+\lambda z_\sigma. \]

Convexity preserves membership in \(P\) and every required equality. For each strict comparison,

\[ \sigma_eM_e(x_\lambda) =(1-\lambda)\sigma_eM_e(x_\sigma^0) +\lambda\sigma_eM_e(z_\sigma)>0. \]

Thus \(x_\lambda\in S_\sigma\), and linearity gives \(c(x_\lambda)\to v_\sigma\) as \(\lambda\to0\). This proves the claim.

The successful-transfer set is the finite union of the realizable winning sets \(S_\sigma\). Therefore, on feasible instances,

\[ \mathrm{OPT}=\min_\sigma v_\sigma. \]

Testing attainment

Let \(v=\mathrm{OPT}\). For each winning pattern, repeat the common-slack feasibility test with the additional equality \(c(x)=v\).

A positive-slack solution is exactly a successful transfer of cost \(v\). Consequently, these LPs decide attainment and produce an optimal transfer whenever one exists. In particular, they distinguish an attained zero optimum from the obstruction in Section 1.

Running time

There are \(3^d\) outcome patterns, at most \(\tau2^d\) mass variables, and a constant number of LPs per pattern. Their rational coefficients have encoding lengths polynomial in \(m\) and \(L\): each finite \(\gamma(t,u)\) is a sum of at most \(d\) input costs.

The standard polynomial-time theorem for rational linear programming applies because these LPs are explicitly represented rational systems, and every optimization LP is bounded. It supplies exact values and rational witnesses of polynomial encoding length.

The resulting running time is

\[ 3^{\binom m2}\operatorname{poly} \bigl(\tau2^{\binom m2},m,L\bigr) = 2^{O(m^2)}\operatorname{poly}(\tau,L). \]

For the requested \(m=3\), there are \(27\) patterns and at most \(8\tau\) mass variables, so the running time is \(\operatorname{poly}(\tau,L)\). The output explicitly specifies the transfer variables required in the question.

3. Polynomial approximation whenever the zero-infimum obstruction is absent

Fix a rational \(K>1\). Consider the promise that every feasible instance with \(\mathrm{OPT}=0\) admits a successful zero-cost transfer.

The preceding algorithm reports infeasibility correctly. If \(v=\mathrm{OPT}=0\), the attainment test returns the promised successful zero-cost transfer.

Suppose instead that \(v>0\). Choose a realizable winning pattern attaining the minimum \(v_\sigma=v\), together with its weak minimizer \(x^0\) and strict witness \(z\).

If \(c(z)=v\), return \(z\). Otherwise \(c(z)>v\); define

\[ \lambda=\min\left\{1,\frac{(K-1)v}{c(z)-v}\right\}, \qquad x=(1-\lambda)x^0+\lambda z. \]

Here \(0<\lambda\le1\), so the argument from Section 2 proves that \(x\) is successful. Its cost satisfies

\[ c(x)=v+\lambda(c(z)-v)\le Kv. \]

All quantities are rational and have polynomial encoding length. Thus, for \(m=3\), this gives a polynomial-time \(K\)-approximation on the promised class, for every fixed rational \(K>1\). In particular, \(K=2\) suffices.

4. Relation to the discrete hardness result

The cited discrete proof reduces from Partition: only an exact selection of whole voter weights can create the required pairwise tie. [Elkind–Faliszewski, Proposition 4.3](https://arxiv.org/pdf/1004.0334).

That selection obstruction disappears with divisible mass: taking half of every adjustable voter’s mass supplies exactly half the total adjustable weight. The LP construction above proves tractability of feasibility and the infimum for three candidates.

Accordingly, the stated approximation requirement is unconditionally impossible, while its natural version with attained zero infima admits polynomial-time constant-factor approximation.

⟨structured verdict parsed — rendered above⟩

The prover’s argument is correct. It establishes an unconditional obstruction to the required approximation guarantee and separately proves polynomial-time computability of feasibility, the infimum, and attainment for \(m=3\). No mathematical gaps or false steps were found.

The appropriate complexity label is “other”: the original approximation requirement cannot be satisfied at all on some feasible inputs. This is not a computational hardness reduction, although it implies the requested conditional nonexistence statement.

1. Scope and quantifiers

The counterexample applies to every fixed rational \(\alpha\in[0,1)\) and every finite \(K\ge1\).

It uses exactly three candidates, two positive binary-rational masses summing to one, and symmetric integer flip costs. Its cyclic destination table is permitted because the task explicitly allows cycles.

The obstruction follows from the task’s explicit use of an infimum and its requirement of a successful transfer costing at most \(K\mathrm{OPT}\), including when \(\mathrm{OPT}=0\). It therefore addresses the stated problem, rather than exploiting an unstated or unintended convention.

2. Counterexample verification

• Initial supports. From the two initial orders and equal masses, the reported supports are correct:

\(N(p,a)=N(p,b)=1/2\) and \(N(a,b)=1\).

• Initial scores. Candidate \(p\) ties both opponents; \(a\) ties \(p\) and defeats \(b\); \(b\) ties \(p\) and loses to \(a\). Thus the scores are respectively \(2\alpha\), \(1+\alpha\), and \(\alpha\). Since \(1+\alpha-2\alpha=1-\alpha>0\), \(p\) is unsuccessful throughout the stated parameter range.

• Destination cost. The cyclic table \(u\) agrees with \(q_2\) on \(\{a,b\}\) and \(\{p,b\}\), and differs only on \(\{p,a\}\). Consequently, \(\gamma(2,u)=1\).

• Transfer feasibility. For \(0<\varepsilon\le1/2\), every allocated mass is nonnegative and each type retains its total mass. All destinations are allowed.

• Final supports and scores. Only \(N(p,a)\) changes, increasing by \(\varepsilon\). Thus \(p\) defeats \(a\), ties \(b\), and scores \(1+\alpha\). Candidate \(a\) scores \(1\), and \(b\) scores \(\alpha\). Candidate \(p\) is therefore a winner, including at \(\alpha=0\), where the nonunique-winner convention is essential.

• Infimum. The successful transfer costs exactly \(\varepsilon\). Arbitrarily small positive choices of \(\varepsilon\), together with nonnegative costs, establish \(\mathrm{OPT}=0\).

• Nonattainment. Every destination other than a type’s initial table has cost at least one. Since every contribution to total cost is nonnegative, a zero-cost transfer assigns no positive mass to any such destination. It therefore reproduces the unsuccessful initial society.

• Approximation impossibility. Every finite multiplicative factor requires cost at most \(K\mathrm{OPT}=0\) on this feasible instance. No successful transfer satisfies that bound. Reporting infeasibility would also violate the specification.

This central argument is complete.

3. Linear-programming construction

• Allowed destinations and compactness. Each initial table has zero cost and is allowed. Hence \(P\) is nonempty. Its nonnegativity and mass-conservation constraints imply \(0\le x_{t,u}\le\mu_t\), so it is compact.

• Outcome enumeration. Every transfer determines exactly one sign pattern of pairwise margins. Copeland scores depend only on that pattern and \(\alpha\). Enumerating winning patterns therefore covers exactly the successful transfers.

• Strict-feasibility test. Positive common slack implies all required strict signs. Conversely, finitely many positive strict margins have a positive minimum. The bound \(h\le1\) is harmless because normalized margins lie in \([-1,1]\). The all-tie pattern is correctly treated separately.

• Infimum over a pattern. Weakening strict inequalities gives \(S_\sigma\subseteq Q_\sigma\). For a realizable pattern, interpolation between a weak minimizer and a strict witness preserves mass constraints and tie equalities, and makes every prescribed strict margin positive. Its cost converges to the weak minimum. Both inequalities needed for equality of infima are established.

• Global infimum. There are finitely many realizable winning patterns. Taking the minimum of their infima is therefore valid, even when no successful transfer attains that value.

• Attainment test. Adding \(c(x)=v\) to each winning-pattern slack LP tests precisely whether a successful transfer of cost \(v\) exists. Unrealizable patterns cannot generate false positives.

• LP theorem hypotheses. The systems have explicit rational coefficients. All nonempty optimization regions are bounded, and infeasible systems can be detected. The invoked polynomial-time rational LP result supplies exact optimal values and rational witnesses of polynomial encoding length under these hypotheses.

• Running time. The counts \(3^{\binom m2}\) patterns and at most \(\tau2^{\binom m2}\) mass variables are correct. Computing destination costs requires sums of at most \(\binom m2\) encoded costs, preserving polynomial coefficient lengths. The stated bound

\(2^{O(m^2)}\operatorname{poly}(\tau,L)\)
follows. At \(m=3\), this is polynomial in \(\tau,L\).

4. Promised approximation guarantee

The additional promise is stated explicitly and is not substituted for the original problem.

For \(v=0\), the attainment test returns a successful zero-cost transfer under that promise. For \(v>0\), the chosen strict witness has cost at least \(v\). Equality permits immediate return; otherwise the denominator in the formula for \(\lambda\) is positive.

The specified \(\lambda\) satisfies \(0<\lambda\le1\), ensuring success by the earlier interpolation argument. Its cost calculation gives \(c(x)\le Kv\). For fixed rational \(K>1\), the rational arithmetic preserves polynomial output length.

This establishes the claimed approximation result on the promised class. It makes no unsupported claim for \(K=1\).

5. Discrete comparison and final adjudication

The description of the discrete reduction is accurate: Proposition 4.3 uses Partition, permits only the relevant zero-cost flips, and requires a pairwise tie produced by selecting whole voter weights. Dividing each adjustable mass equally removes that selection obstruction in the cited construction. [Elkind–Faliszewski, Proposition 4.3](https://arxiv.org/pdf/1004.0334)

The prover distinguishes three valid conclusions: unconditional impossibility of the original approximation guarantee, polynomial-time computation of the auxiliary optimization quantities, and polynomial-time approximation under the stated promise.

Required repair or clarification: none.

⟨structured verdict parsed — rendered above⟩