Maximizing Truth Learning in a Social Network is NP-hard

This paper is a continuation of my work at REU 2024.

We look at the problem of truth learning with unreliable information in a social network. We analyze the complexity of deciding how well a given network can learn. We reach the conclusion that this problem is in fact NP-hard. For more information, see the REU website.

This paper was written by me and Amanda Wang with equal contribution, and by Jie Gao. It was accepted to the 24th International Conference on Autonomous Agents and Multi-Agent Systems in Detroit, United States.

An extended version was invited to the AAMAS journal, and is currently under review.

The paper can be accessed in the Proceedings here, as well as on arXiv.

Abstract

Sequential learning studies prediction in social settings, where agents predicting in sequence may leverage not only their own private observations, but also past predictions broadcasted by earlier agents. This paper focuses on sequential learning in social networks, where agents only see predictions broadcasted by those in their immediate neighborhood. As such, the proportion of agents to successfully predict the ground truth exhibits a careful dependence on both the network topology and the order in which the agents make and announce their predictions. A natural objective in this setting is thus to find an optimal ordering of agents, given a particular network, which maximizes the fraction of agents who make correct predictions. We show that absent specific assumptions on network structure, this basic desiderata is unattainable for both networks of fully rational agents and those with bounded rationality. Indeed, we can construct a large class of networks for which it is computationally infeasible to determine an optimal ordering. We conclude by leveraging the same construction to prove a stronger hardness of approximation result.