wiki:ProportionalOrderOfSuggestions

Proportional ordering of suggestions

As of LiquidFeedback Core v2.2.1 suggestions are sorted using a "proportional_order" property. This property is calculated using a generalized version of the Proportional Runoff Algorithm:

We create virtual ballots based on the initiative supporters opinions on suggestions:

  • 1st preference: All suggestions marked as "must" and "not implemented", or "must not" and "implemented"
  • 2nd preference: All suggestions marked as "should" and "not implemented", or "should not" and "implemented"
  • 3rd preference: All suggestions marked as "must" and "implemented", or "must not" and "not implemented"
  • 4th preference: All suggestions marked as "should" and "implemented", or "should not" and "not implemented"

We only consider suggestions at least ranked by one supporter of the initiative. These are the "candidates". The "seats" to be filled are our display positions. We proceed as follows:

  1. All candidates are marked as unseated.
  2. All unseated candidates are marked as remaining.
  3. The score of all candidates is set to zero.
  4. Store a temporary value for each candidate, and (re-)set it to zero.
  5. For each ballot: Determine the first preference section containing a remaining candidate. If there is such section, then for each remaining candidate in that section increase these candidates temporary values by the following amount: Voting weight divided by the number of remaining candidates in that section.
  6. Determine a maximum factor, so that multiplying that factor with the temporary value calculated in steps 4 and 5 and adding this product to candidates scores, causes at least one candidate to reach a score of 1.0, but no candidate to exceed a score of 1.0.
  7. Perform the addition described in step 6, and remove those candidates, which reach a score of 1.0, from the list of remaining candidates.
  8. Repeat steps 4 through 7, as long as there is more than one remaining candidate.
  9. If there is one remaining candidate, then this candidate is seated, starting from the worst rank. If there is no remaining candidate, then tie-breaking is needed between those candidates which have been removed during the last application of step 7.
  10. Steps 2 through 9 are repeated until all candidates but one have been seated.
  11. The last unseated candidate gets the seat with the best rank.

Implementation

Implementation is done in an optimized C program lf_update_suggestion_order.c, which ships with the LiquidFeedback Core. It should be executed after running "lf_update", but may also be executed in parallel to "lf_update", if your setup requires splitting the load to multiple processor cores.

Simpler algorithm for sorting initiatives

Initiatives are not sorted using this algorithm, but a more simple algorithm called Harmonic Weighting.

Last modified 4 years ago Last modified on Mar 18, 2013, 10:30:13 AM