d4-journals-jair-2021-0005 (d4-journals-jair-2021-0005)

Given a finite set of voter types \(T\), rational masses \(\mu_t>0\) summing to \(1\), strict score vectors, a positive-mass seed cohort sending one positive article on \(c_2\), a rational baseline contact-density matrix \(Q^0\), and an eligibility mask, choose a rational matrix \(Q\) with \(Q_{tu}\in[Q^0_{tu},1]\) on eligible pairs and \(Q_{tu}=Q^0_{tu}\) elsewhere. Interpret \(Q_{tu}\) as the probability that each possible directed contact from type \(t\) to type \(u\) is present, with certain transmission. In the dense-population limit, a type receives the article exactly when reachable from seed mass along type pairs with positive density. Maximize the gain in \(c_0\)’s vote margin over \(Q^0\), with complexity measured in \(|T|\) and the input bit length.

A society is given by its support: a list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) counts listed types, not possible types. There are \(m\geq3\) candidates \(C=\{c_0,\ldots,c_{m-1}\}\). Each type has pairwise distinct nonnegative integer scores \(\pi_t(c)\), encoded in binary.
A nonempty seed cohort \(S\subseteq T\) broadcasts one common positive article about \(c_2\). Let \(Q^0\in([0,1]\cap\mathbb Q)^{T\times T}\) and an eligibility mask \(A\subseteq T\times T\) be given. Choose rational \(Q\) with \(Q^0_{tu}\leq Q_{tu}\leq1\) on \(A\), and \(Q_{tu}=Q^0_{tu}\) elsewhere; there is no budget or cost constraint.
The entry \(Q_{tu}\) is a directed contact density with certain transmission. In the dense-population model, precisely the types reachable from \(S\) along pairs with \(Q_{tu}>0\) receive the article, including seeds via paths of length zero. Each receiving type increases its score for \(c_2\) by exactly \(1\), once regardless of paths or seed mass; all other scores stay fixed. Plurality votes follow the resulting scores, with ties favoring the tied candidate with lowest initial score.
Let \(v_i(Q)\) be the total mass voting for \(c_i\), \(M(Q)=v_0(Q)-\max_{1\leq i<m}v_i(Q)\), and \(\Delta(Q)=M(Q)-M(Q^0)\). Define \(\mathrm{OPT}=\max_Q\Delta(Q)\) and a multiplicative \(\rho\)-approximation by \(\Delta(Q)\geq\rho\,\mathrm{OPT}\). Let \(L\) be the total binary input length.

Does this problem admit a polynomial-time multiplicative approximation with any guaranteed factor \(0<\rho(m,\tau,L)\leq1\), or is every such positive-factor approximation NP-hard? State running times in \(m,\tau,L\).

