Possible and Necessary Winner Problem in Social Polls

Social networks are increasingly being used to conduct polls. We introduce a simple model of such social polling. We suppose agents vote sequentially, but the order in which agents choose to vote is not necessarily fixed. We also suppose that an agent’s vote is influenced by the votes of their friends who have already voted. Despite its sim-plicity, this model provides useful insights into a number of areas including social polling, sequential voting, and manipulation. We prove that the number of candidates and the network structure affect the computational com-plexity of computing which candidate necessarily or pos-sibly can win in such a social poll. For social networks with bounded treewidth and a bounded number of candi-dates, we provide polynomial algorithms for both prob-lems. In other cases, we prove that computing which can-didates necessarily or possibly win are computationally intractable.