PaperlayerView exact revision on arXiv

Source-linked AI summary

Strategic Information Transmission over Gossip Networks

Emirhan Tekez, Melih Bastopcu, Sinan Gezici

arXiv:2609.10576v1cs.GTcs.ITcs.NIcs.SIcs.SYeess.SYmath.IT

TL;DR

The paper studies strategic state-dependent updates in a gossip network, where receivers decide whether to follow the sender. Using an SHS recursion in a Stackelberg game, it proves budget binding and characterizes gossip behavior and equilibrium. In the strategic regime, receivers choose the gossip cap; an optimistic equilibrium exists and is unique when a strategic-half policy is feasible at that cap.

  • Problem

    Gossip models largely treat source updates as exogenous, leaving strategic sender objectives outside models of receiver packet exchange and gossip.

    Source: §V · p. 8

  • Method

    The paper models sender and receiver decisions as a Stackelberg game and uses an SHS framework to derive a backward recursion for steady-state mode-tagged accuracies.

    Source: §VIII · p. 13

  • Results

    In the strategic regime s > c, receiver utility strictly increases with gossip while sender utility strictly decreases; an optimistic equilibrium exists and is unique when a strategic-half policy is feasible at the gossip cap.

    Source: §VIII · p. 13

  • Takeaways & Limitations

    Gossip has no direction of its own and works against the asymmetry in the sender’s policy rather than reinforcing it.

    Source: §VIII · p. 13

Abstract

from arXiv · show

We consider a fully connected gossip network of $n$ nodes that track a binary continuous-time Markov source through a strategic sender transmitting updates under a communication budget at a rate that depends on the source state. The receivers exchange packets through gossip and decide whether to follow the sender. We model this interaction as a Stackelberg game and analyze it through a stochastic hybrid systems (SHS) framework. We prove that the sender's budget constraint binds at every interior optimum, reducing its problem to a one-dimensional search on the budget line. When the sender pushes its preferred state at the higher rate, the receivers gossip at the highest available rate. Gossip has no direction of its own and works against the asymmetry in the sender's policy rather than reinforcing it. We prove that an optimistic Stackelberg equilibrium exists, and that it is unique and explicitly characterized whenever a policy on the strategic half of that line is feasible at the gossip cap. Monte Carlo simulations agree with the analytical recursion.

I. INTRODUCTION

The paper combines strategic, state-dependent updates with receiver gossip in a fully connected network, where receivers choose whether to follow the sender. It contributes results on budget use, gossip behavior, and equilibrium, extending non-strategic gossip and strategic-transmission models.

I. INTRODUCTION

  • AoI measures elapsed time since the latest received update, but it does not establish whether that information is currently correct.The paper motivates accuracy-aware monitoring metrics because recent information can be wrong after a source transition, while older information can remain correct after a reversion.Source: §I · p. 1

II. SYSTEM MODEL AND PROBLEM FORMULATION

  • A sender observes a binary CTMC and pushes version-stamped updates to each of n receivers at state-dependent rates s and c, subject to s + c ≤ R.Receivers exchange packets through gossip and choose whether to follow the sender and which common gossip rate to use.Source: §I · p. 1

A. Related Work

  • Prior gossip models largely treat source updates as exogenous, while prior strategic timing models do not include receiver packet exchange and network-wide gossip choice.The paper also differs from the non-strategic gossip model in [15] by introducing state-dependent strategic sender behavior.Source: A. Related Work · pp. 1–2

B. Contributions

  • At interior optima the sender’s budget binds; when s > c, receiver utility rises and sender utility falls with gossip, so receivers choose the gossip cap.Gossip counteracts the sender’s policy asymmetry rather than reinforcing it, and the paper establishes equilibrium existence and conditional uniqueness.Source: B. Contributions · p. 2

B. Information Accuracy

  • A receiver’s accuracy is whether its stored packet content matches the current source state, so a stale packet can still be accurate after the source returns to its state.A fresher packet can instead be less accurate if the source changed after that packet was generated.Source: B. Information Accuracy · p. 3

C. Utility Structure

The paper defines sender and receiver utilities from mode-tagged average node accuracies and formulates their interaction as a Stackelberg game. It computes the needed accuracies using an SHS framework.

C. Utility Structure

  • Receivers estimate the source using the content of their freshest stored packet, and the sender’s utility rewards declarations of state 1 regardless of the true state.Receiver utility weights correct declarations by q in state 0 and 1 − q in state 1.Source: C. Utility Structure · p. 3

