Node Conversion Optimization in Multi-hop Influence Networks (aamas23-00258)

Given a finite role set \(Q\), a role-level relational template \(H\) for measured dense blow-ups, rational masses \(\mu\in\mathbb{Q}_{\ge 0}^{Q}\) with \(\sum_{q\in Q}\mu_q=1\), normalized thresholds \(\theta:Q\to[0,1]\), and root-specific weighted \(k\)-hop views \(\Gamma_k(q)\) with local incidence measures \(\nu_q\), find a local \(r/s\) rule \(F\) maximizing \(\sum_{q\in Q}\mu_q\mathbf{1}[F(\Gamma_k(q))=r]\), subject to \(F(\Gamma_k(q))=r \Rightarrow\ \nu_q(\{p:F(\Gamma_k(p))=r\})\ge\theta(q)\) for every root role and every admissible measured blow-up in the template class. The bounded-template version additionally requires \(\max_q|N_k(q)|\le w\) for fixed \(w\).

A society is given by its support: a nonempty list \(Q\) of \(\tau\) types with positive binary-rational masses \(\mu_q\), summing to \(1\). Here \(\tau=|Q|\) is the support size, not the number of possible types.
A template \(H\in\{0,1\}^{Q\times Q}\) is symmetric; diagonal entries are allowed. Its admissible measured blow-ups are all atomless probability spaces partitioned into sets \(X_q\) of masses \(\mu_q\), with distinct points of roles \(q,p\) adjacent exactly when \(H_{qp}=1\); require these graphs to be connected. Let \(m\) count unordered permitted role pairs, including diagonal pairs.
The input also gives an integer \(k\ge1\), binary-rational thresholds \(\theta(q)\in(0,1]\), and a binary-rational target \(b\in[0,1]\). All agents initially have state \(s\) and make one irreversible decision to retain \(s\) or adopt \(r\), without communication or history.
For a root of role \(q\), its view \(\Gamma_k(q)\) contains the root, all points reachable within \(k\) edges, and exactly the edges occurring on paths of length at most \(k\) starting at the root. It records visible role labels, thresholds, restricted masses, and the distinguished root, using the finite role representation; information outside the view is unavailable.
Let \(N_k(q)\) be the roles represented in this view, including the root role, and let \(\nu_q(A)\) be the population mass of points in the root's neighborhood whose roles lie in \(A\subseteq Q\). This measure is not divided by neighborhood mass; the root itself has zero mass.
A deterministic local rule \(F\) depends only on the marked view and gives every agent of a role the same decision. It is protocol-safe if, for every admissible blow-up and every root role \(q\), \(F(\Gamma_k(q))=r\) implies \(\nu_q(\{p:F(\Gamma_k(p))=r\})\ge\theta(q)\); retaining \(s\) is always safe.
The decision problem asks whether some protocol-safe local rule achieves \(\sum_{q\in Q}\mu_q\mathbf{1}[F(\Gamma_k(q))=r]\ge b\). The bounded-template restriction is \(\max_q|N_k(q)|\le w\).

Is this decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard, both without the bound and for each fixed \(w\)? State running times in \(m,\tau,L,k,w\), where \(L\) is the total input bit length.

