d4-conf-atal-2011-0070 (d4-conf-atal-2011-0070)

Fix a pure scoring rule whose vector for \(|C|+1\) candidates is \((\alpha_1,\alpha_2,1,0,\ldots,0)\), with \(\alpha_1>\alpha_2>1\). Given an initial candidate set \(C\), a new candidate \(a\), a target \(c^\star\in C\), and a rational distribution \(\mu\) over a finite support \(T\) of strict rankings of \(C\), is there a mass assignment \(q_{t,p}\ge 0\), for \(t\in T\) and \(p\in\{0,\ldots,|C|\}\), with \(\sum_p q_{t,p}=\mu_t\), such that inserting \(a\) after position \(p\) for mass \(q_{t,p}\) makes \(c^\star\) a co-winner?

Fix a pure positional scoring rule whose vector for every candidate count \(n\geq4\) is \((\alpha_1,\alpha_2,1,0,\ldots,0)\), where \(\alpha_1>\alpha_2>1\) are fixed integers.
An instance consists of an initial candidate set \(C\), with \(m=|C|\geq3\), one new candidate \(a\notin C\), and a target \(c^\star\in C\).
A society is given by its support: a list \(T\) of \(\tau\) distinct strict rankings of \(C\), each with positive mass \(\mu_t\) encoded as a binary rational, with \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number \(m!\) of possible rankings; let \(L\) be the total input bit length.
An admissible extension assigns real masses \(q_{t,p}\geq0\), for \(t\in T\) and \(p\in\{0,\ldots,m\}\), satisfying \(\sum_{p=0}^{m}q_{t,p}=\mu_t\). This mass ranks \(a\) immediately after the first \(p\) candidates of \(t\), preserving their order; \(p=0\) puts \(a\) first.
Scores are the mass-weighted positional scores in the extended society. The target is a co-winner exactly when its score is at least that of every candidate in \(C\cup\{a\}\); ties are accepted without tie-breaking.

Is deciding whether an admissible extension makes \(c^\star\) a co-winner in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?

For indivisible unweighted voters, adding exactly one new candidate under these scoring rules is \(\mathrm{NP}\)-complete (Baumeister, Roos, and Rothe, 2011). No result settling this exact divisible-mass version was located in the literature search.

Result

The problem is in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\). We prove this by constructing a rational linear feasibility problem with \(4\tau\) variables and proving its exact equivalence to the required extension.

1. Four insertion types suffice

Fix a ranking \(t\in T\), and denote its first three candidates by \(b_{t,1},b_{t,2},b_{t,3}\). These exist because \(m\geq3\).

The extended election has \(m+1\geq4\) candidates, so its scoring vector is the specified vector. The scores contributed per unit mass are:

| Insertion position | \(a\) | \(b_{t,1}\) | \(b_{t,2}\) | \(b_{t,3}\) |
|---|---:|---:|---:|---:|
| \(p=0\) | \(\alpha_1\) | \(\alpha_2\) | \(1\) | \(0\) |
| \(p=1\) | \(\alpha_2\) | \(\alpha_1\) | \(1\) | \(0\) |
| \(p=2\) | \(1\) | \(\alpha_1\) | \(\alpha_2\) | \(0\) |
| \(p\geq3\) | \(0\) | \(\alpha_1\) | \(\alpha_2\) | \(1\) |

Every other initial candidate contributes zero in every row: its original rank is at least four, and inserting \(a\) cannot improve that rank.

For \(p\geq3\), the original first three candidates retain their positions, while \(a\) occupies a position at least four. Thus all such insertion positions have identical score contributions.

Let \(J=\{0,1,2,3\}\), where type \(3\) represents all positions \(p\geq3\). For each \(t\in T\), \(j\in J\), and \(d\in C\cup\{a\}\), define \(w_{t,j}(d)\) as the corresponding entry in the table, or zero if \(d\) is an initial candidate outside its first three positions.

2. The rational linear system

Introduce real variables \(x_{t,j}\), representing the mass of ranking \(t\) assigned insertion type \(j\). Impose nonnegativity and preservation of each ranking’s mass:

\[ \]
\(x_{t,j}\geq0\qquad(t\in T,\ j\in J),\)

\(\displaystyle \sum_{j\in J}x_{t,j}=\mu_t\qquad(t\in T).\)

For every candidate \(d\in C\cup\{a\}\), define its score as the linear expression

\(\displaystyle S_d(x)=\sum_{t\in T}\sum_{j\in J}w_{t,j}(d)x_{t,j}.\)

Finally, impose one inequality for each competitor:

\(\displaystyle \sum_{t\in T}\sum_{j\in J}\bigl(w_{t,j}(c^\star)-w_{t,j}(d)\bigr)x_{t,j}\geq0 \qquad\bigl(d\in(C\cup\{a\})\setminus\{c^\star\}\bigr).\)

These inequalities are exactly \(S_{c^\star}(x)\geq S_d(x)\). Their weak form implements the stipulated acceptance of ties.

3. Exact equivalence

From an admissible winning extension to feasibility.
Given masses \(q_{t,p}\), set

\(x_{t,0}=q_{t,0},\quad x_{t,1}=q_{t,1},\quad x_{t,2}=q_{t,2},\quad \displaystyle x_{t,3}=\sum_{p=3}^{m}q_{t,p}.\)

Nonnegativity and mass preservation follow directly from admissibility. By the table, aggregating positions \(p\geq3\) preserves every candidate’s score. Consequently, if the extension makes \(c^\star\) a co-winner, all competitor inequalities hold.

