d4-conf-ecai-2016-0354 (d4-conf-ecai-2016-0354)

For a scoring generator \(f\), given \(m\) candidates, a target \(p\), a support of \(\tau\) complete rankings with positive rational masses \(\mu_t\) summing to \(1\), and a rational deletion budget \(\kappa\), determine whether there are deletion masses \(d_t\) with \(0 \le d_t \le \mu_t\) and \(\sum_t d_t \le \kappa\) such that \(p\) is a winner under the residual scores \(\sum_t (\mu_t-d_t)s_f(t,c)\). Classify the problem’s complexity in \(m\), \(\tau\), and the input bit length.

Fix a pure, polynomial-time uniform scoring generator \(f\): \(f(m)=(\alpha^m_1,\ldots,\alpha^m_m)\) has nonincreasing rational coefficients, possibly negative; deleting one coefficient from \(f(m+1)\) yields \(f(m)\), and \(f(m)\) is computable in polynomial time from unary \(m\).
A society is given by its support: a list of \(\tau\) distinct complete strict rankings of a candidate set \(C\), with positive binary rational masses \(\mu_t\) summing to \(1\). Here \(\tau\) is the support size, not the number \(m!\) of possible rankings; \(m=|C|\geq1\).
The input also specifies \(p\in C\) and a binary rational budget \(\kappa\geq0\). Write \(s_f(t,c)=\alpha^m_{\operatorname{rank}_t(c)}\), and let \(L\) be the total input bit length.
Every type is deletable: choose real masses \(0\leq d_t\leq\mu_t\) with \(\sum_t d_t\leq\kappa\). The residual score is \(S_d(c)=\sum_t(\mu_t-d_t)s_f(t,c)\); success means \(S_d(p)\geq S_d(c)\) for every \(c\in C\). Ties count as winning, and zero residual mass is allowed.

For each fixed generator \(f\) satisfying these conditions, is this continuous deletion decision problem in \(\mathrm{P}\) or \(\mathrm{NP}\)-hard? State running times in \(m\), \(\tau\), and \(L\).

