Rational Viral Marketing: Bridging Cryptography and Game Theory

TL;DR

Calculating social influence for viral marketing is a "data silo" problem: Social platforms own the graph, but stores own the purchase logs. While previous work used Secure Multi-Party Computation (SMC) for "semi-honest" players, this paper tackles rational selfishness. By introducing a protocol with "fake rounds" and statistical verification, the authors force self-interested players to participate truthfully to maximize their own utility.

The Gap Between Theory and Reality

In the academic world of "Influence Maximization," we often assume $p_{u,v}$ (the probability that user $u$ influences user $v$) is a known constant. In reality:

1. Data is Distributed: Facebook has the links; Amazon has the purchase history.
2. Trust is Non-Existent: Neither party wants to hand over their raw data due to privacy laws and commercial secrets.
3. Players are Rational: Why would a service provider contribute data to a host if the host gets all the results? Or why wouldn't the host lie to maintain a monopoly on the insights?

Existing SMC protocols assume players follow the rules (semi-honest). This paper assumes they are selfish—they will cheat if it's more profitable.

Methodology: The Incentive Mechanism

The core of the paper is the Modified Protocol (MP). It builds upon two foundational arithmetic protocols:

• ${\Pi }_S$ (Additive Sharing): Distributes a sum into random pieces so no single party knows the total.
• ${\Pi }_Q$ (Secure Quotient): Allows a host to compute $b_{u,v}/a_u$ (the influence probability) without seeing the raw values of successful influences or total actions.

The "Fake Round" Game

To keep the host $H$ honest, the authors introduce a coordinator $T$ who manages multiple rounds of computation.

1. Randomized Timing: $T$ tosses a $(\varphi ,1-\varphi )$ coin. Most rounds are "fake" (meaningless results). The "true" round happens at a secret time.
2. Masking Multipliers: In the true round, multipliers are consistent ($r^1=r^2$); in fake rounds, they are independent, yielding noise.
3. The Utility Trade-off: If $H$ is caught cheating during a verification check, the protocol aborts, and $H$ loses everything. Because $H$ doesn't know which round is "true," the risk of losing the real data outweighs the benefit of cheating.

Mathematical Intuition for Truthfulness

The paper's breakthrough is defining the Utility Function conditions:

• [CH1]: The host prefers "everyone learning" over "no one learning."
• [CH2]: The host would rather a provider didn't learn, but [CH1] acts as a baseline to prevent total failure.

The authors prove that if the probability of a true round ($\varphi$) is set correctly (see formula 14), the host's best strategy is to be honest. This is the Nash Equilibrium of the computational game.

Experimental Insight: Statistical Verification

In Step MP9, the coordinator $T$ asks for a random subset of encrypted results to be decrypted and verified.

• If the host reports $d$ wrong values, the probability of getting caught $\psi (d)$ is: $\psi (d)=\frac{\left(\genfrac{}{}{0ex}{}{w-d}{t}\right)}{\left(\genfrac{}{}{0ex}{}{w}{t}\right)}$
• This ensures that even "small" cheating is statistically likely to lead to a total protocol abort.

Critical Analysis & Conclusion

This paper effectively moves privacy-preserving data mining from a purely cryptographic problem to an economic one.

Takeaways:

• Incentives Matter: Purely technical privacy isn't enough; players need a reason to participate.
• Coordinators as Trust Anchors: While the coordinator sees some data, a secret random labeling of users keeps the identities private.

Limitations:

• Coalitions: Currently, if two service providers collude, they could potentially break the protocol.
• Computational Overhead: Running multiple rounds (mostly fake) increases the communication cost significantly.

Future work remains in making these "Rational" protocols immune to collusion and more computationally efficient for massive social networks with millions of edges.