Maximal Information Propagation via Lotteries

Jing Chen, Bo Li

Abstract

This paper addresses the challenge of maximizing information propagation in decentralized networks through a novel "free market with lotteries" mechanism. By allowing participants to autonomously determine the portion of a reward to pass to their peers, the authors demonstrate that a "Full Propagation" strategy—where players keep only a minimal fee—constitutes a stable Nash equilibrium. This approach inherently resists Sybil attacks and collusion, providing a robust framework for applications ranging from viral marketing to blockchain transaction broadcasting.

Introduction

How do you convince individuals to spread information? Whether it's a viral marketing campaign or broadcasting a new transaction in a blockchain like Bitcoin, there is a fundamental tension: sharing information might create a competitor for the associated reward. Existing centralized rewarding schemes, where a designer sets fixed rewards for every hop in a chain, often struggle to balance incentive compatibility, budget feasibility, Sybil-proofness, and individual rationality.

The authors identify that initial "aware" players face a version of the Prisoner's Dilemma: they could hoard information to keep their winning probability high, but if everyone does that, the information doesn't spread, and the system fails. This paper proposes a decentralized "free market with lotteries" to solve this problem.

Methodology: The Free Market with Lotteries

The proposed mechanism moves away from central authority dictation. Instead, it operates on two pillars:

  1. The Lottery: A single winner is chosen randomly from all "aware" players to receive a normalized reward of 1.
  2. The Free Market: When a player receives information, it comes with a "remaining reward" value. The player decides how much of that reward to keep (a "withholding" fee) and how much to pass to their neighbors.

The authors focus on the Full Propagation (FP) strategy, where every player withholds only the system-mandated minimum ($x_{min}$) and passes the rest to all their friends.

Theoretical Framework

The analysis begins with $d$-ary trees, which serve as the foundational model for proving the stability of propagation strategies.

Figure 1: A d-ary tree network model where a sender s initiates information propagation through subtrees T_i.

In this model, the sender $s$ initiates the process. The paper uses game-theoretic proofs to analyze this model on $d$-ary trees and then extends the logic to general non-tree networks using the concepts of "good friends" and "best friends" (based on shortest paths from the sender).

Experimental Setup

To validate the theoretical findings, the authors conducted simulations on synthetic random networks with $n=1000$ players. Connectivity was varied such that the expected degree ($d$) was 6, 10, or 14. They ran 100 experiments for each configuration to calculate the expected utility of different strategies.

Key Insights and Results

Market Self-Regulation and Sybil-proofness

A striking insight is that the mechanism designer does not need to specify rewards for each player. The market self-regulates because the "referring utility" (the cut received if a recruited friend wins) outweighs the loss in "authorizing utility" (one's own chance of winning).

Furthermore, Sybil-proofness is "built-in." In many systems, creating fake identities (Sybil attacks) is a major vulnerability. Here, because a player can already choose to withhold any amount of the reward, creating a fake "middleman" identity is mathematically equivalent to withholding a larger fee. Since withholding more than the minimum is shown to be suboptimal, Sybil attacks become pointless.

Stability and Robustness

  • Stability in Trees: For tree networks with a branching factor $d \geq 3$, Full Propagation is a Nash Equilibrium and is "connected coalition-proof," meaning groups of friends cannot benefit by deviating together.
  • Uniqueness: FP is the unique strategy surviving iterative elimination of dominated strategies, suggesting it is the logical conclusion for rational players.
  • Non-Tree Robustness: In general networks, if every player has at least 3 "good friends" (neighbors on a shortest path from the sender), Full Propagation remains a Nash Equilibrium.

Discussion and Limitations

While the results are promising, several limitations warrant future exploration. The theoretical proofs assume players have knowledge of the network structure to calculate optimal moves. While simulations suggest results hold in random graphs, real-world social networks are significantly more complex.

Additionally, the "Single Winner Risk" might deter risk-averse players. Rewarding multiple winners or paths could encourage broader participation. Finally, "local monopolies"—where a player exclusively controls access to a cluster—might still incentivize hoarding, though these cases are considered rare in well-connected networks.

Conclusion

By introducing a free market into the propagation of information, this research demonstrates that decentralized incentives can achieve maximal spread while maintaining security against common network attacks. The Full Propagation strategy emerges as a robust, self-sustaining equilibrium that aligns individual greed with the collective goal of information dissemination.

Summary updated

BibTeX
@inproceedings{chen2021maximal,
  author = {Jing Chen and Bo Li},
  title = {{Maximal Information Propagation via Lotteries}},
  booktitle = {WINE},
  year = {2021},
  doi = {10.1007/978-3-030-94676-0\_27},
}
Figure