Ito et al. (2018) “Information Diffusion Enhanced by Multi-Task Peer Prediction”

Abstract: Our study aims to strengthen truthfulness of the two-path mechanism: an information diffusion algorithm to find an influential node in non-cooperative directed acrylic graphs (DAGs). This subject is important because the two-path mechanism ensures only weak truthfulness (i.e., nodes are indifferent between reporting true or false out-edges), which restricts node selection accuracy. To enhance the mechanism, we employed an additional reward layer based on a multi-task peer prediction, where an informative equilibrium provides strictly higher rewards than any other equilibrium in virtually all cases (strong truthfulness). Rewards, which are derived from a comparison of each report, encourage a node to report true out-edges without affecting its own probability of being selected by the original two-path mechanism. We have also experimentally confirmed that our proposed strongly truthful two-path mechanism can sufficiently elicit true out-edges from each node.