PaperlayerView exact revision on arXiv

Source-linked AI summary

Network Intervention by Polling Strategic Agents

Chenyu Zhang, Rohit Parasnis, Saurabh Amin

arXiv:2610.08347v1cs.GTcs.MAcs.SImath.OCstat.ML

TL;DR

A network planner must choose welfare-maximizing policy despite agents’ private information and strategic responses, while learning from reports and disciplining them. The paper characterizes optimal intervention through preference-reweighted centrality and motivates Poll; on DBLP, Poll reaches near-optimal welfare with 316–1572× fewer pairwise exchanges than other distributed methods.

  • Problem

    Network planners must set welfare-maximizing policies for networked, strategic agents with private information while learning from reports and disciplining them.

    Source: §1 · pp. 1–2

  • Method

    The paper characterizes optimal intervention through agents’ centralities in a preference-reweighted network and uses this to motivate Poll’s local polling process.

    Source: §1 · p. 2

  • Results

    316–1572× fewer pairwise exchanges let Poll reach near-optimal welfare than other distributed methods on the complete DBLP coauthorship network with 317,080 agents.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The paper concludes that Poll’s computational, learning, and economic efficiencies all flow from a centrality-based characterization of optimal intervention.

    Source: §7 · p. 10

    In the worst case of growing heterogeneity, the query-complexity bound degrades to O(ϵ^-2(1 - δn^2)^-2) for a star graph.

    Source: §5.2 · p. 8

Abstract

from arXiv · show

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.

1 Introduction

The paper studies how a planner can set welfare-maximizing prices by polling strategic agents whose private technologies and network positions affect both their responses and the computation required. A centrality-based characterization motivates Poll and its computational, statistical, and economic efficiency claims.

1 Introduction

  • Learning, strategic reporting, and computation are entangled because the optimal policy depends on private information and network position, while queried agents may misreport to influence it.The planner therefore must learn from reports while disciplining them, without directly observing agents’ private information.Source: §1 · pp. 1–2
  • Heterogeneous private technologies make the planner’s problem network-dependent, and optimal prices decompose welfare contributions by squared centrality in a preference-reweighted network.Poll samples an agent, walks briefly through its neighborhood, aggregates a local preference for the price change, and updates the price. The paper says the underlying principle also extends to semi-decentralized federated learning.Source: §1 · pp. 2–3
  • On the complete DBLP network of 317,080 agents, Poll reaches near-optimal welfare with 316–1572× fewer pairwise exchanges than other distributed methods.Poll also uses fewer operations than exact computation or other distributed methods and supports decentralized, asynchronous, and online implementations.Source: §1 · p. 2
  • Poll’s query complexity falls with homogeneity in network topology and activity preferences, it has variance-reduction properties, and it is robust to endogenous and exogenous noise.These statistical efficiencies are presented alongside Poll’s convergence to welfare-maximizing prices and strategy-proof and Byzantine-robust implementations that induce truthful reports and detect adversarial deviations.Source: §1 · p. 2

1.1 Related work

  • Prior intervention studies characterize network centrality or optimal pricing, but assume homogeneous costs or knowledge of network topology or agent types, unlike this work’s learning setting.The cited work includes Ballester et al. (2006), Parise and Ozdaglar (2021), Galeotti et al. (2020), Chen et al. (2018), Kor and Zhou (2023), Parasnis and Amin (2025), and Dasaratha et al. (2024).Source: §1.1 · p. 3
  • Strategic distributed learning spans federated learning, mechanism design, control and optimization, and performative prediction; this design draws on ambiguity aversion, incentive design, and Byzantine-robust learning.The passage cites work across these areas, including Blum et al. (2021), Fallah et al. (2024), Tanaka et al. (2015), Mendler-Dünner et al. (2020), Gilboa and Schmeidler (1989), and Blanchard et al. (2017).Source: §1.1 · p. 3

2 Problem setup

The setup models strategic agents choosing across activities under a common price, heterogeneous private technologies, and network spillovers. Under small-interaction and regularization assumptions, the planner’s welfare-maximizing intervention is well-defined and unique.

