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.
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:
- 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.
- 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.
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