Ranked Voting on Social Networks / 2040
Ariel D. Procaccia, Nisarg Shah, Eric Sodomka
PDF

Classic social choice theory assumes that votes are independent (but possibly conditioned on an underlying objective ground truth). This assumption is unrealistic in settings where the voters are connected via an underlying social network structure, as social interactions lead to correlated votes. We establish a general framework — based on random utility theory — for ranked voting on a social network with arbitrarily many alternatives (in contrast to previous work, which is restricted to two alternatives). We identify a family of voting rules which, without knowledge of the social network structure, are guaranteed to recover the ground truth with high probability in large networks, with respect to a wide range of models of correlation among input votes.