2 Problem setup

  • Agents’ costs depend on heterogeneous private technologies, while a common price and network spillovers shape their utilities and activity choices.Each agent’s technology captures how its activities complement one another; spillovers depend on both technology and network position.Source: §2 · p. 3
  • The small-network-effect condition ensures a unique Nash equilibrium and oscillation-free best-response dynamics.The condition is δσmax(DG) < 1.Source: §2 · pp. 3–4
  • Sufficient regularization makes the planner’s intervention objective concave, with an existing and unique optimum.The condition is µΨ ≻ Φ; Ψ can encode budget constraints, sustainability considerations, or prior beliefs.Source: §2 · p. 4

3 A centrality-based interpretation

The section shows that the welfare kernel decomposes into activity-bundle contributions weighted by squared centralities in networks reweighted by agents’ preferences. It then explains how centrality elasticity shapes agents’ utility responses to preferences and why network ignorance creates uncertainty that can help mitigate manipulation.

3 A centrality-based interpretation

  • Optimal intervention for a bundle increases with its welfare-kernel eigenvalue, while an agent’s equilibrium effort in that bundle increases as its technology cost falls.The bundle corresponds to a linear combination of activities specified by a shared eigenbasis in the section’s simplifying case.Source: §3 · p. 4
  • The welfare kernel assigns each activity bundle an intervention determined by agents’ squared centralities in a network reweighted by their preferences for that bundle.Each bundle-induced network aggregates preferences through interactions, and its centralities determine the optimal intervention.Source: §3 · p. 4
  • The bundle-induced centrality structure favors susceptible agents who absorb influence and agents with lower preference for the bundle, while the planner targets bundles through non-discriminatory prices.A higher bundle cost can mean greater compensation from neighbors’ efforts, as in the R&D example.Source: §3 · pp. 4–5

3.1 Centrality elasticity

  • Centrality elasticity links an agent’s utility sensitivity to its preference with the shares of its centrality walks that end at itself versus other nodes.An agent absorbing more influence has high elasticity and can benefit from spillovers as it further reduces its preference; in the R&D example, this measures marginal returns on investment.Source: §3.1 · p. 5
  • The utility effect of changing preference flips exactly when self-contribution and others’ contribution to centrality are equal, leaving network-ignorant agents uncertain about the direction of the effect.This ambiguity is a lever for the planner to mitigate strategic manipulation.Source: §3.1 · p. 5

4 A polling algorithm

Poll is a distributed algorithm for computing the optimal intervention, motivated by its centrality-based characterization and designed to reduce the cost of exact computation. It estimates the aggregate preference through local sampling and uses the estimate to update the price.

4 A polling algorithm

  • Exact computation of (4) requires O(n3 + n2m2 + nm3) operations, motivating Poll’s distributed approach to computing the optimal intervention.Poll uses local reports and sampling rather than requiring the planner or agents to know the full network structure.Source: §4 · pp. 5–6
  • Under Assumption 2, the iterative scheme is contractive, converges to the optimal solution q∗, and has complexity O(n3 + tm2) after t iterations.Source: §4 · p. 5
  • The stochastic approximation uses a step size satisfying Robbins and Monro (1951), and its convergence rate depends on the stochastic estimate’s bias and variance.Source: §4 · p. 6
  • Poll’s estimate of eΦ is unbiased: each round samples an agent and uses two independent random walks, which are required for an unbiased estimate of the quadratic term.The random walk length follows a geometric distribution, and each step samples uniformly from the current agent’s incoming neighbors.Source: §4 · p. 6
  • At each round, the planner samples an agent, starts two walks, collects degrees, and asks endpoints to report preference-price products for the price update.Neither planner nor agents need network knowledge beyond local neighborhoods; agents do not report raw preferences, preserving privacy and reducing communication and computation.Source: §4 · p. 6

5 Efficiency guarantees

Poll reduces the cost of computing and learning welfare-maximizing prices, with query needs governed by preference and network heterogeneity rather than population size. Its economic-efficiency guarantees include a mechanism that limits strategic misreporting under specified uncertainty and behavioral assumptions.

