Intro to social choice theorems

Author: Jagrut Kosti, R&D Team Lead

Ever had to go out with your colleagues for lunch and experienced how hard it can be to come to a conclusion on where to eat? Making decisions alone is difficult. Collective decision-making is much more complex (an understatement)! This is very important. It is especially important in decentralized autonomous organizations (DAOs). To be able to come to a conclusion using code as a mediator is challenging. Before we explore the complexities of governance onchain or offchain, let's learn some basics from social choice theory. Researchers have studied decision-making in democratic systems for decades.

Most of the DAOs that have implemented a governance mechanism essentially boil down their voting method to a single choice "yes", "no" or "abstain" option. Single-choice voting seems simple and removes the complex parts of ranked choice voting. However, it is not the best system for every situation. And most of the projects do not seem to highlight this.

Challenges with split proposals and ranked choice

Let's say for the platform X (sarcasm intended), a decision has to be made about which logo, out of logoA, logoB and logoC, should be adopted. One can argue that instead of creating one proposal and tallying using ranked choice preference, we can split the proposal into 3 and carry-on with the usual voting methods adopted by DAOs:

• Should we go with logoA? Options: "yes", "no", "abstain"
• Should we go with logoB? Options: "yes", "no", "abstain"
• Should we go with logoC? Options: "yes", "no", "abstain"

This opens up a can of worms! What happens if logoA and logoB both have "yes" as the winner? Should we then create another proposal to resolve the tie? Are the same voters going to vote on that? What if some significant portion of the old voters does not show up? What if new voters show up? Would this not increase voter fatigue?

While most DAOs try to avoid such proposals, it can still happen depending on the topic of discussion. There is a reason why ranked choice preference tallying is avoided but that does not mean it cannot be made practical. In this article, we will look into a few of the well-known theorems in social choice theory and to keep in mind when designing any governance mechanism.

Why DAOs use May's theorem for voting

The reason that most DAOs use the single-choice simple majority voting method is because of the May's theorem:

May's theorem says that for two voting methods, simple majority is the only social choice function that is anonymous, neutral, and positively responsive.¹

Anonymous: There is no distinction between the votes, and each voter is identical.

Neutral: Reversing the choice of each voter reverses the group outcome.

Positively responsive: if some voters change their preference to support one option and others do not change, the outcome will not go against that option. If the previous outcome was a tie, the tie is broken in the direction of the change.

The theorem only applies if there are two options. In most DAO ballots (sets of options in proposals), the "abstain" vote is not counted, and hence, the theorem applies.²

Arrow's impossibility theorem

Arrow's impossibility theorem applies only to ranked choice voting. A voting rule is a method of choosing a winner from a set of options (ballot) on the basis of voters' ranking of those options. Before jumping into the theorem, let's examine a couple of different voting rules.

In the plurality rule, the winning option is the option which was ranked first the most than any other option. E.g. for three options X, Y & Z, if 40% voters liked X best, i.e. ranked it first, 35% liked Y best, and 25% liked Z best, then X wins, even though it is short of an overall majority (greater than 50%).

In majority rule, the winning option is the option that is preferred by a majority to each other option. For example, with three options X, Y, and Z: 40% of voters rank X>Y>Z, 35% rank Y>Z>X, and 25% rank Z>Y>X. The winner is Y because 60% of voters prefer Y to X, and 70% prefer Y to Z.

Note that plurality and majority rule lead to different outcomes. This prompts the question: Which outcome is "right"? Or, which one is better to use? We can then ask a general question: Among all possible voting rules, which is the best?

Arrow proposed that we should first identify what we want out of the voting rule, i.e. what properties should be satisfied. The best voting rule will then be the one that satisfies all of them. Those properties are:

Decisive/unrestricted domain

All voters' preferences should be accounted for, and there should always be a winner. There should not be more than one winner.

Pareto principle

If all voters rank X above Y and X is on the ballot, Y should not be the outcome.

Non-dictatorship

No single voter's choice should decide the outcome.

Independence of irrelevant alternatives