From feasibility to an admissible winning extension.
Given a feasible vector \(x\), set

\(q_{t,p}=x_{t,p}\quad\text{for }p\in\{0,1,2,3\},\)

and set \(q_{t,p}=0\) for \(4\leq p\leq m\).

Position \(3\) is available because \(m\geq3\). The resulting masses are nonnegative and sum to \(\mu_t\) for each ranking. Again, the table shows that their actual scores equal \(S_d(x)\). The competitor inequalities therefore make \(c^\star\) a co-winner.

This proves equivalence in both directions.

4. Polynomial bit complexity

The system has \(4\tau\) variables, \(4\tau\) nonnegativity inequalities, \(\tau\) mass equalities, and \(m\) competitor inequalities. Replacing each equality by two inequalities gives \(6\tau+m\) inequalities.

All matrix coefficients are integers of absolute value at most \(\alpha_1\). Because the scoring rule is fixed, these coefficients have constant bit length. The only nonzero right-hand sides are copies of the input rationals \(\mu_t\), whose total encoding length is bounded by \(L\). The rankings and table coefficients can be processed in polynomial time, and even a dense encoding of the resulting system has length polynomial in \(m,\tau,L\). No rankings outside the supplied support are enumerated.

We apply the standard polynomial-time rational linear feasibility theorem: given a rational matrix \(A\) and rational vector \(b\) in binary encoding, deciding whether there exists a real vector \(x\) satisfying \(Ax\leq b\) takes time polynomial in the total encoding length. This is the exact feasibility theorem underlying Khachiyan’s polynomial-time algorithm for linear programming. [Khachiyan, 1979](https://www.mathnet.ru/eng/dan42319).

Every hypothesis holds here: the system is finite, all its data are rational, and its encoding has polynomial length. The theorem decides exact feasibility, including feasible sets confined to equality boundaries; no positive winning margin is required.

Together with the equivalence proved above, this establishes the claimed polynomial-time algorithm. The indivisible-voter hardness result does not obstruct it: indivisibility restricts how each voter may be assigned, whereas this problem permits arbitrary splitting of mass, exactly as represented by the continuous variables.

⟨structured verdict parsed — rendered above⟩

The argument establishes polynomial-time solvability. The score reduction and both directions of the feasibility equivalence are correct. There is one minor encoding-size imprecision, which does not affect the complexity conclusion.

1. Four insertion types

Every row of the score table is correct:

• At \(p=0\), the new candidate takes first place, and the original first three candidates move to positions two, three, and four.
• At \(p=1\), the original first candidate stays first, the new candidate takes second place, and the original second and third candidates move to positions three and four.
• At \(p=2\), the original first two candidates retain their positions, the new candidate takes third place, and the original third candidate moves to fourth.
• At every \(p\geq3\), the original first three candidates retain their positions, and the new candidate receives zero.

An original candidate ranked fourth or lower cannot improve its rank through insertion, so its contribution remains zero. Consequently, aggregating all positions \(p\geq3\) preserves every candidate’s score.

The edge case \(m=3\) is covered: the extended election has four candidates, and the aggregated type consists solely of position \(p=3\). No assumption about the scoring vector for three candidates is needed.

2. Linear-system formulation

The variables correctly represent divisible real masses. Nonnegativity and the equality for each ranking impose precisely the required mass preservation.

The score expressions include every supported ranking and every insertion type. There are exactly \(m\) competitors: the \(m-1\) original candidates other than the target, together with the new candidate.

The competitor inequalities have the correct sign and are weak inequalities, so they implement co-winning with ties accepted. No integrality requirement or positive winning margin is introduced.

3. Exact equivalence

Extension to feasibility. The proposed aggregation preserves nonnegativity and each ranking’s total mass. The verified table establishes score preservation for every candidate, so a winning extension satisfies every competitor inequality.

Feasibility to extension. Assigning type-three mass to position three is valid because \(m\geq3\). Setting all later insertion masses to zero preserves the ranking masses and realizes exactly the specified linear scores. For \(m=3\), the instruction concerning positions \(4\leq p\leq m\) is simply vacuous.

Both implications apply to arbitrary real feasible masses. No rationality assumption about a winning extension is needed.

4. Polynomial complexity

The variable and constraint counts are correct: \(4\tau\) variables and, after converting equalities, \(6\tau+m\) inequalities.

Every matrix coefficient has absolute value at most \(\alpha_1\), including score differences, nonnegativity constraints, and mass constraints. Since the scoring rule is fixed, their bit lengths are constant. The dense matrix therefore has polynomial encoding length, and its construction uses only the supplied support.

Minor issue: After replacing each mass equality by two inequalities, the right-hand sides contain both \(\mu_t\) and \(-\mu_t\). Their total encoding length is therefore not necessarily bounded by \(L\) literally, as asserted. It is bounded by \(O(L)\), allowing constant duplication and encoding overhead.

Minimum clarification: Replace “bounded by \(L\)” with “bounded by \(O(L)\).”

The rational linear feasibility theorem is stated precisely enough for this application: binary rational input, real feasibility, and polynomial time in encoding length. Its hypotheses are satisfied. Exact feasibility includes systems with equalities and feasible sets without interior. The [Khachiyan reference](https://www.mathnet.ru/eng/dan42319) identifies the cited polynomial-time linear-programming result.

5. Resolution of the assigned task

The proof settles the stated divisible-mass decision problem in polynomial time in \(m,\tau,L\). The indivisible-voter hardness observation is contextual and is not used in the proof. No major gap, false central step, or unresolved edge case was found.

⟨structured verdict parsed — rendered above⟩