5.1 Computational efficiency

  • Poll requires O(tm^2) operations, compared with O(n^3 + m^2) for exact computation, while its per-query computation is independent of n.Computing bΦt costs O(m^2), and the number of queries t is independent of n.Source: §5.1 · p. 7
  • Poll requires no agent memory or central collection of private technology, and uses O(m) planner storage with O(t) expected communication rounds.Each asynchronous price update involves one queried agent communicating through two random walks; Poll also adapts online to dynamic environments and is robust to endogenous query noise and exogenous shocks.Source: §5.1 · p. 7

5.2 Learning efficiency

  • Poll’s query complexity is bottlenecked by preference and network heterogeneity, not explicitly by population size.Theorem 1 characterizes learning error under its stated assumptions and step-size condition; even equal-centrality networks can retain random-walk variance from network asymmetry.Source: §5.2 · p. 8
  • The dimension-agnostic query guarantee is not universal: on a star graph, d = n and σmax(DG) = n^2, worsening the bound.For d-regular graphs, the stated network-heterogeneity bound is independent of n; real-system heterogeneity may nevertheless grow with system size.Source: §5.2 · p. 8

5.3 Economic efficiency

  • Under max-min utility, if the agent’s uncertainty set contains both degree-product extremes, its optimal report deviates from truth by at most O(αt).The planner creates uncertainty with decoy walk signals; Proposition 3 focuses on one-dimensional preference scaling and max-min utility, while Appendix I.2 analyzes a continuum of ambiguity attitudes.Source: §5.3 · p. 9

6 Numerical experiments

Poll is evaluated on synthetic settings and a large real-world coauthorship network, where it demonstrates computational and learning efficiency, robustness to manipulation, and truthful reporting across a range of ambiguity attitudes.

Synthetic data

  • Synthetic simulations show Poll’s runtime scaling, heterogeneity-aware query complexity, and robustness to decoy manipulation by ambiguity-averse agents.The manipulation test compares mean relative error against the optimal price with no decoys, random decoys, and carefully designed decoys.Source: §6 · p. 10, Figure 3 · p. 10

Real-world network

  • On DBLP (317,080 authors; 1,049,866 edges), Poll reaches Gap ≤ 10^-5 with 316× to 1572× fewer exchanges than other distributed methods, and its gap is below 4 × 10^-8 before Federated and Consensus produce their first updated iterate.Exact computation is omitted as infeasible at this scale; Random-Walk does not reach either threshold within 10^9 exchanges.Source: Table 4 · p. 10, §6 · p. 10
  • On DBLP, designed decoys elicit truthful reports for a nontrivial range of ambiguity attitudes, from fully ambiguity-averse to fully optimistic.The stress test uses multi-dimensional reports and includes the fully ambiguity-averse case from Proposition 3.Source: §6 · p. 10

7 Conclusion · Appendix · A Additional numerical experiments

The polling algorithm’s computational, learning, and economic efficiency all follow from a centrality-based characterization of optimal intervention. Some results rely on linear-quadratic utility, and the payment-free incentive guarantee requires sufficient ambiguity aversion.

7 Conclusion

  • The polling algorithm’s computational, learning, and economic efficiency all flow from a centrality-based characterization of optimal intervention.The conclusion identifies this characterization as the common basis for the algorithm’s efficiencies.Source: §7 · p. 10
  • Some results rely on linear-quadratic utility, while the payment-free incentive guarantee requires sufficient ambiguity aversion.Extending the analysis to general utilities and designing decoys for more optimistic agents remain open.Source: §7 · p. 10

A.1 Synthetic data … B.2 Specific structures

Across synthetic and real-world settings, Poll reduces computation or communication costs, while its query complexity and strategic performance depend on network and preference heterogeneity and signal design. The appendix also generalizes the game formulation, derives equilibrium conditions, and contrasts shared with heterogeneous activity technologies.

