Sybil-Resilient Social Choice
share
We consider an electorate composed of both genuine and fake voters, aka sybils, and investigate the resilience of its decision making against two types of sybil attacks: Sybils enforcing decisions on the genuine voters, and sybils blocking decisions by the genuine voters. We follow Reality-Aware Social Choice and use the status quo as the anchor of sybil resilience, which we characterize by sybil safety -- the inability of sybils to change the status quo against the will of the genuine voters, and sybil liveness -- the ability of the genuine voters to change the status quo against the will of the sybils. We show that supermajorities are sybil-resilient for voting on a single alternative to the status quo, and describe several rules which are sybil-resilient for voting on multiple alternatives to the status quo. Specifically, we show that these rules are safe against arbitrarily-high sybil penetration, but can uphold liveness only if sybil penetration is under one third. We present a simple and efficient sybil-resilient Reality-aware Condorcet-consistent voting process and analyze its liveness as it depends on the degree of sybil penetration.
READ FULL TEXT