Research map / Multi-agent systems and games / Games and equilibria

Network Intervention by Polling Strategic Agents

NeurIPS 2026 · Multi-agent systems and games › Games and equilibria · approach: Learning with strategic agents

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes POLL, a memory-free polling algorithm that estimates the optimal non-discriminatory price in multi-activity network games with heterogeneous private technologies via random-walk sampling, plus payment-free incentive designs (decoy signals, Knightian uncertainty) against misreporting.

Problem

A planner setting non-discriminatory prices in a network of strategic agents with private technologies must learn the welfare-optimal price without knowing the network or agents' types, while agents may misreport and exact computation does not scale.

Approach

Decomposes the welfare kernel into a sum over agents of squared Katz-Bonacich centralities in a bundle-induced network reweighted by preferences, and turns this into an unbiased stochastic estimator via sampling an agent and two independent random walks, so each query is an O(1)-communication local report; decoy signals create ambiguity that deters misreporting without payments.

Key results

• On DBLP (317,080 agents), POLL reaches welfare gap 1e-5 with 1.20e4 pairwise exchanges vs 3.80e6 for Gossip (316x), 1.23e7 for Federated (1023x), and 1.89e7 for Consensus (1572x).
• With designed decoy signals, all simulated agents (100% truthful) under ambiguity-averse maxmin preference in the m=1 synthetic setting, versus 0% truthful with no signals.
• On DBLP under theta-maxmin agents, designed signals eliminate manipulation for all theta >= 0.8 (theoretical threshold approx 0.8).

Surprising findings

• Random decoy signals alone induce roughly 50% truthful reporting because agents systematically want to understate preferences under a small network effect.
• Heterogeneity-aware query complexity is dimension-agnostic for regular graphs, but a star graph degrades the bound to scale with n^2 in the worst case.

Limitations

• Results rely on a linear-quadratic utility model.
• Payment-free incentive guarantee requires sufficient ambiguity aversion; optimistic agents (theta < 0.8) are not deterred by designed signals.
• Query complexity can degrade with network heterogeneity (e.g., star graphs), so no free lunch in general.

Experimental setup

Datasets: DBLP coauthorship network synthetic random graphs (directed hierarchical, Erdos-Renyi, approximately regular)

Benchmarks: DBLP coauthorship network (n=317,080) synthetic networks

Metrics: normalized welfare gap communication complexity (pairwise exchanges) wall-clock time mean relative error truth rate

Baselines: Exact computation Consensus Federated Gossip Random-Walk

Builds on: Katz-Bonacich centrality multi-activity network games stochastic approximation maxmin expected utility

Closest papers by meaning

• Multi-Sender Persuasion: A Computational Perspective (ICML 2024 · similarity 0.87)
• Strategic Manipulation in Temporal Voting with Undesirable Candidates (Student Abstract) (AAAI 2025 · similarity 0.86)
• Steering the Herd: A Framework for LLM-based Control of Social Learning (ICLR 2026 · similarity 0.85)
• Information Design for Congestion Games with Unknown Demand (AAAI 2024 · similarity 0.85)
• Collaborative Mean Estimation Among Heterogeneous Strategic Agents: Individual Rationality, Fairness, and Truthful Contribution (ICML 2025 · similarity 0.85)
• Trade-Offs Between Information and Crowding in Sequential Decisions (Student Abstract) (AAAI 2025 · similarity 0.85)