Sybil-Resilient Reality-Aware Social Choice

Gal Shahaf, Ehud Shapiro, Nimrod TalmonIJCAI 2019 · DOI

TL;DR

This paper tackles the challenge of making group decisions in online communities fair and resilient, even when a significant portion of participants might be fake accounts (sybils). They introduce "sybil-resilience" by anchoring decisions to the status quo, ensuring sybils can't easily manipulate outcomes while still allowing genuine users to enact change. This work proposes novel voting rules for various scenarios, from single-issue votes to parameter updates, that maintain this balance.

What Problem Does This Paper Address?

Online communities, from social media platforms to decentralized organizations, rely on collective decision-making. However, these systems are vulnerable to "Sybil attacks," where a single malicious entity creates numerous fake identities (sybils) to disproportionately influence votes and decisions. While methods exist to detect and limit sybils, complete eradication is often impossible. This leaves communities susceptible to manipulation, where the will of genuine users can be overridden by a coordinated sybil attack. The paper addresses this by developing social choice mechanisms that are robust to a bounded but non-negligible fraction of sybils, ensuring that decisions reflect the genuine users' preferences as much as possible.

Methods

The core of the paper's approach is "Reality-Aware Social Choice," which treats the current state of affairs (the "status quo" or "reality") as a special, ever-present alternative. This provides a stable anchor for decision-making. They define two key properties for sybil resilience:

  • Sybil Safety: Sybils cannot change the status quo against the will of genuine agents.
  • Sybil Liveness: Genuine agents can change the status quo against the will of sybils.

The authors then adapt these concepts to three distinct social choice settings:

  1. Single Proposal (Yes/No Decisions): They propose a "reality-aware $\delta$-supermajority rule." Instead of a simple majority, a proposal needs a supermajority (e.g., more than 1/2 + $\delta$ of votes) to pass. They show that a $\delta$ of 1/2 ensures safety, and with $\delta=1/2$, the rule is resilient up to 1/3 sybil penetration. This means sybils can't force a change, but can block one if their penetration exceeds 1/3.
  2. Ordinal Elections (Ranking Alternatives): They extend the Condorcet principle by introducing "$\delta$-supermajority Condorcet winners." They propose "Reality-Aware $\delta$-Supermajority Condorcet criteria" (both conservative and permissive variants) and an efficient "Amendment Agenda" algorithm. These rules ensure that a $\delta$-supermajority of genuine voters is needed to overcome the status quo or to elect an alternative over another, providing resilience up to 1/3 sybil penetration.
  3. Parameter Update: For continuous parameters (like interest rates), they use a "Reality-Aware Median" and propose a "Suppress Outer-$\sigma$ Parameter Update Rule." This rule, inspired by single-peaked preferences, removes a fraction of extreme votes (potentially sybil votes) before calculating the median, ensuring safety and liveness for sybil penetration below 1/3.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • The Status Quo as a Shield: Elevating the status quo to a special alternative is a powerful way to build resilience. It acts as a default that sybils must actively overcome, rather than a passive option that can be easily discarded.
  • The 1/3 Sybil Penetration Threshold: For several of their proposed rules, a sybil penetration rate of 1/3 emerges as a critical inflection point. Below this, both safety and liveness are generally maintained. Above it, safety is preserved, but liveness can be compromised, meaning sybils can effectively veto changes.
  • Supermajority as a Sybil-Resilience Tool: Moving beyond simple majority voting is crucial. Supermajorities, especially when tailored with a $\delta$ parameter, provide a tunable mechanism to resist sybil influence.
  • Simplicity is Key for Trust: The authors emphasize that voting rules must be easy to understand for voters to trust them, even if it means sacrificing some theoretical optimality. This practical consideration is vital for real-world adoption.
  • Parameter Updates Need Special Care: Decisions about continuous parameters require different approaches than discrete choices, highlighting the need for tailored solutions that account for preference distributions and the "direction" of change.

Key Results

The paper presents several theoretical results demonstrating sybil resilience for various social choice settings:

  • Single Proposal: The reality-aware $\delta$-supermajority rule with $\delta=1/2$ is sybil-safe and resilient to up to $\sigma=1/3$ sybil penetration.
  • Ordinal Elections: Reality-Aware $\delta$-Supermajority Condorcet criteria and the proposed Amendment Agenda algorithm are sybil-safe with respect to their base Condorcet rules and resilient to up to $\sigma=1/3$ sybil penetration.
  • Parameter Update: The Suppress Outer-$\sigma$ Parameter Update Rule is resilient up to $\sigma < 1/3$ sybil penetration.

Limitations and Future Work

The authors acknowledge several avenues for future research:

  • Further Settings: Extending sybil resilience to other social choice scenarios like multidimensional parameter updates, multiwinner elections, and different voting systems (e.g., cumulative or quadratic voting).
  • Different Base Rules: Exploring the use of alternative base rules for social choice settings, such as Borda count for ordinal elections.
  • Partial Participation: The current model assumes all agents participate. Future work could explore scenarios where genuine agents might be less motivated to vote, requiring mechanisms to handle partial participation (e.g., through vote delegation).
  • Estimating Sybil Penetration: While the paper assumes a known or estimable sybil penetration rate ($\sigma$), practical estimation of this rate remains an important challenge.

Summary updated

BibTeX
@inproceedings{shahaf2019sybil,
  author = {Gal Shahaf and Ehud Shapiro and Nimrod Talmon},
  title = {{Sybil-Resilient Reality-Aware Social Choice}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/81},
}
Figure