D. Stackelberg Game Formulation

  • The sender commits to state-dependent push rates; receivers then follow only if their best achievable utility meets the participation constraint, otherwise they default to estimating state 0.Under Assumption 1, receivers prefer the state-0 outside option without sender information, and the sender must provide sufficient information quality for participation.Source: D. Stackelberg Game Formulation · p. 3

III. THE SHS MODEL AND THE ACCURACY RECURSION

  • An SHS balance identity applied to mode-tagged accuracies yields a backward recursion for steady-state accuracies used in both utilities.The freshest-node accuracy vector tracks the accuracy of the freshest node within each k-node subset, tagged by source state.Source: §III · p. 4

A. The SHS Model

The SHS construction tracks source mode, receiver accuracy, and version age, then uses set-level reset maps to derive a backward recursion for steady-state accuracy. The recursion uniquely determines the needed values and can be evaluated in linear operations in n.

A. The SHS Model

  • The hybrid state combines source mode, an accuracy vector, and a version-age vector; source flips, state-dependent pushes, and directed gossip are its transitions.Sender policy affects the source-push rates, whereas gossip remains mode independent.Source: A. The SHS Model · p. 4

B. Reset Maps

  • For a receiver subset, its version age and freshness-based accuracy are those of its freshest node, with reset maps for source flips, pushes, and inbound gossip.A source flip increments version age and flips accuracy; a push into the subset resets its version age and makes the packet accurate, while inbound gossip can bring in a fresher packet.Source: B. Reset Maps · p. 4

C. Accuracy Recursion

  • Mode-tagged accuracies fk are uniquely determined by backward recursion; at k = 1, fk gives the per-node average accuracy, whereas for k > 1 it tracks the freshest node of a k-set rather than a fixed node.Uniqueness holds when q01, q10 > 0 and c+s > 0.Source: C. Accuracy Recursion · p. 5
  • O(n) operations suffice to evaluate both utilities at a fixed policy and gossip rate, using n solves of a 2 × 2 system.The recursion proceeds from level n down to k = 1, even though the full accuracy vector has 2^n configurations.Source: C. Accuracy Recursion · p. 6

D. Sign-Preservation Property

The sign-preservation property shows that inversion of the specified positive 2 × 2 matrices preserves a particular component-wise sign pattern. The paper applies this property to the recursion matrices in its later inductions.

D. Sign-Preservation Property

  • For a 2 × 2 matrix with positive entries and determinant, inversion preserves opposite component signs in its input vector.The same property applies to each W_k recursion matrix because its entries and determinant are positive.Source: D. Sign-Preservation Property · p. 6

IV. SENDER OPTIMALITY AND BUDGET BINDING

The sender’s utility is monotone in its push rates, and the section establishes that its budget binds at any interior optimum. The sensitivity analysis explains how each state’s pushes affect accuracy across source states.

IV. SENDER OPTIMALITY AND BUDGET BINDING

  • The sender’s budget constraint binds at every interior optimum.Source: §IV · p. 6

A. Sensitivity Analysis and Monotonicity of the Sender Utility

  • The sensitivity analysis establishes the monotonicity properties of sender utility with respect to the two push rates.Source: A. Sensitivity Analysis and… · p. 6
  • Increasing the state-0 push rate raises mode-0 accuracy but lowers mode-1 accuracy; increasing the state-1 rate has the mirror effect.Packets can continue circulating after the source changes state, reducing accuracy in the other mode.Source: A. Sensitivity Analysis and… · p. 6

B. Budget Binding

At any interior optimum with both push rates positive, the sender exhausts its budget. The proof uses the distinct effects of the two rates on accuracy to find a feasible improvement whenever budget remains.

B. Budget Binding

  • The positive determinant of the accuracy-sensitivity matrix means the two push rates change the accuracy vector in different directions.This allows a direction that improves sender and receiver utility together when budget is unspent.Source: B. Budget Binding · pp. 6–7
  • Every interior optimal policy with s⋆ > 0 and c⋆ > 0 satisfies s⋆ + c⋆ = R.Source: B. Budget Binding · p. 7
  • The interior condition excludes the two endpoint policies, which Section VI-A shows are not participation-constraint feasible.Source: B. Budget Binding · p. 7

C. Budget-Line Parameterization and Sender Optimality

Once the budget binds, the sender’s policy can be parameterized by the state-0 push rate along the budget line. The optimal policy uses the smallest feasible state-0 rate.

