d4-conf-aaai-2013-0015 (d4-conf-aaai-2013-0015)

Given finitely many role types \(T\) with rational masses \(\mu_t\) summing to \(1\), initial inclinations \(b_t\in\{0,1\}\), and a rational nonnegative acyclic matrix \(A\) with row sums at most \(1\), choose bribed mass \(\delta_t\in[0,\mu_t]\) for types initially inclined to \(\bar{x}\). Set \(q_t=b_t+(1-b_t)\delta_t/\mu_t\), and propagate \(z_t=(1-\sum_u A_{tu})q_t+\sum_u A_{tu}z_u\) in topological order. With unit cost per bribed mass and ties broken against \(x\), decide whether a budget \(B\) permits \(\sum_t\mu_t z_t>1/2\).

There is one binary issue, so \(m=1\), with alternatives \(x\) and \(\bar{x}\). A society is given by its support: a list \(T\) of \(\tau\) role types with positive binary rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types.
Each type has initial inclination \(b_t\in\{0,1\}\), where \(1\) means support for \(x\). Input also includes a binary rational budget \(B\geq0\) and an explicitly encoded nonnegative rational matrix \(A\), with \(\sum_u A_{tu}\leq1\); the graph with edges \(u\to t\) whenever \(A_{tu}>0\) is acyclic.
Before influence, choose real bribed masses \(0\leq\delta_t\leq\mu_t\) for types with \(b_t=0\), and set \(\delta_t=0\) otherwise. Bribery costs \(\sum_t\delta_t\), which must not exceed \(B\), and changes only initial inclinations; influence remains active.
Set \(q_t=b_t+(1-b_t)\delta_t/\mu_t\). In dependency order define the final support fraction \(z_t=(1-\sum_u A_{tu})q_t+\sum_u A_{tu}z_u\). Alternative \(x\) wins exactly when \(\sum_t\mu_tz_t>1/2\); ties favor \(\bar{x}\).
Let \(L\) be the total binary input length. State running times in \(m\), \(\tau\), and \(L\).

Is deciding whether an admissible bribery makes \(x\) win solvable in polynomial time, or is it NP-hard?