A.1 Synthetic data

  • Poll is the only tested method whose operation complexity does not scale with n; the other methods scale polynomially, with exact computation worst at O(n3).The comparison uses m = 10 and three random graph models, with k = 10 and MRE tolerance 10−3 for non-exact methods.Source: §A.1 · p. 16
  • Poll’s query complexity increases with both preference and network heterogeneity in the directed Watts–Strogatz experiments.Rewiring probability p is a proxy, not an exact equivalent, for network heterogeneity σM.Source: §A.1 · p. 16
  • Random signals induce 50% truthful reporting among ambiguity-averse agents, whose systematic tendency is to understate preferences.A sufficiently strong one-directional signal can deter that misreporting; stronger network effects make misreporting more uniform, while larger δ increases method variance and query complexity.Source: §A.1 · pp. 16–17, Table 5 · p. 17

A.2 Real-world network

  • At welfare-gap thresholds 10−5 and 10−7, Poll reduces communication relative to Consensus, Federated, and Gossip by 1572×, 1023×, and 316×, then 48×, 34×, and 10×, respectively.When Federated and Consensus first produce updated iterates at 1,366,946 and 2,099,732 exchanges, respectively, Poll has already reached welfare gaps of 3.15 × 10−8 and 2.51 × 10−8.Source: §A.2 · p. 18
  • Designed signals eliminate manipulation for DBLP agents with θ ≥0.8, while polarized signals outperform randomization for θ ≤0.7 and underperform it for θ ≥0.8.For θ <0.8, designed signals fail because optimistic agents exploit the amplified best case; random signals retain partial deterrence, while polarized signals’ effects depend on whether the signal matches the profitable manipulation direction. Both are alternative decoy-signal distributions, not standalone mechanisms.Source: §A.2 · pp. 18–19, Figure 6 · p. 19

B General problem setup

  • In general multi-activity network games, utility combines marginal-price and interaction terms, and activity choices by each agent form a cooperative coalition rather than competing players.The distinction between agent and activity spaces is important for analyzing strategic manipulation.Source: B General problem setup · p. 19

B.1 Nash equilibrium

  • Under Assumption 4’s concavity and small-network-effect conditions, an unbounded strategy space yields the unique Nash equilibrium s*(p) = (QI − QC)^−1p.QI captures idiosyncratic effects and QC captures network effects; QI is positive definite and QI − QC is invertible.Source: §B.1 · p. 20

B.2 Specific structures

  • With heterogeneous technologies Wi, the game kernel no longer has a tensor structure, and may be nonsymmetric even when Wi and G are symmetric.With shared activity interaction W and network G, the tensor structure obscures the network effect under non-discriminatory intervention.Source: §B.2 · pp. 20–21

B.3 Optimal intervention … C.4 Semi-decentralized federated learning

The intervention’s dependence on network structure varies with agents’ activity kernels, while the motivations and federated-learning example explain how shared prices, private technologies, and local peer exchange create the setting Poll addresses. The section also explains why intervention may be non-discriminatory and how regularization can encode planner priorities.

B.3 Optimal intervention

  • With a shared tensor structure, network differences affect only regularization strength; heterogeneous activity kernels instead make each activity’s optimal intervention depend on its own network.Source: §B.3 · p. 22
  • The regularizer can encode a hard L2 budget, sustainability preferences, partial authority over activities, intervention costs, and prior beliefs about private technologies.Source: §B.3 · p. 22

C Motivations

  • The motivations focus on heterogeneous activity kernels, network spillovers, and non-discriminatory price intervention.Source: C Motivations · p. 22

C.1 Public price and private technology

  • The model pairs a public price with private technologies, with each agent’s cost capturing its technology and network spillovers through an activity-interaction matrix.Source: §C.1 · p. 22

C.2 Absorptive capacity

  • Quadratic costs model absorptive capacity and aligned, beneficial cross-agent and cross-activity spillovers using the same Wi; shared eigenbases represent standardized exchange, and industry clusters illustrate complementary technologies.Source: §C.2 · p. 23

