| paper | d4-conf-aaai-2013-0015 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Polynomial-time solvable for \(m=1\), with a conservative bit-operation running time of \(O(\tau^5L^3)\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
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\).
A one-issue population divided into role types, where a fraction of each type follows the inclination distribution of each source type. Bribery changes initial inclination mass before influence; the objective is to minimize changed mass until the target wins by majority.
The recurrence replaces the paper’s general deterministic rules over particular influencers with linear mass action, so it does not preserve outcomes when updates depend jointly on multiple influencers; the proponent’s narrower one-feature scope bounds this concern but does not derive the recurrence from the paper’s full model.
fatal: False
Covers one binary issue with positive acyclic mass-action influence, uniform bribery cost, and majority aggregation; leaves out multifeature CP-net propagation and the paper’s general conditional influence patterns.
The strongest positive case is Theorem 3, proved in this paper. It says that, for an I-profile with positive acyclic influences and per-agent, per-feature bribery costs, deciding whether a given candidate can be made the winner within a budget is NP-complete for both Level Aggregation and Finally Aggregation, and under both priority schemes \(b\gg i\) and \(i\gg b\). The result holds even when all agents and features have the same cost. The paper proves it by reduction from X3C.
I would mirror its one-feature, positive-influence case. Consider a large consultation or election over one binary issue, where agents’ initial inclinations and influence roles repeat across cohorts. A type records an agent’s initial inclination, bribery cost, and influence behavior. Its mass \(\mu_t\) is the fraction of the population in that type; the support has size \(\tau\). In a plausible regime, the population may be very large while \(\tau\) stays modest. For example, a company could repeatedly consult a large workforce whose members fall into a few inclination and communication-role groups.
Here is a concrete continuous problem: Typed Mass Bribery under Acyclic Influence. An instance has finitely many types \(T\), rational masses \(\mu_t>0\) summing to \(1\), initial inclinations \(b_t\in\{0,1\}\), and a rational influence matrix \(A\). The matrix is part of the mass-action model: \(A_{tu}\geq 0\) is the fraction of type \(t\)’s mass that follows the inclination distribution of type \(u\), and \(\sum_u A_{tu}\leq 1\). The positive entries form a directed acyclic graph. The remaining fraction of type \(t\) retains its post-bribery inclination. To mirror the paper’s uniform-cost case, set the cost per unit mass to \(1\).
The briber chooses \(\delta_t\in[0,\mu_t]\) for types initially inclined to \(\bar{x}\), paying \(\sum_t\delta_t\) to change that mass to \(x\). Write \(q_t\) for type \(t\)’s fraction initially inclined to \(x\) after bribery. The resulting influence dynamics have a unique terminal type-level share \(z_t\), computed in topological order by
\[
z_t=\left(1-\sum_u A_{tu}\right)q_t+\sum_u A_{tu}z_u.
\]
Each unit of population still has an integral inclination; \(z_t\) is the fraction of type \(t\) inclined to \(x\). Under the paper’s one-feature majority aggregation and tie-breaking against \(x\), the target wins exactly when \(\sum_t\mu_tz_t>1/2\). Given a budget \(B\), the problem asks whether a mass vector \(\delta\) costing at most \(B\) can make \(x\) win. Equivalently, the objective is to minimize bribed mass subject to that winning condition.
I expect this typed mean-field version to be Class A. Its influence equations are linear, as are the mass-cost and majority constraints. For the budget decision, an LP can maximize the final margin \(\sum_t\mu_tz_t-1/2\); the target can be made winner exactly when the optimum is positive. This is polynomial in the encoded instance size, including \(\tau\) and the rational bit lengths. The contrast with Theorem 3 is useful: fractional bribery can remove the indivisible set-selection choices behind the X3C reduction. That reduction therefore motivates the continuous question, but does not establish hardness for it.
This mirror covers the paper’s single-feature bribery question with positive acyclic influence and mass-based aggregation. It does not cover arbitrary multifeature CP-nets or every influence pattern in Theorem 3. Further questions include whether tractability survives richer type-level influence rules, how to model full multi-feature propagation, and which network structures still allow a finite-support formulation.
The weak point is that the paper’s agents follow particular named agents through deterministic influence functions, while this mirror uses a type-level mass-action influence matrix. Also, the X3C construction gives agents distinct influence roles, so its support can grow with the population. A referee could reasonably ask whether the typed dynamics are a continuous form of the authors’ problem or a new influence model. I think the case remains worth making because the intervention, influence-before-aggregation sequence, and winner objective are all preserved, and large cohorts with shared influence roles are a credible regime. But the paper’s theorem is an anchor for asking the continuous question, not evidence that this particular LP captures all of its discrete instances.
Theorem 3 is a real computational anchor, so the case against cannot be that the paper has no result to mirror. The difficulty is that its hardness comes from exact influence neighborhoods. In the X3C reduction, a bribed set-agent’s outgoing links encode a set, and element-agents respond to which particular sources changed. That is a Boolean coverage cascade, not just aggregation of source masses.
The proposed LP changes that mechanism. In the paper, an agent updates deterministically from the joint values of specific influencers. The equations for \(z_t\) replace those tests with linear averaging. But type-level marginals need not determine the result of even a positive rule such as “follow \(x\) if either parent favors \(x\).” If two parent types each have \(x\)-share \(1/2\), the share following \(x\) is \(1/2\) when those shares overlap completely, and \(1\) when they are disjoint. The same \(q_t\) and source marginals can therefore produce different outcomes. The LP is tractable because it models averaging; it does not establish that the paper’s influence-and-bribery problem has that linear form.
The strongest repair is to take the type to include an agent’s full network role and study a continuum of copies of an influence network. That preserves the local dynamics, but it does not yield a closed model over role masses: bribery across roles can create different joint configurations within copies, and those correlations affect later influence. Encoding the exact joint distribution may require exponentially many configurations, with a pricing problem that retains the original graph-based bribery problem. If the network template is fixed, the hard structure is fixed too; if it varies with the input, its incidence structure remains in the continuous instance.
That is a strong objection to this particular LP mirror, but it does not establish the universal negative. Repeated cohorts with broadcast or averaging influence are plausible, and a computational study of their mass-bribery problem could be worthwhile. The honest conclusion is that the proponent has not yet shown that its typed linear dynamics preserve Theorem 3’s model. I cannot honestly rule out a better continuous mirror; the negative case is substantial against the proposed formulation, but weak against the claim that no useful scenario exists.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.