C. Budget-Line Parameterization and Sender Optimality

V. RECEIVER’S BEST RESPONSE AND GOSSIP MONOTONICITY

The receiver team chooses a gossip rate to maximize its utility, but gossip can initially spread fresh yet inaccurate packets before synchronizing nodes on the freshest update. The analysis transforms the recursion to study this behavior in the strategic regime.

V. RECEIVER’S BEST RESPONSE AND GOSSIP MONOTONICITY

  • Gossip can first hurt receivers by spreading fresh but inaccurate packets, before helping synchronize nodes on the freshest available update.Source: §V · p. 8

A. The Transformed Recursion

  • A change of coordinates separates the receiver-weighted defect from the mode gap that governs sender utility.Each utility depends on one component of the transformed defect.Source: A. The Transformed Recursion · p. 8
  • The transformed defect recursion yields component-wise nonincreasing behavior in gossip rate when s > c, under Assumption 1.The sign condition makes the recursion matrices nonsingular M-matrices; once their inverse sign property holds, the subsequent inductions need no further parameter restrictions.Source: A. The Transformed Recursion · p. 8

B. Gossip Monotonicity in the Strategic Regime

In the strategic regime s > c, backward induction establishes that receivers benefit from faster gossip while the sender does not. For c > s, the endpoint behavior is established, but the broader best-response shape is conjectural and supported by a parameter sweep.

B. Gossip Monotonicity in the Strategic Regime

  • Backward induction shows that, when s > c, accuracy increments between adjacent subset sizes and their mode gap are both positive.The proof signs these increments first, then uses them to establish the gossip-rate sensitivities.Source: B. Gossip Monotonicity in the… · pp. 8–9
  • For s > c, receiver utility strictly increases with gossip rate, so receivers uniquely choose the gossip cap λ⋆ = Λ at every network size.The sender's utility strictly decreases with λ in this regime.Source: B. Gossip Monotonicity in the… · pp. 8–9
  • Outside s > c, receiver utility benefits from gossip at both rate extremes, but an interior best response would require its derivative to turn from positive to negative.The reported sweep covered 134,217,728 parameter combinations; every observed sign change was from negative to positive, at most once.Source: B. Gossip Monotonicity in the… · p. 9
  • Conjecture 1 predicts that for positive push rates receiver utility falls until λd and rises afterward, making its maximum over [0, Λ] occur at an endpoint.The conjecture is used only when c > s; it is not needed for the strategic regime.Source: B. Gossip Monotonicity in the… · p. 9

C. Sender Utility in the Remaining Regimes

The sender-side results extend across the remaining push-rate regimes by relabeling the source states, while the equal-rate case is symmetric. Sender utility is independent of receiver weight, and receiver utility increases with gossip when s ≥ c.

C. Sender Utility in the Remaining Regimes

  • For c > s, state relabeling maps the system to one with the higher push rate in state 1 and yields sender utility below π1.The relabeled system swaps q01 with q10 and s with c, while leaving gossip unchanged.Source: C. Sender Utility in the Remaining… · pp. 9–10
  • Across push-rate regimes, sender utility depends on push rates, source rates, and λ through f1 alone, and does not depend on receiver weight q..Source: C. Sender Utility in the Remaining… · p. 9
  • When c = s, sender utility equals π1 and is independent of gossip rate λ.This follows by subtracting the two rows of the defect recursion.Source: C. Sender Utility in the Remaining… · p. 10
  • When s > c, faster gossip spreads corrective state-0 packets after a source switch and reduces persistence of stale sender-preferred state-1 declarations.Gossip propagates the freshest packet regardless of its content, so it does not favor either source state.Source: C. Sender Utility in the Remaining… · p. 10
  • For every s ≥ c > 0, receiver utility strictly increases with gossip rate λ.The equal-rate case completes the result that is strict for s > c.Source: C. Sender Utility in the Remaining… · p. 10

VI. STACKELBERG EQUILIBRIUM AND THE EFFECT OF GOSSIP

Neither endpoint of the budget line satisfies the receivers' participation constraint, so the sender-optimal feasible policy lies in its interior and binds that constraint. An optimistic Stackelberg equilibrium exists; it is unique and explicitly characterized when a strategic-half policy is feasible at the gossip cap.

A. Boundary Characterization of the PC Slack

  • At c = 0 and c = R, the receiver team defaults, leaving the sender with zero utility; at the sender-optimal feasible interior point, the participation constraint binds.At c = 0, a following node is accurate only while Q = 1; at c = R, following yields the default utility, below the participation threshold.Source: A. Boundary Characterization of the PC… · p. 10