C.3 Non-discriminatory subsidy/tax

  • Non-discriminatory prices are motivated by fairness, practicality, and limiting arbitrage; aggregating agents’ opinions also makes network effects salient.Source: §C.3 · p. 23

C.4 Semi-decentralized federated learning

  • A client’s local geometry filters the public signal through its inverse, while peer exchange rewards aligned neighboring models and can correct directions dampened by that geometry.Source: §C.4 · p. 24
  • Private client data geometries and potentially unknown network positions jointly shape the welfare-maximizing public signal, which Poll learns through client queries and local graph walks without centralized access to raw geometries or the full network.Source: §C.4 · p. 24

D Derivations of solution characterizations … D.4 Proof of Proposition 2

The derivations characterize the intervention through bundle-specific centralities when agents share activity eigenbases, and show how general planner or agent preferences couple those networks. They also connect agents’ equilibrium utility kernels to the social-welfare kernel.

D.1 Bundle-induced networks

  • Proposition 4 diagonalizes the welfare kernel in the shared activity eigenbasis, with each diagonal element characterized using bundle-induced networks.The eigenvectors of Φ are the columns of U, and Φ = UΛΦU^T.Source: §D.1 · p. 25
  • Each bundle-induced network’s Katz–Bonacich centrality measures how strongly agents are influenced within that activity bundle.The cited passage identifies f_cena,i as agent i’s centrality in the network induced by bundle a.Source: §D.1 · p. 25

D.2 Planner-informed second-stage communication

  • When planner and agent preferences share an eigenbasis, activity bundles determine interventions independently; general planner preferences instead couple the bundle-specific networks.A general planner preference introduces a second communication stage, with Ψ^-1Φ as the higher-level communication network; shared eigenbases make this network diagonal.Source: §D.2 · p. 26
  • The intervention then has two communication stages: agents communicate within bundle-induced networks to form votes, and the planner mediates across networks to form the final intervention.A planner activity bundle may align with multiple agent bundles, requiring coordination among their networks.Source: §D.2 · p. 26

D.3 Proof of Proposition 1

  • When agents’ activity kernels lack a common eigenbasis, bundle-induced networks no longer apply, and the characterization instead uses a planner-informed network with matrix-valued edge weights.The modified network incorporates planner preferences as well as agents’ preferences.Source: §D.2 · p. 26, §D.3 · p. 26

D.4 Proof of Proposition 2

  • Under a shared activity eigenbasis, each agent’s utility kernel has a form similar to the social-welfare kernel, and equilibrium utility is monotonic in that kernel under the Loewner order.The social-welfare kernel aggregates agents’ utilities; for a fixed price, the proof therefore tracks how each eigenvalue changes with preference.Source: §D.4 · p. 27

E Centrality simulations

A seven-data-center, two-activity example illustrates the theoretical results in a directed provider-to-client cascade, with the planner optimizing an intervention from p0 = (2, 0)^T under an L2 budget of 1.

E Centrality simulations

  • Although providers are most central in the original network, client-side centers 6 and 7 become most central in the archival and retrieval committees, respectively, despite low preferences for those activities.Center 6 is the most central archival committee member despite low archival preference; center 7 is the most central retrieval committee member despite low retrieval preference.Source: E Centrality simulations · p. 28, Figure 7 · p. 28
  • Despite a slight archival bias, the intervention spends relatively more on retrieval, increasing neutral centers’ retrieval effort to empower reluctant members influential in that activity’s committee.The effort increases toward retrieval for centers 3–5.Source: E Centrality simulations · pp. 28–29, Figure 8 · p. 28
  • As retrieval reluctance rises, optimal retrieval intervention decreases at cloud center 1 but increases at backup center 7, illustrating how network effects can counter individual preferences.The comparison also plots intervention levels for isolated centers without network effects.Source: E Centrality simulations · p. 29, Figure 9 · p. 29

F Implementation details of Poll

Poll’s implementation is model-free: the planner has no prior knowledge of the network or agents’ technologies, and each time step uses random walks to update prices. The protocol’s communication and computation costs are O(m) and O(m²), respectively.

