d4-conf-ecai-2020-0253 (d4-conf-ecai-2020-0253)

Given a candidate set \(C\), a supplied partition of \(C\) into three blocks, supported complete rankings whose restrictions to each block are single-peaked, registered masses \(\mu_t\), a target \(p\), a budget \(b\), and an add or delete mode (with available masses \(\nu_t\) in add mode), does there exist an action vector \(x\) with \(0\le x_t\le\nu_t\) for adding or \(0\le x_t\le\mu_t\) for deleting, and \(\sum_t x_t\le b\), such that the resulting society makes \(p\) beat every \(c\ne p\)? The resulting mass is \(\rho_t=\mu_t+x_t\) in add mode and \(\rho_t=\mu_t-x_t\) in delete mode; require \(\sum_t\rho_t(\mathbf 1[p\succ_t c]-\mathbf 1[c\succ_t p])>0\) for each opponent.

Let \(C\) have \(m\) candidates, with target \(p\in C\) and a supplied partition \((C_1,C_2,C_3)\) into nonempty blocks. Types are strict complete rankings. For each block, there must exist one common axis on which every supported ranking restricted to that block is single-peaked; axes need not be supplied. In add mode this promise covers both registered and available types.
A society is given by its support: the list of types with positive mass, each mass encoded as a binary rational. Let \(\tau\) be the number of distinct types in the union of the supplied supports, not the number of possible rankings, and \(L\) the total input bit length. Registered masses \(\mu_t\) and, in add mode, available masses \(\nu_t\) are nonnegative, with absent types assigned zero. Masses are finite measures and need not sum to one. The budget \(b\) is a positive binary rational.
An action may split type masses: choose \(x_t\in\mathbb R_{\geq0}\) with \(\sum_t x_t\leq b\). In add mode require \(x_t\leq\nu_t\) and set \(\rho_t=\mu_t+x_t\); in delete mode require \(x_t\leq\mu_t\) and set \(\rho_t=\mu_t-x_t\).
The action succeeds precisely when \(p\) is the strict Condorcet winner: for every \(c\in C\setminus\{p\}\), require \(\sum_t\rho_t(\mathbf1[p\succ_t c]-\mathbf1[c\succ_t p])>0\). Pairwise ties do not suffice.

For each of add mode and delete mode, is this decision problem in \(\mathrm P\), with running time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?

