Ranked choice voting

[blue-note]

How does ranked choice voting work?

• Imagine there is a multiple choice proposal with a few options to choose from. When voting, users will rank those choices
  in order of preference.
• If there is an option with the majority of first-preference votes, this option has won. If not, the option
  with the fewest first-preference votes is eliminated, and for whomever ranked that choice first, their second-choice votes are promoted to first-choice.
  Then if there is a candidate with the first-preference majority, this procedure will be repeated until a winner is found (or none is found).

How shall we implement this?

After some deliberation, I think it makes the most sense to introduce a new proposal module for this change. Introducing ranked choice as a new voting strategy in the existing multiple choice proposal module will require changing the existing vote data structures and passing / rejection logic in a way that will introduce too much unnecessary confusion. The multiple choice module has also already been audited so it is preferred to not make major changes and there is little cost to introducing a new proposal module.

Proposed Design: Implement a new ranked choice proposal module

How will ranked preferences be indicated to the module?

• When a user submits a vote, instead of selecting a single option, they will instead pass a list of option IDs whose order determines ranking.

pub struct MultipleChoiceVote {
    pub option_ids: Vec<u32>,
}

How will we keep track of the vote counts for each rank?

• I propose that each CheckedRankedChoiceOption persist a list of ranks that will hold vote weights.

/// A verified option that has all fields needed for voting.
#[cw_serde]
pub struct CheckedRankedChoiceOption {
    // This is the index of the option in both the vote_weights and proposal.choices vectors.
    // Workaround due to not being able to use HashMaps in Cosmwasm.
    pub index: u32,
    pub option_type: MultipleChoiceOptionType,
    pub title: String,
    pub description: String,
    pub msgs: Vec<CosmosMsg<Empty>>,
    pub ranks_to_vote_counts: Vec<Uint128>,
}

How will is_passed and is_rejected change? Will we be able to declare proposal status early?

• A proposal will be considered "passed" if quorum has been met and there has been an option found that has the majority of first-preference votes. It will be considered "rejected" if either there the quorum has not been met, if "None of the Above" option has received majority of the votes, or if none of the votes have received a majority.
• Similar to existing proposal modules, if revoting is enabled, we will not be able to declare a proposal 'passed' or 'rejected' before expiration.

Will there be a quorum?

• There can be. This would mean that quorum amount of votes must be cast before we can consider a proposal for passing, and the majority will be calculated based off the quorum rather than the total votes.
• If there is no quorum, we could instead require that an option must have achieved a majority of the total voting power in the DAO. I would argue that a quorum is useful for passing proposals faster with lower participation than the whole DAO.

How will is_passed work?

1. We will see if the option which has the highest vote weight for first preference has a majority of all possible votes. If so, the proposal has passed, regardless of whether or not it is expired. If not:
   a. If the proposal is expired:
   Find the option with the least first-preference votes and eliminate this option (e.g. flag it as such). For all ballots which have marked this option as first preference, elevate their second preferences to first. OPEN QUESTION HERE: HOW DO WE DO THIS EFFICIENTLY? CAN WE STORE THIS DATA IN SOME WAY SUCH THAT WE DON'T HAVE TO LOAD ALL BALLOTS? Repeat step 1.
   b. If the proposal is not expired:
   If there is no majority winner in the first round, we cannot make a conclusion until more votes are cast.

How will is_rejected work?

1. If the proposal is expired and quorum has not been met, it is rejected.
2. We will see which option has the highest vote weight for first preference. If this option is "None of the Above" and it has the majority of all possible votes, then the proposal is rejected, regardless of whether or not it is expired.
3. If not, we will proceed with the ranked-choice procedure outlined above. If none of the votes have garnered a majority, and if none of the votes are able to garner a majority with the amount of remaining voting power to be cast, then the proposal is rejected.

Note: the passing and rejection logic is obviously complicated will require very careful consideration of all edge cases.

[0xekez]

this is a really great spec. memorializing some of our discussion yesterday, structurally, to get around this gas issue we likely either need to:

1. discover another algorithm / datastructure for tallying ranked choice votes.
2. do some pre-compute on every vote where we calculate all the possible rearrangements of the vote somehow.

[0xekez]

we've come up with a spec for gas-efficent voting which can be found here: https://gist.github.com/0xekez/e4d3ff76bf76f052af1a8768231831aa