Jump to: navigation, search

Difference between revisions of "Governance/TieBreaking"

m (Text replace - "__NOTOC__" to "")
m
 
Line 103: Line 103:
 
* that they got the same seed hash
 
* that they got the same seed hash
 
* that they got the same winner!
 
* that they got the same winner!
 +
 +
[[Category: Elections]]

Latest revision as of 18:49, 8 January 2015

Tie breaking

We use Condorcet voting system for all Technical Committee elections (PTL and direct seats).

Condorcet may result in ties, which should be broken fairly and in a reproducible manner. We will use the hash of a string describing the tie results as a seed in a random generator to determine the tie winners, this way anyone may verify the fairness of the tie break. Read on for more details ;-)

Desired Features

The features we need in a process that addresses a tie-breaking scenario are the following:

  • has to be fair
  • has to support a remote process
  • results need to be verifiable (repeatable)
  • results need to also be random
  • process needs to severely limit (or remove altogether) the possibility of "gaming" the system
  • process needs to support multi-way ties

A Tool

As such, we wrote a quick little python tool that supports part of the this list; the other part of the list is addressed via the process that makes use of the tool. The tool is available on github and you can take a look at it with the following:

  $ git clone git@github.com:oubiwann/coin-toss.git
  $ cd coin-toss


This tool takes advantage of the Python standard library's random module. By using a seed, we can get the same series of random selections every time, thus satisfying our requirement for verifiability and repeatability (as well as randomness!).

Note that the tool standardizes on Python 3. Anyone verifying a tie-breaking result should use Python 3.

The Process

The process described in detail below attempts to leave no ambiguity in the minds of community members as to the steps election officials will take when determining who wins in the event of a tie. In order to be as explicit as possible about the process, we'll illustrate with an example. In our example election for three available seats, the following Condorcet results came in:

  • Alice: 1st place
  • Bob: 2nd place
  • Carol: tied 3rd with Dave (lost to Alice by 40-47; lost to Bob by 38-45; beat Dave 41-40; lost to Eve 40-41)
  • Dave: tied 3rd with Carol (lost to Alice 29-54; lost to Bob by 26-48; lost to Carol; 40-41; beat Eve 44-42)
  • Eve: 4th place

We need to break the tie between Carol and Dave. We would like for our seed to be unique for time date and for the organization (in the event of an amazing coincidence where there was another tie between the same candidates running for a different election; we'd like to have a different hash/seed for ours!) . As such, we will be adding the following data to the seed:

  • the date that the election opened
  • the openstack.org domain to generate a UUID namespace

We know this information ahead of time, but we have to wait until the elections finish before we can generate our seed, since we also need:

  • the scores of each tied candidate with all the other candidates (e.g., the data that is in the parentheses above for Carol and Dave)

So here's how we will put this together:

  $ ./bin/get_seed \
    --namespace=openstack.org \
    --data=2012-08-21 \
    --data=Carol.Smith:40-47:38-45:41-40:40-41 \
    --data=Dave.Doe:29-54:26-48:40-41:44-42


Important things to note:

  • the date the election was opened is the first data added for the hash
  • the scores of the tied candidates are provided next, in ascending alphabetical order by first name
  • the scores are prepended with Firstname.Lastname of the candidate, colon-delimited from the scores (no spaces)
  • the individual scores vs. another candidate are separated by a dash with the first score being that of the tied candidate (e.g., Carol Smith lost to Alice, 40 to 47 = 40-47)
  • the individual scores are colon-delimited

Coin-toss supports any number of tied candidates. In the event of 4 tied candidates, we'd have two more --data=Firstname.Lastname:<scores> arguments. We'd also need to update the toss command to include the two additional tied candidates.

Our call to get_seed gives us the following hash:

  e9ca327a-7deb-5919-a207-5d519c2d7837


With the seed generated, we can then finally "toss a coin" to see which of the tied candidates will be awarded the seat:

  $ ./bin/toss e9ca327a-7deb-5919-a207-5d519c2d7837 Carol.Smith,Dave.Doe


Important items of notice:

  • the tied candidates are listed here in ascending alphabetical order by first name
  • they are comma-delimited
  • there are no spaces

And our winner is:

  ['Carol.Smith']


You can also specify the number of winners using a command line option to the tool For instance, if there were three seats available and 4 candidates tied for 1st place, you can use the --winner-count option:

  $ ./bin/toss 3641f821-6fb4-7d51-94e1-dce0e92f4571 --winner-count=3 Alice,Bob,Carol,Dave
  ['Bob', 'Carol', 'Dave']


Election officials need to confirm the following with each other:

  • that they got the same seed hash
  • that they got the same winner!