2013/02/07 by Serge Gaspers, Gaspers, Serge, Victor Naroditskiy +5
Computer Science · Decision Sciences · Economics, Econometrics and Finance · Physics and Astronomy · #Artificial Intelligence (cs.AI) #Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Game Theory and Applications #Game Theory and Voting Systems #Opinion Dynamics and Social Influence #Social and Information Networks (cs.SI) #cs.AI #cs.DS #cs.GT #cs.SI
paper · pdf · doi:10.48550/arxiv.1302.1669
arxiv created 2013/02/07 · openalex publication_date 2013/02/07 · arxiv updated 2013/02/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 simplicity, 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 complexity of computing which candidate necessarily or possibly can win in such a social poll. For social networks with bounded treewidth and a bounded number of candidates, we provide polynomial algorithms for both problems. In other cases, we prove that computing which candidates necessarily or possibly win are computationally intractable.