Optimal Welfare in Noncooperative Network Formation under Attack¶

🕒 Published (v1): 2025-11-13 23:12 UTC · Source: Arxiv · Venue: AAAI 2026 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

TL;DR¶

This paper revisits a game-theoretic model of noncooperative network formation under attack (Goyal et al., WINE 2016), where selfish agents independently decide which links to form and whether to immunize themselves. The main result proves that Nash equilibrium networks achieve asymptotically optimal social welfare of n²−O(n) under the "super-quadratic-disruptor" (SQD) attacker class—resolving a longstanding open problem. Counterintuitively, it also shows that a tailored attacker can enforce lower social welfare than the attacker explicitly optimizing for disruption.

Problem¶

The Goyal et al. 2016 model left the social welfare of Nash equilibria under the maximum disruption attacker (which minimizes post-attack welfare) as an open problem. Prior bounds were n²−O(n^{5/3}) only for connected equilibria under this attacker, while maximum carnage and random attack had the same loose bound. No tight unified bound existed for a broad attacker class, and the question of whether decentralized agents can maintain robust welfare against adversarial attackers was unresolved.

Method¶

The authors introduce the f-opponent framework: an attacker defined by a function f:ℕ→ℝ₊ that selects vulnerable regions T minimizing Uf(T,s) = Σ_{K∈K(T)} f(|K|), attacking uniformly among minimizers. Maximum carnage corresponds to f=x¹, maximum disruption to f=x².

They define super-quadratic-disruptors (SQD): f-opponents where f is strictly convex and f(x)/x² is non-decreasing. The analysis proceeds through a series of structural lemmas about Nash equilibria with SQD opponents: - Vulnerable regions in equilibrium networks are trees (from Goyal et al.). - SQD opponents are edge-averse and target large components preferentially (Corollary 2–3). - Targeted regions are singletons in components with immunized nodes (Lemma 4). - Targeted cut-vertices only arise in networks bounded by O(C_E·C_I) agents (Lemma 9). - Large enough non-trivial Nash equilibria with SQD opponents are connected (Lemma 14, via centroid argument).

For maximum carnage/random attack, the proof uses block-cut decomposition, bounding vulnerable cut-vertex path length by 2C_E+1 (Lemma 1), then applies Jensen's inequality to yield the tight bound.

Key Contributions¶

Tight optimal social welfare bound n²−O(n) for non-trivial Nash equilibria under maximum carnage and random attack (improving n²−O(n^{5/3})).
Proof that social welfare is n²−O(n) for the entire SQD attacker class, which subsumes maximum disruption—resolving the open problem.
Structural theorem: large enough Nash equilibria with SQD opponents must be connected, with targeted regions being isolated singleton nodes.
Construction of a tailored f-opponent that achieves social welfare Θ(n) in Nash equilibria—lower than the maximum disruption attacker—showing the optimality boundary is non-trivial.
Introduction of the SQD abstraction unifying multiple attacker types under a clean convexity condition.

Results¶

Attacker	Goyal et al. 2016	This paper
Maximum carnage	n²−O(n^{5/3})	n²−O(n)
Random attack	n²−O(n^{5/3})	n²−O(n)
Maximum disruption	open (n²−O(n^{5/3}) for connected only)	n²−O(n)
Tailored opponent	not considered	Θ(n) (lower bound)

All bounds are on social welfare of non-trivial Nash equilibria with C_E, C_I > 1.
The n²−O(n) bound matches the welfare in the attack-free setting, confirming asymptotic optimality.
Tailored opponent example: C_E=C_I=6, f with non-zero values only at sizes {1,7,8,9,10}; equilibrium s_bad has n−9 isolated nodes, achieving social welfare in Θ(n).

Limitations¶

Results are asymptotic; constants in O(n) terms depend on C_E and C_I and may be large for small networks.
The "tailored attacker" result raises the characterization problem of which f-functions yield suboptimal welfare—left open.
Only Nash equilibria are analyzed as the stability concept; other solution concepts (strong Nash, correlated equilibria) are not addressed here.
The model assumes a single-node attack with deterministic spread along unprotected subgraphs—a stylized model of real-world attacks.
Cooperation among agents (coalition formation) is explicitly listed as future work and not handled.

Relevance to Agentic AI / LLM Agents¶

This paper addresses multi-agent systems of strategic, self-interested agents making decentralized decisions about connectivity and security—a formal game-theoretic precursor to questions that arise in multi-agent AI architectures (e.g., peer-to-peer agent networks, federated systems, or multi-agent communication topologies). The central question—whether individually rational agents produce collectively robust structures without central coordination—is directly relevant to designing resilient agentic networks where agents independently choose communication links. The SQD attacker framework also provides formal grounding for adversarial robustness analysis in agent networks, complementing empirical red-teaming work. That said, this is a theoretical CS/economics contribution; it does not involve LLMs or learned agents, so practitioners working with LLM-based agents would engage with it primarily as foundational theory rather than immediately applicable methodology.