Random walks

  • The random-walk scheme also accommodates weighted graphs, and a walk can stop with a zero estimate when an intermediate agent has no incoming neighbor.In that case, the degree product is zero.Source: F Implementation details of Poll · p. 29

Knowledge

  • The planner has no prior knowledge of the network or agents’ technologies; agents know only their local neighborhoods, and their technologies are private.The initial price p0 and corresponding Nash equilibrium s∗(p0) are public; agents need neighbors’ degrees only for the general importance-sampling scheme.Source: F Implementation details of Poll · p. 30

Behavior

  • After announcing Poll, the planner samples agent i; agents report degrees, follow two walks, process the query through endpoint products, and return the final report that determines the updated price.After receiving the final report, the planner needs no further action unless using a payment mechanism whose payment depends on that report.Source: F Implementation details of Poll · p. 30
  • The analysis covers strategic misreporting of W_i only, assuming faithful degree reports and walks executed as specified; broader strategic behaviors are left to future work.Poll variations with control variates use the same communication protocol.Source: F Implementation details of Poll · p. 30

Complexity

  • At each time step, each random walk has O(m) expected communication complexity, while endpoint agents perform three matrix-vector multiplications for O(m²) computation.Each walk uses at most two rounds of message passing, carrying scalar degrees or vectors of length m.Source: F Implementation details of Poll · p. 31

Privacy

  • Even when endpoint identities are known, the planner cannot infer agents’ preferences from the final report.Agents’ cost structures may not share the same eigenbasis.Source: F Implementation details of Poll · p. 31

G Proofs of learning efficiency … H.2 Preference correlation

The proofs establish Poll’s robustness to noisy queries and derive its learning-efficiency bounds. The variance-reduction sections use a control variate and show how positive preference correlation can further reduce query complexity.

G Proofs of learning efficiency

  • With zero-mean additive noise, the update-direction variance increases by the noise variance; bounded noise can leave a non-vanishing error floor when σ² = ω(√α).The paper presents this robustness result as supporting approximate truthfulness under noisy queries.Source: G Proofs of learning efficiency · p. 32
  • Positive preference correlation can sharpen the variance bound when technology heterogeneity κW is large, whereas a wide range of technologies can make κW a bottleneck.The proof accounts for coupling between degree products and preference products that can arise when sampled walks overlap.Source: G Proofs of learning efficiency · pp. 32, 34
  • Combining Lemmas G.1–G.4 yields the query-complexity result in Theorem 1.Source: G Proofs of learning efficiency · p. 35

H Variance reduction

  • The variance-reduced update retains the same operation complexity while reducing variance.Source: §H.1 · p. 36

H.1 Control variate

  • The control variate uses the known expectation of the k = 0 case, which is a significant part of the estimator under its exponential tail, and samples only the residual.Subtracting the control variate and adding its expectation yields an unbiased, variance-reduced estimator.Source: §H.1 · p. 36

H.2 Preference correlation

  • When κW is large, positive preference correlation can significantly reduce query complexity as r(1) approaches 1 and δ decreases.The result assumes a non-increasing correlation function with r(0) = 1 and r(1) > 0.Source: §H.2 · p. 36

H.3 Degree correlation … I.1 Groves payment

Degree correlation and tailored importance sampling shape Poll’s estimator variance, while Groves-like payments can align queried agents’ incentives with truthful reporting. The sections specify when these variance and incentive properties hold and where they require conditions.

H.3 Degree correlation

  • Strong disassortativity strictly reduces Poll’s variance proxy, while positive degree correlation can inflate query complexity, especially with a large degree gap.In the two-degree model, disassortativity stabilizes the estimator by forcing walks to alternate between high- and low-degree classes; assortativity keeps walks among high-degree agents.Source: §H.3 · p. 38
  • For multiple degree classes, the relevant variance quantity is governed by the Perron root of the class-level matrix diag(d_c^2)P.The two-class model makes this dependence explicit.Source: §H.3 · p. 39

