Voting methodology for CR increase

TL;DR

I propose to make the choices of the poll go from 150% to 300% in increments of 5% and include an extra option for “Higher”. The results be aggregated by taking the median. If the result is equal to “Higher” another poll will be held with higher numbers.

Introduction

I’ve been thinking of what would be the best way to conduct the vote on CR, especially on what’s the best way to derive a final number from the poll. I think this is important because, if we were to use an operation such as the mean, as it was done for the previous poll, the stakers would be incentivized to misreport their preferred CR in order to gain an unfair advantage.

Let’s take for example a poll where two votes have been cast for 170% and 180%. If an staker wanted the CR to be 200% it would vote for 250%, misrepresenting their preference in order to make his vote weight more.

Another possible solution would be to just pick the most voted response, but then you run into the same problems that regular electoral elections have: voters are incentivized not to vote for low-support options in order to avoid “wasting” their vote.

Because of this I think it’s worth looking for an alternative that incentivizes users to vote truthfully and makes it impossible to gain an unfair edge.

Previous work

Surprisingly there’s very little literature on the topic of surveys for continuous variables. There’s a paper^[1] that focuses on that in the context of quantum voting, but it mostly focuses on using quantum properties to make voting anonymous and receipt-free (to prevent coercion) and it actually aggregates the votes with a simple sum, so it’s not interesting for the case at hand.

On the other hand, optimal voting seems to be a well studied topic in the area of economics, where there’s a whole branch called social choice theory that is dedicated to this topic^[2]. What’s more, they have named the property that we are looking for in our survey as strong group strategyproofness (abbreviated SGSP from now on), which is defined in the following way^[3]:

A game is SGSP if and only if no group of people can collude to misreport their preferences in a way that makes at least one member of the group better off without making any of the remaining members worse off.

This is equivalent to having the best outcome for every player be always achieved by answering truthfully.

Interestingly, a capstone theorem in this area, the Gibbard–Satterthwaite theorem, states that electoral voting systems can’t be strategy proof unless there’s a single voter or there are only two choices^[4]. This may seem to spell doom for our goal, but I think this doesn’t apply to this case since I’ve found a method that I believe to be SGSP: calculate the median of the votes.

Proof

In this section I’ll prove that if we were to use the median of all votes the resulting system would satisfy SGSP.

Intuition

If a voter lies and votes for a value other than the one he wants four things could happen:

  • Median moves further away from the wanted → worse outcome than being truthful (if truthful the median will always stay the same or get closer)

  • Median gets closer but doesn’t reach the wanted value → if vote is lower than new median we would have had the same outcome than being truthful but if that was not the case the new median would be even lower if voter had been truthful

  • Median becomes the wanted value → Same outcome if truthful

  • Median gets closer and overshoots the wanted value → if voter was truthful the overshooting would have been lower or equal → median would have been closer or equal

In all these cases being truthful leads to the median being equal or closer to what the voter wants whereas lying has the opposite effect → it’s optimal to be truthful.

Complete proof

Given a set of votes, with a total median of m (new median after applying the new vote is m_2 when lying and m_3 when not), and a single voter that casts a vote v and wants to get the final result as close as possible to x (minimizes |m-x|):

If x<m:

  • v>=m → m_2>=m → |m_2-x|>=|m-x|, it’s increasing or staying equal but v<m → m_3<=m→ |m_3-x|<=|m-x|<=|m_2-x| will always make |m-x| equal or lower → v<m optimal choice.

  • if x<v<m, v_2=x → x<=m_3 and v_2<v → m_3<=m_2→ |m_3-x|<=|m_2-x| → v_2 is better

  • if v<x we’d be in one of the following situations:

    • m_2 > x → |m_2-x|=|m_3-x|
    • m_2 =x → |m_2-x|=|m_3-x|
    • m_2 < x, v_2=x →v<v_2→ m_2<=v_3 → |m_3-x|<=|m_2-x|

If x>m the previous argument can be applied again to reach the same conclusion.

If x=m, |m-x| has already reached a minimum and it’s trivial to see that v=x is optimal (any other number moves it away).

Originally I had proved that this also holds true in the presence of unknown/future votes but the proof was really long, thus I decided to just provide this handwavy and simple version. If someone wants to see the other proof just let me know, it’s only an extension of this one that uses induction on the scenario that n-1 out of n votes are known. On top of that, please note that my proof assumes several properties of the median that haven’t been proved but would need to be.

Simulation

The following code runs 1M polls with 100 randomized votes and checks whether a better outcome for the last voter is achieved whether he votes for his preferred value or a random one:

from random import random
for i in range(1000000):
  votes = [random() for _ in range(100)]
  desired_vote = random()
  truthful_median = sorted(votes + [desired_vote])[50]
  fake_median = sorted(votes + [random()])[50]
  if abs(truthful_median-desired_vote) > abs(fake_median-desired_vote):
    print("Truthful voting is not optimal")

In all cases, a vote for the desired value leads to better results for the voter.

Choices

In order to avoid bloating the possible choices we can just provide an extra option labeled “Higher” that will aggregate all the possibilities higher than certain value. Due to the properties of the median, if a value higher than the ones that can be picked were to become the final result then the end result would just be “Higher” so at that point we can organize a new poll with higher choices for the users that chose “Higher”.

The idea is to pick a maximum number that is high enough that the chances of it winning the poll are slim, thus another poll won’t be needed.

Another possibility would be to make numbers increase logarithmically, but then you lose precision.

Proposal text

I think it’s best not to list the arguments on both sides and keep the proposal as short as possible because, if we were to do that, it’d be easy to end up with a heavily biased text that favors one outcome. At the same time I imagine it would be helpful for stakers that haven’t been involved with the discussions to have an abbreviated version of them available, so I’m not sure what’s best.

Draft of the snapshot proposal

Title: What should the collateralization ratio of new deposits be?

Text: The final value will be calculated through a median. If you’d like to vote for a higher value than the ones available select “Higher”. Check the #governance-discussions channel on KEEP’s discord for discussion on this governance proposal.

Choices:

  • 150%
  • 155%
  • 300%
  • Higher

Duration: 72 hours

Notes

  • I’m not familiar with most of the research on social choice theory so it’s entirely possible that I misinterpreted something. If that’s the case please let me know.

  • Some of the values used, such as proposal duration, have been picked by me arbitrarily.

References

[1] Phys. Rev. A 85, 042309 (2012) - Quantum anonymous voting for continuous variables

[2] http://pareto.uab.es/sbarbera/SB-SCW10180619introduc.pdf

[3] Strategyproofness - Wikipedia

[4] Manipulation of Voting Schemes: A General Result on JSTOR

2 Likes