Sybil-Resilient Reality-Aware Social Choice

Sybil-Resilient Reality-Aware Social Choice

Gal Shahaf, Ehud Shapiro, Nimrod Talmon

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
Main track. Pages 572-579. https://doi.org/10.24963/ijcai.2019/81

Sybil attacks, in which fake or duplicate identities (a.k.a., Sybils) infiltrate an online community, pose a serious threat to such communities, as they might tilt community-wide decisions in their favor. While the extensive research on sybil identification may help keep the fraction of sybils in such communities low, it cannot however ensure their complete eradication. Thus, our goal here is to enhance social choice theory with effective group decision mechanisms for communities with bounded sybil penetration. Inspired by Reality-Aware Social Choice, we use the status quo as the anchor of Sybil Resilience, characterized by Sybil Safety -- the inability of sybils to change the status quo against the will of the genuine agents, and Sybil Liveness -- the ability of the genuine agents to change the status quo against the will of the sybils. We consider the social choice settings of deciding on a single proposal, on multiple proposals, and on updating a parameter. For each, we present social choice rules that are sybil-safe and, under certain conditions, satisfy sybil-liveness.
Keywords:
Agent-based and Multi-agent Systems: Computational Social Choice
Agent-based and Multi-agent Systems: Voting