Multi-Winner Contests for Strategic Diffusion in Social Networks

Wen Shen, Yang Feng, Cristina V. Lopes

Abstract

Strategic diffusion, or viral marketing, relies on incentivizing users to propagate information through social networks. However, traditional reward mechanisms are vulnerable to "false-name attacks," where users create multiple fake identities to siphon rewards. This paper introduces the Multi-Winner Contest (MWC) mechanism, a manipulation-proof framework that employs a quadratic credit allocation system and probabilistic contests. By penalizing identity-splitting and optimizing a "noise factor" in reward distribution, MWC incentivizes honest participation and maximizes total network effort across complex, real-world social structures.

Introduction: The Challenge of Strategic Diffusion

"Strategic diffusion" is the academic term for viral marketing—encouraging users to refer others to a product or task. While highly effective, traditional reward systems (like geometric rewards, where you get a cut of your referrals' rewards) have a major flaw: they are incredibly easy to hack.

A savvy user can launch a false-name attack, creating a chain of fake identities to refer themselves repeatedly, effectively siphoning off more rewards than they deserve. This "free rider" problem drains the budget of the campaign and discourages honest participants. Previous solutions often only worked on simple tree-like structures or excluded users with low influence.

Comparison of network structures under false-name attacks: Type 1 (sequential) vs. Type 2 (parallel).

As shown in Figure 3, attackers can manipulate the network topology by splitting a single node into multiple identities (nodes $2_1$ to $2_m$). This paper seeks a mechanism that is manipulation-resistant, fair to all skill levels, and works on the messy, interconnected graphs of real social networks.

The MWC Mechanism: Quadratic Credits and Probabilistic Contests

The authors introduce the Multi-Winner Contests (MWC) mechanism, which operates in two main stages:

  1. Virtual Credit Allocation: Instead of giving cash rewards immediately, the system assigns "virtual credits" ($b_v$) to participants. A crucial innovation here is the formula: credits are based on a participant's own effort ($t_v$) squared, plus a weighted sum of their referrals' efforts. Because the self-effort term is quadratic ($\eta \cdot t_v^2$), splitting effort across multiple fake accounts actually reduces total credits more than the extra referrals gain the attacker. This mathematical "poison pill" makes identity-splitting a losing strategy.
  2. The Contest: The mechanism then holds a contest within each rooted subgraph. A participant's probability of winning a share of the reward pool is determined by a Contest Success Function (CSF). This function uses a "noise factor" ($\sigma$) to determine how much a higher credit score actually helps you win. If $\sigma$ is low, the contest is "noisy" (like a lottery); if $\sigma$ is high, it is highly discriminating (the highest credit score almost always wins).

The authors mathematically prove that this setup is false-name-proof, individually rational, and budget-constrained.

Experimental Evaluation and Population Dynamics

The researchers evaluated MWC using four large-scale, real-world social network datasets: Twitter (323k nodes), Flickr (145k nodes), Flixster (96k nodes), and Digg (18k nodes). To ensure robustness, they simulated different types of user populations with varying ability distributions.

Probability distributions of player abilities across different simulated populations, including homogeneous (HO), high-ability (HH), and distinct (DI) mixes.

As illustrated in Figure 6, these distributions allowed the researchers to see how the mechanism performed across various social dynamics. They discovered a "sweet spot" for the noise factor (typically between 0.45 and 0.65) that maximizes total effort. If the contest is too noisy, high-ability users don't try hard; if it is too competitive, average users give up. By using a multi-winner approach (proportional rewards) rather than a single winner, the mechanism keeps low-ability players engaged without discouraging "superstars."

Key Results and Strategic Insights

  • Resistance to Cheating: Numerical experiments confirmed that as a player creates more fake identities, their total rewards drop significantly and then plateau at a very low level.
  • Boosting Total Effort: By selecting the right noise factor, stakeholders could significantly increase the total aggregated effort of participants compared to a random lottery or a winner-take-all approach.
  • Scalability: The algorithm is computationally efficient ($O(|V|^2 + |V| \cdot |E|)$), meaning it can handle networks with hundreds of thousands of nodes in a reasonable timeframe.

Limitations and Future Work

The current model assumes agents have perfect information and do not discount the future. In real-world scenarios, users might be skeptical of probabilistic rewards or risk-averse. Furthermore, the "optimal" noise factor currently requires manual tuning through experimentation. Future research could involve developing algorithms to automatically select the best $\sigma$ based on specific network and population characteristics.

Summary updated

Abstract

Strategic diffusion encourages participants to take active roles in promoting stakeholders' agendas by rewarding successful referrals. As social media continues to transform the way people communicate, strategic diffusion has become a powerful tool for stakeholders to influence people's decisions or behaviors for desired objectives. Existing reward mechanisms for strategic diffusion are usually either vulnerable to false-name attacks or not individually rational for participants that have made successful referrals. Here, we introduce a novel multi-winner contests (MWC) mechanism for strategic diffusion in social networks. The MWC mechanism satisfies several desirable properties, including false-name-proofness, individual rationality, budget constraint, monotonicity, and subgraph constraint. Numerical experiments on four real-world social network datasets demonstrate that stakeholders can significantly boost participants' aggregated efforts with proper design of competitions. Our work sheds light on how to design manipulation-resistant mechanisms with appropriate contests.
BibTeX
@inproceedings{shen2019multi,
  author = {Wen Shen and Yang Feng and Cristina V. Lopes},
  title = {{Multi-Winner Contests for Strategic Diffusion in Social Networks}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33016154},
}
Figure