| paper | d4-journals-ai-2014-0036 |
| 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→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-complete}\), already for \(m=2\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4.10
statement extracted from the paper’s text layer
Given a finite type set \(T\), rational masses \(\mu_t\), thresholds \(b_t\), type-level influence coefficients \(W_{st}\), and prescribed masses \(p_t\leq\mu_t\), decide whether a nonatomic type-block LIG has an equilibrium in which at least \(p_t\) mass of each type chooses \(+1\). Let \(z_t\in[p_t,\mu_t]\) be the mass of type \(t\) choosing \(+1\), set \(a_t=2z_t-\mu_t\), and define \(F_t=\sum_{s\in T}W_{st}a_s-b_t\). Every agent, including those in the prescribed mass, must best respond: \(z_t=\mu_t\) when \(F_t>0\), \(z_t=0\) when \(F_t<0\), and any \(z_t\in[0,\mu_t]\) when \(F_t=0\), with a split at indifference assigning pure actions to different agents.
A finite-step nonatomic LIG: each type has mass \(\mu_t\), a common threshold and type-level influence profile, and individuals choose pure actions. Aggregate signed masses determine each type's field; prescribed adopters are a mass lower bound, and all agents must best respond. The nonatomic limit changes the finite atomic PSNE solution concept and does not preserve Theorem 4.10's hardness reduction.
Even after the repair, replacing atomic players with nonatomic mass permits indifferent agents of one type to split across actions, and the theorem's SAT gadgets rely on player-specific interaction incidences.
fatal: False
The mirror covers Theorem 4.10's constrained-PSNE existence decision; it leaves unrestricted PSNE hardness, equilibrium counting, most-influential-node approximation, and other results unmirrored.
The strongest case I see is a mean-field version of the paper’s intervention question for a large population with a small number of repeated influence roles.
My anchor is Theorem 4.10, proved in this paper: given a linear influence game (LIG) and a designated subset of \(k\) players, it is NP-complete to decide whether there is a pure-strategy Nash equilibrium (PSNE) in which every designated player chooses action \(1\). The theorem reduces monotone one-in-three SAT to that question. It is a useful anchor because the designated players’ behavior is the starting point for the paper’s “most influential” problem.
Here is the continuous problem I would hand to a prover. Mass-Compatible LIG Equilibrium takes a finite set of types \(T\), rational masses \(\mu_t\geq 0\) summing to \(1\), rational thresholds \(b_t\), and signed influence coefficients \(W_{st}\). Type \(t\) means agents have the same threshold and the same influence relationships with every type. Each agent still chooses a definite action in \(\{-1,+1\}\). An agent of type \(t\) feels the field
\[
F_t(a)=\sum_{s\in T}W_{st}a_s-b_t,
\]
where \(a_s\) is the mass of type \(s\) choosing \(+1\) minus the mass choosing \(-1\). The instance also specifies rational masses \(p_t\leq\mu_t\) whose members are prescribed to choose \(+1\), corresponding to the designated players in Theorem 4.10. The question is whether there is a PSNE extending those prescriptions. A solution is an aggregate vector \(a\), together with an assignment of pure actions to the agents that realizes it and satisfies best response for every unprescribed agent.
In this model \(a_t\in[2p_t-\mu_t,\mu_t]\). If \(F_t(a)>0\), all unprescribed agents of type \(t\) choose \(+1\), so \(a_t=\mu_t\); if \(F_t(a)<0\), they all choose \(-1\), so \(a_t=2p_t-\mu_t\); if \(F_t(a)=0\), any split of the remaining mass is consistent with best response. That split is across people: no agent randomizes.
I expect the existence decision to be tractable—in fact, every valid instance has an equilibrium. For each type, let its unprescribed agents choose some mass \(q_t\) of \(+1\), with \(q_t\in[0,\mu_t-p_t]\). Their best-response correspondence sends \(q_t\) to the full interval when \(F_t=0\), to the upper endpoint when \(F_t>0\), and to zero when \(F_t<0\). The product correspondence has nonempty compact convex values and is upper hemicontinuous on the compact convex box of possible \(q\)’s, so Kakutani gives a fixed point. This works with negative as well as positive influence coefficients. Thus the NP-complete finite existence question has a genuinely different answer in this continuous-population regime. That is a substantive continuization result, though it does not show that finding an equilibrium efficiently is easy: Kakutani establishes existence, not a polynomial-time construction.
The regime I have in mind is a very large population—say, residents or platform users making a binary adoption decision—with a modest number of repeated roles or communities. Within a type, people share thresholds and their influence profile over those roles; influence is measured by exposure to the masses of each type. Population size is then much larger than the number of types, and the designated intervention is naturally a fraction of a type rather than a list of named people. This is a dense, type-block network regime: per-person interactions are scaled so that aggregate influence from a type has a finite limit. It fits the paper’s interest in large populations, strategic behavior, stable outcomes, and targeted interventions. The computational question remains about equilibria and intervention, not about diffusive dynamics or a continuous outcome space.
I think the authors could recognize this as their problem in a population-limit regime: it retains binary behavior, linear threshold responses, PSNE, signed influence, and the question of whether prescribed adopters are compatible with a stable outcome. The important qualification is that the model uses a type-level aggregate influence matrix in place of the paper’s arbitrary person-to-person graph. It is not the mirror of every LIG instance.
The main further questions are whether one can compute an equilibrium with a useful complexity bound in \(\tau=|T|\) and the input bit length; whether a given intervention yields a unique aggregate equilibrium; and how the least mass that must be committed to \(+1\) can be chosen to make a target equilibrium unique. One should also establish when equilibria of finite replicated block networks converge to equilibria of this mass model.
My weakest point is the block-network assumption. In a sparse graph where each person’s particular neighbors matter, a type may need to encode a nearly unique neighborhood or influence profile. Then \(\tau\) can grow with the population and the continuum advantage disappears. There is also a real solution-concept question: allowing indifferent people of the same type to split across actions makes equilibrium existence far easier than in the finite theorem. I think that is defensible here because each person still takes a pure action and the paper is explicitly concerned with large populations, but it is the point on which acceptance of this mirror most depends.
The strongest objection is that the proposed mirror does not quite model Theorem 4.10. The theorem asks whether a PSNE exists in which designated players choose \(+1\); those players must still be best responding. The proposed mass model instead fixes a fraction \(p_t\) at \(+1\) and exempts them from the best-response condition. That turns the designated players into committed intervention targets.
For example, take one type, set \(W=0\), \(b=1\), and prescribe \(p>0\) at \(+1\). Every agent’s field is \(-1\), so no PSNE can have those prescribed agents choosing \(+1\). Yet the proposed Kakutani argument still returns an equilibrium for the unprescribed mass. It proves existence for the clamped-intervention model, not for the condition in Theorem 4.10.
The natural repair is to require every agent, including the designated mass, to best respond, while requiring the aggregate \(+1\) mass \(q_t\) to satisfy \(q_t\ge p_t\). Then \(q_t>0\) requires \(F_t\ge0\), and \(q_t<\mu_t\) requires \(F_t\le0\). The unconditional fixed-point argument no longer applies. This repaired question is a finite-dimensional complementarity feasibility problem, but its relationship to Theorem 4.10’s hardness is no longer clear.
The harder objection is about what happens when one tries to preserve that theorem’s network structure. Its reduction uses distinct variable and clause players whose individual incidences encode the formula. In a faithful high-multiplicity model, a type must include the player’s relevant interaction profile. For such instances, that can require a type for nearly every player, leaving no population compression. Keeping only a small number of types instead imposes a block interaction structure in which agents respond to type-level totals; that is a coherent model, but it excludes the sparse, identity-specific incidence patterns on which the theorem’s reduction rests.
A graphon or continuum-network model might retain richer neighborhoods, but then one needs a finite input representation for a computational classification. Exact PSNE questions are also sensitive to the sign of fields at thresholds, so an approximate network limit alone does not preserve the decision problem. Restricting to finite-step models makes the question computable, but returns us to the block-structure restriction.
This makes a strong case against presenting the proponent’s Kakutani result as a mirror of Theorem 4.10. It does not establish that no worthwhile mirror exists. A dense, repeated-role network could make the corrected mass-compatible question sensible and authors might recognize it as a useful restricted LIG regime. That is the weak point in the negative case: the theorem’s own reduction does not support the mirror, but a plausible new type-block problem remains.
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.