Discrete constructive control by adding votes and by deleting votes to obtain a unique Condorcet winner is \(\mathrm{NP}\)-hard even with a supplied partition into three single-peaked blocks ([Yang, 2020](https://arxiv.org/pdf/2002.03539)). No result settling this exact divisible-mass problem was located in the literature search.

Result

Both add mode and delete mode are in \(\mathrm P\), with running time polynomial in \(m,\tau,L\). The proof works for arbitrary strict rankings, so the three-block single-peakedness promise is unnecessary.

1. Pairwise margins and action constraints

Let \(T\) be the union of the supplied supports, with \(|T|=\tau\). Assign mass zero to absent types. For each \(c\in C\setminus\{p\}\) and \(t\in T\), define

\[ a_{ct}=\mathbf 1[p\succ_t c]-\mathbf 1[c\succ_t p]\in\{-1,1\}, \qquad d_c=\sum_{t\in T}\mu_ta_{ct}. \]

Thus \(d_c\) is the registered pairwise margin of \(p\) against \(c\).

Use the following mode-dependent constants:

• In add mode, let \(s=1\) and \(u_t=\nu_t\).
• In delete mode, let \(s=-1\) and \(u_t=\mu_t\).

In either mode, the admissible actions are precisely the vectors satisfying

\[ 0\leq x_t\leq u_t\quad(t\in T), \qquad \sum_{t\in T}x_t\leq b. \]

The resulting mass is \(\rho_t=\mu_t+s x_t\). Consequently, the resulting margin against \(c\) is

\[ M_c(x)=\sum_{t\in T}\rho_ta_{ct} =d_c+s\sum_{t\in T}a_{ct}x_t. \]

The required success condition is \(M_c(x)>0\) for every opponent \(c\).

2. A linear program handling strict victory

Introduce a real variable \(\varepsilon\) and solve the following rational linear program:

\[ \text{maximize }\varepsilon \]

subject to

\[ 0\leq x_t\leq u_t\quad(t\in T), \]

\[ \sum_{t\in T}x_t\leq b, \]

\[ 0\leq\varepsilon\leq1, \]

\[ d_c+s\sum_{t\in T}a_{ct}x_t\geq\varepsilon \quad(c\in C\setminus\{p\}). \]

If the program is infeasible, reject. Otherwise, let \(\varepsilon^\ast\) be its optimal value and accept exactly when \(\varepsilon^\ast>0\).

Correctness. Suppose first that a successful action \(x\) exists. The supplied partition has three nonempty blocks, so \(m\geq3\), and the opponent set is finite and nonempty. Every margin is positive; hence

\[ \delta=\min_{c\in C\setminus\{p\}}M_c(x)>0. \]

Taking \(\varepsilon=\min\{1,\delta\}\) gives a feasible point with positive objective value. Therefore \(\varepsilon^\ast>0\).

Conversely, a feasible point with \(\varepsilon>0\) satisfies all action constraints and, for every opponent,

\[ M_c(x)\geq\varepsilon>0. \]

Its action therefore makes \(p\) a strict Condorcet winner.

Finally, whenever the program is feasible, its feasible region is closed and bounded: every \(x_t\) lies in the finite interval \([0,u_t]\), and \(\varepsilon\in[0,1]\). It is therefore compact, so the objective attains its maximum. Thus accepting when \(\varepsilon^\ast>0\) is equivalent to the existence of a successful action, including when actions are allowed to have irrational coordinates.

3. Polynomial bit complexity

The program has \(\tau+1\) variables and \(2\tau+m+2\) scalar inequalities. The coefficients \(a_{ct}\) can be computed by reading the supplied rankings in time polynomial in \(m,\tau,L\).

The only newly computed rational constants are the margins \(d_c\). To bound their encoding lengths, let \(Q\) be the product of the denominators of all registered masses. Because their encodings are part of the input, \(Q\) has \(O(L)\) bits. Writing each registered mass over denominator \(Q\) produces integer numerators of \(O(L)\) bits. Summing at most \(\tau\) signed numerators produces a numerator with \(O(L+\log(\tau+1))\) bits. Thus every \(d_c\), and consequently the entire linear program, has encoding length polynomial in \(m,\tau,L\).

We apply the standard polynomial-time theorem for rational linear programming: given explicitly encoded rational constraints and objective coefficients, one can decide infeasibility and, when a finite optimum exists, compute its exact rational value in time polynomial in the encoding length. See [Khachiyan, *Polynomial algorithms in linear programming*](https://doi.org/10.1016/0041-5553(80)90061-0).

All hypotheses hold here: the program is explicit, its data are rational, and any feasible instance has an attained finite optimum. Comparing the exact rational value \(\varepsilon^\ast\) with zero therefore decides strict victory in polynomial time.

4. Relation to discrete control

The reduction uses divisibility exactly by allowing continuous variables \(x_t\). Discrete vote control imposes integrality constraints, yielding a different feasibility problem. The discrete hardness results in [Yang (2020)](https://arxiv.org/pdf/2002.03539) therefore do not contradict the polynomial-time algorithms proved here.

⟨structured verdict parsed — rendered above⟩

The output resolves both modes correctly. The linear program exactly captures divisible actions and strict Condorcet victory, and its encoding has polynomial length. No major or minor mathematical issues were found.

• Support and pairwise margins. Using only the supplied support union \(T\) is valid: types absent from both supports have zero mass and zero action capacity. Strict complete rankings ensure \(a_{ct}\in\{-1,1\}\). The definition \(d_c=\sum_t\mu_ta_{ct}\) is exactly the registered margin against \(c\).

• Action constraints and mode signs. In add mode, \(s=1\) and \(u_t=\nu_t\) reproduce the availability restrictions and resulting masses. In delete mode, \(s=-1\) and \(u_t=\mu_t\) reproduce the deletion restrictions and ensure nonnegative remaining masses. In both modes, the budget inequality is exact. Substitution gives the stated margin formula \(M_c(x)=d_c+s\sum_ta_{ct}x_t\), with the correct sign in each mode.

• Successful action implies positive LP objective. The partition into three nonempty blocks guarantees \(m\geq3\), so the minimum defining \(\delta\) is over a finite, nonempty set. For a successful action, every margin is positive, hence \(\delta>0\). Choosing \(\varepsilon=\min\{1,\delta\}\) satisfies every LP constraint and has positive objective. The cap at \(1\) therefore excludes no successful action.

• Positive LP objective implies success. Every feasible point with \(\varepsilon>0\) satisfies the original action constraints and \(M_c(x)\geq\varepsilon>0\) for every opponent. This establishes strict victory; pairwise ties cannot cause acceptance.

• Attainment and rejection cases. All capacities are finite. The LP feasible region is closed and bounded in finite-dimensional Euclidean space, hence compact when nonempty. The continuous objective therefore attains its maximum. Consequently, acceptance based on \(\varepsilon^\ast>0\) is justified. An infeasible LP cannot coexist with a successful action, by step 3. A feasible LP with optimum zero also cannot coexist with a successful action. The argument applies directly to real action coordinates, including irrational ones.

• LP dimensions. The stated count is correct: there are \(\tau+1\) variables and \(2\tau+m+2\) inequalities, consisting of \(2\tau\) action bounds, one budget constraint, two bounds on \(\varepsilon\), and \(m-1\) margin constraints.

• Rational encoding and arithmetic. The denominator product \(Q\) has bit length bounded by the sum of the input denominator lengths, hence \(O(L)\). Each rescaled numerator has \(O(L)\) bits, and summing at most \(\tau\) signed numerators adds at most \(O(\log(\tau+1))\) bits. These bounds also permit polynomial-time construction of the margins using integer arithmetic. The remaining numerical data are input rationals or constant-size coefficients. Thus the entire explicitly constructed LP has encoding length polynomial in \(m,\tau,L\).

• Polynomial-time LP theorem. The prover states the required theorem precisely: explicitly encoded rational LPs admit polynomial-time infeasibility detection and exact optimization when a finite optimum exists. This is the standard exact rational LP result; exact polynomial-time algorithms are also explicitly discussed in [Gleixner and Steffy, Section 1.3](https://arxiv.org/html/1912.12820#S1.SS3). Its hypotheses hold here: rational explicit data, polynomial encoding length, and an attained finite optimum whenever feasible. Exact comparison with zero handles arbitrarily small positive optima without a numerical-tolerance assumption.

• Promise, edge cases, and discrete control. The proof requires no single-peakedness property, so it applies to every promised instance without recovering axes. Zero capacities, empty supports, and zero total remaining mass introduce no exception: the same constraints and strict-margin criterion apply. No normalization is assumed. The distinction from discrete control is valid because the proposed LP imposes no integrality restriction.

No additional clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