Discrete bribery with positive acyclic conditional influences is NP-complete even for one binary issue and uniform unit costs, both when influence overrides bribery and when bribery fixes opinions permanently ([source](https://ojs.aaai.org/index.php/AAAI/article/download/8639/8498)).
No result settling exactly the continuous formulation above was identified in the search.

Conclusion

The problem is polynomial-time solvable. Linear influence gives each type a fixed marginal benefit per unit of bribed mass. The resulting optimization is a continuous fractional-knapsack problem, which can be solved exactly, including the strict winning threshold.

For the stated case \(m=1\), the algorithm uses \(O(\tau^2+\tau\log\tau)\) exact rational operations. A conservative bit-operation bound is \(O(\tau^5L^3)\).

1. Expressing the final vote as a linear function

Write \(\mu\), \(q\), and \(z\) as column vectors indexed by the supported types. Define

\(s_t=1-\sum_u A_{tu}\), and \(D=\operatorname{diag}(s_t)\).

The assumptions imply \(s_t\geq0\). The influence equations become

\(z=Dq+Az\).

Because the dependency graph is acyclic, its vertices admit a topological ordering in which \(A\) is strictly lower triangular. Consequently \(A^\tau=0\), and

\(R=(I-A)^{-1}=I+A+\cdots+A^{\tau-1}\).

Thus the unique final support vector is \(z=RDq\).

Define

\(h=R^{\mathsf T}\mu\), and \(w_t=s_th_t\).

The total final support for \(x\) is therefore

\(S=\mu^{\mathsf T}z=\mu^{\mathsf T}RDq=\sum_t w_tq_t\).

Every entry of \(R\) is nonnegative, so \(h_t\geq0\) and \(w_t\geq0\). Moreover, these weights sum to one. Indeed, writing \(\mathbf1\) for the all-ones vector,

\(D\mathbf1=(I-A)\mathbf1\),

and hence

\(\sum_t w_t=\mu^{\mathsf T}RD\mathbf1=\mu^{\mathsf T}\mathbf1=1\).

The weights can be computed without forming \(R\). The identity \((I-A^{\mathsf T})h=\mu\) gives

\(h_u=\mu_u+\sum_t A_{tu}h_t\).

Evaluating this recurrence in reverse topological order computes all \(h_u\), and then all \(w_u\), using \(O(\tau^2)\) rational operations for the explicitly encoded matrix.

2. Reduction to continuous knapsack

Let \(E=\{t:b_t=0\}\) be the eligible types, and define the support without bribery by

\(S_0=\sum_t w_tb_t\).

For each eligible type, define its marginal benefit

\(c_t=\dfrac{w_t}{\mu_t}\).

This is well-defined because every supported type has positive mass. Substituting the definition of \(q_t\) into the expression for \(S\) yields

\(S(\delta)=S_0+\sum_{t\in E}c_t\delta_t\).

Therefore the maximum attainable support is exactly

\(S_{\max}=S_0+\max\left\{\sum_{t\in E}c_t\delta_t:0\leq\delta_t\leq\mu_t,\ \sum_{t\in E}\delta_t\leq B\right\}\).

All coefficients \(c_t\) are nonnegative. Each unit of bribed mass costs one unit, so the objective assigns a fixed benefit per unit cost to each eligible type.

3. A greedy optimum, with proof

If \(E\) is empty, then \(S_{\max}=S_0\). Otherwise, let \(r=|E|\), and relabel the eligible types so that

\(c_1\geq c_2\geq\cdots\geq c_r\geq0\).

Set

\(B'=\min\left(B,\sum_{i=1}^r\mu_i\right)\).

Construct a bribery by starting with remaining budget \(B'\), and, in this order, bribing each type by the smaller of its mass and the remaining budget. This construction is feasible and uses total mass \(B'\). It completely bribes an initial segment of types, possibly partially bribes the next type, and assigns zero to the remaining types.

To prove optimality, put

\(C_k=\sum_{i=1}^k\mu_i\).

For an arbitrary feasible bribery, put \(D_k=\sum_{i=1}^k\delta_i\). The capacity and budget constraints imply

\(D_k\leq\min(C_k,B')\).

The greedy construction attains equality for every prefix:

\(D_k^{\mathrm{gr}}=\min(C_k,B')\).

The following identity follows by expanding and collecting the coefficient of each \(\delta_i\):

\(\displaystyle \sum_{i=1}^r c_i\delta_i=\sum_{k=1}^{r-1}(c_k-c_{k+1})D_k+c_rD_r.\)

Every coefficient on the right is nonnegative. Replacing each \(D_k\) by its upper bound therefore gives

\(\displaystyle \sum_{i=1}^r c_i\delta_i\leq\sum_{k=1}^{r-1}(c_k-c_{k+1})\min(C_k,B')+c_rB'.\)

The greedy construction attains this bound, proving its optimality.

In particular, although real bribed masses are allowed, a rational optimum always exists: the greedy construction uses only minima and differences of the rational input masses and budget.

4. Deciding the strict winning condition

Compute the exact rational value of \(S_{\max}\) from the greedy optimum. The answer is yes exactly when

\(S_{\max}>\dfrac12\).

If equality holds, no admissible bribery makes \(x\) win: optimality shows that every admissible bribery has support at most one half, and the specified tie rule favors \(\bar{x}\).

Thus no approximation or numerical tolerance is required.

5. Bit complexity

It remains to verify that exact rational arithmetic has polynomial cost.

Let \(Q\) be the product of the positive denominators of all rational input entries. Their total encoding length is at most \(L\), so \(Q\) has \(O(L)\) bits. Every input rational can be written with denominator \(Q\).

The expression

\(h=\sum_{k=0}^{\tau-1}(A^{\mathsf T})^k\mu\)

shows that every denominator of \(h\), after reduction, divides \(Q^\tau\).

Its numerators also have polynomial length. To see this, nonnegativity and the row-sum condition imply \(A\mathbf1\leq\mathbf1\), and consequently \(A^k\mathbf1\leq\mathbf1\) for every nonnegative integer \(k\). Therefore

\(\displaystyle \sum_t h_t=\sum_{k=0}^{\tau-1}\mu^{\mathsf T}A^k\mathbf1\leq\tau.\)

Hence every \(h_t\) can be represented with \(O(\tau L)\) bits. Every denominator of \(w_t=s_th_t\) divides \(Q^{\tau+1}\), and \(0\leq w_t\leq1\).

Write \(\mu_t=p_t/Q\), where \(p_t\) is a positive integer. Then

\(c_t=\dfrac{Qw_t}{p_t}\)

has a denominator dividing \(p_tQ^\tau\). Since \(p_t\leq Q\), each \(c_t\) also has \(O(\tau L)\) bits.

Every greedy mass has denominator dividing \(Q\). During evaluation of the objective, a common denominator for all terms divides

\(\displaystyle Q^{\tau+1}\prod_{t\in E}p_t.\)

This integer has \(O(\tau L)\) bits, because there are at most \(\tau\) factors \(p_t\), each with \(O(L)\) bits. The objective’s partial sums are nonnegative and at most one. Consequently, reducing fractions after each operation keeps all stored quantities, and the temporary operands used in arithmetic and comparisons, within \(O(\tau L)\) bits.

Topological ordering and weight computation take \(O(\tau^2)\) operations; sorting takes \(O(\tau\log\tau)\) comparisons; greedy allocation and objective evaluation take \(O(\tau)\) operations. Thus the total is

\(O(\tau^2+\tau\log\tau)\)

exact rational operations.

For an explicit conservative bit bound, elementary integer arithmetic together with Euclidean fraction reduction costs at most \(O(n^3)\) per rational operation on \(n\)-bit operands. Taking \(n=O(\tau L)\) gives

\(O(\tau^5L^3)\)

bit operations. Since \(\tau\leq L\), this is polynomial in the total input length. This running-time statement applies to the required domain \(m=1\).

⟨structured verdict parsed — rendered above⟩

The prover’s claim is correct. The argument establishes polynomial-time solvability for the stated continuous problem with \(m=1\), including exact treatment of the strict winning threshold. I found no major or minor mathematical issues.

• Linear influence and acyclicity

With edges \(u\to t\) whenever \(A_{tu}>0\), a topological ordering makes \(A\) strictly lower triangular. Thus \(A^\tau=0\), and the displayed finite geometric series is indeed the inverse of \(I-A\).

Consequently, \(z=RDq\) is the unique solution of the influence equations. This agrees with evaluation in dependency order and preserves the specified influence mechanism after bribery.

The row-sum hypothesis gives \(s_t\geq0\), so \(D\) and \(R\) are entrywise nonnegative. No additional assumption is needed here.

• Effective voting weights

The definitions \(h=R^{\mathsf T}\mu\) and \(w_t=s_th_t\) correctly yield
\[ \mu^{\mathsf T}RDq=\sum_t w_tq_t. \]
Here and below, this identity is understood as \(\mu^{\mathsf T}RDq=\sum_t w_tq_t\).

Nonnegativity of \(R\), \(D\), and \(\mu\) establishes \(w_t\geq0\). The normalization argument is also correct: \(D\mathbf1=(I-A)\mathbf1\), so \(RD\mathbf1=\mathbf1\), and therefore \(\sum_t w_t=1\).

Types with \(s_t=0\) simply have zero effective weight. The proof never divides by \(s_t\), so these permitted cases cause no difficulty.

• Computing the weights

The recurrence
\[ h_u=\mu_u+\sum_t A_{tu}h_t \]
is exactly the componentwise form of \((I-A^{\mathsf T})h=\mu\).

Its evaluation in reverse topological order is valid: every nonzero summand involves a successor \(t\) of \(u\), whose value has already been computed. Scanning the explicitly encoded matrix and computing these sums takes \(O(\tau^2)\) rational operations. Forming \(R\) is unnecessary.

• Reduction to continuous knapsack

For eligible types, substitution of \(q_t=\delta_t/\mu_t\) gives the stated objective
\[ S(\delta)=S_0+\sum_{t\in E}c_t\delta_t. \]

The division defining \(c_t\) is valid because all supported masses are strictly positive. For ineligible types, \(q_t=1\) and \(\delta_t=0\), exactly as required.

The optimization constraints reproduce the task’s capacity and budget constraints without changing their meaning. In particular, the reduction allows arbitrary real allocations and incorporates continuing influence through the weights \(w_t\).

• Greedy optimality

The sorting order and capped budget \(B'\) are valid because every marginal coefficient is nonnegative.

For any feasible allocation, its total allocated mass is at most both \(B\) and the total eligible mass. Hence the claimed prefix bound \(D_k\leq\min(C_k,B')\) holds.

The greedy allocation attains every prefix bound simultaneously. The displayed summation identity has the correct coefficients: the coefficient of each \(\delta_i\) telescopes to \(c_i\). Since the differences \(c_k-c_{k+1}\) and the final coefficient \(c_r\) are nonnegative, replacing each prefix sum by its upper bound preserves the inequality. The greedy allocation attains the resulting upper bound, proving optimality.

This argument also covers equal marginal coefficients, zero marginal coefficients, \(B=0\), and budgets exceeding total eligible mass. When \(r=1\), the sum over the first \(r-1\) prefixes is empty and the identity remains valid. The case \(E=\varnothing\) is explicitly handled.

• Rational attainment and the strict threshold

The greedy construction uses rational capacities and rational budget remainders, so it produces a rational feasible allocation attaining the maximum over all real feasible allocations.

Therefore an admissible winning bribery exists exactly when \(S_{\max}>1/2\). Equality cannot produce a winner under the stipulated tie rule. There is no unresolved issue involving a supremum, numerical precision, or an unattained optimum.

• Bit-length bounds

The common-denominator argument is correct. The product \(Q\) has \(O(L)\) bits, and every input denominator divides \(Q\). Each term \((A^{\mathsf T})^k\mu\) has denominator dividing \(Q^{k+1}\), so reduced denominators of \(h\) divide \(Q^\tau\).

The numerator bound also follows as written. Nonnegativity and \(A\mathbf1\leq\mathbf1\) imply \(A^k\mathbf1\leq\mathbf1\). Thus \(\sum_t h_t\leq\tau\), bounding each component and giving \(O(\tau L)\)-bit representations.

Multiplication by \(s_t\) gives the stated denominator bound for \(w_t\). Normalization supplies \(0\leq w_t\leq1\).

Writing \(\mu_t=p_t/Q\) is valid, with \(1\leq p_t\leq Q\). The claimed denominator bound \(p_tQ^\tau\) for \(c_t\) follows directly from \(c_t=Qw_t/p_t\), and its numerator also has polynomial length.

Greedy allocations have denominators dividing \(Q\). The proposed common denominator for objective evaluation accommodates both the baseline and every allocated-benefit term. Its bit length is \(O(\tau L)\). Nonnegative objective partial sums are bounded by one because the weights sum to one and allocated fractions do not exceed one.

Reducing fractions after arithmetic operations therefore controls stored sizes. Temporary products and cross-products increase these bit lengths only by constant factors.

• Running time and task coverage

The count \(O(\tau^2+\tau\log\tau)\) correctly includes weight computation, sorting, allocation, and objective evaluation. Topological ordering fits within the matrix-processing bound.

The conservative \(O(n^3)\) cost per rational operation is sufficient for elementary arithmetic with Euclidean reduction. Substituting \(n=O(\tau L)\) gives the stated \(O(\tau^5L^3)\) bit-operation bound.

Since the task fixes \(m=1\), explicitly restricting the running-time statement to that domain satisfies the requested dependence on \(m\), \(\tau\), and \(L\). No generalization to multiple issues is required. The discrete hardness result does not conflict with the continuous optimization established here.

No additional mathematical clarification is needed.

⟨structured verdict parsed — rendered above⟩