For finite voters, edge addition admits no polynomial-time positive-factor approximation unless \(\mathrm{P}=\mathrm{NP}\), even with three candidates, consecutive integer scores, one seed, certain transmission, restricted eligible edges, and unlimited budget. [Source](https://arxiv.org/pdf/1911.06198v2)
No result settling this exact distributional contact-density problem was identified in the literature search.

Result

Every strictly positive multiplicative approximation is NP-hard, already for \(m=3\). Consequently, unless \(\mathrm{P}=\mathrm{NP}\), there is no algorithm running in \(\operatorname{poly}(m,\tau,L)\) that guarantees any factor \(0<\rho(m,\tau,L)\leq1\).

We prove this directly for the weighted support representation. The [cited finite-voter paper](https://arxiv.org/html/1911.06198v2) provides related background; its hardness theorem is not needed for the reduction.

More precisely, deciding whether \(\mathrm{OPT}>0\) is NP-complete. An exact algorithm runs in \(O\!\left(2^\tau(\tau^2+m\tau)L^2\right)\) bit operations.

1. Reduction from positive-integer subset sum

We use the standard NP-complete problem: given positive integers \(a_1,\ldots,a_n,B\), encoded in binary, decide whether some \(I\subseteq\{1,\ldots,n\}\) satisfies \(\sum_{j\in I}a_j=B\).

Set

\(\displaystyle W=\sum_{j=1}^n a_j,\qquad H=4W+8B+2.\)

Let \(N\) be the smallest power of two strictly greater than \(H\). Construct \(m=3\) candidates and \(\tau=n+5\) types, with masses and initial scores as follows.

| Type | Mass | Base scores \((c_0,c_1,c_2)\) |
|---|---|---|
| Seed \(s\) | \(1/N\) | \((0,1,2)\) |
| Gateway \(g\) | \((2B-1)/N\) | \((2,0,1)\) |
| Item \(x_j\), for each \(j\) | \(2a_j/N\) | \((0,2,1)\) |
| Ballast \(b_1\) | \((6B+1)/N\) | \((0,2,1)\) |
| Ballast \(b_2\) | \((2W+1)/N\) | \((0,1,2)\) |
| Ballast \(b_0\) | \((N-H)/N\) | \((2,0,1)\) |

All masses are positive dyadic rationals. Their numerators sum to

\(\displaystyle 1+(2B-1)+2W+(6B+1)+(2W+1)+(N-H)=N,\)

so the masses sum to \(1\).

To ensure that every listed type has a distinct score vector, enumerate the types by distinct integers \(r_t\in\{0,\ldots,\tau-1\}\) and add \(3r_t\) to all three base scores of type \(t\). This preserves all voting behavior. Every type has three consecutive, distinct, nonnegative integer scores.

Take

\(\displaystyle S=\{s\},\qquad Q^0_{tu}=0\ \text{for every pair},\)

and permit exactly the contacts

\(\displaystyle A=\{(s,g)\}\cup\{(g,x_j):1\leq j\leq n\}.\)

Thus the eligible graph is acyclic, every seed-to-type path has length at most two, and all ballast types are unreachable.

Because transmission depends only on positivity, an eligible contact is effectively either inactive or active. Every choice of active eligible contacts is realizable by setting their densities to \(1\) and all other densities to \(0\).

2. Exactly which votes change

Initially, the gateway and \(b_0\) vote for \(c_0\); the items and \(b_1\) vote for \(c_1\); and the seed and \(b_2\) vote for \(c_2\).

The seed receives the article even at \(Q^0\), but continues voting for \(c_2\). Therefore, writing \(v_i^0=v_i(Q^0)\),

\(\displaystyle v_0^0=\frac{2B-1+N-H}{N},\qquad v_1^0=\frac{2W+6B+1}{N},\qquad v_2^0=\frac{2W+2}{N}. \)

In particular,

\(\displaystyle v_1^0-v_2^0=\frac{6B-1}{N}>0,\qquad M(Q^0)=v_0^0-v_1^0.\)

A receiving gateway has its \(c_2\) score increased from the middle score to the top score. The resulting tie favors \(c_2\), whose initial score was lower than \(c_0\)'s. Hence the gateway switches from \(c_0\) to \(c_2\). Each receiving item similarly switches from \(c_1\) to \(c_2\).

If \(Q_{sg}=0\), only the seed receives the article, regardless of the item-contact densities. Consequently, \(\Delta(Q)=0\).

If \(Q_{sg}>0\), the gateway receives the article, and precisely the items indexed by

\(\displaystyle I=\{j:Q_{g x_j}>0\}\)

receive it. Every subset \(I\) is possible. Put

\(\displaystyle k=\sum_{j\in I}a_j,\qquad y=\frac{2B-1}{N},\qquad x=\frac{2k}{N}.\)

The resulting vote masses are

\(\displaystyle v_0=v_0^0-y,\qquad v_1=v_1^0-x,\qquad v_2=v_2^0+y+x.\)

Using \(M=\min\{v_0-v_1,v_0-v_2\}\), we obtain

\(\displaystyle \Delta(Q) =\min\left\{x-y,\ (v_1^0-v_2^0)-2y-x\right\}. \)

Substituting the masses gives the exact identity

\(\displaystyle \Delta(Q) =\frac1N\min\{2(k-B)+1,\ 2(B-k)+1\} =\frac{1-2|k-B|}{N}. \)

Since \(k\) and \(B\) are integers:

• If \(k=B\), then \(\Delta(Q)=1/N\).
• If \(k\neq B\), then \(\Delta(Q)\leq-1/N\).

Together with the always-feasible choice \(Q=Q^0\), this proves

\(\displaystyle \mathrm{OPT}= \begin{cases} 1/N,&\text{if the subset-sum instance is a yes-instance},\\ 0,&\text{if it is a no-instance}. \end{cases} \)

3. Consequence for every positive factor

Suppose a polynomial-time algorithm returns feasible \(Q\) satisfying

\(\displaystyle \Delta(Q)\geq\rho(m,\tau,L)\,\mathrm{OPT},\qquad \rho(m,\tau,L)>0.\)

Run it on the constructed instance and evaluate its output exactly.

On a yes-instance, the guarantee forces \(\Delta(Q)>0\). On a no-instance, no feasible output has positive improvement. Thus testing whether the returned improvement is positive decides subset sum.

This argument needs neither a lower bound on \(\rho\) nor an algorithm for evaluating \(\rho\). Its strict positivity alone suffices.

The reduction has polynomial binary length: \(N\leq2H\), so every mass has \(O(\log(W+B))\) bits, and every score has \(O(\log\tau)\) bits. With a dense encoding of \(Q^0\), the constructed input length is

\(\displaystyle L=O\!\left(n^2+n\log(W+B)+n\log(n+5)\right).\)

There are only \(n+5\) listed types; no expansion into \(N\) finite voters occurs. The reduction therefore establishes hardness in the requested parameters \(m,\tau,L\).

4. Finite certificates and exact running time

Define the forced and potentially available contact sets by

\(\displaystyle E_0=\{(t,u):Q^0_{tu}>0\},\qquad E_+=E_0\cup A.\)

Any feasible density matrix has the same receiving types as a canonical matrix whose eligible entries are each either their baseline value or \(1\): retain the baseline value for inactive contacts and set active eligible contacts to \(1\). This preserves every contact's positivity.

Hence the objective takes only finitely many values, and its maximum is attained. A choice of active eligible contacts provides a polynomial-size certificate. Reachability, voting, and the strict comparison \(\Delta(Q)>0\) are computable using exact rational arithmetic in \(O((\tau^2+m\tau)L^2)\) bit operations. Combined with the reduction, this proves NP-completeness of deciding \(\mathrm{OPT}>0\).

For an exact algorithm, enumerate all \(R\subseteq T\). A set \(R\) is realizable as the receiving set if and only if:

• \(S\subseteq R\).
• No edge of \(E_0\) leaves \(R\).
• Every vertex of \(R\) is reachable from \(S\) in the graph \((R,E_+\cap(R\times R))\).

Necessity follows directly from reachability: receiving sets contain the seeds, are closed under forced contacts, and contain every vertex on a witnessing path.

For sufficiency, set every eligible contact within \(R\) to \(1\) and leave every other contact at baseline. Condition 3 makes every vertex of \(R\) reachable. Condition 2 ensures that no positive contact leaves \(R\): an eligible contact leaving \(R\) remains at baseline and must have baseline zero. Thus precisely \(R\) receives the article.

Each set can be checked and evaluated in \(O((\tau^2+m\tau)L^2)\) bit operations. Taking the best realizable set gives the stated exact running time

\(\displaystyle O\!\left(2^\tau(\tau^2+m\tau)L^2\right).\)

⟨structured verdict parsed — rendered above⟩

The output resolves the assigned problem. The reduction, improvement calculation, positive-factor hardness argument, and exact algorithm are correct as written. I found no major or minor mathematical issues.

• The constructed instance satisfies the input requirements.

There are exactly \(\tau=n+5\) listed types and \(m=3\) candidates. Because \(B\geq1\), every stated mass numerator is positive; in particular, \(2B-1\geq1\). The choice \(N>H\) also makes the ballast mass \((N-H)/N\) positive.

The numerator sum is correctly computed:
\[ 1+(2B-1)+2W+(6B+1)+(2W+1)+(N-H)=N. \]
Thus the masses sum to \(1\), and their common power-of-two denominator makes them dyadic rationals.

Each score vector has distinct, nonnegative, consecutive integer entries. Adding \(3r_t\) to all entries preserves initial rankings, the effect of the unit score increase, and the initial-score tie-breaking comparisons. It also makes the listed score vectors distinct.

• The reachability description is exact.

With \(Q^0=0\), only the seed receives the article at baseline. The eligibility mask allows only \(s\to g\) and \(g\to x_j\), so all ballast types remain unreachable under every feasible choice.

If \(Q_{sg}=0\), no nonseed type receives the article. If \(Q_{sg}>0\), the gateway receives it, and precisely those items with \(Q_{gx_j}>0\) receive it. Every subset of items is realizable using densities in \(\{0,1\}\). This uses exactly the task’s positivity-based transmission rule and requires no finite-population interpretation.

• The voting transitions and baseline totals are correct.

The seed initially favors \(c_2\), and its baseline receipt leaves that vote unchanged. The gateway initially favors \(c_0\); receipt creates a top-score tie between \(c_0\) and \(c_2\), which favors \(c_2\) because its initial score was lower. The corresponding item tie between \(c_1\) and \(c_2\) also favors \(c_2\).

The stated baseline totals correctly account for every type:
\[ v_0^0=\frac{2B-1+N-H}{N},\qquad v_1^0=\frac{2W+6B+1}{N},\qquad v_2^0=\frac{2W+2}{N}. \]
Consequently,
\[ v_1^0-v_2^0=\frac{6B-1}{N}>0, \]
so the baseline margin is indeed \(v_0^0-v_1^0\).

• The critical improvement identity is correct.

For an activated gateway and selected item sum \(k\), the vote changes are exactly those stated. Subtracting the baseline margin from the two possible resulting margins gives
\[ \Delta(Q)= \min\left\{x-y,\ (v_1^0-v_2^0)-2y-x\right\}. \]
Substitution yields
\[ \Delta(Q)=\frac{1}{N} \min\{2(k-B)+1,\ 2(B-k)+1\} =\frac{1-2|k-B|}{N}. \]

Integrality is used correctly: \(k=B\) gives improvement \(1/N\), whereas \(k\neq B\) gives improvement at most \(-1/N\). The inactive-gateway choice gives improvement \(0\). These alternatives exhaust all feasible receiving patterns, establishing the claimed two-valued characterization of \(\mathrm{OPT}\).

The argument also covers subset-sum instances with \(B>W\): every attainable \(k\) then differs from \(B\), so the optimum is \(0\).

• The positive-factor hardness consequence follows.

The source problem is precisely stated as binary-encoded subset sum with positive integers, a standard NP-complete restriction. The construction has polynomial length: \(N\leq2H\), and the masses, scores, baseline matrix, and eligibility mask have the stated polynomial encodings.

On a yes-instance, any strictly positive multiplicative guarantee forces a strictly positive returned improvement. On a no-instance, no feasible solution has positive improvement. Exact evaluation therefore decides subset sum.

No quantitative lower bound on \(\rho(m,\tau,L)\) is necessary. Strict positivity suffices even if the factor is extremely small or cannot itself be efficiently evaluated. The reduction establishes the claimed obstruction to algorithms running in \(\operatorname{poly}(m,\tau,L)\), already with \(m=3\).

• NP membership and the exact algorithm are justified.

Replacing active eligible contacts by density \(1\) and retaining baseline densities elsewhere preserves every contact’s positivity. Hence polynomial-size contact certificates suffice, and the optimum is attained among finitely many receiving patterns.

The characterization of realizable receiving sets is correct. Necessity follows from seed inclusion, closure under forced positive contacts, and witnessing paths. For sufficiency, activating all eligible contacts inside \(R\) gives internal reachability, while closure under \(E_0\) prevents any positive contact from leaving \(R\). Thus the constructed matrix realizes precisely \(R\).

The claimed per-set bound
\[ O((\tau^2+m\tau)L^2) \]
accommodates graph scans, score comparisons, and exact rational vote calculations. The masses have total encoded length bounded by \(L\), so their sums and comparisons can be handled with polynomially bounded integer representations within this bound. Enumerating all receiving sets therefore gives the stated exact running time
\[ O\!\left(2^\tau(\tau^2+m\tau)L^2\right). \]

Together with the reduction, the certificate argument establishes NP-completeness of deciding whether \(\mathrm{OPT}>0\).

No additional clarification or repair is needed. The finite-voter paper is explicitly background only; none of the conclusions depends on applying its theorem to this model.

⟨structured verdict parsed — rendered above⟩