Approximating Contribution in Misinformation Mitigation

Online social networks (OSNs) have rapidly emerged as prominent platforms for sharing diverse content, where the word-of-mouth effect drives extensive information propagation. However, such powerful dissemination capabilities also accelerate the spread of misinformation, resulting in significant negative impacts. To combat this, the OSN provider often incentivizes some influencers to initiate the truth campaign, enabling users to receive truth before misinformation and thus suppressing its further spread. This mitigation strategy has proven effective in practice and has consequently attracted substantial research interest, particularly in optimizing influencer selection. In this paper, complementing the existing performance-centric line of work, we address the fair allocation of incentives for engaged influencers, an underexplored dimension that is critical for ensuring the long-term sustainability of misinformation mitigation. We first define a novel contribution metric and reveal its rationality by connecting it to the Shapley value, a classic fairness concept in cooperative game theory. We then formulate the mitigation contribution allocation (MCA) problem, which seeks to compute, for each influencer, the expected mitigation contribution conditioned on the observed mitigation result (which corresponds to exponentially many possible diffusion cascades). In view of the prohibitive cost of exactly solving MCA via exhaustive enumeration, we propose VG-App, an efficient sampling-based approximation algorithm with provable accuracy guarantees. VG-App is built upon the advanced VG-Sampling method, which reduces the global sampling task to independent node-wise decisions, drastically pruning the sample space to ensure that generated samples are consistent with the observed mitigation result, while maintaining unbiasedness. Extensive empirical studies on large real-world datasets demonstrate that VG-App achieves accurate approximations while preserving high efficiency.