If a voting rule picks X as the winner and we remove Y from the ballot because Y did not win, then X should still win. This means the result does not depend on irrelevant alternatives. To give an example, in the plurality rule example above, if option Z was removed and all those who chose Z as their first choice now choose Y, Y will be the winning choice with 60%.

Politically speaking, Z is a spoiler. Even though Z was not going to win in either case, it ended up determining the outcome. This has happened several times in democratic elections. This property serves to rule out irrelevant alternatives or spoilers.

The plurality rule is vulnerable to spoilers and hence violates the property of independence. Majority rule satisfies the independence property, i.e. if X beats each of the other choices, it continues to do so if one of the choices is dropped. But majority rule does not satisfy the decisiveness property, i.e it doesn't always produce a winner. In the table of ranked choices, Y beats Z by 68% to 32%. X beats Y by 67% to 33%. Z beats X by 65% to 35%. So, no option beats the other two. This is called Condorcet's Paradox.

Arrow tried to find a voting rule that satisfied all the properties, but eventually it concluded that no voting rule satisfied all four properties!

The name of the theorem is itself a source of pessimism: if something is "impossible", it can't be accomplished. This theorem prompts the question: Given that no voting rule satisfies all properties, which rule satisfies them most often? One plausible answer is that in majority voting, if one particular class of ranking (e.g. Z>Y>X) is removed with high probability of it not occurring, then majority rule will always have an outcome. In this case, majority rule does not violate the decisive property.

There is another theorem called the domination theorem. The theorem says that if a voting rule works well for certain rankings and is different from majority rule, then majority rule must also work well for those rankings. Furthermore, there must be some other class of rankings for which majority rule works well, and the voting method we started with does not. Whenever another voting rule works well, majority rule must work well, too, and there will be cases where majority rule works well and the other voting rule does not.

This applies only if identifying a class of ranking is possible, but is highly unlikely. In the case of DAOs, the question arises as to who is responsible for identifying and eliminating such a class of ranking for each proposal. Simply eliminating the least voted class of ranking results in utter neglect of the minority.

Gibbard–Satterthwaite theorem on ranked choice voting

Gibbard-Satterthwaite's theorem is applicable to ranked choice voting that chooses a single winner. It follows from Arrow's impossibility theorem.³ For every voting rule, one of three things must hold:

• There is a dictatorship, i.e. one voter's choice determines the outcome, OR...
• There are only two choices (in the ballot) and hence only two possible outcomes, OR...
• Tactical voting is possible, i.e., some strategies exist where a voter's ranked choice does not show their sincere opinion but gives the outcome they want.

Borda count: For the ranked choice ballot of each voter with n options, assign \(n−1\) points to the top option, \(n−2\) to the second option, ... and zero to the last option. The option with the most points is the winner.,

To demonstrate the theorem, consider 3 voters A, B & C and four options: W, X, Y & Z, and their ranked preferences are as follows:

Based on Borda's count (W: 3, X: 6, Y: 7, Z: 2), Y is the winner. But if Alice changes her ballot as follows:

From the Borda count (W: 2, X: 7, Y: 6, Z: 3), X is the winner, and Alice's preference for X over Y is still maintained. Therefore, we can say that there exists a strategy where the Borda count is manipulable.

Key considerations for DAO governance design

Before designing governance for DAOs, understand that onchain voting is a useful tool. However, it does not fix the main problems in social choice theory. We also want to experiment with new systems, but first, we will base our work on decades of research that have already been proven to work or not work. This article explains why ranked choice voting is hard to use. Most DAOs now use single-choice voting, but it can be manipulated.

Most DAOs allow the voters to weigh their preferences by either using more tokens or time-locking tokens (conviction voting). This is limited to putting the weight towards one option in single-choice voting. Ranked choice voting is complex to begin with, and introducing weights can potentially add more complexities and result in unforeseen outcomes.

As shown in the Gibbard-Satterthwaite theorem, the Borda count is manipulable. Adding weights will open up even more possibilities for the system to be gamed.

Nonetheless, it is a great domain to research and experiment!