H.4 Power law and importance sampling

  • For heavy-tailed networks, Poll can sample neighbors with probability proportional to degree and replace the degree-product update factor with an unbiased importance weight.The passage also extends uniform-neighbor sampling to weighted graphs without changing the algorithm or its analysis.Source: §H.4 · pp. 39–40
  • The tailored sampling scheme significantly reduces variance for heavy-tailed networks as the power-law exponent approaches the regime where uniform sampling fails.The analysis considers a mean-field configuration model and reports the variance reduction as the exponent approaches the stated failure boundary.Source: §H.4 · p. 40

H.4.1 Proof of Proposition 9

  • Within the family hβ(j) = deg_j^β, the optimal exponent β lies strictly between 0 and 1.The second term of the variance expression decreases up to β = 1, while the third increases with β.Source: §H.4.1 · pp. 41–42

I.1 Groves payment

  • Because Poll is asynchronous, a myopic queried agent faces a one-shot interaction, and its utility provides an unbiased proxy for the planner’s objective, making Poll incentive compatible.Earlier reports are settled at the current price, and the queried agent does not act strategically against future agents.Source: §I.1 · p. 42
  • Truthful-report incentives require the agent to accept the regularizer; without it, an agent with utility convex in price can scale the update arbitrarily and obtain unbounded utility.Source: §I.1 · p. 43
  • With the Groves-like payment, the queried agent’s best response is to report Poll’s stochastic estimate almost truthfully, with at most a higher-order deviation.The payment depends on other agents’ reports and the planner’s objective, not the queried agent’s reported preference.Source: §I.1 · p. 43

I.2 Knightian uncertainty · I.2.1 Beyond full ambiguity aversion · I.3 Byzantine audit

The paper extends Poll’s truth-inducing signals beyond full ambiguity aversion and develops random-walk audits to detect Byzantine misreports. Its guarantees depend on the agent’s ambiguity attitude, the manipulation space, and the audit design.

I.2 Knightian uncertainty

  • Under full ambiguity aversion, planner signals can make almost-truthful reporting the only strategy with zero worst-case regret.For radial over- or understatements, the planner can induce positive regret when α_t is sufficiently small; the signals create plausible extreme cases that penalize deviations.Source: §I.2 · pp. 44–45
  • With unrestricted preference matrices, agents can coordinate misreports in an orthogonal direction that decoy signals do not penalize; querying one activity at a time restores the one-dimensional case.The workaround assumes agents share the same activity-kernel eigenbasis.Source: §I.2 · p. 45

I.2.1 Beyond full ambiguity aversion

  • For θ-maxmin agents, the optimal report deviates from truth by at most O(α_t); above θ*(d−, d+), truth uniquely attains the maximal zero objective up to O(α_t).θ = 1 recovers the full maxmin case, while θ = 0 represents full optimism.Source: §I.2.1 · pp. 45–46
  • Greater separation between d− and d+ does not necessarily lower θ*, because stronger signals deter one direction of misreporting while amplifying the other’s best case.A stronger d+ deters understatement but can amplify optimistic gains from overstatement, and vice versa.Source: §I.2.1 · p. 46

I.3 Byzantine audit

  • Because an agent’s effort depends on connected agents’ preferences, a single peer estimate is uncertain; batches reduce variance and make the audit committee more credible.Poll forms the committee from random-walk endpoints, whose audit reports can be checked against the queried agent’s report.Source: §I.3 · pp. 46–47
  • Guaranteeing only higher-order Byzantine-induced error requires a large batch; a deterministic neighbor audit ensures exact truth but is noise-fragile, collusion-prone, and separate from Poll.The deterministic alternative uses the queried agent’s nearest neighbors as a fixed committee.Source: §I.3 · pp. 46–47
  • Under public initial-price efforts, nonzero principal-bundle prices, and no collusion, batch random-walk audits reject mismatches and accepted reports have bounded mismatch with probability at least 1−ι.Endpoint agents compare reported preferences with estimates derived from observed equilibrium efforts.Source: §I.3 · pp. 46–47

Related papers

Loading 2610.08347v1…