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.
Introduction
Strategic diffusion, or referral marketing, leverages social networks to spread information through incentivized referrals. While effective, traditional systems like the geometric reward mechanism are highly susceptible to false-name attacks, where a single user creates multiple fake accounts to capture a larger share of rewards. This paper introduces the Multi-Winner Contests (MWC) mechanism, a novel framework designed to be manipulation-resistant while maximizing the total effort contributed by the crowd.
The MWC Mechanism
The MWC mechanism operates through a two-stage process:
- Virtual Credit Allocation: Users earn credits based on their verifiable task effort and the effort of their referrals. A key innovation is the inclusion of a quadratic term for individual effort. This ensures that splitting effort across multiple identities is mathematically less rewarding than honest participation, as the cost of effort is linear while the credit gain is quadratic.
- Ratio-Form Contest: These credits determine a user's probability of winning a share of the reward pool. This stage introduces a "noise factor" ($\sigma$) that modulates the competitiveness of the contest.
Unlike previous mechanisms limited to simple tree structures, MWC is designed to function on Directed Acyclic Graphs (DAGs), which more accurately represent the complex flow of information in real-world social media.
Experimental Evaluation
The researchers evaluated the MWC mechanism using four large-scale social network datasets: Twitter (323k nodes), Flickr (145k nodes), Flixster (95k nodes), and Digg (17k nodes). They simulated four distinct population types based on player ability: Homogeneous (HO), Heterogeneously Low (HL), Heterogeneously High (HH), and Distinct Groups (DI).
Optimizing Total Effort
A central insight of the study is the impact of the noise factor ($\sigma$). If the contest is too competitive ($\sigma \approx 1$), average users may be discouraged. If it is too random ($\sigma \approx 0$), high-ability users lack incentive. As shown in Figure 4, there is a "sweet spot" (typically between 0.4 and 0.7) where total contributions are maximized across all population types.
Resistance to False-Name Attacks
The mechanism's primary goal is to prevent cheating. Experimental results on the Digg dataset (Figure 5) confirm that as a player increases the number of false identities, their rewards per player decrease significantly and eventually plateau at a low level. This empirical evidence supports the theoretical claim of false-name-proofness.
Conclusion
The Multi-Winner Contest mechanism represents a significant advancement in designing secure and effective referral systems for social networks. By utilizing a quadratic penalty for credit allocation and a tunable contest success function, it successfully aligns individual incentives with the stakeholder's goal of maximizing total diffusion effort. Future research will focus on automated methods for selecting the optimal noise factor in dynamic network environments.
Summary updated