B. Equilibrium Characterization

  • An optimistic Stackelberg equilibrium exists, including when the participation-feasible set is empty, in which case every policy is an equilibrium.When that set is nonempty, continuity and compactness ensure the optimistic sender payoff attains a maximum.Source: B. Equilibrium Characterization · pp. 10–11
  • Under Conjecture 1, every followed policy with positive push rates has a receiver best response at an endpoint of [0, Λ].The equilibrium characterization in the strategic regime does not require this conjecture.Source: B. Equilibrium Characterization · pp. 10–11
  • If the feasible set at λ = Λ meets [0, R/2], the equilibrium is unique: s⋆ + c⋆ = R, c⋆ = cmin(Λ), and λ⋆ = Λ.The condition asks only that some policy on the strategic half of the budget line be feasible at the gossip cap.Source: B. Equilibrium Characterization · pp. 10–11

C. Who Benefits from Gossip?

Gossip changes both the sender’s equilibrium policy and the fixed-policy receiver and sender outcomes. In the numerical regimes examined, sender reoptimization restores receiver utility to the participation threshold, while whether this raises sender payoff for every admissible parameter remains open.

C. Who Benefits from Gossip?

  • At fixed strategic policies, gossip can hurt the sender even as it raises receiver utility; at equilibrium, sender reoptimization restores receiver utility to qπ0 + η.The net equilibrium payoff effect depends on which of the two effects dominates.Source: C. Who Benefits from Gossip? · p. 11
  • On the strategic half of the budget line, PC-feasible sets are nested as realized gossip rises, so the smallest feasible c is nonincreasing.For fixed-policy receiver gains, however, equilibrium receiver utility remains pinned at qπ0 + η because the sender selects the smallest PC-feasible policy.Source: C. Who Benefits from Gossip? · p. 11

VII. NUMERICAL RESULTS

  • For fixed policies, receiver utility rises with gossip at (17, 3), while at (5, 15) it can dip before recovering; for n = 50, (17, 3) crosses the participation threshold near λ = 10.The initial dip at (5, 15) reflects fresher packets that have become inaccurate after source transitions, before corrective packets propagate faster.Source: §VII · pp. 11–12, Figure 2 · p. 12
  • At fixed policies, gossip moves sender utility toward π1: it decreases at (17, 3), stays at π1 at (10, 10), and increases at (5, 15).At (17, 3), state-0 accuracy rises steeply while state-1 accuracy initially dips; the larger state-0 accuracy gain accounts for declining sender utility.Source: §VII · p. 12, Figure 3 · p. 12
  • As the budget grows with Λ = 20, the equilibrium keeps c nearly constant and increases s almost linearly, while receiver utility stays at the participation threshold.The sender collects the gain at a diminishing rate.Source: §VII · p. 12
  • Above a critical gossip rate near 5.4, the equilibrium policy tracks the decreasing feasibility boundary: c falls, s rises, and sender utility increases at a decreasing slope.This contrasts with the declining sender utility of frozen strategic policies as gossip rises.Source: §VII · p. 12
  • The numerical recursion never found a decrease in equilibrium sender utility between consecutive gossip rates across 362,191 PC-feasible parameter draws on the strategic half.The authors leave open whether the reoptimization gain dominates the fixed-policy loss for every admissible parameter.Source: §VII · p. 12

VIII. CONCLUSION

The paper analyzes strategic, state-dependent updating in a fully connected gossip network through a Stackelberg game and SHS framework. It characterizes sender budget use, gossip incentives, and conditions for a unique optimistic equilibrium.

VIII. CONCLUSION

  • The sender’s budget binds at interior optima, reducing its fixed-gossip-rate problem to one-dimensional optimization on the budget line.The sender utility is strictly decreasing in the state-0 push rate.Source: §VIII · p. 13
  • When s > c, receiver utility rises and sender utility falls with gossip rate, so receivers choose the highest available rate.Gossip has no direction of its own and works against, rather than reinforces, asymmetry in the sender’s policy.Source: §VIII · p. 13
  • An optimistic Stackelberg equilibrium exists and is unique at the smallest PC-feasible budget-line policy when that policy lies on the strategic half.Source: §VIII · p. 13
  • Future work includes costly gossip and network topologies beyond the fully connected case.Source: §VIII · p. 13
Loading 2609.10576v1…