Paper deep dive
Network Intervention by Polling Strategic Agents
Chenyu Zhang, Rohit Parasnis, Saurabh Amin
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 90%
Last extracted: 10/7/2026, 7:48:35 AM
Summary
The paper introduces 'Poll', a distributed polling algorithm for a planner to maximize social welfare in a network of strategic agents with heterogeneous private technologies. The optimal intervention prices are characterized by a centrality-based decomposition of the welfare kernel, where each agent's contribution scales with its squared centrality in a network reweighted by preferences. Poll iteratively samples agents, performs local random walks to estimate this centrality, and updates prices. The algorithm achieves computational, learning, and economic efficiency, requiring significantly fewer operations and communication than exact or other distributed methods while ensuring truthful reporting and robustness against adversarial deviations.
Entities (6)
Relation Signals (6)
Poll → achieves → Computational Efficiency
confidence 95% · Polluses significantly fewer operations than exact computation and other distributed methods
Poll → achieves → Economic Efficiency
confidence 95% · economically, it converges to welfare-maximizing prices while admitting behavior-specific implementations that induce truthful reports
Social Welfare Kernel → decomposedby → Centrality
confidence 92% · optimal prices admit a centrality-based decomposition of the welfare kernel
Poll → uses → Katz-Bonacich Centrality
confidence 90% · The optimal prices admit a centrality-based decomposition... each agent's contribution scales with its squared centrality... This decomposition motivates Poll
Centrality Elasticity → determines → Agent Utility Sensitivity
confidence 88% · Centrality elasticity... captures how the sensitivity of an agent’s equilibrium utility to its preference is affected by network structure
Poll → testedon → DBLP Coauthorship Network
confidence 85% · On the complete DBLP coauthorship network with317,080agents,Pollreaches a near-optimal welfare
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:A planner in a network of strategic agents faces three entangled challenges: the optimum depends on agents' private information, queried agents may misreport to steer the outcome, and exact computation does not scale. We study these challenges in multi-activity network games with heterogeneous private technologies, in which the planner sets non-discriminatory prices. We show that the optimal prices admit a centrality-based decomposition of the welfare kernel: each agent's contribution scales with its squared centrality in a network reweighted by agents' preferences across activities. This decomposition motivates Poll, a polling algorithm in which the planner samples one agent per round, walks briefly through the agent's neighborhood, and updates the price from a local report. From the same decomposition flow three forms of efficiency: computationally, Poll uses significantly fewer operations than exact computation and other distributed methods, requiring up to three orders of magnitude less communication on a real-world network with over 300,000 agents; statistically, its query complexity scales with topology and preference heterogeneity rather than explicitly with population size; and economically, it converges to welfare-maximizing prices while admitting behavior-specific implementations that induce truthful reports and detect adversarial deviations.
Tags
Links
- Source: https://arxiv.org/abs/2610.08347v1
- Canonical: https://arxiv.org/abs/2610.08347v1
Trouble viewing inline? Open PDF directly →
Full Text
149,649 characters extracted from source content.
Expand or collapse full text
Intervention by Polling Strategic Agents Chenyu Zhang MIT zcysxy@mit.edu Rohit Parasnis ∗ IIT Bombay rohit@e.iitb.ac.in Saurabh Amin MIT amins@mit.edu Abstract A planner in a network of strategic agents faces three entangled challenges: the optimum depends on agents’ private information, queried agents may misreport to steer the outcome, and exact computation does not scale. We study these challenges in multi-activity network games with heterogeneous private technologies, in which the planner sets non-discriminatory prices. We show that the optimal prices admit a centrality-based decomposition of the welfare kernel: each agent’s contribution scales with its squared centrality in a network reweighted by agents’ preferences across activities. This decomposition motivatesPoll, a polling algorithm in which the planner samples one agent per round, walks briefly through the agent’s neigh- borhood, and updates the price from a local report. From the same decomposition flow three forms of efficiency: computationally,Polluses significantly fewer operations than exact computation and other distributed methods, requiring up to three orders of magnitude less communication on a real-world network with over 300,000 agents; statistically, its query complexity scales with topology and preference heterogeneity rather than explicitly with population size; and economi- cally, it converges to welfare-maximizing prices while admitting behavior-specific implementations that induce truthful reports and detect adversarial deviations. 1 Introduction Consider a government agency that wants to set subsidies for firms in an R&D sector (Schot and Steinmueller, 2018), a policymaker that must design electricity tariffs across a network of prosumers (Simshauser, 2016), or a platform that rewards users for different types of engagement (Haghtalab et al., 2025). In each case a central planner chooses a policy—prices, subsidies, or rewards—to maximize a system-wide objective such as total welfare, which represents the collective well-being of the agents affected by the policy. The agents—firms, prosumers, or users—are networked, e.g., a firm’s return on R&D depends on the innovation of its collaborators (Cohen and Levinthal, 1989). The agents are also strategic: each responds to the policy in its own interest, and each holds private information, such as its cost of investment and its technological capabilities, that the planner cannot directly observe. Networked and strategic agents appear across distributed systems, including social learning (Acemoglu et al., 2011), multi-agent control (Zhou et al., 2024), and mechanism design (Nisan and Ronen, 1999). In these settings, three challenges become tightly entangled: 1. Learning. The optimal policy depends on every agent’s private information and network position, which means that the planner can only evaluate it by querying agents. 2.Strategy. A queried agent benefits from a policy that favors it and may therefore distort its response to steer the solution toward its own preference. 3. Computation. As the number of agents grows, bottlenecks arise in time, space, communication, and adaptivity. The network coupling locks these challenges together: an agent’s manipulation strategy depends on both its private information and its network position, and the planner cannot disentangle the two ∗ Work done while at MIT 40th Conference on Neural Information Processing Systems (NeurIPS 2026). arXiv:2610.08347v1 [cs.GT] 6 Oct 2026 without simultaneously learning from reports and disciplining them. To tackle such challenges across multiple applications, we ask a fundamental question: How can the planner efficiently learn to maximize social welfare by polling strategic agents in a network? We study this question using a multi-activity network game model, in which strategic agents allocate effort across several activities and the planner sets prices for those activities. In the R&D example, an activity corresponds to a research direction, an firm’s effort represents its investment level, and the prices are government subsidies. We extend this model to allow agents to have heterogeneous utility structures, interpreted in the R&D example as private technologies, that determine both the cost of each activity and the complementarities among activities. Thus, two firms in the same network may face entirely different technological tradeoffs. This heterogeneity makes the planner’s problem genuinely network-dependent and distinguishes our model from prior multi-activity games with a common utility structure (Chen et al., 2018, Kor and Zhou, 2023, Parasnis and Amin, 2025). Under this model, we show that the answer to our research question lies in agents’ centralities in a network reweighted by their preferences across activities. This characterization motivates a polling process: the planner iteratively samples one agent, walks briefly through its neighborhood, aggregates a local preference for the proposed price change, and revises the price accordingly. Cast in optimization terms, the planner runs a stochastic iterative scheme whose gradient oracle is a strategic agent whose report may depend on its private type, its network position, and its incentive to influence the outcome. The design problem is therefore what to share, what to ask, and how to revise—given that each response may be strategically chosen. Main results. Our characterization of the planner’s optimal intervention (Section 3) gives rise to a distributed learning algorithm, Poll (Section 4), with three types of efficiency: •Computational efficiency (Section 5.1).Polluses significantly fewer operations than exact computation or other distributed methods. Lifting any memory burden from the agents,Pollalso has a much lower space and communication complexity, since agents need not store local variables or communicate with all neighbors at each iteration to update them. Additionally,Pollhas an efficient architecture: it admits fully decentralized, asynchronous, and online implementation, which promises scalability, fault tolerance, and environmental adaptability. On the complete DBLP coauthorship network with317,080agents,Pollreaches a near-optimal welfare with316–1572× fewer pairwise exchanges than other distributed methods. •Learning efficiency (Section 5.2). We show that homogeneity in network topology and in activity preferences sharply reducesPoll’s query complexity, as each response is more representative of the overall system. Our characterization further yields various natural variance reduction properties that improve learning efficiency in realistic networks. Without modification,Pollis also robust to endogenous and exogenous noise, demonstrating its statistical efficiency. •Economic efficiency (Section 5.3).Pollconverges to the intervention that maximizes social welfare under the planner’s constraints. Moreover,Polladmits strategy-proof and Byzantine- robust implementations: it induces truthful reports and detects adversarial deviations (see Table 3). Table 1: Comparison of design principles. Please refer to Section 5.1 for a detailed description of the baseline methods. Time is the total operation complexity, equal to the communication complexity up to apoly(m)factor. Space aggregates storage across all agents and the planner. All rates are asymptotic as the number of agentsn, number of activitiesm, and inverse accuracyε −1 grow large. A method is adaptive if it accommodates new agents or dynamic game structures without modifying the algorithm or restarting learning, and it is truthful if no agent has any incentive to misreport. Robustness is against endogenous noise, exogenous shocks, and adversarial deviations. MethodTimeSpaceMemory-freeAsync.AdaptiveTruthfulRobust Poll * m 2 λ −2 (1− δσ max (DG)) −2 ε −2 m""""" Exactn 3 + n 2 m 2 + nm 3 NANANANANA% Consensus † nm 2 lnε −1 nm 2 %%%"%"% Federated † nm 2 lnε −1 nm 2 %%%"%"% Gossip † nm 2 (1− λ 2 (D −1 G)) − 1 2 lnε −1 nm 2 %"""%"% Random-walk † nm 2 (1− λ 2 (D −1 G)) −2 lnε −1 nm 2 %"""%"% * See Section 5.2 for parameter definitions. † Standard formulations of these frameworks assume honest agents and therefore do not retain truthfulness or robustness in the strategic setting we study, while robust variants of each have been developed separately and lie outside this comparison. 2 These three efficiencies flow from a single source: the centrality-based characterization, which inspires the polling process, aligns the price with the polled agent’s interest, and exposes an ambiguity agents cannot resolve—information the planner withholds to encourage truth. The underlying principle extends beyond network games to other settings where the above challenges are entangled. For example, in semi-decentralized federated learning, a central server (planner) must learn a reward to improve the clients’ (agents) local models, and the optimal value of this reward depends on hidden, private data geometries; each client is strategic and may misrepresent its data profile to attract a larger reward; and the server’s computational constraints can impede constant synchronization with the clients (see Appendix C.4 for a detailed discussion). 1.1 Related work Intervention in network games. Ballester et al. (2006) connected Katz–Bonacich centrality to Nash equilibria in network games. Parise and Ozdaglar (2021) surveyed network interventions via variational inequalities. Galeotti et al. (2020) characterized optimal price intervention under a quadratic budget, with multi-activity extensions in Chen et al. (2018), Kor and Zhou (2023), Parasnis and Amin (2025). These works consider a homogeneous cost structure across agents, while we study how heterogeneous technologies compound network interactions. Dasaratha et al. (2024) studied optimal contracts with network spillovers and agent-specific instruments. All the above assume that the planner knows either the network topology or the agents’ types or both, while we consider a learning setup where the planner is unaware of the network topology and agents hold private information. Strategic distributed learning. Distributed learning with strategic agents has been studied in collaborative and federated learning (Blum et al., 2021, Chakarov et al., 2024, Donahue and Kleinberg, 2021, Dorner et al., 2023, El-Mhamdi et al., 2021, Haghtalab et al., 2025, Huang et al., 2023, Karimireddy et al., 2022, Procaccia et al., 2026), algorithmic mechanism design (Fallah et al., 2024, Feigenbaum et al., 2007, Parkes and Singh, 2003), control and optimization (Tanaka et al., 2015, Zhang and Vasal, 2021, Zhong and Angeli, 2026, Zhou et al., 2017), and performative prediction (Mendler-Dünner et al., 2020, Narang et al., 2023, Perdomo et al., 2020, Piliouras and Yu, 2023), under a range of behavioral assumptions and strategic variables. Our design draws on ambiguity aversion (Gilboa and Schmeidler, 1989), incentive design (Ba ̧sar, 1984, Ho et al., 1981), and Byzantine-robust distributed learning (Blanchard et al., 2017, Karimireddy et al., 2020, Yin et al., 2018). 2 Problem setup Consider a network ofninteracting agents (N : = 1,...,n) that engage inmactivities (M : = 1,...,m). Given a price vector p∈ R m ≥0 and an effort profile s∈ R nm , the utility of agent i is u i (s,p) =⟨s i ,p⟩− 1 2 ⟨s i ,W i s i ⟩ + P j̸=i δG ij ⟨s i ,W i s j ⟩,(1) where the first term is the revenue from a non-discriminatory (public, same for all agents) pricep and agenti’s effort levelss i ∈ R m across the activities; the second term is the cost, with different agents having distinct cost structures captured by a positive definite matrixW i ∈ R m×m , referred to as their private technologies, which governs how the agents’ activities complement each other and reflects proprietary characteristics that the agent will not disclose (e.g., R&D capabilities (Cohen and Levinthal, 1990)); the third term is the network spillover, whose strength is quantified byδ > 0; and G∈ R n×n ≥0 is the network’s adjacency matrix withG ij > 0if and only if agentjinfluences agenti, so that an agent’s ability to absorb the spillovers depends on both its technologyW i and its network position. This setup generalizes multi-activity network games (Chen et al., 2018, Kor and Zhou, 2023) by allowing heterogeneous technologies, which enriches the model and yields new insights for optimal intervention design. Remark 1. In this work, we focus on strategic complementarity: one agent’s effort increases the return to its neighbors’ effort. This spillover effect is first studied in general settings by Bulow et al. (1985), Milgrom and Roberts (1990) and later in network games by seminal works such as Ballester et al. (2006), Bramoullé et al. (2014), Galeotti et al. (2010), Jackson and Zenou (2015) for single-activity games and Chen et al. (2018) for multi-activity games. Flipping the sign ofδyields strategic substitutability. Mixed-sign spillovers give a more general model. Assumption 1 (Small network effect). The effect of network interactions is sufficiently small for δσ max (DG) < 1 to hold, where D is the diagonal degree matrix of the network. 3 Assumption 1 is analogous to standard assumptions in the network games literature (Ballester et al., 2006, Bramoullé et al., 2014, Galeotti et al., 2020, Parise and Ozdaglar, 2019) that ensure a unique Nash equilibriums ∗ (p)while guaranteeing that best-response dynamics are oscillation-free. Substituting this equilibrium into the social welfare 1 n P i u i yields the planner’s intervention problem max p∈R m ≥0 1 2 ⟨p, Φp⟩− μ 2 ⟨(p− p 0 ), Ψ(p− p 0 )⟩,(2) where Φ∈ R m×m is the social welfare kernel, defined as Φ : = 1 n (1 T n ⊗ I m )W −T ((I n − δG T ) −1 ⊗ I m )W ((I n − δG) −1 ⊗ I m )W −1 (1 n ⊗ I m ),(3) whereW : = blkdiag(W i ) ∈ R mn×mn is the block diagonal matrix withW i as thei-th diagonal block, and⊗is the Kronecker product. The second term is the planner’s cost of intervention, with its strength quantified byμ > 0,p 0 being the initial price, andΨ∈ R m×m encoding budget constraints, sustainability considerations, or prior beliefs (see Appendix B.3 for detailed modeling motivation). Assumption 2 (Sufficient regularization). We haveμΨ ≻ Φso that the objective function (2) is concave and the optimal intervention both exists and is unique. Under Assumption 2, the first-order condition gives the optimal intervention p ∗ = (I − μ −1 Ψ −1 Φ) −1 p 0 .(4) 3 A centrality-based interpretation The optimal intervention is shaped by the social welfare kernelΦ, which aggregates agents’ heteroge- neous technologies through the network (see (3)) and thus is unknown to the planner. This section characterizes the structure ofΦ, which motivates the design of our learning algorithm and underpins its efficiency guarantees. Related calculations are deferred to Appendix D. Proposition 1. Define f W i = Ψ 1/2 W i Ψ 1/2 and e Φ : = Ψ −1/2 ΦΨ −1/2 . We have e Φ = 1 n P i∈N fcen T i f W −1 i fcen i (5) wherefcen i ∈ R m×m is thei-th block 2 of Katz–Bonacich centralities of the modified network e G∈ R nm×nm : fcen = (I − δ e G) −1 (1 n ⊗ I m )∈ R (n×1)(m×m) ,where e G ij = G ij f W i f W −1 j ∈ R m×m is the ij-th block of e G∈ R (n×n)(m×m) , i.e., the modified network has matrix-valued edge weights. To elucidate Proposition 1, we make the following simplification, only in this section:Ψ = I m (so that e Φ = Φand f W i = W i ) and agents’ cost structures share the same eigenbasis, i.e., there exist an orthogonal matrixU ∈ R m×m and diagonal matricesΛ i ∈ R m×m such thatW i = U Λ i U T holds for alli∈N. We show in Appendix D.1 thatΦandfcen i also share the eigenbasisU. Then, (5) reads φ a = 1 n P i∈N fcen 2 i,a · λ −1 i,a , with fcen a = (I − δ e G a ) −1 1 n , and e G a,ij = G ij λ i,a /λ j,a ,∀a ∈ [m], whereφ a , fcen i,a ,λ i,a are thea-th eigenvalues ofΦ, fcen i ,W i , respectively;fcen i,a is also thei-th entry offcen a ∈ R n . Eacha∈ [m] : =1,...,mcorresponds to a column ofU, which specifies a linear combination of activities, referred to as an activity bundle. We also observe two comparative statics: the optimal intervention for activity bundleaincreases inφ a and an agent’s equilibrium effort in a increases in λ −1 i,a . We therefore refer to λ −1 i,a as agent i’s preference for activity bundle a. Proposition 1 now becomes clear: each activity bundleainduces a network e G a that reweighs the original network by the ratios of the interacting agents’ preferences for the bundle. The agents interact within this bundle-induced network to form an aggregate preference, weighted by their squared centralities in the bundle-induced network, which determines the optimal intervention. Bundle-induced networks assign centralities in a seemingly counter-intuitive way. First, it empowers the influenced, not the influential: an agent’s preference carries more weight when the agent receives more influence from others (high susceptibility inG). Instead of targeting specific agents, the welfare-maximizing planner targets activity bundles via a non-discriminatory price, and therefore 2 gcen i : = (e i ⊗ I m ) T gcen where e i ∈ R n is the i-th standard basis vector. 4 listens to the most susceptible agents—those that absorb the most influence. The bundle-induced network thus acts as an echo chamber that amplifies the intervention’s utility gains. Second, it favors the unfavored: an agent unwilling to engage in the bundle (low preferenceλ −1 i,a ) has greater say in the bundle-induced network. This is because agents absorb network spillovers through their own technologies (see (1)), so a high cost for a bundle implies proportionally higher compensation from neighbors’ efforts—clear in the R&D context, where a higher investment yields a higher return from an innovative community. This centrality structure is contextualized in Appendix E. 3.1 Centrality elasticity It is now clear that agents’ preferences are only half the story, as the optimal intervention also depends on their positions in the network. Consequently, without considering the network structure, one cannot ascertain whether a low-preference agent benefits more or less from intervention than a high-preference one. The following proposition captures how the sensitivity of an agent’s equilibrium utility to its preference is affected by network structure via centrality elasticity. Proposition 2. The equilibrium utility of an agenti ∈ [n]at pricepisu i (p) : = u i (s ∗ (p),p) = 1 2 ⟨p, Φ i p⟩ , where the eigenvalues ofΦ i are given byφ i,a = fcen 2 i,a λ −1 i,a . Thus,u i is monotonically increasing w.r.t. φ i,a for all a∈M. Furthermore, we have ∂ lnφ i,a ∂ lnλ i,a = 2 ∂ ln gcen i,a ∂ lnλ i,a | z centrality elasticity −1 = P j∈N\i e K a,ij P j∈N e K a,ij | z others’ contribution − e K a,i P j∈N e K a,ij | z self-contribution , where e K a : = (I − δ e G a ) −1 is the centrality matrix of the interaction network induced by a. Centrality elasticity (CE) is determined by the shares of the agent’s own and others’ contributions to its centrality. Specifically, agenti’s centrality counts the walks originating ati, and the self-contribution (resp. others’ contribution) is the fraction of these walks ending at i (resp. at other nodes). Consistent with the previous subsection, an agent that absorbs more influence from others has a high CE and thus benefits more from spillovers as it further reduces its preference for the bundle. In the R&D example, whereλ i,a is the investment cost, CE quantifies the marginal return on investment. A firm in a high-tech cluster may want to invest more in R&D to harness the innovative environment. Without such an environment, however, the investment may not justify its cost. Importantly, the decision to invest, i.e., the sign of∂ lnφ i,a /∂ lnλ i,a , flips precisely when the self- contribution and others’ contribution are equal. An agent ignorant of the network structure cannot discern these shares and thus remains uncertain whether increasing or decreasing its preference will improve its utility. This fundamental ambiguity is distinctive to the network setting and serves as a crucial lever for the planner to mitigate strategic manipulation in Section 5.3. 4 A polling algorithm We introducePoll, a distributed algorithm for computing the optimal intervention (4), motivated by the characterization in (5). Our design is driven by a need for computational efficiency: computing (4) exactly requiresO(n 3 + n 2 m 2 + nm 3 )operations, which is prohibitive when the agent population or activity space is large. Throughout, we let ν : = μ −1 and q : = Ψ 1/2 p. Step 1. Iterative communication. Equation (4) directly gives the following iterative scheme: P t+1 τ =0 ν τ e Φ τ q 0 |z q t+1 = q 0 + ν e Φ P t τ =0 ν τ e Φ τ q 0 | z q t t→∞ −→ P ∞ τ =0 ν τ e Φ τ q 0 = q ∗ .(6) Under Assumption 2, the iteration is contractive and converges to the optimal solutionq ∗ , with a computational complexity of O(n 3 + tm 2 ) after t iterations. To address theO(n 3 )computational burden of calculating e Φ, suppose at each time steptwe have an easy-to-compute estimate b Φ t of e Φ. Then, (6) is associated with the stochastic approximation scheme q t+1 = q t − α t ((I − ν b Φ t )q t − q 0 ),(7) 5 wereα t is a step size that satisfies the condition in Robbins and Monro (1951). The convergence rate of (7) depends on the bias and variance of the stochastic estimate b Φ t . Since the intervention problem is deterministic, we introduce a random variableZ t and a mapping b Φ t = b Φ(Z t )such thatE Z t b Φ(Z t ) = e Φ. The semantic characterization of e Φin (5) provides an intuitive and practical way to construct and sample Z t in a distributed and asynchronous manner. Step 2. Sample an agent. Equation (5) gives e Φ = 1 n P i∈N fcen T i f W −1 i fcen i = E i∼Unif(N ) [fcen T i f W −1 i fcen i ]. Step 3. Sample a walk length k. Expanding the centrality of agent i as a Neumann series yields fcen i = P ∞ k=0 δ k [ e G k 1] i = (1− δ) −1 E k∼Geom(δ) [ e G k 1] i , where the distribution is the geometric distribution with success probability1− δsupported on N =0, 1,..., 1 = 1 n ⊗ I m , and [·] i denotes the i-th block 2 of a matrix in R (n×1)(m×m) . Step 4. Sample a walk. We have [ e G k 1] i = P j 1 ,...,j k ∈N i e G ij 1 e G j 1 j 2 · e G j k−1 j k =E (i=j 0 ,j 1 ,...,j k ) h Q k−1 l=0 deg j l · Q k−1 l=0 e G j l j l+1 i , wheredeg j is the in-degree of nodejinG, and(i = j 0 ,...,j k )is a random walk of lengthkstarting at i in which each step samples the next agent uniformly from agent i’s incoming neighbors. Steps 2–4 interpret the composite structures in the exact characterization of e Φas expectations of random variables. Replacing these expectations with appropriately generated stochastic realizations of the corresponding random variables then yields an unbiased estimate of e Φ. Recall our construction e G ij = G ij f W i f W −1 j of the bundle-induced network e G. Suppose the original graph is unweighted (G∈0, 1 n×n ). Then the expectation in Step 4 involves a telescoping product: Q k−1 l=0 e G j l j l+1 = Q k−1 l=0 G j l j l+1 Q k−1 l=0 f W j l f W −1 j l+1 = 1· f W j 0 f W −1 j 1 f W j 1 f W −1 j 2 · f W j k−1 f W −1 j k = f W i f W −1 j k . This observation motivates us to define Z t as the random tuple Z t = i t ∼ Unif(N ),k (1) t ,k (2) t i.i.d. ∼ Geom(δ), j (1) 0 = i t ,j (1) 1 ,...,j (1) k : = j (1) k (1) t , j (2) 0 = i t ,j (2) 1 ,...,j (2) k : = j (2) k (2) t are two independent random walks , so that we have b Φ t = b Φ(Z t ) : = (1− δ) −2 Q k (1) t −1 l=0 deg j (1) l Q k (2) t −1 l=0 deg j (2) l · f W −1 j (1) k f W i t f W −1 j (2) k , along withE Z t b Φ(Z t ) = e Φ . Note that two independently generated random walks are required to obtain an unbiased estimate of the quadratic term in (5). Figure 1: Illustration ofPoll. Blue lines represent the random walks and dashed lines represent the informa- tion flow.d 1 ,d 2 are the degree infor- mation along two walks. We name our method (7–22)Poll, as our sampling process implements a distributed “polling” process to estimate the aggregated preference. Specifically, at each time step, the planner (i) selects an agent uniformly at random, (i) initiates two independent random walks starting at this agent, (i) col- lects degrees along each walk, (iv) asks the endpoint agents to compose the sample vote b Φ t q t according to their prefer- ences, and then (v) compares the sample vote with the current pricep 0 , which simulates the communication process between bundle-induced networks, to update the price intervention as in (7). Throughout the process, neither the planner nor any agent needs to know the network structure beyond its local neighborhood. Moreover, agents only report preference-price products and not their raw preferences, preserving privacy as well as reducing communication and computational cost. Figure 1 illustrates the algorithm. A detailed description of the algorithm and its implementation are provided in Appendix F. 6 5 Efficiency guarantees 5.1 Computational efficiency Throughout, we suppose that sampling a neighbor takesO(1)time andδ < √ 2/2; the latter is implied by Assumption 1 whenever some agent has an in- or out-degree at least2. The expected complexity of computing b Φ t isO((1− δ) −1 + m 2 ) = O(m 2 ), independent of the number of agents n. By contrast, computing e Φ exactly requiresO(n 3 + m 2 )time. Together,PollrequiresO(tm 2 ) operations with the number of queries t being independent of n (as characterized in Section 5.2). Beyond operational complexity,Poll, having been designed for lare-scale systems, imposes minimal resource requirements on both the planner and the agents. Agents need not maintain any local state across iterations, incurring zero memory overhead. Agents’ data (private technology) is never collected centrally. Hence, the planner only needs a total storage ofO(m)to store the price vector. The communication protocol is lightweight and fully asynchronous: for each price update, only one queried agent communicates along two random walks and with the planner. The expected total number of communication rounds isO(4(1− δ) −1 t) = O(t). As a stochastic approximation method implemented in an online manner,Pollautomatically adapts to dynamic environments and is robust to both endogenous query noise and exogenous shocks (Proposition 5). Alternatively, one can estimate Katz–Bonacich centralities by a distributed power iteration, i.e., (6) withν e Φreplaced byδ e G(Foster et al., 2001), at a cost ofO(nm 2 lnε −1 )operations for accuracyε, and then solve (15) by consensus (Nedic and Ozdaglar, 2009) or federated (McMahan et al., 2017) optimization, which repeatedly aggregate local variables across all agents and thus scale in both time and communication withn. Sampling-based centrality estimators (Lin et al., 2021) can similarly be combined with gossip (Boyd et al., 2006, Scaman et al., 2019), which randomly activates pairs of neighboring agents, or random-walk methods (Lopes and Sayed, 2007, Mao et al., 2020, Nedic and Bertsekas, 2001), which pass a single token along the network. Moreover, all these methods require agents to store and update a local centrality estimate, a memory burden that grows with the number of activities; Poll avoids these costs through sampling and memory-free queries (see Table 1). 5.2 Learning efficiency To discuss learning efficiency, we consider a system generated from an underlying distribution, consisting of both a random graph model and a random preference model. Assumption 3 (Independence). Agents’ preferences are identically distributed and the probability distribution that generates these preferences is independent of the network topology. This assumption separates the agent space and activity space: an agent’s network position carries no information about its activity preference. Nonetheless, it is sufficiently general to allow for degree correlation, preference correlation, and coupling between the two (see Table 2) since it imposes independence only on the marginal preference distribution; any two agents may still have correlated preferences that depend on their network positions. While this generality covers a wide range of real-world scenarios, it also couples statistical dependencies with the network structure, making the analysis more involved. We first give a universal guarantee for this model and then discuss how different correlation structures affect learning efficiency. Definition 1 (Preference heterogeneity). The preference heterogeneity on the activity space is σ 2 M = E∥W −1 i ∥ 2 F −∥EW −1 i ∥ 2 F , where the expectation is taken w.r.t. the preference generation. Defined as a variance,σ 2 M measures the diversity of agents’ preferences. Intuitively, when agents are diverse, the planner must query more to form a fair price, and when agents are homogeneous, a single query suffices to learn the population preference. Definition 2 (Network heterogeneity). Define the base network b G = I, degree-scaled network q G = D 1/2 GD 1/2 , and their centralitiesccen = (I − δ b G) −1 1and cen = (I − δ q G) −1 1 . Recall the original network’s centrality cen = (I − δG) −1 1. The network heterogeneity on the agent space is σ 2 N = E|ccen i cen i | 2 −|E cen 2 i | 2 = Var(cen 2 i ) + E[ccen 2 i ( cen 2 i − cen 2 i ) + cen 2 i (ccen 2 i − cen 2 i )], where the expectation is the empirical average across agents. 7 Network heterogeneity, mirroring the preference heterogeneity definition, measures the centrality dispersion of the network. It captures not only the centrality heterogeneity Var(cen 2 i ), but also how network asymmetry assigns centralities to the agents, encoded by the discrepancy amongccen i , cen i , andcen i . Consequently, even when all agents have the same centrality (e.g., in a regular graph), a random walk retains non-vanishing variance due to network asymmetry. We characterize the query complexity ofPollin terms of the constantsψ : = λ max (Ψ),ψ : = λ min (Ψ),λ : = max i∈N λ max (W i ),λ : = min i∈N λ min (W i ), andd : = sup i∈N deg i , and condition numbers κ Ψ : =ψ/ψ, κ W : =λ/λ, κ ν : = (1− νλ max ( e Φ)) −1 , and κ δ : = (1− δσ max (G)) −1 . Theorem 1 (Query complexity). Under Assumption 1–3 and a constant step sizeα = κ ν lnt/twith t/ lnt≥ max2, 4σ 2 , we have E∥p t − p ∗ ∥ 2 2 ≤ e O(t −1 ∥p ∗ ∥ 2 2 σ 2 ), where σ 2 = O ν 2 κ 2 ν κ 2 Ψ κ 2 W (σ 2 M σ 2 N + maxκ 2 δ σ 2 M ,λ −2 σ 2 N ) , where σ M and σ N are as defined in Definitions 1 and 2, respectively. The rate established in Theorem 1 matches the standard sample complexity for stochastic approx- imation (Zhang et al., 2025). The proof is deferred to Appendix G. For a well-conditioned sys- tem withκ ν ,κ Ψ ,κ W ,κ δ ,∥p ∗ ∥ 2 = O(1), using the conservative boundsσ 2 M (23) ≤ κ 2 W λ −2 and σ 2 N (29) ≤ (1−δσ max (DG)) −2 ≤ (1−δd 2 ) −2 gives a query complexity oft = O(ε −2 λ −2 (1−δd 2 ) −2 ). Theorem 1 identifies the heterogeneity levelsσ N andσ M as the bottleneck of learning efficiency, con- firming the intuition that each query is more representative when the population is more homogeneous. Importantly, σ N and σ M do not depend explicitly on the system dimension n. Remark 2 (Free lunch?). The query complexity ofPollis heterogeneity-aware but dimension- agnostic. It thus scales to large systems given controlled heterogeneity. For ad-regular graph, for instance, we haveσ 2 N ≤ (1− δd 2 ) −2 , independent ofn. However, the heterogeneity of real systems typically grows with the system size. In the worst case, a star graph hasd = nandσ max (DG) = n 2 , degrading the bound to O(ε −2 (1− δn 2 ) −2 ). Hence, no free lunch exists in general. That said,Pollis also aware of another facet of system scale: the strengths of the network effect and regularization. The discount factorsδandνcontrol the influence of the network effect and agents’ preferences, compared to the idiosyncratic component and the planner’s preference, respectively. It is therefore intuitive thatPollconcentrates its queries on learning these two components, with complexity decreasing as the network effect weakens or regularization strengthens. An exact method fails to leverage this structure. Pollenjoys variance reduction via structures common in real-world systems and via techniques suggested by our characterization in Proposition 1, catalogued in Table 2. Table 2: Variance reduction. StructureScenarioTechniqueReduction Small network effectEconomic networks (Parasnis and Amin, 2025)Control variateProp. 6 Preference correlationHerding (Acemoglu et al., 2011)Not neededProp. 7 Degree correlationAssortativity (Newman, 2018)Not neededProp. 8 Power law degreesSocial networks (Jackson, 2011)Importance samplingProp. 9 5.3 Economic efficiency To achieve economic efficiency, i.e., to maximize social welfare under the planner’s budget constraint, Pollrelies on agents reporting their preferences truthfully. A strategic agent, however, may misreport to shift the price in its favor; a malicious agent may report arbitrarily to disrupt learning altogether. Facing different agent behaviors,Pollreadily equips the planner with a dedicated device to suppress manipulation, summarized in Table 3. Payment mechanisms (Groves, 1973), the most common tool to elicit truthful reporting, require the planner to collect money after each report, which is often infeasible in practice. In this section, we instead leverage the fundamental ambiguity from Section 3.1 to deter strategic manipulation without payment; the other two devices are detailed in Appendix I. Without payment, preventing misreporting is fundamentally difficult: in the linear-quadratic game, an agent’s utility strictly increases with both the price and the reported utility kernel b Φ t in the Loewner 8 Table 3: Manipulation robustness. Approximate truth presents the asymptotic scale of the maximum deviation from the truthful price update asα t → 0. By Proposition 5, a deviation ofO(α 3/2 t )does not affect the learning complexity. BehaviorDeviceApproximate truth Ambiguity-averseKnightian uncertainty α 2 t (Prop. 3) Payoff-maximizingGroves paymentα 2 t (Prop. 10) MaliciousByzantine auditα t δ d/λ p lnm/B(Prop. 12) order (see (31)), incentivizing it to inflate its report. Hope arises from the observation that inPoll, the queried agent reports only its own preferenceW −1 i . As Section 3.1 establishes, the network topology creates a fundamental ambiguity: whether overstating or understatingW i raises the agent’s utility depends on the unknown network structure. An agent uncertain about this direction faces the risk that misreporting in the wrong direction yields a strictly lower utility than reporting truthfully. To engineer this uncertainty, the planner signals the random walk information to the queried agent before soliciting the latter’s report. The report is then combined with preference–price products from the endpoint agents to compute the price update. The planner’s strategy is to send multiple decoy signals—fictitious walk summaries not used for the actual update—and announces only that one of the signals is genuine. Unable to identify the true signal, the agent forms an uncertainty set over the possible walk outcomes. The planner’s choice of decoys controls the shape of this set. Proposition 3. Letp( c W i )be the price updated byPoll(with control variate (30)) given the agent’s reported preference c W −1 i , and u i ( c W i ) : = u i (s ∗ (p( c W i )),p( c W i )). Consider the following setup: •(One-dimensional manipulation). The agent only overstates or understates its preference by a factor ρ, i.e., c W i = ρW i , and the report must satisfy the known bounds λI ⪯ c W i ⪯λI . •(Planner’s signals). For each query, the planner sends multiple signals, one of which contains the true walk information, one of which contains degree products with meand − < (1− δ)δ −1 κ −1/2 W , and one of which contains d + > (1− δ)δ −1 κ 1/2 W . •(Agent’s uncertainty). For each signal, the agent constructs a beliefP, with the mean of the degree products equal to the signal mean, and the mean of the endpoint agents’ preferences equal to its own preference in the absence of other information. •(Maxmin utility). Given an uncertainty setC, the agent minimizes the worst-case expected regret, or equivalently, maximize the worst-case expected utility gainmax c W i min P∈C E P [u i ( c W i )−u i (W i )]. IfC contains d − and d + , the agent’s optimal strategy deviates from the truth W i by at most O(α t ). bu−u lnρ lnρ ′ lnρ ′ lnρ lnρ d ± d − d + Figure 2: Expected utility gainbu i − u i from re- porting c W i = ρW i . Solid curves are induced by signalsd − andd + . An optimistic agent selects the best case (blue) and overstates its preference; a ambiguity-averse agent selects the worst case (green) and reports truthfullyρ = 1when restricted to[ρ,ρ], but misreports when the strategy space expands to [ρ ′ ,ρ ′ ]. An agent that collapses the signals to a single belief selects the average case (dashed curve) and understates its preference (orange). The uncertainty here can be attributed to Knight (1921): the agent has no prior over the uncertainty set and cannot reduce it to a single belief. Agents with such max-min preferences are ambiguity averse (Gilboa and Schmeidler, 1989), a well-documented feature of real-world decision-making. Intuitively, Knightian uncertainty removes the incentive to misreport, as the agent does not want to regret overstating when it should have under- stated, or vice versa. Additionally, the decoy signals must be strong enough to prevent the utility gain from surfacing above zero again at large deviations. Figure 2 illustrates how different attitudes towards uncertainty lead to different reporting strategies. We restrict the focus of Proposition 3 to one- dimensional scaling and max-min utility for ease of exposition. A general manipulation space with a continuum of ambiguity attitudes is analyzed in Appendix I.2. 9 6 Numerical experiments Please refer to Appendix A for the detailed experimental setup and additional results. Synthetic data. Simulation results are illustrated in Figure 3. Figure 3a presents the scaling (wall- clock time vs. agent space size) of various methods on a directed hierarchical network, highlighting the computational efficiency ofPolland validating the discussion in Section 5.1. Figure 3b presents Poll’s query complexity across different levels of preference and network heterogeneity on a variation of the random network model in Watts and Strogatz (1998), confirming the heterogeneity-aware learning efficiency ofPoll, as discussed in Section 5.2. Figure 3c presentsPoll’s mean relative error (MRE) w.r.t. the optimal price when facing ambiguity-averse strategic agents on an approximately regular graph, given no decoy signals, random decoy signals, or carefully designed decoy signals, confirming the robustness of Poll to manipulation, as discussed in Section 5.3. (a) Scaling.(b) Heterogeneity-aware complexity.(c) Truth under uncertainty. Figure 3: Simulation results. Real-world network. We further evaluatePollon the complete DBLP coauthorship network (Yang and Leskovec, 2012) withn = 317,080authors and1,049,866edges. Authors allocate research effort across them = 10largest research communities (activities), and a funding agency sets field-level funding (prices); an author’s private technology encodes its community memberships (see Appendix A.2 for the full setup). For this experiment, we report the normalized welfare gap Gap t : = (SW(p ∗ )− SW(p t ))/(SW(p ∗ )− SW(p 0 )), which is quadratic in the price’s MRE, and measure computation by communication complexity, i.e., the number of pairwise exchanges. As Table 4 shows,Poll’s advantage is amplified on this large real-world network: it reachesGap≤ 10 −5 with316×to1572×fewer exchanges than the other distributed methods, and by the time Federated and Consensus produce their first updated iterate,Pollhas already reduced the gap below4× 10 −8 . Table 4: Communication complexity to reach a welfare gap threshold on the DBLP network. Median pairwise exchanges over three runs is reported; the deviation is under10%of the median in all cases. Exact computation is omitted due to infeasibility at this scale. Random-Walk does not reach either threshold within 10 9 exchanges. Gap threshold PollGossipFederatedConsensus 10 −5 1.20× 10 4 3.80× 10 6 (316×) 1.23× 10 7 (1023×) 1.89× 10 7 (1572×) 10 −7 5.25× 10 5 5.01× 10 6 (10×) 1.78× 10 7 (34×)2.52× 10 7 (48×) On the same network, we also stress-test the incentive guarantee with multi-dimensional reports and a continuum of ambiguity attitudes, from fully ambiguity-averse as in Proposition 3 to fully optimistic. The designed decoys are still able to elicit truthful reports for a nontrivial range of ambiguity attitudes; see Appendix A.2 for details. 7 Conclusion We derived a polling algorithm whose computational, learning, and economic efficiency all flow from one centrality-based characterization of the planner’s optimal intervention. Some of our results rest on a linear-quadratic utility, and the payment-free incentive guarantee requires sufficient ambiguity aversion. Extending to general utilities and designing decoys for more optimistic agents remain open. 10 Acknowledgments and Disclosure of Funding NSF Award Number 2039771. Directorate for Engineering, Division of Civil, Mechanical, and Manufacturing Innovation References D. Acemoglu, M. A. Dahleh, I. Lobel, and A. Ozdaglar. Bayesian learning in social networks. The Review of Economic Studies, 78(4):1201–1236, 2011. C. Ballester, A. Calvó-Armengol, and Y. Zenou. Who’s who in networks. Wanted: The key player. Econometrica, 74(5):1403–1417, 2006. T. Ba ̧sar. Affine incentive schemes for stochastic systems with dynamic information. SIAM Journal on Control and Optimization, 22(2):199–210, 1984. R. Belderbos, P. A. Mohnen, et al. Inter-sectoral and international R&D spillovers. Maastricht Economic and Social Research Institute on Innovation and . . . , 2020. S. Bhaumik, N. Driffield, K. Lavoratori, M. Song, and P. Vahter. Multinational strategy, institutions and spillovers: the role of institutions in knowledge spillovers in emerging markets. The Journal of Technology Transfer, 50(5):2476–2508, 2025. P. Blanchard, E. M. El Mhamdi, R. Guerraoui, and J. Stainer. Machine learning with adversaries: Byzantine tolerant gradient descent. Advances in neural information processing systems, 30, 2017. A. Blum, N. Haghtalab, R. L. Phillips, and H. Shao. One for one, or all for all: Equilibria and optimality of collaboration in federated learning. In International Conference on Machine Learning, pages 1005–1014. PMLR, 2021. S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah. Randomized gossip algorithms. IEEE transactions on information theory, 52(6):2508–2530, 2006. Y. Bramoullé, R. Kranton, and M. D’amours. Strategic interaction and networks. American Economic Review, 104(3):898–930, 2014. J. I. Bulow, J. D. Geanakoplos, and P. D. Klemperer. Multimarket oligopoly: Strategic substitutes and complements. Journal of Political economy, 93(3):488–511, 1985. D. Chakarov, N. Tsoy, K. Minchev, and N. Konstantinov. Incentivizing truthful collaboration in heterogeneous federated learning. arXiv preprint arXiv:2412.00980, 2024. Y.-J. Chen, Y. Zenou, and J. Zhou. Multiple activities in networks. American Economic Journal: Microeconomics, 10(3):34–85, 2018. F. Chung and L. Lu. The average distances in random graphs with given expected degrees. Proceed- ings of the National Academy of Sciences, 99(25):15879–15882, 2002. W. M. Cohen and D. A. Levinthal. Innovation and learning: The two faces of R & D. The economic journal, 99(397):569–596, 1989. W. M. Cohen and D. A. Levinthal. Absorptive capacity: a new perspective on organization and learning. Administrative Science Quarterly, 35(1):128–152, 1990. K. Dasaratha, B. Golub, and A. Shah.Incentive design with spillovers.arXiv preprint arXiv:2411.08026, 2024. K. Donahue and J. Kleinberg. Model-sharing games: Analyzing federated learning under voluntary participation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 5303–5311, 2021. F. E. Dorner, N. Konstantinov, G. Pashaliev, and M. Vechev. Incentivizing honesty among competitors in collaborative learning and optimization. Advances in Neural Information Processing Systems, 36:7659–7696, 2023. 11 M. Duckworth, G. Serdarevic, and D. de Hita. FRAND or Foe? Regulating access for gigabit infrastructure, 2024. E. M. El-Mhamdi, S. Farhadkhani, R. Guerraoui, A. Guirguis, L.-N. Hoang, and S. Rouault. Col- laborative learning in the jungle (decentralized, Byzantine, heterogeneous, asynchronous and nonconvex learning), 2021. A. Fallah, M. Jordan, and A. Ulichney. Fair allocation in dynamic mechanism design. Advances in Neural Information Processing Systems, 37:125935–125966, 2024. J. Feigenbaum, M. Schapira, and S. Shenker. Distributed algorithmic mechanism design. Algorithmic Game Theory, 14:363–384, 2007. K. C. Foster, S. Q. Muth, J. J. Potterat, and R. B. Rothenberg. A faster Katz status score algorithm. Computational & Mathematical Organization Theory, 7(4):275–285, 2001. A. Galeotti, S. Goyal, M. O. Jackson, F. Vega-Redondo, and L. Yariv. Network games. The review of economic studies, 77(1):218–244, 2010. A. Galeotti, B. Golub, and S. Goyal. Targeting interventions in networks. Econometrica, 88(6): 2445–2471, 2020. P. Ghirardato, F. Maccheroni, and M. Marinacci. Differentiating ambiguity and ambiguity attitude. Journal of Economic Theory, 118(2):133–173, 2004. I. Gilboa and D. Schmeidler. Maxmin expected utility with non-unique prior. Journal of mathematical economics, 18(2):141–153, 1989. T. Groves. Incentives in teams. Econometrica: Journal of the Econometric Society, pages 617–631, 1973. N. Haghtalab, M. Qiao, and K. Yang. Platforms for efficient and incentive-aware collaboration. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2607–2628. SIAM, 2025. R. J. R. K. Heijmans. Unraveling coordination problems. arXiv preprint arXiv:2307.08557, 2023. Y.-C. Ho, P. Luh, and R. Muralidharan. Information structure, Stackelberg games, and incentive controllability. IEEE Transactions on Automatic Control, 26(2):454–460, 1981. B. Huang, S. P. Karimireddy, and M. I. Jordan. Evaluating and incentivizing diverse data contributions in collaborative learning. arXiv preprint arXiv:2306.05592, 2023. M. O. Jackson. Social and Economic Networks. Princeton University Press, Princeton, N.J. Wood- stock, 2011. ISBN 978-0-691-14820-5. M. O. Jackson and Y. Zenou. Games on networks. In Handbook of game theory with economic applications, volume 4, pages 95–163. Elsevier, 2015. S. P. Karimireddy, L. He, and M. Jaggi. Byzantine-robust learning on heterogeneous datasets via bucketing. arXiv preprint arXiv:2006.09365, 2020. S. P. Karimireddy, W. Guo, and M. I. Jordan. Mechanisms that incentivize data sharing in federated learning. arXiv preprint arXiv:2207.04557, 2022. F. H. Knight. Risk, Uncertainty and Profit, volume 31. Houghton Mifflin, 1921. A. M. Knott. R&D/returns causality: Absorptive capacity or organizational IQ. Management Science, 54(12):2054–2067, 2008. R. Kor and J. Zhou. Multi-activity influence and intervention. Games and Economic Behavior, 137: 91–115, 2023. S. Li. Obviously strategy-proof mechanisms. American Economic Review, 107(11):3257–3287, 2017. 12 M. Lin, W. Li, L. J. Song, C.-T. Nguyen, X. Wang, and S. Lu. SAKE: Estimating Katz centrality based on sampling for large-scale social networks. ACM Transactions on Knowledge Discovery from Data (TKDD), 15(4):1–21, 2021. C. G. Lopes and A. H. Sayed. Incremental adaptive strategies over distributed networks. IEEE transactions on signal processing, 55(8):4064–4077, 2007. X. Mao, K. Yuan, Y. Hu, Y. Gu, A. H. Sayed, and W. Yin. Walkman: A communication-efficient random-walk algorithm for decentralized optimization. IEEE Transactions on Signal Processing, 68:2513–2528, 2020. M. Marinacci. Probabilistic sophistication and multiple priors. Econometrica, 70(2):755–764, 2002. P. V. Marsden. Network data and measurement. Annual Review of Sociology, 16(1):435–463, 1990. B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas. Communication-efficient learning of deep networks from decentralized data. In Artificial Intelligence and Statistics, pages 1273–1282. PMLR, 2017. C. Mendler-Dünner, J. Perdomo, T. Zrnic, and M. Hardt. Stochastic optimization for performative prediction. Advances in Neural Information Processing Systems, 33:4929–4939, 2020. P. Milgrom and J. Roberts. Rationalizability, learning, and equilibrium in games with strategic complementarities. Econometrica: Journal of the Econometric Society, pages 1255–1277, 1990. A. Narang, E. Faulkner, D. Drusvyatskiy, M. Fazel, and L. J. Ratliff. Multiplayer performative prediction: Learning in decision-dependent games. Journal of Machine Learning Research, 24 (202):1–56, 2023. A. Nedic and D. P. Bertsekas. Incremental subgradient methods for nondifferentiable optimization. SIAM Journal on Optimization, 12(1):109–138, 2001. A. Nedic and A. Ozdaglar. Distributed subgradient methods for multi-agent optimization. IEEE Transactions on automatic control, 54(1):48–61, 2009. M. E. J. Newman. The structure and function of complex networks. SIAM review, 45(2):167–256, 2003. M. E. J. Newman. Networks. Oxford University Press, second edition edition, 2018. N. Nisan and A. Ronen. Algorithmic mechanism design. In Proceedings of the thirty-first annual ACM symposium on Theory of computing, pages 129–140, 1999. R. Parasnis and S. Amin. Optimal interventions in coupled-activity network games: Application to sustainable forestry. In 2024 IEEE 63rd Conference on Decision and Control (CDC), pages 4706–4711. IEEE, 2024. R. Parasnis and S. Amin. Incentive design for sustainable behavior in coupled-activity economic networks. Available at SSRN 5359432, 2025. F. Parise and A. Ozdaglar. A variational inequality framework for network games: Existence, uniqueness, convergence and sensitivity analysis. Games and Economic Behavior, 114:47–82, 2019. F. Parise and A. Ozdaglar. Analysis and interventions in large network games. Annual Review of Control, Robotics, and Autonomous Systems, 4(1):455–486, 2021. D. C. Parkes and S. Singh. An MDP-based approach to online mechanism design. Advances in neural information processing systems, 16, 2003. J. Perdomo, T. Zrnic, C. Mendler-Dünner, and M. Hardt. Performative prediction. In International Conference on Machine Learning, pages 7599–7609. PMLR, 2020. G. Piliouras and F.-Y. Yu. Multi-agent performative prediction: From global stability and optimality to chaos. In Proceedings of the 24th ACM Conference on Economics and Computation, pages 1047–1074, 2023. 13 A. Procaccia, H. Shao, and I. Shapira. Incentives in federated learning with heterogeneous agents. In International Conference on Learning Representations, volume 2026, pages 41643–41669, 2026. H. Robbins and S. Monro. A stochastic approximation method. The annals of mathematical statistics, pages 400–407, 1951. K. Scaman, F. Bach, S. Bubeck, Y. T. Lee, and L. Massoulié. Optimal convergence rates for convex distributed optimization in networks. Journal of Machine Learning Research, 20(159):1–31, 2019. J. Schot and W. E. Steinmueller. Three frames for innovation policy: R&D, systems of innovation and transformative change. Research policy, 47(9):1554–1567, 2018. P. Simshauser. Distribution network prices and solar PV: Resolving rate instability and wealth transfers through demand tariffs. Energy Economics, 54:108–122, 2016. T. Tanaka, F. Farokhi, and C. Langbort. Faithful implementations of distributed algorithms and control laws. IEEE Transactions on Control of Network Systems, 4(2):191–201, 2015. D. J. Watts and S. H. Strogatz. Collective dynamics of ‘small-world’networks. nature, 393(6684): 440–442, 1998. J. Yang and J. Leskovec. Defining and evaluating network communities based on ground-truth. In Proceedings of the ACM SIGKDD workshop on mining data semantics, pages 1–8, 2012. D. Yin, Y. Chen, R. Kannan, and P. Bartlett. Byzantine-robust distributed learning: Towards optimal statistical rates. In International Conference on Machine Learning, pages 5650–5659. Pmlr, 2018. C. Zhang and N. Azizan. Personalized collaborative learning with affinity-based variance reduction. In International Conference on Learning Representations, volume 2026, pages 31571–31612, 2026. C. Zhang, H. Wang, A. Mitra, and J. Anderson. Finite-time analysis of on-policy heterogeneous federated reinforcement learning. In International Conference on Learning Representations, volume 2024, pages 501–545, 2024. C. Zhang, X. Chen, and X. Di. Stochastic semi-gradient descent for learning mean field games with population-aware function approximation. In International Conference on Learning Representa- tions, volume 2025, pages 42202–42249, 2025. M. Zhang and D. Vasal. Mechanism design for large scale network utility maximization. In 2021 55th Annual Conference on Information Sciences and Systems (CISS), pages 1–6. IEEE, 2021. T. Zhong and D. Angeli. A truthful mechanism design for distributed optimisation algorithms in networks with self-interested agents. Automatica, 184:112727, 2026. F. Zhou, C. Zhang, X. Chen, and X. Di. Graphon mean field games with a representative player: Analysis and learning algorithm. In International Conference on Machine Learning. PMLR, 2024. P. Zhou, W. Wei, K. Bian, D. O. Wu, Y. Hu, and Q. Wang. Private and truthful aggregative game for large-scale spectrum sharing. IEEE Journal on Selected Areas in Communications, 35(2):463–477, 2017. 14 Appendix Table of Contents A Additional numerical experiments16 A.1 Synthetic data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .16 A.2 Real-world network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17 B General problem setup19 B.1 Nash equilibrium . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .19 B.2 Specific structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .20 B.3 Optimal intervention . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .21 C Motivations22 C.1 Public price and private technology . . . . . . . . . . . . . . . . . . . . . . . .22 C.2 Absorptive capacity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .23 C.3 Non-discriminatory subsidy/tax . . . . . . . . . . . . . . . . . . . . . . . . . .23 C.4 Semi-decentralized federated learning . . . . . . . . . . . . . . . . . . . . . . .23 D Derivations of solution characterizations25 D.1 Bundle-induced networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . .25 D.2 Planner-informed second-stage communication . . . . . . . . . . . . . . . . . .26 D.3 Proof of Proposition 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .26 D.4 Proof of Proposition 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .27 E Centrality simulations27 F Implementation details of Poll29 G Proofs of learning efficiency31 H Variance reduction35 H.1 Control variate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .35 H.2 Preference correlation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .36 H.3 Degree correlation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .37 H.4 Power law and importance sampling . . . . . . . . . . . . . . . . . . . . . . .39 IProofs of economic efficiency42 I.1Groves payment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .42 I.2Knightian uncertainty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .44 I.3Byzantine audit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .46 15 A Additional numerical experiments A.1 Synthetic data Setup. We focus on the simplified setting ofΨ = U = I m . The preferences are generated as follows: a base preferenceλ a ∼ Unif[2, 4]is drawn independently for each activitya, and each agent’s preference for activityais generated asλ i,a = λ a + ε i,a , withε i,a ∼ Unif[−σ M , +σ M ]. Then the preference heterogeneity is of scaleσ 2 M . All experiments are averaged over 10 runs with different random seeds, and the interquartile range is plotted for all curves. All experiments are implemented in Python and run on a MacBook Pro with Apple M1 Pro chip and 16GB RAM. Computational efficiency. This experiment inspects how the operation complexity of different methods scales with the system sizen. We focus on an activity space dimensionm = 10and three random graph models: directed hierarchical network (Figure 3a), Erd ̋ os–Rényi (ER) model (Figure 4a), and approximately regular graph (Figure 4b). The directed hierarchical network is generated as ak-ary tree with leaf nodes randomly connected with each other to ensure connectivity. The ER model is generated with edge probabilityk/n. The approximately regular graph starts with a k-regular graph, and then each edge is rewired with probability 0.05. For this experiment, we set k = 10andσ M = 0.05.δandμare calculated after the graph is generated to ensure the small network effect and sufficient regularization conditions. The mean relative error (MRE) tolerance is set to10 −3 for all methods except the exact method. For other distributed methods, the power iteration (Foster et al., 2001) is used to compute the Katz–Bonacich centrality, asychronously with the price updates. We observe that among all scenarios,Pollis the only method whose operation complexity does not scale withn; other methods’ complexities all have a polynomial dependence on n, with the exact method scaling the worst at O(n 3 ). (a) Erd ̋ os–Rényi(b) Approximately regular Figure 4: Further scaling. Learning efficiency. This experiment inspects how different levels of preference and network heterogeneity affectPoll’s query complexity. We focus on an activity space dimensionm = 10 and a directed variation of the network in Watts and Strogatz (1998): start with a directedk-regular ring, with each nodeihas out-edges to(i + 1) mod n,..., (i + k/2) mod nand in-edges from (i− k/2) mod n,..., (i− 1) mod n, and then each edge is rewired with probability (w.p.)p; when rewiring, w.p.1/2the outgoing end is rewired to ajw.p. proportional ton + 1− j, and w.p.1/2 the incoming end is rewired to ajw.p. proportional toj + 1. Parameterpcontrols the network heterogeneity, withp = 0giving a regular ring network and a largerpgiving a larger degree heterogeneity, centrality heterogeneity, and network asymmetry.k = 10and the tolerance is set to10 −3 for this experiment. The results reported in Figure 3b confirm that the query complexity increases with both preference and network heterogeneity. We remark that, however,pis just a proxy for the network heterogeneity σ M , but not exactly equivalent. Economic efficiency. This experiment inspects how different signals affectPoll’s performance facing ambiguity-averse strategic agents. For simplicity, we focus on an activity space dimension m = 1, and an approximately10-regular graph withn = 1000nodes (results on an ER graph G(n, 10/n)and on a directed Watts–Strogatz graph with nominal mean out-degree10are similar and thus omitted). Proposition 3 argues that the decoy signals should be designed according toδ 16 andκ W (controlled byσ M in our setup and calculated after the preferences are realized). Thus, we varyδandσ M to inspect the performance under different signals: no signal, random signals, and carefully designed signals. Agents have a maxmin preference specified in Proposition 3 and always have the incentive to misreport without signals. A random signal is generated asd r = (1− δ)δ −1 κ withlnκ ∼ Unif[− lnκ W , lnκ W ]. Therefore, w.p.0.5 × 0.5, two random signals satisfy the conditions of well-designed signals. The results are reported in Table 5. We observe that random signals induce 50% truthful reporting. This is because agents systematically want to understate their preferences, and thus a sufficiently strong one-directional signal is able to deter misreporting. This universal tendency is due to a small network effect, where agents believe their self-contribution to their centrality dominates others’ contribution (see Section 3.1). As the network effect strengthens, the agent’s belief becomes more balanced and the misreporting behavior becomes more uniform. However, a larger δ also increases the variance of the method and thus the query complexity. Table 5:Pollperformance and misreporting behaviors under different signals. The mean relative error (MRE) is averaged over the last 100 iterations of the total 3000 iterations. "T", "O", and "U" represent "truthful", "overstated", and "understated" respectively. δ σ M No signalRandom signalsDesigned signals MRET / O / U (%)MRET / O / U (%)MRET / O / U (%) 0.01 1.02.22e-010 / 0 / 1009.92e-0259 / 0 / 411.75e-03100 / 0 / 0 1.53.77e-010 / 0 / 1001.69e-0159 / 0 / 412.26e-03100 / 0 / 0 2.05.93e-010 / 0 / 1002.67e-0158 / 0 / 422.94e-03100 / 0 / 0 2.59.43e-010 / 0 / 1004.23e-0157 / 0 / 433.83e-03100 / 0 / 0 3.02.27e+000 / 0 / 1009.50e-0156 / 0 / 445.71e-03100 / 0 / 0 0.03 1.01.16e-010 / 3 / 975.19e-0259 / 1 / 401.22e-02100 / 0 / 0 1.52.02e-010 / 2 / 979.08e-0258 / 1 / 411.20e-02100 / 0 / 0 2.03.19e-010 / 2 / 981.44e-0157 / 1 / 411.18e-02100 / 0 / 0 2.55.04e-010 / 2 / 982.29e-0156 / 2 / 421.14e-02100 / 0 / 0 3.01.09e+000 / 2 / 984.85e-0155 / 2 / 431.14e-02100 / 0 / 0 0.05 1.08.60e-020 / 9 / 915.01e-0259 / 4 / 378.94e-02100 / 0 / 0 1.51.30e-010 / 10 / 904.75e-0257 / 5 / 389.40e-02100 / 0 / 0 2.01.97e-010 / 10 / 905.26e-0255 / 6 / 399.94e-02100 / 0 / 0 2.52.91e-010 / 11 / 897.42e-0253 / 7 / 401.06e-01100 / 0 / 0 3.05.17e-010 / 11 / 891.70e-0150 / 9 / 411.16e-01100 / 0 / 0 A.2 Real-world network Setup. We use the complete DBLP coauthorship network (Yang and Leskovec, 2012), which contains n = 317,080authors and1,049,866undirected coauthorship edges, with an average degree of6.62. Authors are agents, and them = 10largest ground-truth research communitiesC 1 ,...,C m are activities. Agentichooses its research efforts i ∈ R m across these communities, while a funding agency (the planner) sets a common vector of field-level fundingp ∈ R m ≥0 . We model agenti’s private technology as W i = I m + diag 1i /∈C a , so that membership in a community represents a lower effort cost, or equivalently a higher preference, for that field; in particular,κ W = 2. The resulting utility is exactly (1). For intervention, we setΨ = I m ,δ = 5 max i,a λ i,a [Gλ −1 a ] i −1 withλ −1 a : = (λ −1 i,a ) i∈N ,μ = 25 max a φ a , andp 0 ∼ Unif[0, 1] m . All modeling choices were fixed before implementing the methods or running the experiments. Metrics. We report the normalized social welfare gap Gap t = SW(p ∗ )− SW(p t ) SW(p ∗ )− SW(p 0 ) , which is quadratic in the MRE∥p t − p ∗ ∥ 2 /∥p ∗ ∥ 2 used in Appendix A.1, since the social welfare is quadratic in the price. Computation is measured by communication complexity, i.e., the number 17 of bidirectional pairwise exchanges. This is a close proxy for wall-clock time, as each pairwise exchange takes comparable time across methods, while more directly revealing the communication burden. Exact computation is infeasible at this scale and is omitted. Computational efficiency. All baselines use sparse adjacency representations, and we sweep method- specific hyperparameters to select the best step size for each method. We report tail-averaged iterates forPolland Random-Walk, the last iterate for the deterministic Federated and Consensus methods, and the globally averaged last iterate for Gossip. Table 4 and Figure 5 report the communication complexity required to reach a given welfare gap and the welfare gap attained with an increasing number of communication rounds, respectively. At the threshold10 −5 ,Pollreduces communication by factors of1572×,1023×, and316×relative to Consensus, Federated, and Gossip, respectively; at the stricter threshold10 −7 , the factors remain48×,34×, and10×. When the synchronous methods first produce an updated iterate (Federated at1,366,946exchanges and Consensus at2,099,732 exchanges),Pollhas already reduced the welfare gap to3.15× 10 −8 and2.51× 10 −8 , respectively. Federated eventually converges to machine precision through deterministic, synchronous full- population aggregation, whereasPolldelivers a near-optimal solution much sooner through stochas- tic, asynchronous updates. The relevant practical comparison is therefore how much communication each method needs to attain a welfare gap already negligible to the planner. Figure 5: Welfare gap attained versus communication rounds on the DBLP network. Economic efficiency. We extend the manipulation experiment of Appendix A.1 to the DBLP network in two ways. First, agents may manipulate their reports along allmactivities; following Remark 5, Pollqueries one activity at a time, which prevents an agent from coordinating its reports across activities and reduces each query to a one-dimensional manipulation problem. Second, agents follow theθ-maxmin preference (Definition 3) withθ ∈ [0, 1], which interpolates between fully optimistic (θ = 0) and fully ambiguity-averse (θ = 1) attitudes. In this experiment, each agent has only one profitable manipulation direction per activity: either to claim a community membership it does not have, or to disclaim one it has. We run500,000 Polliterations for each of10random seeds and report the seed-median welfare gap and the truth rate (fraction of truthful reports). Besides the designed and random signals of Appendix A.1, we consider polarized signals. Since each agent has a single profitable manipulation direction, the planner can construct two polarized signal sets:C − deters claiming a membership the agent does not have but may encourage disclaiming one it has, andC + has the opposite effect. Without any knowledge of the queried agent, the planner selects each set with probability 1/2. Figure 6 shows that the designed signals eliminate manipulation for allθ ≥ 0.8, extending the maxmin guarantee of Proposition 3 to a nontrivial range of ambiguity attitudes. This matches Proposition 11: substitutingκ W = 2, fixingd − = 1, the choiced + = p 2.5(1− δ) 2 /δ 2 − 1 used here balances the two conditions and gives θ ∗ = 0.8 + 6δ 2 25(1− δ) 2 − 20δ 2 ≈ 0.8 for small δ. For more optimistic agents (θ < 0.8), the designed signals fail because they not only signal the worst case in both manipulation directions but also amplify the best case, which an optimistic agent 18 0.00.20.40.60.81.0 Ambiguity attitude 0.0 0.2 0.4 0.6 0.8 1.0 Truth rate 0.00.20.40.60.81.0 Ambiguity attitude 10 5 10 4 10 3 10 2 10 1 10 0 Welfare gap No decoyDesigned decoysRandom decoysPolarized 50/50 Figure 6: Overall truth rate and tail welfare gap on the DBLP network underθ-maxmin agents, reported as seed medians over ten runs. exploits. Random signals partially avoid this and retain non-vacuous deterrence: since each agent has a single profitable manipulation direction, two random signals may simultaneously encourage truth and discourage the profitable misreport. Polarized signals make the reporting behavior insensitive to the ambiguity attitude, as their effect depends only on whether the selected signal set matches the agent’s profitable manipulation direction. As a compromise, polarized signals outperform uniform randomization in the optimistic regime (θ ≤ 0.7) but underperform it in the pessimistic regime (θ ≥ 0.8). Both randomizations are alternative distributions over the decoy signals of Proposition 3 rather than standalone mechanisms, illustrating how the same design principle accommodates different ambiguity attitudes. B General problem setup This section extends Section 2 to consider general multi-activity network games (MANGs) and derives their Nash equilibrium and optimal intervention. We also summarize the notation used in the main text and appendix in Table 6. We consider a collection of agents (agent space, not necessarily finite)Nand a collection of activities (activity space, not necessarily finite)M. In an MANG, each agenti∈Nspecifies its non-negative effort level on each activitya ∈ M, giving a strategy profilesin the strategy spaceS ⊂ R N×M . The general form of agent i’s utility given strategy s∈S is given by u i (p,s) =⟨p(i,·),s(i,·)⟩ M +⟨s(i,·), (Qs)(i,·)⟩ M , wherep ∈ R N×M ≥0 is the marginal price,Q ∈ L(N ×M)is a linear operator that specifies the interaction between agents and activities, and⟨·,·⟩ M is the inner product over the activity space. Thus, a quadratic multi-activity network game is specified by tuple(N,M,S,p,Q). For a function f onN ×M, we sometimes use the notation f i,a = f (i,a) for brevity. Remark 3 (General agent space and coaltion). Although having a similar form, MANG is not equivalent to a network game on the general agent spaceN ×M, where each agent specifics a scalar efforts i,a and gets a payoffu i,a (p,s) = p i,a s i,a +s i,a (Ms) i,a . Because in the latter case, calculating the best response involves competition between different activities for eachi∈N, while in a MANG, competition only happens between different agents. In other words, if we treat each agent-activity pair as a player in MANG, then fully cooperative coalitions will be formed between(i,a) a∈M for eachi∈N. This viewpoint also helps us tackle strategic manipulation in Appendix I.2 where we need to break the potential coalition. In summary, the distinction between the agent space and the activity space in MANGs is crucial. B.1 Nash equilibrium To calculate the best response, we decompose Q as Q((i,a), (i ′ ,a ′ )) = Q((i,a), (i ′ ,a ′ ))1i = i ′ | z Q I,n +Q((i,a), (i ′ ,a ′ ))1i̸= i ′ |z Q C . 19 Table 6: Notation. SymbolDescriptionSymbolDescription aactivity indexαstep size Brandom walk batch sizeβimportance sampling exponent Cuncertainty setχByzantine audit report Ddegree matrixδnetwork effect strength ddegree productεerror Ffiltrationγpower law exponent f,g,hfunctionιsmall probability Gnetwork adjacency matrixκcondition number i,jagent indexλ, Λeigenvalue(s) of activity kernel KKatz–Bonacich centrality matrixμregularization strength kwalk lengthνregularization strength inverse lwalk step indexΦutility/social welfare kernel Mactivity spaceφ utility/social welfare kernel eigenvalue Maverage preferenceΨplanner’s activity kernel mnumber of activitiesρmisreport factor Nagent spaceσ 2 variance nnumber of agentsτ,ttime step Pbeliefξrandom walk p,qprice Rregret rcorrelation function Sstrategy space sstrategy/effort Uunitary eigenbasis uutility vpayment Wactivity kernel/technology Zrandom element That is,Q I,n , which is not necessarily symmetric, consists of the diagonal “blocks” capturing the idiosyncratic effects, whileQ C consists of the off-diagonal “blocks” capturing the network effects. Then, we have ∂(Q C s) i ∂s i = 0 and ∂(Q I,n s) i ∂s i = Q I,n . DefineQ I = −(Q I,n + (Q I,n ) H ), whereHis the Hermitian transpose;Q I is self-adjoint. We generalize the small network effect assumption in Assumption 1: Assumption 4 (Concave utility and small network effect).Q I is positive definite so the utility is concave ins i . The network effect is sufficiently small such thatQ I ≻ 1 2 (Q C + (Q C ) H )and thus Q I − Q C is invertible. Therefore, for an unbounded strategy spaceS = R N×M , the first-order condition (FOC) gives a unique Nash equilibrium under Assumption 4: ∂u i ∂s i = p i + ((Q I,n + (Q I,n ) H )s) i + (Q C s) i = 0 =⇒ s ∗ (p) = (Q I − Q C ) −1 p.(8) B.2 Specific structures When the agent and action spaces are finite with|N| = nand|M| = mand the game kernelQhas a tensor (Kronecker) structure:Q = (− 1 2 I n + δG)⊗ W, whereG∈ R n×n is the adjacency matrix of an agent network without self-loop,δ > 0is a small constant capturing the network effect strength, and W ∈ R m×m is the symmetric activity interaction matrix. This tensor structure indicates that all agents share the same activity interaction kernelW, and all activities share the same agent interaction network G. Then, the utility function becomes u i (p,s) = X a∈M p i,a s i,a − 1 2 X a,a ′ ∈M W a,a ′ s i,a s i,a ′ + δ X a,a ′ ∈M,i ′ ∈N W a,a ′ G i,i ′ s i,a s i ′ ,a ′ .(9) 20 This reduces to the MANGs considered in Chen et al. (2018), Kor and Zhou (2023), Parasnis and Amin (2024). However, we will see later that if we consider a non-discriminatory intervention, the tensor structure will obscure the network effect in intervention. As motivated in Section 1 and Appendix C, it is more realistic to model agents having heterogeneous technologyW i i∈N . Modifying (9), we have u i (p,s) = X a∈M p i,a s i,a − 1 2 X a,a ′ ∈M W i,a,a ′ s i,a s i,a ′ + δ X a,a ′ ∈M,i ′ ∈N W i,a,a ′ G i,i ′ s i,a s i ′ ,a ′ = X a∈M p i,a s i,a − X a,a ′ ∈M W i,a,a ′ 1 2 s i,a s i,a ′ − δ X i ′ ∈N G i,i ′ s i,a s i ′ ,a ′ ! . Concisely, we have Q = blkdiag(W i )((− 1 2 I n + δG)⊗ I m ).(10) Notably,Qno longer has a tensor structure onN ×M. We remark that in this case, even ifW i and G are symmetric, Q may not be symmetric. Plugging (10) into (8) gives s ∗ (p) = (blkdiag(W i )((I n − δG))⊗ I m )) −1 (1 n ⊗ p),(11) which is the one used in the main text and subsequent sections. B.3 Optimal intervention Suppose the agent space has a finite measure|N| = n. Given the closed-form expression (8) of the Nash equilibrium, the social welfare function is also quadratic in p: Z i∈N u i (s ∗ ,p)di =⟨p,s ∗ ⟩ N×M − 1 2 s ∗ ,Q I s ∗ N×M + s ∗ ,Q C s ∗ N×M = 1 2 s ∗ ,Q I s ∗ N×M = 1 2 p, (Q I − Q C ) −H Q I (Q I − Q C ) −1 p N×M , where⟨·,·⟩ N×M is the inner product over the whole spaceN ×M. Suppose the price is non- discriminatory, i.e., all agents face the same price for each activity. With a slight abuse of notation, let p∈ R M ≥0 be this public price. Then, 1 n Z i∈N u i (s ∗ ,p)di = 1 2 1 N ⊗ p, 1 n (Q I − Q C ) −H Q I (Q I − Q C ) −1 (1 N ⊗ p) N×M = 1 2 (1 N ⊗ I M )p, 1 n (Q I − Q C ) −H Q I (Q I − Q C ) −1 (1 N ⊗ I M )p N×M = 1 2 p, 1 n (1 N ⊗ I M ) H (Q I − Q C ) −H Q I (Q I − Q C ) −1 (1 N ⊗ I M ) |z Φ p M , where1 N is the identity elementN,I M is the identity operator onM, and1 N ⊗ I M : M → N ×M,p7→ 1 N ⊗ p. Plugging (10) into the expression of Φ gives (3). The social planner proposes a non-discriminatory pricepto maximize social welfare with a reg- ularization that encodes the planner’s preferencesΨ ∈ L(N ×M)and ensures the objective is concave: u 0 (p) = 1 2 ⟨p, Φp⟩ M − μ 2 ⟨p− p 0 , Ψ(p− p 0 )⟩ M , wherep 0 is the initial price and the decision variablepis the modified price. We assumeΨis self-adjoint and satisfies Assumption 2. Then, the FOC gives the optimal intervention: du 0 dp = Φp− μΨ(p− p 0 ) = 0 =⇒ p ∗ = argmax p∈R M ≥0 u 0 (p) = (μΨ− Φ) −1 μΨp 0 , proving (4). 21 We see that the network effect comes into the optimal intervention throughΦ. If we have a tensor structure as in (9), then Φ = 1 n (1 T n ⊗ I m )((I n − δG)⊗ W ) −T (I n ⊗ W )((I n − δG)⊗ W ) −1 (1 n ⊗ I m ) = 1 n (1 T n (I n − δG) −T (I n − δG) −1 1)· (I m W −T W −1 I m ) = 1 n ∥(I n − δG) −1 1∥ 2 |z c G ·W −1 . Note thatc G is a constant w.r.t. the activity index, meaning that the underlying network does not affect the planner’s perception of the relative importance of different activities. Specifically, the planner’s objective becomes argmax p u 0 (p) = argmax p 1 2n p,W −1 p − μ 2c G ⟨p− p 0 , Ψ(p− p 0 )⟩. That is, different networks only differ in the regularization strength, essentially decoupling interven- tion from the network structure. On the other hand, with heterogeneous activity kernels, we show in Section 3 that the optimal intervention for each activity depends on an activity-specific network, capturing the intricate interplay between the optimal intervention and the network structure widely observed in real-world systems. We provide some modeling motivations for the regularization term. •The regularization encodes the planner’s budget constraint, making the objective function corre- spond to a hard L 2 budget constraint, with μ being the Lagrange multiplier. • It can incorporate sustainability considerations. AsΨdetermines the cost of intervening different activities, it can have a large Rayleigh quotient for unsustainable activities to suppress raising prices for them, thus promoting sustainable activities and discouraging unsustainable ones. •An infinitely large Rayleigh quotient in some directions also implements a partial intervention, where the planner only has the power to intervene on some activities but not others. •The intervention problem is also a principal-agent Stackelberg game, and the planner’s strategy space, the price spaceR m + , is the dual space of an agent’s strategy space. Thus, having a sim- ilar interpretation asW i in the agent’s utility function,Ψspecifies a quadratic cost in exerting intervention. •The planner can also have their prior belief about agents’ private technologies encoded inΨ. Suppose the initial pricep 0 is set by the planner based on this prior belief, then the objective penalizes deviating from the initial price, withμreflecting the ratio between the confidence of the planner and the evidence revealed by the agents’ actions. C Motivations We provide more micro-founded motivations for our setup, with a focus on heterogeneous activity kernels, network spillover, and non-discriminatory price intervention. C.1 Public price and private technology In a networked market, extensive empirical evidence suggests heterogeneity, diversification, and specialization among agents. For example, different firms have different innate abilities (Zhang et al., 2024), R&D (Knott, 2008), or institutional environments (Bhaumik et al., 2025). This motivates us to consider a market with a public price and private technologies: u i (s,p) =⟨p,s i ⟩− c i (s i ,s −i ), where the cost functionc i captures both the agent-specific technology and the network spillover from other agents. In our setup with multiple activities, the technology is characterized by the activity interaction matrix W i . 22 C.2 Absorptive capacity In a networked market, the network spillover does not only depend on external connections but also the agent’s internal capabilities. For example, in the context of R&D, Cohen and Levinthal (1989, 1990) suggest that a firm’s R&D efforts contribute to its ability to recognize, assimilate and apply relevant information from external sources to generate new knowledge. Such ability is termed "absorptive capacity" and is crucial for firms to benefit from knowledge spillovers in the network. On the other hand, R&D requires investment and involves costs. Additionally, R&D costs and gains should be aligned to capture the absorptive capacity. Our quadratic cost function models the absorptive capacity, capturing both inter-sectoral (across activities) and geographical (across agents) R&D spillovers (Belderbos et al., 2020). Specifically, the network spillover term is positive, capturing beneficial absorption; for agenti, we use the same activity interaction kernelW i in both the quadratic cost term and network compensation term, capturing the alignment between R&D costs and gains; we assume agents’ activity interaction kernels share the same eigenbasis, capturing the standardized interface for R&D and knowledge exchange. Another motivating example is the phenomenon of industry clusters. For example, a labor-intensive manufacturing firm may benefit more from being located in a cluster of similar firms, with easier access to specialized labor. Our model captures this complementarity in technology. C.3 Non-discriminatory subsidy/tax Although discriminatory price intervention is generally required for optimal intervention, we impose a non-discriminatory price intervention for the following considerations: • Fairness, reasonable, and non-discriminatory principle in pricing (Duckworth et al., 2024). •Practicality of intervention process and similar efficiency compared to discriminatory intervention (Heijmans, 2023). • Preventing strategic behaviors such as arbitrage. In our setup, a non-discriminatory intervention aggregates the opinions of all agents and thus demonstrates various network effects, which may play less of a role in a personalized intervention. C.4 Semi-decentralized federated learning We describe a stylized federated-learning interpretation of the model in Section 2. The purpose of this example is not to model a full federated-learning protocol, but to show how the mathematical objects in our network game arise naturally from local data geometry, public (broadcast) server-side incentives, and peer-to-peer model exchange. Consider n clients. Client i holds a local dataset X i ∈ R N i ×m , y i ∈ R N i , where the rows ofX i are feature vectors andy i contains labels. The client fits a local linear model s i ∈ R m . Its empirical square loss is 1 2N i ∥X i s i − y i ∥ 2 2 = 1 2 s ⊤ i Σ i s i − b ⊤ i s i + κ i ,Σ i := 1 N i X ⊤ i X i , b i := 1 N i X ⊤ i y i , whereκ i andb i are constants. Thus the local feature geometry enters through the Gram matrixΣ i . If the features are centered, thenΣ i is the empirical covariance matrix of clienti’s features. Without centering,Σ i is the uncentered second-moment matrix, which means its eigenvalues measure feature energy along the corresponding modes. The server chooses a public interventionp∈ R m , common to all clients, which can be interpreted as a reward, subsidy, or global first-order signal assigned to feature directions. To isolate the effect of this public intervention, we suppress the client-specific label termb i , or equivalently absorb it into the baseline pricep 0 and treat fluctuations inb i as exogenous noise. Retainingb i would add affine terms to the equilibrium but would not change the role ofW i as the private local geometry that shapes the client’s response to the public signal. Clients also exchange their local ML models over a communication graph. LetG ij ≥ 0measure the influence of clientj’s model on clienti. A semi-decentralized federated-learning objective for client 23 i can then be written as the utility u i (s,p) = p ⊤ s i − 1 2 s ⊤ i W i s i + δ X j̸=i G ij s ⊤ i W i s j . Equivalently, clientiminimizes a local quadratic loss regularized by a peer-alignment reward. Indeed, s ⊤ i W i s j = 1 N i ⟨X i s i ,X i s j ⟩, which means that the spillover term rewards clientiwhen its predictions align with the predictions of neighboring clients, evaluated on clienti’s own local feature distributionW i . The matrixW i therefore plays two roles: it penalizes local model complexity and determines how strongly clienti can absorb useful information from neighboring models. The first-order condition for client i’s best response is p− W i s i + δ X j̸=i G ij W i s j = 0, or s i = W −1 i p + δ X j̸=i G ij s j . Thus the public signalpis filtered through the inverse local geometryW −1 i . Ifuis an eigenvector of W i with eigenvalueλ i,u , then an isolated client responds to the component ofpalonguwith strength proportional toλ −1 i,u . In this sense,λ −1 i,u is the client’s preference for that feature mode. At the same time, the network term makes neighboring models complementary: effort by neighboring clients in the same mode, where “effort” is to be interpreted as local ML models, increases clienti’s marginal utility through the factorW i . Hence peer exchange can partially correct the client’s local geometric bias by encouraging effort in directions that would otherwise be dampened by the local Gram matrix. This interpretation explains the informational structure studied in the paper. The matricesW i encode private statistical properties of the clients’ data and are therefore not observable by the server. The graphGalso may not be known to the clients, because each client communicates with a small set of neighbors. Nevertheless, the welfare-maximizing public intervention depends jointly on these private geometries and on the network positions of the clients. A client may also have an incentive to misrepresent its geometry in order to steer the public reward toward directions—and thereby, towards ML models—that benefit it. The polling algorithm developed in the main text addresses precisely this setting: the server learns the welfare-maximizing public signal by querying clients and walking locally through the communication graph, without requiring centralized access to the full network or to the raw data geometries. An alternative interpretation of the utilityu i (s,p): For a fixed magnitude∥s i ∥of the model vectors i , the agent knows thatW i penalizess i more if it places more weight on feature directions with higher variance. This is easily verified as follows: the second loss term decomposes as s ⊤ i W i s i =∥s i ∥ 2 m X ℓ=1 λ ℓ ⟨bs i ,v ℓ ⟩ 2 , bs i := s i ∥s i ∥ , wherev ℓ is the unit vector along theℓ-th feature direction, andλ 1 ≥ λ 2 ≥ · ≥ λ m ≥ 0are the eigenvalues ofW i (all non-negative sinceW i is PSD). Under centering,λ ℓ is proportional to the empirical variance alongv ℓ . Thus the second loss term is minimized ats i = v m , the feature mode with the smallest eigenvalue (hence the lowest variance). Therefore, this term constrainss i to place lower weight on higher-variance feature directions. Under the linear-model assumption, this means the agent’s bias underlying the second component of the loss is that the labels are not as sensitive to high-variance features as they are to low-variance ones. To correct for this bias, for every neighborj of agent i, the i-th agent reduces the loss by δG ij s ⊤ i W i s j = X ℓ α ℓ β ℓ λ ℓ , whereα ℓ := ⟨s i ,v ℓ ⟩(respectivelyβ ℓ := ⟨s j ,v ℓ ⟩) is the alignment between thei-th agent’s model (respectively thej-th agent’s model) and theℓ-th feature direction. Thus, for any fixed model norm ∥s j ∥, the higher the varianceλ ℓ and the greater the value ofβ ℓ , which denotes thej-th agent’s perceived sensitivity of the labels to theℓ-th feature, the more strongly this network-effect term increasesα ℓ , thereby correcting the weight that models i places on featureℓ(which would have been smaller otherwise). 24 D Derivations of solution characterizations D.1 Bundle-induced networks We formally present the proposition under the simplification in Section 3. Proposition 4. The eigenvectors ofΦare the columns ofU. Moreover,Φdecomposes asΦ = U Λ Φ U T , where Λ Φ is diagonal and its a-th diagonal element is given by φ a = 1 n X i∈N fcen 2 a,i · λ −1 i,a , wherefcen a,i , which is thei-th entry offcen a : = (I − δ e G a ) −1 1 n , is the Katz–Bonacich centrality of agent i in the interaction network induced by the activity bundle a∈ [m]. Proof.LetK = (I − δG) −1 . Note thatK1is the Katz–Bonacich centrality vector of the agent networkG. 3 By (3), when agents share the same eigenbasisUof their activity kernelsW i = U Λ i U T , Φ has the following transformation: nΦ =(W −1 1 ,...,W −1 n )(K T ⊗ I m )W (K⊗ I m )W −1 (1 n ⊗ I m ) =U (Λ −1 1 U T ,..., Λ −1 n U T )(K T ⊗ I m )W (K⊗ I m )W −1 (1 n ⊗ I m ) =U P j K 1j Λ −1 j U T ,..., P j K nj Λ −1 j U T W (K⊗ I m )W −1 (1 n ⊗ I m ) =U P j K 1j Λ −1 j Λ 1 U T ,..., P j K nj Λ −1 j Λ n U T (K⊗ I m )W −1 (1 n ⊗ I m ) =U P i P j K i1 K ij Λ −1 j Λ i U T ,..., P i P j K in K ij Λ −1 j Λ i U T W −1 (1 n ⊗ I m ) =U ( P i,j,k K ik K ij Λ −1 j Λ i Λ −1 k )U T .(12) Thus,Φis also diagonalizable in the eigenbasisU; and we writeΦ = U Λ Φ U T with itsa-th diagonal element given by φ a = 1 n X i,j,k∈N K ij K ik λ −1 j,a λ i,a λ −1 k,a , ∀a = 1, 2,...,m. Define the vectorλ a = (λ 1,a ,...,λ n,a ) T ∈ R n andλ −1 a as its element-wise inverse. Then, we can rewrite φ a as φ a = 1 n (Kλ −1 a )⊙ λ a , diag(λ −1 a )((Kλ −1 a )⊙ λ a ) .(13) Recall our construction of the bundle-specific network: e G a = Λ a GΛ −1 a . Its Katz–Bonacich centrality satisfies fcen a =(I − δ e G a ) −1 1 n =(I − δΛ a GΛ −1 a ) −1 1 n =Λ a (I − δG) −1 Λ −1 a 1 n =Λ a Kλ −1 a =Kλ −1 a ⊙ λ a .(14) Combining (13) and (14) gives the desired expression. 3 Our notation specifiesG ij = 1ifyinfluencesi, and thusGis the transpose of the usual convention in the network literature. As a result, the Katz–Bonacich centrality here is higher for agents that receive more influence from others, which is consistent with the convention. 25 D.2 Planner-informed second-stage communication This section discusses the path of generalizing Proposition 4 to the more general Proposition 1. The simplifications in Section 3 have two implications: (i)W i i∈N share the same eigenbasis, so we can define bundle-specific networks, and (i)Ψshares the same eigenbasis withW i , so we directly get the optimal intervention for each activity bundle from the corresponding eigenvalue ofΦby [U T p ∗ ] a = (1− μ −1 φ a ) −1 [U T p 0 ] a . In words, different activity bundles induce different networks to determine the optimal intervention for the bundle independently with no communication between bundle-induced networks. This is not possible when the agents and the planner do not share the same set of activity bundles. We now modelΨas an arbitrary positive definite matrix that may not share the same eigenbasis as W i i∈N . Similarly, we can interpretΨas encoding the planner’s preferences across activities. A general planner preference introduces a second stage of communication between bundle-induced networks. Specifically, under Assumption 2, we can expand the optimal intervention as Neumann series: p ∗ = ∞ X t=0 μ −t (Ψ −1 Φ) t p 0 ,(15) which can be interpreted as the result of iterative planner-mediated communication between bundle- specific networks, with the higher-level communication network beingΨ −1 Φ. This communication network becomes diagonal, onceΨshares the same eigenbasis asW i and we apply an eigende- composition toΦ, reducing to the case of no communication between bundle-induced networks. With a generalΨ, a activity bundle of the planner may partially align with multiple activity bundles of the agents, thus prompting communication between bundle-induced networks. Intuitively, when the planner proposes a price change for one of its activity bundles, multiple agent activity bundles may be affected, and thus requiring different bundle-induced networks to coordinate to achieve the optimal intervention. Formally, after being transformed byΨ −1 , agents’ activity bundles are no longer orthogonal. Combined with Proposition 1, the intervention problem corresponds to a two-stage communication scheme: agents first communicate within bundle-induced networks to form their votes, and then the planner mediates the communication between bundle-specific networks to form the final intervention. We further model the agent’s activity kernelsW i i∈N as arbitrary positive definite matrices that may not share the same eigenbasis, which invalidates bundle-induced networks in Proposition 4 as agents no longer have a common set of activity bundles. If we generalize the definition of a network to allow for matrix-valued edge weights, we can consider a single generalized network that also incorporates the planner’s preference, similar to how an bundle-induced network incorporates agents’ preferences. By (4), we haveΨ 1/2 p ∗ = (I − μ −1 e Φ) −1 (Ψ 1/2 p 0 ) , where e Φ : = Ψ −1/2 ΦΨ −1/2 ∈ R m×m is characterized in Proposition 1. We note that e G is planner-informed, as it is modified by the planner’s preference in addition to those of the agents. IfΨandW i share the same eigenbasisU, then f W i i∈N are simultaneously diagonalizable, and we can split e Gintombundle-induced networks with scalar edge weights, reducing to Proposition 4. D.3 Proof of Proposition 1 Recall that e Φ = Ψ −1/2 ΦΨ −1/2 . Following (12), we have e Φ = Ψ −1/2 ( P i,j,k K ik K ij W −1 j W i W −1 k )Ψ −1/2 . Our centrality measure has a “dimensionlessness” structure, which gives e Φ = P i,j,z K ik K ij (Ψ −1/2 W −1 j Ψ −1/2 )(Ψ 1/2 W i Ψ 1/2 )(Ψ −1/2 W −1 k Ψ −1/2 ). Recall f W i = Ψ 1/2 W i Ψ 1/2 . Then, following (14), we get e Φ = X i,j,k K ik K ij f W −1 j f W i f W −1 k = X i∈N fcen T i f W −1 i fcen i , wherefcen i is thei-th block of the Katz–Bonacich centrality of the modified network e Gwith matrix- valued edge weight e G ij = G ij f W i f W −1 j . 26 D.4 Proof of Proposition 2 Following the derivation in Appendix B, the utility of agent i at the Nash equilibrium at price p is u i (s ∗ (p)) =⟨s ∗ i (p), (p + Qs ∗ (p)) i ⟩ =⟨s ∗ i (p), ((Q I − Q C )s ∗ (p) + (− 1 2 Q I + Q C )s ∗ (p)) i ⟩ = 1 2 ⟨s ∗ i (p), (Q I s ∗ (p)) i ⟩. Note thatQ I = blkdiag(W i )andQ I − Q C = blkdiag(W i )((I n − δG)⊗ I m ). Recall thatK = (I − δG) −1 . Therefore, u i (s ∗ (p)) = 1 2 ⟨s ∗ i (p),W i s ∗ i (p))⟩ = 1 2 ⟨p, X j,k K ij K ik W −1 j W i W −1 k | z Φ i p⟩. Then, when all agents share the same eigenbasis of activity kernel (W i = U Λ i U T for alli∈N), we have Φ i =U diag(fcen 2 a,i λ −1 i,a )U T . Thus, thea-th eigenvalue ofΦ i isφ i,a = fcen 2 a,i λ −1 i,a . We see that agenti’s utility kernelΦ i has a similar form to the social welfare kernelΦin Proposition 4, which is not a surprise since the social welfare is simply the aggregate of all agents’ utilities. Fixing a price, agents’ equilibrium utilities are linear and monotonic in their utility kernel w.r.t. the Loewner order. Therefore, we only need to know how φ i,a changes w.r.t. the preference. We have ∂ lnφ i,a ∂ lnλ i,a = 2 ∂ ln fcen a,i ∂ lnλ i,a − 1.(16) Further, ∂ ln fcen a,i ∂ lnλ i,a = λ i,a fcen a,i ∂ fcen a,i ∂λ i,a = P j∈N K ij λ i,a λ j,a − K i λ i,a λ i,a P j∈N K ij λ i,a λ j,a = 1− K i fcen a,i ,(17) where K = (I − δG) −1 is the Katz–Bonacich centrality matrix of the original network. Note that K ij λ i,a λ j,a = (diag(λ a ))K diag(λ −1 a )) ij = ((I−δ diag(λ a )G diag(λ −1 a )) −1 ) ij = ((I−δ e G a ) −1 ) ij = e K a,ij . Thus, combining (16) and (17) gives the desired result. E Centrality simulations This section provides a concrete example to illustrate the theoretical results derived in Section 3. We consider a network ofn = 7data centers. All centers engage inm = 2activities—compute (a 1 ) and storage (a 2 )—and two activity patterns: archive (u 1 = (1, 1) T / √ 2) and retrieve (u 2 = (1,−1) T / √ 2). Specifically, the archival pattern means the center produces one unit of data and stores it; the retrieval pattern means the center retrieves one unit of data from storage and processes it. The resulting activity interaction kernel basis is U = 1 √ 2 1 1 1 −1 . We categorize the data centers into three distinct tiers based on their role in the data lifecycle: 1.Provider-Side centers (Centers 1–2): Center 1 is a cloud storage hub focusing on the archival pattern (λ 1,1 = 1,λ 1,2 = 10). Center 2 is a data processing hub focusing on the retrieval pattern (λ 2,1 = 10,λ 2,2 = 1). Both act as sources of influence in the network. 2.Intermediary centers (Centers 3–5): These centers act as neutral bridges, balancing equally between archival and retrieval tasks. They possess moderate preferences for both patterns: λ x,1 = 5,λ x,2 = 5 for x∈3, 4, 5. 27 3.Client-Side centers (Centers 6–7): These centers are at the edge of the network and are highly specialized. Center 6 serves user queries (high preference for retrieval:λ 6,1 = 10,λ 6,2 = 1). Center 7 serves data backups (high preference for archival: λ 7,1 = 1,λ 7,2 = 20). The network structure is given by the following attenuated adjacency matrixG, representing a directed cascade from providers to clients: G = 0.1· 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 . We set the initial pricep 0 = (2, 0) T and consider the optimal non-discriminatory intervention under an L 2 constraint with budget B = 1. Figure 7: Original network and activity-specific networks for archival and retrieval patterns. Edge width and node size are proportional to edge weight and squared centrality, respectively. We visualize the original network together with activity-specific networks in Figure 7. They verify our theory that while in the original network nodes on the provider side have higher influence and are more central, in the activity-specific networks, the most central nodes are on the client side, which absorb most of the influence while casting the largest votes in the committee. Specifically, in the committee for archival activities, the query center (6), which has a low preference for archival activities, is the most central member; in the committee for retrieval activities, the backup center (7), which has a low preference in retrieval activities, is the most central. Figure 8: Pre- and post-intervention effort levels across data centers and activities. We plot the pre- and post-intervention effort levels in Figure 8 to further validate our analysis. We see that the cloud (1) and backup (7) data centers indeed prefer, both before and after the intervention, archival over retrieval activities; while the processing (2) and query (6) centers consistently prefer 28 retrieval. Additionally, the overall network has a slight bias towards archival activities (due to the largeλ 7,2 ), but the intervention spends relatively more on retrieval activities, evident by the effort increases from the neutral centers (3, 4, 5) towards retrieval. This confirms our counter-intuitive insight that the optimal intervention allocates more resources to the less preferred activity pattern to empower reluctant members who hold significant influence in that activity’s committee. Figure 9: Optimal intervention level vs. stiffness for retrieval activities at cloud center (1) and backup center (7). The dashed lines represent intervention levels when centers are isolated (no network effects). Finally, we further illustrate this “paradox” of empowering reluctant members and intervening less preferred activities in Figure 9 by inspecting two key data centers: the cloud storage center (1) and the backup center (7). We vary their stiffness parameters for retrieval activities (λ 1,2 andλ 7,2 ) and plot the resulting optimal intervention level for retrieval activities. We also plot the intervention levels when the centers are isolated (i.e., no network effects) for reference. We see that, changes in the stiffness of the cloud center (1) behave intuitively: as it becomes more reluctant towards retrieval activities (higherλ 1,2 ), the intervention level for retrieval activities decreases, as the planner focuses on other activities with higher participation. However, the backup center (7) exhibits the paradoxical behavior: as it becomes more reluctant towards retrieval activities (higherλ 7,2 ), the intervention level for retrieval activities increases. This confirms our insight that in a networked setting, optimal interventions may need to counteract individual preferences to effectively leverage the influence dynamics within the network. F Implementation details of Poll Random walks. We provide a more detailed derivation of Step 4 in Section 4: [ e G k 1] i = X j 1 ∈N i e G ij 1 [ e G k−1 1] j 1 = deg i E j 1 ∼Unif(N i ) [ e G ij 1 [ e G k−1 1] j 1 ] = deg i E j 1 ∼Unif(N i ) [ e G ij 1 deg j 1 E j 2 ∼Unif(N j 1 ) [ e G j 1 j 2 [ e G k−2 1] j 2 ]] =E j 1 ∼Unif(N i ),j 2 ∼Unif(N (j 1 )) [deg i deg j 1 · e G ij 1 e G j 1 j 2 [ e G k−2 1] j 2 ] =· =E (i=j 0 ,j 1 ,...,j k ) " k−1 Y l=0 deg j l · k−1 Y l=0 e G j l j l+1 # ,(18) Please refer to Appendix H.4 for a more general sampling scheme, which also accommodates weighted graphs. On a random walk, when an intermediate agent has no incoming neighbor, we can simply stop the walk and return a zero estimate, as the degree product will be zero. 29 Knowledge. There is a fundamental trade-off between the planner’s knowledge and the agents’ behavior: the more the planner knows, the less it relies on agents to behave faithfully, and vice versa. For example, if the planner knows the network topology, agents need not report their degrees. InPoll, we shift this burden to the agents. The planner has no prior knowledge of the network or agents’ technologies, making the algorithm fully model-free. Each agent knows only its local neighborhood; agents need their neighbors’ degrees only when performing general importance sampling in Appendix H.4. Agents’ technologies are private; the initial pricep 0 and the corresponding Nash equilibrium s ∗ (p 0 ) are public. Algorithm 1: Poll 1 input Initial price q 0 = Ψ 1/2 p 0 , game parameters n =|N|, δ, ν = μ −1 2 parameters Step sizesα t t≥0 3 Initialize q ← 0 (or some initial guess) 4 for t = 0, 1, 2,... do 5Sample an agent i uniformly fromN 6Sample two trajectory lengths k (1) ,k (2) independently from Geom(δ) 7for x∈1, 2 do 8Initialize a random walk at j (x) 0 = i 9Initialize d x ← 1 10for l = 0 to k (x) − 1 do 11d x ← d x · deg j (x) l // by the planner 12Sample j (x) l+1 uniformly from the incoming neighborsN j (x) l // by the agents 13Compute stochastic estimate: b Φ t ← (1− δ) −2 d 1 d 2 f W −1 j (1) k (1) f W i f W −1 j (2) k (2) // by the agents 14Update intervention: q ← (1− α t )q + α t (q 0 + ν b Φ t q) 15 return q or p = Ψ −1/2 q Behavior. We give a detailed behavioral description and timeline at each time step, expanding Algorithm 1: 1. Planner: announces the update rule Poll; 2. Planner: samples an agent i; 3. Agent i: initiates two random walks; 4. Agent along the walks: report its degree to the planner 4 and choose the next step following the algorithm’s instructions; 5. Planner: collects the degree information along the random walks; 6. Planner: sends the query q t to the endpoint agent j (2) k ; 7. Agent j (2) k : computes f W −1 j (2) k q t and sends it back to agent i through the walk; 8. Planner: signals the degree information of the walks to agent i; 9. Agenti: left-multiplies the received vector with f W i and sends it to the other endpoint agentj (1) k through the other walk; 10. Agent j (1) k : left-multiplies the received vector with f W −1 j (1) k and sends it back to the planner. The updated price follows deterministically from the announced algorithm and the agents’ responses, so no further action is required from the planner after receiving the final report. This changes if the planner employs a payment mechanism to enforce truthful reporting, where the payment depends on the final report; see Appendix I.1. Variations ofPoll, such as those with control variates (Appendix H.1), use the same communication protocol. In this work, we analyze strategic misreporting ofW i only, assuming degrees are reported faithfully and walks are executed as specified; the analysis of broader strategic behaviors is left to future work. 4 The planner can also ask each walk’s endpoint to report the degree product directly, in which case agents along the walk collect and multiply degrees before passing the message onward. 30 Complexity. At each time step, each random walk requires at most two rounds of message passing— one forward traversal for degree collection and one backward pass for the computation result—with each message containing a scalar degree or a vector of lengthm, giving an expected communication complexity ofO(2(m + 1)(1 − δ) −1 + m) = O(m). Three matrix-vector multiplications are performed at the endpoint agents, giving a computational complexity of O(m 2 ). Privacy. The planner only receives the final preference-price product f W −1 j (1) k f W i f W −1 j (2) k q t . Since agentionly receives f W −1 j (2) k q t with the identity of agentj (2) k masked, the former cannot infer the preferenceW j (2) k . Similarly, agentj (1) k cannot infer the preferenceW i orW j (2) k from its received vector f W i f W −1 j (2) k q t . Finally, since the agents’ cost structures may not share the same eigenbasis, the planner cannot infer agents’ preferences from the final report, even if the identities of the endpoint agents are known to the planner. G Proofs of learning efficiency Recall the notation:ψ : = λ max (Ψ),ψ : = λ min (Ψ),λ : = max i∈N λ max (W i ),λ : = min i∈N λ min (W i ) ,d : = max i∈N deg i ,κ Ψ : = ψ/ψ,κ W : = λ/λ,κ ν : = (1 − νλ max ( e Φ)) −1 , κ δ : = (1−δσ max (G)) −1 . Lete t = p t −p ∗ andF t be theσ-field generated by the randomness up to time t. Lemma G.1 (Error dynamics). If we have a uniform boundν 2 E∥ b Φ t − e Φ∥ 2 ≤ σ 2 , settingα = κ ν lnt/t and letting t/ lnt≥ max 2, 4κ 2 ν σ 2 gives E∥e t ∥ 2 ≤ (1− α/κ ν ) t ∥e 0 ∥ 2 + 2ακ ν σ 2 ∥p ∗ ∥ 2 = e O t −1 κ 2 ν σ 2 ∥p ∗ ∥ 2 . Proof. Note that the optimal solution satisfies(I − ν e Φ)p ∗ = p 0 . We have the following error dynamics e t+1 =e t − α((I − ν b Φ t )p t − p 0 ) =e t − α(p 0 − (I − ν e Φ)p ∗ + (I − ν b Φ t )p t − p 0 ) =e t − α((I − ν e Φ)(p t − p ∗ )− (I − ν e Φ)p t + (I − ν b Φ t )p t ) =(I − α(I − ν e Φ))e t + αν( b Φ t − e Φ)p t ,(19) which gives the mean squared error (MSE) dynamics E∥e t+1 ∥ 2 =E∥(I − α(I − ν e Φ))e t ∥ 2 + α 2 ν 2 E∥( b Φ t − e Φ)p t ∥ 2 (20) ≤∥I − α(I − ν e Φ)∥ 2 E∥e t ∥ 2 + α 2 ν 2 E[E[∥ b Φ t − e Φ∥ 2 |F t ]∥p t ∥ 2 ], whereF t be the filtration generated by the randomness up to timet. Since b Φ t is independent ofF t , we have E[∥ b Φ t − e Φ∥ 2 |F t ] = E∥ b Φ t − e Φ∥ 2 . Then, given the uniform bound, E∥e t+1 ∥ 2 ≤∥I − α(I − ν e Φ)∥ 2 E∥e t ∥ 2 + 2α 2 σ 2 (E∥p t − p ∗ ∥ 2 +∥p ∗ ∥ 2 ) ≤(1− 2ακ −1 ν + α 2 (κ −2 ν + 2σ 2 ))E∥e t ∥ 2 + 2α 2 σ 2 ∥p ∗ ∥ 2 .(21) Setting α≤ minκ ν /2, 1/(4κ ν σ 2 ) gives E∥e t+1 ∥ 2 ≤ (1− ακ −1 ν )E∥e t ∥ 2 + 2α 2 σ 2 ∥p ∗ ∥ 2 . Setting t accordingly gives the desired result. As a corollary, we get: Proposition 5. Consider Poll update rule (7) with additive noise: p t+1 = p t − α t ((I − ν b Φ t )p t − p 0 + ε (1) t + ε (2) t ), whereE Z t [ε (1) t ] = 0 ,E∥ε (1) t |≤ σ 2 1 , and∥ε (2) t ∥≤ σ 2 almost surely. Then, with a constant step size α≡ κ ν lnt/t, we have E∥p t − p ∗ ∥ 2 = e O(t −1 κ 2 ν (σ 2 ∥p ∗ ∥ 2 + σ 2 1 + σ 2 2 ) + κ 2 ν σ 2 2 ). 31 If the additive noise has zero mean, then the variance of our update direction is increased by the noise variance. Otherwise, if the additive noise is bounded, then we may have a non-vanishing error floor when σ 2 = ω( √ α). Proof of Proposition 5. With an additive noise ε t , (19) becomes e t+1 = (I − α(I − ν e Φ))e t + αν( b Φ t − e Φ)p t + αε (1) t + αε (2) t . Then, (20) becomes E∥e t+1 ∥ 2 =E∥(I − α(I − ν e Φ))e t ∥ 2 + α 2 E∥ν( b Φ t − e Φ)p t + ε (1) t + ε (2) t ∥ 2 + 2αE D (I − α(I − ν e Φ))e t ,ε (2) t E , where the additional cross term is due to the non-zero mean ofε (2) t . By Young’s inequality, (21) becomes E∥e t+1 ∥ 2 ≤E∥(I − α(I − ν e Φ))e t ∥ 2 + 3α 2 (ν 2 E∥( b Φ t − e Φ)p t ∥ 2 + σ 2 1 + σ 2 2 ) + α((2κ ν ) −1 E∥(I − α(I − ν e Φ))e t ∥ 2 + 2κ ν σ 2 2 ) ≤((1 + α(2κ ν ) −1 )(1− 2ακ −1 ν + α 2 κ −2 ν ) + 6α 2 σ 2 ))E∥e t ∥ 2 + 3α 2 (2σ 2 ∥p ∗ ∥ 2 + σ 2 1 + σ 2 2 ) + 2ακ ν σ 2 2 ≤(1− 3 2 ακ −1 ν + 6α 2 σ 2 + 1 2 α 3 κ −3 ν )E∥e t ∥ 2 + 3α 2 (2σ 2 ∥p ∗ ∥ 2 + σ 2 1 + σ 2 2 ) + 2ακ ν σ 2 2 . Letting α≤ minκ ν /2, 1/(24κ ν σ 2 ) gives E∥e t ∥ 2 ≤(1− ακ −1 ν )E∥e t−1 ∥ 2 + 3α 2 (2σ 2 ∥p ∗ ∥ 2 + σ 2 1 + σ 2 2 ) + 2ακ ν σ 2 2 ≤(1− ακ −1 ν ) t ∥e 0 ∥ 2 + 3ακ ν (2σ 2 ∥p ∗ ∥ 2 + σ 2 1 + σ 2 2 ) + 2κ 2 ν σ 2 2 . Setting α = κ ν lnt/t gives the desired result. Remark 4 (Noisy query). Querying a social network with economic agents is often influenced by subjective biases, recall difficulty, and incomplete observation, introducing inevitable estimation noises in the data (Jackson, 2011, Marsden, 1990). Proposition 5 showcases the robustness ofPollto such endogenous noise and exogenous shocks. Additionally, it justifies the “approximate truthfulness” in Appendix I. Within one iteration, dropping the time indext, we denoteξ 1 ,ξ 2 as the two random walks,k 1 = k (1) t ,k 2 = k (2) t the lengths,j (1) = j (1) k (1) t ,j (2) = j (2) k (2) t the endpoints, andd 1 = Q k (1) t −1 l=0 deg j (1) l ,d 2 = Q k (2) t −1 l=0 deg j (2) l the degree products, of the two random walks. Although Assumption 3 implies the independence between the degree and preference of a single agent, it does not decouple the degree product and the preference product in the update direction. For example, if two random walks end at the same nodej (1) = j (2) , thenW j (1) andW j (2) coincide. In general, random walks may cause the indicesi,j (1) , orj (2) to overlap, and thus couple the degree product and the preference product. One can argue that when n is large, such scenarios are rare and thus the coupling is weak. Nonetheless, we can have a uniform variance decomposition, by using a reference point M to be determined. LetF N be theσ-field generated by the network sampling, includingi,k (1) ,k (2) ,ξ 1 ,ξ 2 ,d 1 , andd 2 . F N is independent ofF t , and by Assumption 3, the marginal distribution ofW i is independent of bothF t andF N , i.e., anyF t - orF N -measurable function, for any i∈N . Lemma G.2 (Variance decomposition). LetV N : = Var(d 1 d 2 ),E N : = E[d 1 d 2 ]. For anyM ∈ R m×m , let E M : =∥M∥. If we have E[∥W −1 z (1) W x W −1 z (2) − M∥ 2 |F N ]≤ V M , then σ 2 ≤ 6ν 2 κ 2 Ψ (1− δ) −4 V M V N + E 2 N V M + E 2 M V N . 32 IfE M andV M are the exact mean and variance of the preference distribution, then the above result exactly recovers the variance decomposition of the product of two independent random variables, i.e.,Var(XY ) = Var(X) Var(Y ) + E[X] 2 Var(Y ) + E[Y ] 2 Var(X), suggesting its tightness. That said, our update direction has a much more intricate and coupled structure. The reference pointMto be determined, is used to decouple the degree product and the preference product, and later used to derive a bound of V M . Proof. We recall the following derivation from Section 5.3: b Φ t = b Φ(Z t ) : = (1− δ) −2 k (1) t −1 Y l=0 deg j (1) l k (2) t −1 Y l=0 deg j (2) l · f W −1 j (1) k f W i t f W −1 j (2) k .(22) By (22), we have ∥ b Φ t − e Φ∥≤(1− δ) −2 ψ −1 ∥d 1 d 2 W −1 j (1) W i W −1 j (2) − E[d 1 d 2 W −1 j (1) W x W −1 j (2) ]∥. We have d 1 d 2 W −1 j (1) W i W −1 j (2) − E[d 1 d 2 W −1 j (1) W x W −1 j (2) ] =d 1 d 2 W −1 j (1) W i W −1 j (2) − d 1 d 2 M + d 1 d 2 M − E[d 1 d 2 ]M + E[d 1 d 2 ]M − E[d 1 d 2 W −1 j (1) W i W −1 j (2) ] =d 1 d 2 (W −1 j (1) W i W −1 j (2) − M ) + (d 1 d 2 − E[d 1 d 2 ])M + E[d 1 d 2 (M − W −1 j (1) W i W −1 j (2) )]. The last term is a by-product of our arbitrary reference point; nonetheless, it’s dominated by the first term by Jensen’s inequality. Therefore, we have E∥d 1 d 2 W −1 j (1) W i W −1 j (2) − E[d 1 d 2 W −1 j (1) W i W −1 j (2) ]∥ 2 ≤3 2E∥d 1 d 2 (W −1 j (1) W i W −1 j (2) − M )∥ 2 + E∥(d 1 d 2 − E[d 1 d 2 ])M∥ 2 ≤6 E[d 2 1 d 2 2 ]V M + E 2 N Var(d 1 d 2 ) ≤6 V N V M + E 2 N V M + E 2 M V N . We thus only need to bound the first and second moments of the degree product and the preference product. Lemma G.3. Let M : = EW −1 i , where the expectation is w.r.t. the preference generation. We have E[∥W −1 j (1) W i W −1 j (2) − M∥ 2 |F N ]≤ 9κ 2 W σ 2 M . Proof. The reference point M helps decouple the product: W −1 j (1) W i W −1 j (2) − M = (W −1 j (1) − W −1 i )W i W −1 j (2) + (W −1 j (2) − W −1 i ) + (W −1 i − M ). First note that we have a trivial bound ∥W −1 j (1) W i W −1 j (2) − M∥≤ 9 λ 2 /λ 4 .(23) By Assumption 3, W −1 i ,W −1 j (1) ,W −1 j (2) have the same marginal distribution, giving E∥W −1 i − M∥ 2 F = E∥W −1 j (1) − W −1 i ∥ 2 F = E∥W −1 j (2) − W −1 i ∥ 2 F = σ 2 M . Let E F N be the expectation conditioned onF N . We have E F N ∥W −1 j (1) W i W −1 j (2) − M∥ 2 ≤3 κ 2 W E F N ∥W −1 j (1) − W −1 i ∥ 2 F + E F N ∥W −1 j (2) − W −1 i ∥ 2 F + E F N ∥W −1 i − EW −1 i ∥ 2 F =3(2κ 2 W (1− Corr F N (W −1 j (1) ,W −1 i )) + 2(1− Corr F N (W −1 j (2) ,W −1 i )) + 1)σ 2 M , 33 where Corr F N returns the correlation conditioned onF N . By symmetry, we also have E F N ∥W −1 j (1) W i W −1 j (2) − M∥ 2 ≤3(2κ 2 W (1− Corr F N (W −1 j (2) ,W −1 i )) + 2(1− Corr F N (W −1 j (1) ,W −1 i )) + 1)σ 2 M . Note thati,j (1) ,j (2) areF N -measurable. Thus, we can defineCorr F N : = 1 2 (Corr F N (W −1 j (1) ,W −1 i )+ Corr F N (W −1 j (2) ,W −1 i )) to get E F N ∥W −1 j (1) W i W −1 j (2) − M∥ 2 ≤ 3(2(κ 2 W + 1)(1− Corr F N ) + 1)σ 2 M .(24) Or, defining Corr F N : = maxCorr F N (W −1 j (1) ,W −1 i ), Corr F N (W −1 j (2) ,W −1 i ), we get E F N ∥W −1 j (1) W i W −1 j (2) − M∥ 2 ≤ 3(2κ 2 W (1−Corr F N ) + 5)σ 2 M .(25) Note that κ W ≥ 1 and Corr F N , Corr F N ∈ [−1, 1]. Thus, a universal bound is E∥W −1 j (1) W i W −1 j (2) − M∥ 2 ≤ 9κ 2 W σ 2 M ≤ 9 λ 2 /λ 2 σ 2 M . For a system with a wide range of technologies,κ W can be large and becomes a bottleneck. In such cases, a positive correlationCorr F N can be of huge help. Thus, (24) is a strictly sharper bound than the universalV M : = 9κ 2 W σ 2 M , and we will revisit it later once we introduce the correlation structure. Lemma G.4. We have V N = Var(d 1 d 2 ) = σ 2 N . Proof.In this proof we adopt a modular approach so we can reuse the calculations later. Conditioned on i, two random walks ξ 1 and ξ 2 are i.i.d. We thus drop the subscript to refer to either of them. By our sampling procedure, we have E " k−1 Y l=0 deg j l i,k # = X |ξ|=k k−1 Y i=0 deg j i · 1 deg i 1 deg j 1 · 1 deg j k−1 = X |ξ|=k 1, where the summation counts the number of distinct walks of lengthkstarting fromx, which is equivalent to E " k−1 Y l=0 deg j l i,k # = X |ξ|=k 1 = X j 1 ∈N,...,j k ∈N G ij 1 G j 1 j 2 ·G j k−1 j k = e T i G k 1. Integrating over k gives E " k−1 Y l=0 deg(j l ) i # = (1− δ)e T i (I − δG) −1 1. Integrating over i gives E[d 1 d 2 ] =E (1− δ) 2 (e T i (I − δG) −1 1) 2 =(1− δ) 2 (I − δG) −1 1, E[e i e T i ](I − δG) −1 1 = (1− δ) 2 n ∥(1− δG) −1 1∥ 2 . 34 The second moment is calculated similarly: E " k−1 Y l=0 deg 2 j l i,k # = X |ξ|=k k−1 Y l=0 deg 2 j l · 1 deg i 1 deg j 1 · 1 deg j k−1 (26) = X |ξ|=k k−1 Y l=0 deg j l = X j 1 ∈N,·,j k ∈N k−1 Y l=0 deg j l G ij 1 ·G j k−1 j k = X j 1 ∈N,·,j k ∈N D i G ij 1 D j 1 j 1 ·G j k−2 j k−1 D j k−1 j k−1 G j k−1 j k =e T i (DG) k 1, where D = diag(deg i ) is the diagonal degree matrix. Integrating over k gives E " k−1 Y l=0 deg 2 j l i # = (1− δ)e T i (I − δDG) −1 1.(27) Then, E[d 2 1 d 2 2 ] = E[(1− δ) 2 (I − δDG) −1 1,e i e T i (I − δDG) −1 1 ] = (1− δ) 2 n ∥(I − δDG) −1 1∥ 2 . (28) Note that∥(I − δI) −1 1∥ 2 = (1− δ) −1 n. Thus, we have Var(d 1 d 2 ) = (1− δ) 4 n 2 ∥(I − δDG) −1 1∥ 2 ∥(I − δI) −1 1∥ 2 −∥(I − δG) −1 1∥ 4 = σ 2 N . A direct consequence is a trivial bound: Var(d 1 d 2 )≤ E[d 2 1 d 2 2 ]≤ (1− δ) 2 (1− δσ max (DG)) −2 ≤ (1− δ) 2 (1− δd 2 ) −2 .(29) Combining Lemmas G.1 to G.4 gives the desired query complexity in Theorem 1. H Variance reduction Throughout this section, we denoteσ bl N ,σ bl M as the standard deviations defined in Definitions 1 and 2 under the baseline model, and σ vr N ,σ vr M as those after variance reduction. H.1 Control variate Notice that the centrality in (5) is equivalent to fcen = ∞ X k=0 δ k e G k 1 = 1 + δ ∞ X k=0 δ k e G k+1 1 = 1 + δ(1− δ) −1 E k∼Geom(δ) e G k+1 1. If we sample the walks using the above expression, although we would have a one-step longer walk in expectation, the whole walk is discounted by an additionalδ, leading to a much smaller variance when δ is small (Assumption 1). Specifically, the algorithm is modified as follows: we sample the agentiandk 1 ,k 2 ∼ Geom(δ)as before, but we set the walk lengths to bek 1 + 1andk 2 + 1instead ofk 1 andk 2 . Letd 1 andd 2 be the degree products of the walks calculated the same way as before. The agent composes the estimator as b Φ = I m + δ(1− δ) −1 d 1 f W −1 j (1) k 1 +1 f W i f W −1 i I m + δ(1− δ) −1 d 2 f W i f W −1 j (2) k 2 +1 = f W −1 i + δ(1− δ) −1 d 1 f W −1 j (1) k 1 +1 + d 2 f W −1 j (2) k 2 +1 + δ 2 (1− δ) −2 d 1 d 2 f W −1 j (1) k 1 +1 f W i f W −1 j (2) k 2 +1 , (30) 35 and then reports b Φq t as before. Proposition 6. The above update has the same operation complexity, but enjoys the following variance reduction: σ vr N σ bl N 2 ≲ δ 2 (δ 2 ∨(1− δσ max (DG))). Proof. Note that f W −1 j = f W −1 j f W j f W −1 j for anyj ∈N. Thus, the variance of the preference products in (30) is still bounded by σ M as before. The variance of the degree products becomes σ vr N ≲ δ 2 (1− δ) −2 Var(d 1 ) + δ 4 (1− δ) −4 Var(d 1 d 2 ). By Lemma G.4, Var(d 1 d 2 ) = (σ bl N ) 2 and Var(d 1 ) = 1− δ n 1 T (I − δDG) −1 1− 1− δ n ∥(I − δG) −1 1∥ 2 ≲ (1− δσ max (DG)) −1 . Note that σ bl N ≍ (1− δσ max (DG)) −2 . Combining the above gives the desired result. Notably, the above technique, purely motivated by our optimal intervention characterizations, coin- cides with the standard control variate technique (Zhang and Azizan, 2026). A control variate is a random variable with known expectation that is positively correlated with the original estimator. Thus, subtracting the control variate and adding its expectation reduces the variance. Alternatively, if we know the expectation of a part of the estimator, then we only need to sample the residual part, and the difference between the original estimator and the residual is a control variate. Formally, X = X cv + X residual ,with EX cv known =⇒ X new = E[X cv ] + X residual = X − X cv + E[X cv ] is unbiased and variance reduced. In our case, whenk = 0, we do not need to sample the walk, and we know the expectation of this scenario. This base case happens to be the most significant part of the estimator due the exponential tail, and thus serves as a very effective control variate that correlates well with the original estimator. Then, the new estimator contributes the residual part. H.2 Preference correlation Real-world network systems often observe correlated preferences within local neighborhoods. There are two scenarios in which a system generation model satisfying Assumption 3 produces positive correlation: preferences are developed on a given network, e.g., through assimilation or social learning (Acemoglu et al., 2011), or the network is formed based on preference similarity, e.g., through homophily or assortative mixing (Newman, 2018). Proposition 7. Suppose there exists a non-increasing functionr : [k] → [−1, 1]withk ≥ 1and [k] : = 0,...,k such that r(0) = 1 and r(1) > 0, such that for any two agents i,j ∈N , Corr(W −1 i ,W −1 j )≥ r(dist(i,j)), whereCorris w.r.t. the preference generation and Frobenius inner product, anddistreturns the shortest path distance. Then, σ vr M σ bl M 2 ≲ 5 4κ 2 W + min k∈[ k] f δ (k) 5 4κ 2 W + 1 , where f δ (k) : = (2(1 + δ 4 )) −1 (1− r(k) + 2δ 2k+2 ) and min k f δ (k)≤ f δ (1) = 1− 1+r(1) 2(1+δ 4 ) < 1. Whenκ W is large, positive preference correlation can significantly reduce the query complexity when r(1)↑ 1 and δ ↓ 0. Proof. To inspect the effect of preference correlation, we need to handle the coupling between the degree product and the preference product more carefully than in Lemma G.3. Instead of conditioned onF N , we condition on the walk lengths. By the tower property, E[d 2 1 d 2 2 ∥W −1 j (1) W i W −1 j (2) − M∥ 2 |k 1 ,k 2 ] = E[d 2 1 d 2 2 E[∥W −1 j (1) W i W −1 j (2) − M∥ 2 |F N ]|k 1 ,k 2 ]. 36 By (25), E[d 2 1 d 2 2 ∥W −1 j (1) W i W −1 j (2) − M∥ 2 |k 1 ,k 2 ]≤ E[d 2 1 d 2 2 · 3(2κ 2 W (1− Corr F N ) + 5)σ 2 M |k 1 ,k 2 ], where Corr F N = maxCorr F N (W −1 j (1) ,W −1 i ), Corr F N (W −1 j (2) ,W −1 i ). If k 1 ∧ k 2 ≤k, since r is non-increasing, we have Corr F N ≥ r(k 1 ∧ k 2 ). If k 1 ∧ k 2 >k, we have the trivial boundCorr F N ≥−1. Thus, E[d 2 1 d 2 2 ∥W −1 j (1) W i W −1 j (2) − M∥ 2 |k 1 ,k 2 ] ≤3(2κ 2 W (1− r(k 1 ∧ k 2 )1 k 1 ∧ k 2 ≤k + 1 k 1 ∧ k 2 >k ) + 5)σ 2 M · E[d 2 1 d 2 2 |k 1 ,k 2 ]. By (26) and the memoryless property of the geometric distribution, we have E[d 2 1 d 2 2 |k 1 ∧ k 2 >k] = (1− δ) 2 n ∞ X k 1 = k+1 ∞ X k 2 = k+1 δ k 1 +k 2 −2( k+1) D (DG) k 1, (DG) k ′ 1 E = (1− δ) 2 n ∞ X k 1 =0 ∞ X k 2 =0 δ k 1 +k 2 D (DG) k 1, (DG) k ′ 1 E = (1− δ) 2 n ∥(I − δDG) −1 1∥ 2 =E[d 2 1 d 2 2 ]. Finally, we have E[d 2 1 d 2 2 ∥W −1 j (1) W i W −1 j (2) − M∥ 2 ] =P (k 1 ∧ k 2 ≤ k)· E[d 2 1 d 2 2 ∥W −1 j (1) W i W −1 j (2) − M∥ 2 |k 1 ∧ k 2 ≤k]+ P (k 1 ∧ k 2 >k)· E[d 2 1 d 2 2 ∥W −1 j (1) W i W −1 j (2) − M∥ 2 |k 1 ∧ k 2 >k] ≤3(2κ 2 W (1− r(k)) + 5)· P (k 1 ∧ k 2 ≤k)· E[d 2 1 d 2 2 |k 1 ∧ k 2 ≤k]+ 3(4κ 2 W + 5)· P (k 1 ∧ k 2 >k)· E[d 2 1 d 2 2 |k 1 ∧ k 2 >k] ≤3(2κ 2 W (1− r( k)) + 5)· E[d 2 1 d 2 2 ]+ 3(4κ 2 W + 5)· P (k 1 ∧ k 2 > k)· E[d 2 1 d 2 2 |k 1 ∧ k 2 >k] =3(2κ 2 W (1− r(k)) + 5)· E[d 2 1 d 2 2 ]+ 3(4κ 2 W + 5)· δ 2(k+1) · E[d 2 1 d 2 2 ] =3(4κ 2 W + 5)E[d 2 1 d 2 2 ] 2κ 2 W (1− r( k)) + 5 4κ 2 W + 5 + δ 2(k+1) |z shrinkage of σ 2 M . The above result holds for arbitrary k ∈ [ k]. Thus, σ vr M σ bl M 2 ≤ min k∈[k] 2κ 2 W (1− r(k)) + 5 4κ 2 W + 5 + δ 2(k+1) ≤ 5(1+δ 4 ) 2κ 2 W + min k∈[k] 1− r(k) + 2δ 2k+2 5 2κ 2 W + 2 . H.3 Degree correlation Real-world network systems often exhibit degree correlation (Newman, 2018). Two polar cases are assortativity, where high-degree agents tend to connect to other high-degree agents, and disassortativ- ity, where high-degree agents tend to connect to low-degree agents. In our setting, degree correlation 37 affects the variance through the degree products accumulated along the random walks. While a general graph-level condition is less transparent than in Proposition 7, a stylized two-degree model already captures the key effect: assortativity keeps the walk in the high-degree class and amplifies the estimator, whereas disassortativity forces alternation between high- and low-degree classes and stabilizes it. Proposition 8. Suppose the network is undirected and unweighted, and every agent belongs to one of two degree classes with degreesd L < d H . Assume that under the vanilla uniform-neighbor walk in Poll, the induced degree-class process is exactly the two-state Markov chain P η : = η1− η 1− η η , η ∈ [0, 1], whereη = 1corresponds to perfect assortativity,η = 1/2to degree-independent mixing at the class level, and η = 0 to perfect disassortativity. Assume also that δd 2 H < 1. Let(σ bl N ) 2 and(σ vr N ) 2 denote the corresponding class-level upper bounds on the network variance term σ 2 N under η = 1 and under a general η ∈ [0, 1], respectively. Then, σ vr N σ bl N 2 ≲ 1− δd 2 H 1− δf d (η) , where f d (η) : = η(d 2 L + d 2 H ) + p η 2 (d 2 H − d 2 L ) 2 + 4(1− η) 2 d 2 L d 2 H 2 . Moreover, the right-hand side is non-decreasing in η, with 1− δd 2 H 1− δf d (1) = 1, 1− δd 2 H 1− δf d (0) = 1− δd 2 H 1− δd L d H < 1. In particular, degree disassortativity strictly reduces the variance proxy of the original estimator. When the degree gap is large, positive degree correlation can severely inflate the query complexity, while strong disassortativity can substantially reduce it, especially as δd 2 H ↑ 1. Proof. Letc l ∈ L, Hdenote the degree class visited at steplof a uniformly sampled walk, and write1 2 = (1, 1) T . Under the assumed two-class model,(c l ) l≥0 is a Markov chain with transition matrix P η . Define B η : = diag(d 2 L ,d 2 H )P η = ηd 2 L (1− η)d 2 L (1− η)d 2 H ηd 2 H . Then the class-level analogue of (26) gives, for a walk starting in class c∈L, H, E " k−1 Y l=0 deg 2 j l c 0 = c,k # = e T c B k η 1 2 , where e L ,e H are the standard basis vectors in R 2 . Integrating over k ∼ Geom(δ) yields E " k−1 Y l=0 deg 2 j l c 0 = c # = (1− δ)e T c (I − δB η ) −1 1 2 . Conditioned on the starting node, the two walks in Poll are independent. Hence E[d 2 1 d 2 2 | c 0 = c] = (1− δ) 2 e T c (I − δB η ) −1 1 2 2 . Averaging over the starting class and using Var(d 1 d 2 )≤ E[d 2 1 d 2 2 ], we get (σ vr N ) 2 ≤ E[d 2 1 d 2 2 ]≲ (1− δ) 2 (I − δB η ) −1 1 2 2 2 . 38 Let T : = diag(d L ,d H ). Since B η = TS η T −1 , S η : = ηd 2 L (1− η)d L d H (1− η)d L d H ηd 2 H , the matrices B η and S η have the same eigenvalues. Since S η is symmetric and nonnegative, (I − δB η ) −1 1 2 2 ≲ (1− δλ max (S η )) −1 , where the hidden constant is universal because the class space has fixed dimension two. Thus, (σ vr N ) 2 ≲ (1− δf d (η)) −2 , where f d (η) = λ max (S η ) equals f d (η) = η(d 2 L + d 2 H ) + p η 2 (d 2 H − d 2 L ) 2 + 4(1− η) 2 d 2 L d 2 H 2 . For the perfectly assortative baseline η = 1, we have S 1 = diag(d 2 L ,d 2 H ), f d (1) = d 2 H , and hence (σ bl N ) 2 ≲ (1− δd 2 H ) −2 . Taking square roots and then the ratio of the two bounds yields σ vr N σ bl N 2 ≲ 1− δd 2 H 1− δf d (η) . It remains to show monotonicity in η. For η ′ ≥ η, S η ′ − S η = (η ′ − η) d 2 L −d L d H −d L d H d 2 H = (η ′ − η) d L −d H d L −d H T ⪰ 0. Thus S η is increasing in the Loewner order, and therefore f d (η) is non-decreasing in η. Finally, f d (0) = d L d H , f d (1) = d 2 H , which implies 1− δd 2 H 1− δf d (1) = 1, 1− δd 2 H 1− δf d (0) = 1− δd 2 H 1− δd L d H < 1. This proves the claim. The same proof extends to any finite number of degree classes: the relevant quantity is the Perron root of the class-level matrixdiag(d 2 c )P, wherePis the transition matrix of the degree-class process. The two-class model makes this dependence explicit. H.4 Power law and importance sampling Many real-world networks exhibit a heavy-tailed power law degree distributiondeg i ∝ i −γ (Newman, 2003), which has large higher-order moments. For these networks,(1− δσ max (DG)) −1 can be a severe bottleneck. Our centrality characterization in (5) gives a natural remedy as it allows flexible sampling in (18). First, we note that the uniform sampling of neighbors can be directly generalized to accommodate weighted graphs using a weighted sampling such that agentj l is chosen with probability∝ G j l−1 j l without any modification to the algorithm or its analysis. We further notice that the degree product in our update direction is simply the probability normalization factor, or the importance weight, of the random walk. This motivates us to design a tailored sampling scheme and adjust the importance weight to ensure unbiasedness; this is the standard importance sampling technique. 39 Proposition 9. Consider a random walk sampling scheme where a neighborj l is sampled with probability∝ deg j l . The importance weight of this scheme is deg i deg j k k−1 Y i=0 deg ′ j i ,where deg ′ j = P j∈N j deg j |N j | is the average neighbor degree. We replace the degree product with this importance weight; other parts of the algorithm remain the same. Suppose the degreesdeg i i∈N follows a power law with exponentγand the network is generated by a mean field configuration model (Chung and Lu, 2002) with G ij = d i d j P i d i . Then, σ vr N σ bl N ≲ γ−4 δ(γ−2) − 1 γ−4 δ(γ−2) − min β∈[γ−2] f γ (β) , where f γ (β) : = 1 (1− β γ−2 )(1+ β γ−4 ) and min β f γ (β) = f γ (1) = (γ−2)(γ−4) (γ−3) 2 < 1. We see thatσ vr N /σ bl N ↓ 0asγ ↓ (1− δ) −1 (4− 2δ), which is when the original uniform sampling scheme fails, showcasing a significant variance reduction for heavy-tailed networks. Heuristically, our weighted sampling offers variance reduction from three aspects: 1.With lower entropy, weighted sampling returns more consistent trajectories. Specifically, weighted sampling consistently walks towards high-degree nodes. 2. Essentially all information, technological, and biological networks appear to be disassortative (Newman, 2003), in which a high-degree nodejis more likely to satisfydeg j ≥ deg j ′ for its neighborsj ′ , thus it is more likely thatdeg j =|N j |≥ deg ′ j , resulting in a smaller value of the degree product when using weighted sampling. 3.When ending at a high-degree node,deg i / deg j k < 1, further reducing the magnitude of the estimator when using weighted sampling. Consistent with importance sampling theory, we cannot expect a universal variance reduction across all classes of networks; instead, we should choose the right scheme based on the given structure. In Appendix H.4, we consider general importance sampling schemes and discuss principled ways of choosing the right importance weighting. H.4.1 Proof of Proposition 9 We consider a general importance sampling scheme which samples a neighbor ofj l−1 with probability ∝ G j l−1 j l h(j l ), where h(·) is a positive function to be designed. Following (18), we have [G k 1] i = X j 1 ∈N i G ij 1 [G k−1 1] j 1 = X j 1 ∈N i G ij 1 h(j 1 ) X j 1 ∈N i h −1 (j 1 ) G ij 1 h(j 1 ) P j 1 ∈N i G ij 1 h(j 1 ) [G k−1 1] j 1 . Lettingh ′ (i) : = h −1 (i) P j∈N i G ij h(j)and denotingE imp as the expectation under the importance sampling, we get [G k 1] i = h(i)h ′ (i)E imp j 1 h −1 (j 1 )[[G k−1 1] j 1 ]. By induction, we get [G k 1] i = E imp (j 1 ,...,j k ) " k−1 Y l=0 h(j l )h ′ (j l )h −1 (j l+1 ) # = E imp (j 1 ,...,j k ) " h(i)h −1 (j k ) k−1 Y l=0 h ′ (j l ) # . When h(j)≡ 1, h ′ (j) = deg j , and we recover the original uniform sampling procedure. Lemma H.1 (Importance weight variance). Denoteh 1 ,h 2 as the importance weights, which replace the degree products, of the two walks under the importance sampling procedure. LetH = diag(h(i)) and H ′ = diag(h ′ (i)). We have E imp [h 2 1 h 2 2 ] = (1− δ) 2 n ∥(I − δH ′ GH −1 ) −1 1∥ 2 . 40 Proof. We omit the superscript imp for brevity. Following (26), we have E " h 2 (i)h −2 (j k ) k−1 Y l=0 h ′ (j l ) 2 i,k # = X |ξ|=k h 2 (i)h −2 (j k ) k−1 Y l=0 h ′ (j l ) 2 · G ij 1 h(j 1 ) P j 1 ∈N i G ij 1 h(j 1 ) · G j k−1 j k h(j k ) P j k ∈N j k−1 G j k−1 j k h(j k ) = X |ξ|=k h(i)h −1 (j k ) k−1 Y l=0 h ′ (j l )· G ij 1 ·G j k−1 j k = X |ξ|=k H i H −1 j k j k k−1 Y l=0 H ′ j l j l G j l j l+1 =e T i H(H ′ G) k H −1 1. Then, following (27) and (28) gives E[h 2 1 h 2 2 ] = (1− δ) 2 n ∥(I − δH ′ GH −1 ) −1 1∥ 2 . Again, settingh(i)≡ 1gives the original variance in Lemma G.4. We should designhto minimize σ max (H ′ GH −1 ). Lemma H.2 (Expected configuration model). Consider a parameterized family of importance sampling schemes withh β (j) = deg β j forβ > 0. Given a degree sequencedeg i i∈N , letGbe generated by the expected Chung-Lu configuration model (Chung and Lu, 2002), i.e.,G ij = deg i deg j P i deg i . We have 1 n ∥(I − δH β H ′ β GH −1 β ) −1 1∥ 2 = (1 + 2z 2 g δ (β) + z 4 g 2 δ (β)), where z l = E[deg l i ] is the l-th moment of the degree distribution, and g δ (β) = δz 1+β z 1−β z 2 1 −δz 1+β z 3−β . Proof. We denote w l : = (deg l 1 ,..., deg l n ) T ∈ R n and z l : = E[deg l i ] for l > 0. Then, G = 1 nz 1 w 1 w T 1 , H β = diag(w β ), and H ′ β = diag(H −1 β Gw β ) = 1 nz 1 diag(H −1 β w 1 w T 1 w β ) = z 1+β z 1 diag(w 1−β ). Thus, H β H ′ β GH −1 β = 1 nz 1 H ′ β diag(w β )w 1 (diag(w −1 β )w 1 ) T = 1 nz 1 H ′ β w 1+β w T 1−β = z 1+β nz 2 1 w 2 w T 1−β . By the Sherman-Morrison formula, we have (I − δH β H ′ β GH −1 β ) −1 = I + δ n z 1+β z 2 1 − δz 1+β z 3−β w 2 w T 1−β . Let g δ (β) : = δz 1+β z 1−β z 2 1 −δz 1+β z 3−β . Finally, 1 n ∥(I − δH β H ′ β GH −1 β ) −1 1∥ 2 = 1 n 1 + δz 1+β z 1−β z 2 1 − δz 1+β z 3−β w 2 2 = 1 n (1 + 2z 2 g δ (β) + z 4 g 2 δ (β)). 41 Proof of Proposition 9.Since we allow weighted graphs, we consider real-valued degrees. The general moment of a continuous power law distribution is given by E[deg β i ] = γ− 1 γ− 1− β . Plugging this into Lemma H.2 gives ∥(I − δH β H ′ β GH −1 β ) −1 1∥ 2 = n(γ− 1) (γ− 5) 1− δ (γ− 2) 2 (γ− 2− β)(γ− 4 + β) −2 (γ− 4 + β) 2 (γ− 2 + β) 2 . Note that the second term monotonically decreases withf γ (β) : = (γ− 2− β)(γ− 4 + β), which achieves its maximum atβ = 1. The third term monotonically increases withβ. Thus, the optimal choice of β is in (0, 1). Compared to the baseline: ∥(I−δDG) −1 1∥ 2 =∥(I−δH 0 H ′ 0 GH −1 0 ) −1 1∥ 2 = n(γ− 1) (γ− 5) 1− δ (γ− 2) 2 (γ− 2)(γ− 4) −2 (γ− 4) 2 (γ− 2) 2 , we have σ vr N σ bl N = γ−4 δ(γ−2) − 1 γ−4 δ(γ−2) − 1 (1− β γ−2 )(1+ β γ−4 ) · 1 + β γ−4 1 + β γ−2 2 . We see that in the critical regime where1− δ γ−2 γ−4 ↓ 0,σ bl N diverges whileσ vr N is upper bounded by a constant, leading to σ vr N /σ bl N ↓ 0. I Proofs of economic efficiency I.1 Groves payment For a large-scale system, given the small query complexity in Theorem 1, a queried agent should not expect to be queried again. Thus, consistent with memoryless agents, we consider myopic agents who only care about maximizing their immediate utility in the current iteration when they are queried. Another feature of our method is that its asynchronous nature greatly simplifies an agent’s strategic considerations. When queried, an agent is presented with the current pricep t and can influence the updated pricep t+1 . Previous agents’ reports are settled inp t , unchangeable by the current agent, and a myopic agent is also not strategic against future agents. Therefore, the queried agent only plays a one-shot game against the planner. A fundamental aspect of any asynchronous distributed mechanism for (2) is that it’s incentive compatible, in the sense that at each iteration, the planner is essentially maximizing the “social welfare” of the queried agent, which is its utility: p t+1 = argmax p u i (p)− reg(p;p t ,α,μ), whereu i (p) : = u i (s ∗ (p),p)and the regularizer ensures the update is not too aggressive and takes into account the planner’s considerations. In other words, the update direction (linear system residual) calculated at each iteration is the steepest ascent direction for the queried agent’s regularized utility. Intuitively, the fundamental idea of an asynchronous distributed mechanism is to use the queried agent’s utility as a proxy for the social welfare, making the planner’s and the agent’s objectives aligned at each iteration. Formally, letΦ i be the utility kernel of agentiderived in Proposition 2 and e Φ i : = Ψ −1/2 Φ i Ψ −1/2 . Following (14), we have e Φ i = fcen T i f W −1 i fcen i , where f W −1 i = Ψ −1/2 W −1 i Ψ −1/2 is the planner- informed preference. Notably, we have established that E[ b Φ t |i] = fcen T i f W −1 i fcen i = e Φ i , i.e., b Φ t is an unbiased estimate of e Φ i , implying that the planner optimizes their objective using the queried agent’s utility as a proxy at each iteration, and thusPollis incentive compatible for the agent. 42 However, elimination of any incentive to misreport requires the agent to accept the regularizer, i.e., internalize the planner’s considerations in its utility. Otherwise, for example in our setting where agents have a utility convex in the price, the queried agent can scale up the price update by an arbitrary factor, leading to an unbounded unregularized utility. This internalization of the planner’s considerations can be achieved through a payment. Proposition 10. Suppose the queried agent has full control over the price updatep t+1 − p t , i.e., it has a strategy space R m , and for a submitted updated price p, the planner collects a payment of v(p) = μ 2 ⟨p− p 0 , Ψ(p− p 0 )⟩ + α −1 t ⟨p− p t , Ψ(p− p t )⟩ . Then, maximizing the total payoff gives argmax p u i (p)− v(p) = p t − α t ((I − ν e Φ i )p t − p 0 ) + O(α 2 t ), whereu i (p) : = u i (s ∗ (p),p)withs ∗ specified in (11) is the equilibrium utility of agenti, and e Φ i is its utility kernel such that u i (p) = 1 2 ⟨p, e Φ i p⟩. Since the agent does not know e Φ i but only has a stochastic estimate b Φ i , the above proposition implies that the agent’s best response when facing a payment is to report b Φ i according toPollalmost truthfully, i.e., with at most a higher-order deviation tolerated by our method. Our payment is Groves-like (Groves, 1973), as it does not depend on the reported preference of the queried agent but only on other agents’ reports and the planner’s objective. This connection suggests the strategyproofness of Poll with payment. We also share the same information structure as incentive design, where the planner first announces a strategy, the agent takes an action, and then the planner observes the action and takes its own action (collecting payment). In contrast, in a classic Stackelberg game, the leader does not observe the follower’s action before taking its own action. Note that the price update rule is the planner’s strategy but the update itself can be seen as the agent’s action, as it is determined by the agent’s report and is not modified by the planner. Proof of Proposition 10. Under payment, the total payoff of the queried agent is u G i (p) : = u i (p)− v(p) = 1 2 ⟨p, Φ i p⟩− μ 2 ⟨p− p 0 , Ψ(p− p 0 )⟩− μ 2α t ⟨p− p t , Ψ(p− p t )⟩, whose first-order condition is du G i (p) dp = Φ i p− μΨ(p− p 0 )− μ α t Ψ(p− p t ) = 0. For a sufficiently small step size α t , the payoff is concave and achieves its maximum at p G ∗ =(μ(1 + α −1 t )Ψ− Φ i ) −1 μΨ(p 0 + α −1 t p t ) = I − ν α t 1 + α t Ψ −1 Φ i −1 α t p 0 + p t 1 + α t = I + ν α t 1 + α t Ψ −1 Φ i p t + α t p 0 1 + α t + O(α 2 t ) =p t − α t 1 + α t I − ν 1 + α t Ψ −1 Φ i p t + α t 1 + α t I + ν α t 1 + α t Ψ −1 Φ i p 0 + O(α 2 t ) =p t − α t I − νΨ −1 Φ i p t + α t p 0 + O(α 2 t ) =p t − α t I − νΨ −1 Φ i p t − p 0 + O(α 2 t ), where the third and fifth equalities use(I + α t C) −1 = I − α t C + O(α 2 t ) for any constantC. Renormalizing all prices by p← Ψ 1/2 p gives the desired result. 43 I.2 Knightian uncertainty Lemma I.1 (Regret). Letu i ( c W i )be the equilibrium utility of agentiat the price updated byPoll with control variate and the reported preference c W i . The expected loss (or negative gain) w.r.t. the agent’s posterior beliefP by deviating from truthful reporting is R P ( c W i ) : = E P [u i (W i )−u i ( c W i )] =−α t trace C T I−W −1 i c W i I−c P W −1 i c W i c W −1 i +O(α 2 t ), whereC = νΦ i Ψ −1/2 p t p T t Ψ −1/2 withΦ i being the utility kernel of agenti, andc P = δ 2 /(1− δ) 2 E P [d 1 d 2 ] are constants w.r.t. c W i . Proof. Recall the update rule of Poll with control variate (30): p( c W i ) =p t − α t ((I − ν b Φ i )p t − p 0 ) =α t νΨ −1/2 c W −1 i + δ 2 /(1− δ) 2 d 1 d 2 W −1 j (1) c W i W −1 j (2) Ψ −1/2 p t + (1− α t )p t + α t p 0 + α t νδ/(1− δ)Ψ −1/2 d 1 W −1 j (1) + d 2 W −1 j (2) Ψ −1/2 p t |z c . c is a constant vector with respect to c W i .W −1 j (1) ,W −1 j (2) are the preferences reported by the endpoint agents of the two random walks, which are unknown to agentiand are not necessarily truthful.d 1 ,d 2 are the degree products of the two random walks, which are also unknown to agentibut signaled by the planner. The actual utility of agentidepends on its true preferenceW i and the updated price determined by c W i . LetPbe the agent’s posterior belief over the unknown variables after receiving the planner’s signals. We have E P u i ( c W i ) =E P 1 2 p( c W i ) 2 Φ i =E P 1 2 c + α t νΨ −1/2 ( c W −1 i + δ 2 /(1− δ) 2 d 1 d 2 W −1 j (1) c W i W −1 j (2) )Ψ −1/2 p t 2 Φ i =α t trace (νΦ i Ψ −1/2 p t p T t Ψ −1/2 | z C ) T c W −1 i + δ 2 /(1− δ) 2 E P d 1 d 2 W −1 j (1) c W i W −1 j (2) |z E P b Φ i + 1 2 ∥c∥ 2 Φ i + O(α t ) 2 .(31) Suppose in the posterior beliefW −1 j (1) andW −1 j (2) are independent and agentiuses its own preference as the posterior mean. Thus, E P u i ( c W i ) = α t trace(C T ( c W −1 i + δ 2 /(1− δ) 2 E P [d 1 d 2 ] | z c P W −1 i c W i W −1 i )) + 1 2 ∥c∥ 2 Φ i + O(α 2 t ). Then, the expected utility loss by deviating from truthful reporting is E P [u i (W i )− u i ( c W i )] =α t trace C T W −1 i − c W −1 i + c P W −1 i W i − c W i W −1 i + O(α 2 t ) =− α t trace C T I − W −1 i c W i I − c P W −1 i c W i c W −1 i + O(α 2 t ). Proof of Proposition 3. For a radial misreport c W i = ρW i , Lemma I.1 gives R P ( c W i ) = α t (1− ρ)(c P − ρ −1 ) trace(C T W −1 i ) + O(α 2 t ). Note thatC T W −1 i is of rank-one but non-zero, sotrace(C T W −1 i )̸= 0. Without loss of generality, supposetrace(C T W −1 i ) > 0. Then, when the agent overstates its preference, i.e.,ρ > 1, the planner picksc P < ρ −1 ; when the agent understates its preference, i.e.,ρ < 1, the planner picksc P > ρ −1 , leading to a positive regret in both cases when α t is sufficiently small. 44 Specifically, letρ= infρ : ρW i ⪰ λIandρ = supρ : ρW i ⪯λI. Thenρ ∈ [ρ,ρ] and we know thatρ≥ λ/λ = κ −1 W andρ ≤λ/λ= κ W . The planner’s signals ensure that the agent has posterior beliefsP − andP + such thatc P − = δ 2 /(1− δ) 2 d 2 − < κ −1 W ≤ρ −1 and c P + = δ 2 /(1−δ) 2 d 2 + > κ W ≥ ρ −1 . Then, the worst-case regret is always non-negative, and almost truthful reporting is the only strategy that achieves a zero worst-case regret, or formally: argmin ρ max P∈P − ,P + R P (ρW i ) = 1 + O(α t ). In other words, the planner induces the agent to believe the true update might be an extreme case where any deviation from truthful reporting leads to a positive regret, thus driving the agent to report truthfully. Note that the slope ofR P atρ = 1is proportional toc P − 1, but it has a negative Hessian independent ofc P . Therefore, the uncertainty structure needs to meet two requirements: it needs to change the sign of the slope and also make it steep enough to prevent the negative curvature from bending the regret below zero at larger deviations. Figure 2 illustrates the intuition. Remark 5 (General manipulation space). When the agent’s strategy space is relaxed to the general m-dimensional space of all possible preference matrices, coaltion between activities occurs (see Remark 3). Specifically, since the decoy signals only kills one degree of freedom, the agent can coordinate its activities to misreport in an orthogonal hyperplane that is not penalized by the decoy signals. An illustration is provided in Figure 10, generalizing the 2D case in Figure 2. To break this coalition, the planner can query one activity at a time. Consider the simplification in Section 3 where agents share the same activity kernel eigenbasis U . Note that Φ i = X a∈[m] φ i,a u a u T a = E a∼Unif([m]) φ i,a u a u T a . Thus, the planner queries one activityaat a time, which provides an unbiased estimate ofΦ i . Since now the manipulation space of φ i,a reduces to the one-dimensional case, Proposition 3 applies. 0 bu− u d + d − lnρ 2 lnρ 1 Figure 10: Although an ambiguity averse agent would avoid misreporting along one dimension, it can coordinate its activities to misreport along the other direction (highlighted in green). Remark 6 (Regret). We benchmark regret against truthful reporting, as truth minimizes the agent’s cognitive load (Li, 2017). Using the optimal misreport as the benchmark, which leads to the standard minimax regret in online learning, would require both the agent to compute the best misreport for each signal and the planner to craft signals with approximately equal optimal utility gains. I.2.1 Beyond full ambiguity aversion We extend Proposition 3 to consider a continuum of ambiguity attitudes, from full ambiguity aversion to full optimism. Definition 3 (θ-maxmin preference; Ghirardato et al. (2004), Marinacci (2002)). Given an uncertainty setC and an ambiguity attitude θ ∈ [0, 1], a θ-maxmin agent solves max c W i θ min P∈C E P [u i ( c W i )− u i (W i )] + (1− θ) max P∈C E P [u i ( c W i )− u i (W i )] . 45 The caseθ = 1recovers the maxmin preference in Proposition 3, andθ = 0corresponds to a fully optimistic agent that selects the best case. Proposition 11. Consider the setup of Proposition 3 with the maxmin preference replaced by the θ-maxmin preference, and letC =P − ,P + be induced by signals d − < d + . If θ > θ ∗ (d − ,d + ) : = max ( d 2 + − κ −1 W (1− δ) 2 /δ 2 d 2 + − d 2 − , −d 2 − + κ W (1− δ) 2 /δ 2 d 2 + − d 2 − ) , the agent’s optimal strategy deviates from the truth W i by at most O(α t ). Proof. Following the proof of Proposition 3, up toO(α 2 t ), the expected utility gain of the reportρW i increases inc P ± ifρ > 1and decreasing ifρ < 1. Thus, whenρ > 1, theθ-maxmin objective is proportional to(ρ− 1)(θc P − + (1− θ)c P + − ρ −1 ), which is strictly negative for allρ ∈ (1,ρ]if θc P − + (1− θ)c P + < κ −1 W ; forρ < 1, it is proportional to(ρ− 1)(θc P + + (1− θ)c P − − ρ −1 ), which is strictly negative for allρ∈ [ρ, 1)ifθc + + (1−θ)c − > κ W . Rearranging the two conditions givesθ > θ ∗ (d − ,d + ), under which truthful reporting uniquely attains the maximal (zero) objective up to O(α t ). Atθ = 1,θ ∗ < 1recovers the conditions ond ± in Proposition 3. Larger separations betweend − and d + do not necessarily lowerθ ∗ : a strongerd + deters understating but also amplifies the best case of overstating, and vice versa. I.3 Byzantine audit The above strategyproof mechanisms work for rational agents but are not necessarily robust to Byzantine agents, who may misreport an arbitrary preference for malicious purposes beyond their self-interest. Poll already possesses a natural device to safeguard against Byzantine agents, by forming an audit committee consisting of the agents at the endpoints of the random walks at each iteration. Suppose agents observe or communicate each other’s equilibrium efforts at the initial price, and try to form an estimate of each other’s preferences. Then, an endpoint agent can check this estimate against the reported preference of the queried agent, and submit an audit report. The planner rejects the vote if many audit committee members report a large mismatch. Note that an agent’s equilibrium effort is influenced by its own preference and the preferences of all other agents it is connected to. Therefore, without knowing other agents’ preferences, an agent’s estimate of another agent’s preference is highly uncertain. This motivates the use of a batch of random walks at each iteration, which not only reduces the variance ofPollbut also forms a more credible audit committee. Proposition 12. Suppose agents have the same set of activity bundles, the initial price is non-zero for all principal activity bundles, i.e.,U T p 0 has no zero entry. Suppose agents’ equilibrium efforts at the initial pricep 0 are public information. Letibe the queried agent andjbe an agent at the end of a random walk inPoll. Letd j be the degree product of the corresponding random walk. Suppose no collusion. Afterjseesi’s reported preference c W i , it submits an audit reportχ j = c W −1 i p 0 −s ∗ i (p 0 )+δ(1−δ) −1 d j W −1 j p 0 , which is an unbiased estimate of mismatch c W −1 i p 0 −W −1 i p 0 . Given a batch ofBrandom walks at each iteration, we reject the vote if the audit committee gives an aggregated report∥ 1 B P B j=1 χ j ∥ > ε B , whereε B = 2δd∥p 0 ∥ (1−δ) 2 λ q ln(2m/ι) B . Then, with probability at least1− ι, any accepted report c W i has a bounded mismatch∥ c W −1 i − W −1 i ∥ ≤ 2ep 0 −1 ε B and ∥ c W i − W i ∥≤ 2ep 0 −1 λ 2 ε B , where ep 0 : = min a∈M [U T p 0 ] a . To completely hold Byzantine agents in check, i.e., guarantee a mismatch of only higher or- der,Pollneeds a large batch size, which is inevitable as we adopt a sampling approach. A simple deterministic approach is using neighbors as the auditing committee, rejecting a vote if c W i s ∗ i (p 0 )− δ P j∈N i s ∗ j (p 0 ) ̸= p 0 , which guarantees that any accepted report is exactly truthful. However, this approach (a) is not robust to any noise, (b) makes it easier for agents to collude as 46 the audit committee has fixed members consisting of the queried agent’s nearest neighbors, and (c) requires implementing a separate module rather than being directly enabled by Poll. If we accept a non-vanishing Byzantine-induced error, our result is consistent with the current literature on Byzantine-robust federated learning (Yin et al., 2018), which shows the error is of q bσ 2 nB , whereb/nis the fraction of Byzantine agents,Bis the number of local steps, andσ 2 is the variance of the stochastic gradients. This is recovered by our result recognizing that multiple random walks are equivalent to multiple local steps, which also reduces the variance of the stochastic update. Proof of Proposition 12. By (11), s ∗ i (p) =[((I n − δG) −1 ⊗ I m ) blkdiag(W −1 i )] i p = ∞ X k=0 δ k X j∈N (G k ) ij W −1 j p =W −1 i p + δ(1− δ) −1 E k∼Geom(δ) X j∈N (G k+1 ) ij W −1 j p =W −1 i p + δ(1− δ) −1 E random walk (i,...,j k ) of length k∼Geom(δ) " k−1 Y l=0 deg j l W −1 j k p # . The expectation above is w.r.t. the exact same sampling process inPoll, giving a natural audit committee consisting of the agents at the endpoints of the random walks inPoll. Separating private W i and public information gives W −1 i p = s ∗ i (p)− δ(1− δ) −1 E[d j W −1 j p], where we denotejas a generic endpoint agent of a random walk andd j as the degree product of the walk. Checking against the submitted report c W i , an audit report from an endpoint agent j is thus χ j = c W −1 i p 0 − s ∗ i (p 0 ) + δ(1− δ) −1 d j W −1 j p 0 , giving the average report χ B : = 1 B B X j=1 χ j = c W −1 i p 0 − s ∗ i (p 0 ) + δ(1− δ) −1 1 B B X j=1 d j W −1 j p 0 . That is, we replace the expectation with the batch average. Note that∥d j W −1 j ∥ ≤ k j d/λwhere k j ∼ Geom(δ)has a sub-exponential norm ofO((1− δ) −1 ). Thus, by Bernstein’s inequality, for any ε B ∈ (0, (1− δ) −1 d/λ), if agent i reports truthfully, we have P δ(1− δ) −1 1 B B X j=1 d j W −1 j p 0 − E[d j W −1 j p 0 ] > ε B ≤2m exp −4 −1 Bδ −2 (1− δ) 4 λ 2 ∥p 0 ∥ −2 d −2 ε 2 B . Let ι = 2m exp −4 −1 Bδ −2 (1− δ) 4 λ 2 d −2 ∥p 0 ∥ −2 ε 2 B =⇒ ε B = 2δ d∥p 0 ∥ (1− δ) 2 λ r ln(2m/ι) B ! . Then with probability at least1−ι, we know the noise in the average audit report is at mostε B . Thus, the planner rejects c W i if∥χ B ∥ > ε B . Consequently, if a report c W i is accepted, with probability at 47 least 1− ι, we have ∥ c W −1 i p 0 − W −1 i p 0 ∥ =∥ c W −1 i p 0 − s ∗ i (p 0 ) + δ(1− δ) −1 E[d j W −1 j p 0 ]∥ ≤ c W −1 i p 0 − s ∗ i (p 0 ) + δ(1− δ) −1 1 B B X j=1 d j W −1 j p 0 + δ(1− δ) −1 1 B B X j=1 d j W −1 j p 0 − E[d j W −1 j p 0 ] ≤∥χ B ∥ + ε B ≤2ε B . Under the shared activity kernel eigenbasis assumption, we have ∥ c W −1 i − W −1 i ∥≤ 1 min a∈M |ep 0,a | ∥ c W −1 i p 0 − W −1 i p 0 ∥≤ 2ep 0 −1 ε B , where ep 0 = U T p 0 and ep 0 : = min a∈M |ep 0,a | is assumed to be non-zero. And we have ∥ c W i − W i ∥≤ 2ep 0 −1 λ 2 ε B . 48