Discrete unweighted voter deletion is polynomial-time solvable for generators ultimately equivalent to \(1\)-approval, \(2\)-approval, \(3\)-veto, \((0,\ldots,0,-\beta,-\alpha)\) with fixed rational \(\alpha\geq\beta\geq0\), or \((2,1,\ldots,1,0)\), and is \(\mathrm{NP}\)-complete otherwise. Ultimately equivalent means that, for every sufficiently large \(m\), the vectors differ by a positive scaling and a common additive offset. [Hemaspaandra–Schnoor](https://arxiv.org/pdf/1604.05264).
No result settling exactly this continuous deletion problem was located in the literature search.

Result

For every fixed generator \(f\) satisfying the hypotheses, continuous deletion is in \(\mathrm{P}\). Purity and nonincreasing coefficients are unnecessary for this conclusion; polynomial-time generation of rational coefficients suffices.

If \(\kappa\geq1\), deleting all mass succeeds. If \(m=1\), deleting nothing succeeds. The algorithm below also covers the substantive case \(m\geq2\) and \(0\leq\kappa<1\).

Exact linear-programming formulation

For each supported type \(t\), introduce its residual mass \(x_t=\mu_t-d_t\). For each opponent \(c\in C\setminus\{p\}\), define the rational coefficient

\(\Delta_{c,t}=s_f(t,p)-s_f(t,c)=\alpha^m_{\operatorname{rank}_t(p)}-\alpha^m_{\operatorname{rank}_t(c)}.\)

Consider the following linear feasibility problem over real variables \(x_1,\ldots,x_\tau\):

• \(0\leq x_t\leq\mu_t\) for every \(t\in\{1,\ldots,\tau\}\);
• \(\sum_{t=1}^{\tau}x_t\geq1-\kappa\);
• \(\sum_{t=1}^{\tau}\Delta_{c,t}x_t\geq0\) for every \(c\in C\setminus\{p\}\).

It has exactly \(\tau\) variables and \(2\tau+m\) scalar inequalities.

Claim. This system is feasible if and only if a successful deletion exists.

Proof. Suppose first that \(d\) is an admissible successful deletion, and set \(x_t=\mu_t-d_t\). The bounds on \(d_t\) give \(0\leq x_t\leq\mu_t\). Because the initial masses sum to \(1\),

\(\sum_{t=1}^{\tau}x_t=1-\sum_{t=1}^{\tau}d_t\geq1-\kappa.\)

For every opponent \(c\), success gives

\(\sum_{t=1}^{\tau}\Delta_{c,t}x_t=S_d(p)-S_d(c)\geq0.\)

Thus \(x\) satisfies the system.

Conversely, suppose \(x\) satisfies the system and define \(d_t=\mu_t-x_t\). The bounds on \(x_t\) imply \(0\leq d_t\leq\mu_t\), and the mass constraint implies

\(\sum_{t=1}^{\tau}d_t=1-\sum_{t=1}^{\tau}x_t\leq\kappa.\)

Finally, each opponent constraint is precisely \(S_d(p)-S_d(c)\geq0\). Hence \(d\) is an admissible successful deletion. This proves both directions.

The proof uses only score differences, so negative scoring coefficients cause no difficulty.

Bit complexity and running time

Let \(T_f(m)\) be a polynomial upper bound on the time needed to compute \(f(m)\) from unary \(m\). Let \(B_f(m)\geq1\) bound the binary encoding length of each output coefficient. Polynomial-time generation implies that \(B_f(m)\) is polynomially bounded in \(m\).

Each \(\Delta_{c,t}\) has encoding length \(O(B_f(m))\). Indeed, writing two coefficients as \(a/b\) and \(u/v\), with positive denominators, their difference is \((av-ub)/(bv)\); both resulting integers have \(O(B_f(m))\) bits. Computing each difference takes polynomial time in \(B_f(m)\).

The right-hand sides are \(0\), the input masses \(\mu_t\), and \(1-\kappa\). Their combined encoding length is \(O(L)\). No products of masses and scores are required in this formulation.

Consequently, a dense encoding of the entire system has length

\(N=O\!\left(L+m\tau(B_f(m)+1)+\tau^2\right).\)

Here the opponent rows contribute \(O(m\tau(B_f(m)+1))\) bits, while the bound and mass rows contribute \(O(\tau^2)\) matrix bits. Computing the scoring vector, reading the rankings, forming the differences, and writing the system all take polynomial time in these quantities.

We use the standard exact rational linear-programming theorem: feasibility over the reals of a finite system of rational linear inequalities is decidable in deterministic time polynomial in its binary encoding length. The theorem includes systems whose feasible regions have empty interior. See [Nemirovski’s lecture notes, Section 8.4](https://www2.isye.gatech.edu/~nemirovs/OPTIII_LectureNotes2020.pdf).

All hypotheses hold here: every coefficient is rational, the system is explicitly represented, and its encoding length is polynomially bounded. Thus exact feasibility decides the deletion problem. In particular, ties are handled exactly, without a numerical tolerance.

For an absolute constant \(a\), chosen sufficiently large for the construction and a fixed polynomial-time LP algorithm, the total bit running time is bounded by

\(T_f(m)+O\!\left(\left[L+m\tau(B_f(m)+1)+\tau^2\right]^a\right).\)

For fixed \(f\), this is \((m+\tau+L)^{O_f(1)}\). Since the support rankings are explicitly listed, both \(m\) and \(\tau\) are bounded by the input length, so it is also \(L^{O_f(1)}\). The algorithm never enumerates the \(m!\) possible rankings.

Consequence for the proposed classification

The polynomial-time conclusion applies to every generator in the question, including those whose discrete unweighted deletion problem is NP-complete under the supplied classification.

Discrete deletion imposes integer restrictions on the numbers of deleted voters. The present problem permits arbitrary real masses, and the equivalence proved above yields a rational linear feasibility problem without integer restrictions. Therefore the discrete hardness classification does not transfer to this model.

The target question is completely resolved: all qualifying fixed generators yield polynomial-time solvable continuous deletion problems.

⟨structured verdict parsed — rendered above⟩

The prover’s conclusion is correct: every qualifying fixed generator gives a continuous deletion problem in \(\mathrm{P}\). The argument resolves the entire target, with no major or minor mathematical issues identified.

• Scope and edge cases. If \(\kappa\geq1\), deleting all mass is admissible and gives every candidate score zero, so success follows from the stated tie convention. If \(m=1\), deleting nothing succeeds. These observations correctly cover the specified degenerate cases.

• Residual-mass substitution. The transformation \(x_t=\mu_t-d_t\) is bijective between the permitted deletion bounds and \(0\leq x_t\leq\mu_t\). Using the input assumption \(\sum_t\mu_t=1\), the budget condition is exactly

\[ \sum_t d_t\leq\kappa \quad\Longleftrightarrow\quad \sum_t x_t\geq1-\kappa. \]
Both directions are justified as written.

• Winning constraints. For each opponent \(c\), the identity

\[ S_d(p)-S_d(c)=\sum_t\Delta_{c,t}x_t \]
follows directly from the score definitions. The non-strict inequalities therefore encode precisely the required winning condition, including ties. Negative coefficients do not affect this equivalence.

• System size. There are \(\tau\) real variables, \(2\tau\) bound inequalities, one budget inequality, and \(m-1\) opponent inequalities: exactly \(2\tau+m\) inequalities. The construction uses only supported rankings.

• Coefficient bit lengths. Polynomial-time generation bounds the output coefficient lengths polynomially in \(m\). The displayed rational-subtraction calculation correctly gives \(O(B_f(m))\) bits per difference; cancellation or reduction cannot increase this bound. The input right-hand sides require \(O(L)\) bits in total, including the transformation to \(1-\kappa\).

• Dense encoding bound. The opponent rows require \(O(m\tau(B_f(m)+1))\) bits. The bound rows and budget row require \(O(\tau^2)\) matrix bits, and their right-hand sides are covered by \(O(L)\). Thus the stated bound

\[ N=O\!\left(L+m\tau(B_f(m)+1)+\tau^2\right) \]
is valid.

• Exact LP theorem. The prover states the necessary theorem precisely: rational linear feasibility over the reals is decidable in deterministic polynomial bit time, without an interior-point assumption. Section 8.4 of the cited notes supports exact feasibility decision and polynomial bit complexity. All applicable hypotheses are verified: finitely many variables and inequalities, rational data, and explicit polynomial-length encoding. Consequently, lower-dimensional feasible regions and exact ties introduce no gap. [Ben-Tal–Nemirovski lecture notes, Section 8.4](https://www2.isye.gatech.edu/~nemirovs/OPTIII_LectureNotes2020.pdf).

• Running time and classification. The stated construction-plus-LP running time is a valid polynomial bound in \(m,\tau,L\) for each fixed \(f\). Explicitly listed complete rankings ensure \(m,\tau=O(L)\), yielding \(L^{O_f(1)}\). Purity and monotonicity are indeed unused. The discrete classification supplies no hardness conclusion for this continuous formulation, and the prover correctly avoids transferring it.

No additional clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