For finite connected simple graphs with arbitrary positive integer thresholds, an optimal protocol-safe local rule maximizing conversions on every graph is known, with an exponential recursive implementation ([verified result](https://aamas.csc.liv.ac.uk/Proceedings/aamas2023/pdfs/p2205.pdf)). No result settling this exact measured formulation was located.

Result and scope

The decision problem is in \(\mathrm{P}\), both without the bound and for every fixed \(\w\).

Here and below, \(\w\) denotes the given width bound. Safety is quantified over the admissible blow-ups of the supplied template and masses, as specified in the question. The rule may be chosen separately for each input.

The key fact is that there is a unique largest feasible set of adopting roles. Repeatedly deleting roles with insufficient remaining neighborhood mass computes this set.

1. Computing neighborhood masses

Write \(\lambda\) for population measure, and define
\[ C_k(q)=\{p\in Q:\text{the points of role }p\text{ in the neighborhood of }q\text{ have positive mass}\}. \]

Unlike \(N_k(q)\), the set \(C_k(q)\) need not contain \(q\).

To compute it, form the simple role graph \(G_H\): its vertices are \(Q\), and distinct roles \(q,p\) are adjacent when \(H_{qp}=1\). Diagonal entries are recorded separately.

For distinct roles, we have
\[ p\in C_k(q)\quad\Longleftrightarrow\quad \operatorname{dist}_{G_H}(q,p)\le k. \]
Indeed, a path in a blow-up projects to a role walk; removing repetitions gives a role path no longer than the original path. Conversely, a role path lifts to a point path ending at any prescribed point of its final role.

For the root role,
\[ q\in C_k(q)\quad\Longleftrightarrow\quad H_{qq}=1\ \text{or}\ \bigl(k\ge2\text{ and }q\text{ has a distinct neighboring role}\bigr). \]
A diagonal entry gives a one-edge path to every other point of the same role. A distinct neighboring role gives a two-edge path. If neither condition holds, only the distinguished root represents its role in the view, and its mass is zero.

Consequently, for every admissible blow-up and every \(A\subseteq Q\),
\[ \nu_q(A)=\sum_{p\in A\cap C_k(q)}\mu_p. \tag{1} \]
Thus these quantities depend only on the finite input.

Connectedness is also decidable from the template: for \(\tau\ge2\), it is equivalent to connectedness of \(G_H\); for \(\tau=1\), it requires \(H_{qq}=1\). We work on the connected inputs required by the question.

2. Reduction to a finite feasibility problem

Call a set \(A\subseteq Q\) feasible if
\[ \sum_{p\in A\cap C_k(q)}\mu_p\ge\theta(q) \qquad\text{for every }q\in A. \tag{2} \]
The empty set is feasible.

Every protocol-safe local rule determines a feasible set \(A\) of adopting roles, by equation (1) and the safety requirement.

Conversely, every feasible \(A\) can be implemented by the local rule
\[ F_A(\Gamma)= \begin{cases} r,&\text{if the distinguished root's role belongs to }A,\\ s,&\text{otherwise}. \end{cases} \]
This rule reads only the visible root-role label. Its membership table is part of the chosen protocol; agents do not access information outside their views. Equation (2) proves safety simultaneously in every admissible blow-up of the supplied input.

Therefore the optimum conversion mass is exactly
\[ \max\left\{\sum_{q\in A}\mu_q:A\subseteq Q\text{ is feasible}\right\}. \tag{3} \]

3. The largest feasible set

Start with \(S=Q\). While there is a role \(q\in S\) satisfying
\[ \sum_{p\in S\cap C_k(q)}\mu_p<\theta(q), \]
delete \(q\). Let \(S^\star\) be the set when no further deletion is possible.

Claim. Every feasible set is contained in \(S^\star\), and \(S^\star\) is feasible.

Proof. Fix any feasible \(A\). Initially \(A\subseteq S\). Suppose this containment holds immediately before deleting a deficient role \(q\).

If \(q\in A\), then positivity of the masses and \(A\subseteq S\) imply
\[ \sum_{p\in A\cap C_k(q)}\mu_p \le \sum_{p\in S\cap C_k(q)}\mu_p < \theta(q), \]
contradicting feasibility of \(A\). Hence \(q\notin A\), so the containment persists after deletion.

There are at most \(\tau\) deletions. At termination, every surviving role satisfies equation (2), so \(S^\star\) is feasible. The containment invariant proves that every feasible \(A\) lies inside \(S^\star\). This proves the claim.

Since all masses are positive, the unique optimum adopting set is \(S^\star\). The decision algorithm returns yes exactly when
\[ \sum_{q\in S^\star}\mu_q\ge b. \]

The argument also proves that deletion order does not affect the answer.

4. Running times

Let
\[ D=\sum_{q\in Q}|C_k(q)| \]
be the number of ordered neighborhood incidences. Always \(D\le\tau^2\); under the width restriction, \(D\le\tau w\).

Neighborhood computation

Breadth-first search from every role computes the required distances in
\[ O\bigl(\tau(m+\tau)\bigr) \]
graph operations. A search stops expanding vertices at distance \(k\). Diagonal entries and the root-role correction are handled separately.

There is no multiplicative dependence on the numerical value of \(k\): on a connected admissible input, replacing \(k\) by \(\min\{k,\tau\}\) preserves all neighborhood masses. Distinct-role distances are at most \(\tau-1\), and same-role reachability requires at most two edges when \(\tau\ge2\).

Under the width bound, each search visits at most \(w\) roles. Every role has at most \(w-1\) distinct neighbors, because its immediate neighboring roles belong to \(N_k(q)\). Scanning adjacency lists therefore takes
\[ O(\tau w^2) \]
graph operations across all searches. Timestamped visitation arrays avoid clearing a length-\(\tau\) array between searches.

Peeling

Store the reverse incidence list
\[ R(p)=\{q:p\in C_k(q)\} \]
and initialize
\[ a_q=\sum_{p\in C_k(q)}\mu_p. \]
Maintain a queue of deficient surviving roles. Removing \(p\) subtracts \(\mu_p\) from \(a_q\) for surviving \(q\in R(p)\); any newly deficient role enters the queue.

Each role is removed at most once, and each reverse incidence is processed at most once. Initialization, peeling, and the final objective comparison require
\[ O(D+\tau) \]
exact arithmetic operations.

Bit complexity

Take a common denominator \(B\) equal to the product of the denominators of all masses, thresholds, and \(b\). Its bit length is \(O(L)\). Scale all these rationals to integers over \(B\).

Using elementary integer arithmetic, this preprocessing takes \(O(\tau L^2)\) bit operations. All neighborhood sums lie between zero and \(B\), so each subsequent addition, subtraction, or comparison takes \(O(L)\) bit operations.

A conservative total bit-complexity bound is therefore
\[ O\!\left( L+\tau(m+\tau)\log(\tau+1)+\tau L^2+(D+\tau)L \right). \]
Using \(D\le\tau^2\) gives the unrestricted bound
\[ O\!\left( L+\tau(m+\tau)\log(\tau+1)+\tau L^2+\tau^2L \right). \]

Under the width restriction, the corresponding bound is
\[ O\!\left( L+\tau w^2\log(\tau+1)+\tau L^2+\tau wL \right). \]
Both bounds are polynomial in the total input length; the latter is polynomial for every fixed \(w\).

5. A nontrivial example and the literature distinction

Consider the loopless path \(a-b-c-d\), with \(k=1\), masses \(\mu_q=1/4\), and thresholds
\[ \theta(a)=\theta(b)=\theta(d)=1/4,\qquad \theta(c)=3/4. \]
Initially, \(c\) has neighborhood mass \(1/2\), so it is deleted. Then \(d\) has no adopting neighbor and is deleted. The surviving set \(\{a,b\}\) is feasible and, by the proved containment invariant, optimal. Its conversion mass is \(1/2\).

The supplied-template safety quantifier is essential to the implementation argument. The [cited finite-graph paper](https://aamas.csc.liv.ac.uk/Proceedings/aamas2023/pdfs/p2205.pdf) requires a protocol to be safe on every influence network. That broader requirement couples decisions across different networks sharing local views. The problem stated here quantifies over realizations of the supplied template and masses, for which equation (1) and the local membership rule give the complete polynomial-time solution above.

⟨structured verdict parsed — rendered above⟩

The argument establishes polynomial-time solvability under the stated interpretation: the rule is chosen for the supplied template and masses, and inputs admit connected blow-ups. I found no substantive mathematical gap. There is one minor notation issue.

• Neighborhood computation is correct.

For distinct roles, projecting a point path to a role walk and removing repetitions proves the forward distance implication. Conversely, a simple role path lifts to a point path ending at any prescribed point of the final role: every permitted pair gives complete adjacency between its role classes, and positive masses ensure those classes are nonempty.

The root-role correction is also correct. A diagonal permits reaching every other point of the root role in one edge. A distinct neighboring role permits doing so in two edges. Without either applicable condition, the root role contributes only the distinguished point, whose measure is zero by atomlessness.

Consequently, equation (1) correctly uses full population masses, with no neighborhood normalization. The special definition of visible edges does not invalidate this calculation: the calculation concerns reachable points.

• The connectedness characterization is correct.

For \(\tau\ge2\), connectedness of the role graph permits paths between different role classes and two-edge paths between distinct points in the same class. Conversely, disconnected role components cannot have edges between their corresponding populations.

For \(\tau=1\), the diagonal is necessary and sufficient. The proof explicitly limits its conclusion to connected inputs, consistent with the intended connected setting.

• The reduction to feasible role sets respects locality.

A safe rule gives a feasible adopting set by equation (1) and the stipulated uniform decision within each role.

Conversely, the proposed membership rule reads the visible distinguished root-role label. Different roles remain distinguishable even when their other visible data agree. A table incorporated into the selected rule does not require agents to inspect information outside their views.

Crucially, the task permits selecting a rule for the supplied instance and quantifies safety over that instance’s admissible blow-ups. It does not impose safety on unrelated templates. Under this quantifier, the implementation argument is valid.

• The deletion invariant proves maximality.

The displayed inequality is justified by nonnegative masses and containment \(A\subseteq S\). It shows that deleting a deficient role cannot delete a member of any feasible set.

Termination occurs after at most \(\tau\) deletions. At termination, every surviving role satisfies its feasibility inequality, including equality cases because deletion uses strict inequality. The empty surviving set is feasible vacuously.

Thus the terminal set is feasible and contains every feasible set. Positive masses then justify the claimed unique optimum: any proper subset has strictly smaller conversion mass. The same characterization establishes deletion-order independence.

• The decision comparison handles boundary cases.

Comparing the terminal conversion mass with \(b\) is exactly the requested objective. In particular, \(b=0\), \(b=1\), thresholds equal to available mass, and an empty terminal set require no exceptional argument.

For the connected single-role case, the mass is \(1\), the diagonal is present, and every permitted threshold is at most \(1\). The formulas and algorithm apply correctly.

• The neighborhood running-time bounds are valid.

Repeated breadth-first search costs \(O(\tau(m+\tau))\) graph operations; counting diagonal pairs in \(m\) only enlarges this upper bound.

Capping \(k\) at \(\tau\) preserves the required reachability. For \(\tau\ge2\), distinct-role distances are at most \(\tau-1\), and root-role reachability needs at most two edges. For \(\tau=1\), the admissible connected case needs only one edge. Reading a large binary encoding of \(k\) is covered by the \(O(L)\) term.

Under the width restriction, each search visits at most \(w\) roles, and each role has at most \(w-1\) distinct neighbors because \(k\ge1\). Therefore the stated \(O(\tau w^2)\) bound is valid. Timestamped arrays address the otherwise additional initialization cost per search.

• The peeling and bit-complexity bounds are valid.

Every removal processes its reverse incidences once. Queue entries that become stale can be discarded by checking whether the role survives; even repeated enqueueing is bounded by the incidence updates. Thus \(O(D+\tau)\) arithmetic operations is justified.

The product denominator has bit length \(O(L)\). Scaling the \(O(\tau)\) rational inputs using elementary integer arithmetic fits the conservative \(O(\tau L^2)\) preprocessing bound. Maintained sums remain between zero and the common denominator, so subsequent arithmetic has \(O(L)\) cost per operation.

Both displayed total bounds are polynomial in the explicit input length. The width bound correctly gives \(D\le\tau w\).

• The example and literature distinction check out.

The example’s deletions and final conversion mass are correct.

The cited paper defines protocol safety for every node and every influence network, supporting the asserted distinction in quantifiers. Its theorem is not used to justify the measured algorithm, so no external theorem application remains unverified. See [Definition 2.2 in the cited paper](https://aamas.csc.liv.ac.uk/Proceedings/aamas2023/pdfs/p2205.pdf).

Minor issue and required clarification. The command \(\backslash\mathrm{w}\), written as \w in the prover’s source, is not a standard defined mathematical macro. Replace every occurrence of \w with w, or explicitly define the macro. This is purely an exposition and rendering repair.

⟨structured verdict parsed — rendered above⟩