Ito, Kensuke, Shohei Ohsawa, and Hideyuki Tanaka. (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.

【Best Paper Award】at the 20th International Conference on Information Integration and Web-based Applications & Services (iiWAS2018), November 19th to 21st, 2018, Yogyakarta: Grand Mercure Yogyakarta Adisucipto, pp.96-104.