Democratic Forking: Choosing Sides with Social Choice

Ben Abramowitz, Edith Elkind, Davide Grossi, Ehud Shapiro, Nimrod Talmon

Abstract

In voluntary communities such as open-source software projects and blockchain networks, disagreements often lead to "forking"—a process where a minority group splits from the main collective to pursue a different technical or social path. While common, these splits are typically governed by informal, off-chain social processes. This paper introduces a formal computational social choice framework to model forking. We present a polynomial-time algorithm to identify stable community splits and establish theoretical limits on the design of strategyproof voting rules in these environments.

Introduction

In traditional democratic systems, voting outcomes are binding; once a winner is chosen, the entire electorate is expected to adhere to the decision. However, in decentralized or voluntary organizations, agents possess a unique recourse: the exit. If a subset of the community is dissatisfied with a protocol upgrade or a project's direction, they can "fork" the codebase or the ledger, creating two or more independent versions of the community.

Despite the frequency of forks in the digital age, there is a lack of formal mechanisms to elicit preferences and determine optimal splits. This research addresses this gap by asking how we can design voting mechanisms where agents express preferences not just over alternatives (e.g., Protocol A vs. Protocol B), but also over the size of the resulting community. The objective is to find a "stable" assignment—a split where no individual or group has an incentive to defect from their assigned fork.

The Model: Preferences and Monotonicity

The authors model agent preferences as rankings over tuples of (Alternative, Coalition Size). A central assumption in this framework is monotonicity: for any given alternative, an agent is assumed to prefer being in a larger community over a smaller one. This reflects the network effects inherent in software development and cryptocurrencies, where the value of a platform often scales with its user base.

Algorithmic Approaches to Stability

For the case of two alternatives, the paper demonstrates that a stable assignment always exists and can be found efficiently.

The Greedy Algorithm

The authors propose a greedy, polynomial-time algorithm (Algorithm 1) that operates in $O(n^2)$ time. The process begins by assigning all agents to Alternative A. It then iteratively identifies subsets of agents who would prefer to defect to Alternative B, given the current sizes of both groups. These agents are moved to Alternative B, and the process repeats until no further beneficial defections are possible.

Iterative Elicitation

Recognizing that ranking every possible combination of alternatives and sizes is cognitively demanding for users, the authors also introduce Algorithm 2. This mechanism iteratively queries agents for the minimum information necessary to converge on a stable split, reducing the communication overhead required for practical implementation.

Theoretical Analysis and Strategyproofness

A significant portion of the research is dedicated to the mathematical limits of these mechanisms, particularly regarding strategyproofness (the property that agents cannot benefit by misrepresenting their true preferences).

  • The Cost of Multiplicity: Theorem 3 proves an impossibility result: no assignment rule can be strategyproof if the domain of preferences allows for more than one stable split. If multiple stable states exist, agents will inevitably have incentives to lie to steer the outcome toward their preferred split.
  • Unique Stability: To guarantee strategyproofness, the community's preferences must be highly structured and polarized. For example, "non-interleaving" preferences—where an agent would rather be alone with their favorite alternative than with the entire group at the other alternative—guarantee a unique stable assignment.
  • Optimal Performance: Theorem 4 establishes that Algorithm 1 is group-strategyproof specifically over domains that admit a unique stable assignment, making it a mathematically optimal choice for those scenarios.

The Complexity of Multiple Alternatives

While the 2-alternative case yields positive results, the framework faces significant hurdles when expanded to three or more choices. Proposition 5 demonstrates that for $\ge 3$ alternatives, deciding whether a stable assignment even exists is NP-complete. In these cases, the mathematical guarantees of stability and efficiency break down, leading to potential computational intractability.

Limitations and Future Directions

The current model assumes that agents care only about the size of their community and the alternative chosen, ignoring the specific identities of other members. In reality, developers or miners may wish to fork specifically with certain influential figures or trusted peers.

Future research directions include:

  • Generalizing the model to handle multiple alternatives and resource splitting.
  • Incorporating agent identities and social graphs into the preference model.
  • Exploring mechanisms for community merging (the reverse of forking).
  • Utilizing forced forks as a governance tool to isolate malicious actors, such as Sybil attackers, from the primary network.

Conclusion

By formalizing the process of forking through the lens of social choice, this paper provides a foundation for more transparent and algorithmic community governance. While the path to strategyproofness is narrow and the complexity of multiple alternatives remains a challenge, the existence of efficient algorithms for stable 2-way splits offers a promising starting point for decentralized decision-making.

Summary updated

Abstract

Any community in which membership is optional may eventually break apart, or fork. For example, forks may occur in political parties, business partnerships, social groups, cryptocurrencies, and federated governing bodies. Forking is typically the product of informal social processes or the organized action of an aggrieved minority, and it is not always amicable. Forks usually come at a cost, and can be seen as consequences of collective decisions that destabilize the community. Here, we provide a social choice setting in which agents can report preferences not only over a set of alternatives, but also over the possible forks that may occur in the face of disagreement. We study this social choice setting, concentrating on stability issues and concerns of strategic agent behavior.
BibTeX
@inproceedings{abramowitz2021democratic,
  author = {Ben Abramowitz and Edith Elkind and Davide Grossi and Ehud Shapiro and Nimrod Talmon},
  title = {{Democratic Forking: Choosing Sides with Social Choice}},
  booktitle = {ADT},
  year = {2021},
  doi = {10.1007/978-3-030-87756-9\_22},
}
Figure