The evolution of proportional representation in LiquidFeedback

In this article, I want to give a short review on the development of proportional representation algorithms in the software LiquidFeedback.

Creation of LiquidFeedback and design goals

LiquidFeedback was created in Autumn 2009 when the first beta version of the backend (October 27, 2009) and the first alpha version of the frontend (November 18, 2009) were published. Starting with the very first draft of the software, the inventors' goal (our goal) was to create a decision-making process that does not require a request-commission or a moderator with special privileges.

First approach to achieve collective moderation

The first approach to design such a “moderator-less” process was to grant every participant in the system (i. e. every eligible voter) the right to propose motions and to create counter-proposals to existing motions. These motions and counter-proposals (called “initiatives” in LiquidFeedback), would need to pass a predefined quota of supporters (i. e. supporting votes) in order to become eligible for the final voting procedure. Assuming the number of proposals is small enough, then any group including minorities of any size and even individuals have the chance to promote their positions and gain a majority for their point of view in the final voting. However, if the system is flooded with a lot of proposals (with either good cause or malicious intent), then this statement doesn't hold anymore.

In December 2009, when the first beta version of the frontend was published, a contingent system was introduced in order to deal with the issue of flooding. The contingent system would limit each participant in regard of the number of proposals that he or she may post within a given time frame. Multiple time frames with different limits could be specified such that, for example, participants could be throttled down to posting one initiative per day if they posted more than 30 initiatives within the last 7 days.

While this approach worked quite well in practice for installations with a few thousand participants where not every participant was engaging in a discussion on every issue, it is obvious that this approach doesn't scale up indefinitely; if the number of participants grows, then a minority of a given fraction (e. g. 5%) may organize in such way that their ability to flood the system grows in a linear fashion in regard to the increase of population.

In the following table, we want to show a 5% minority's ability to post initiatives, if every participant is limited to create one initiative per day.

1st column: participants in the system (population). 2nd column: if every participant is limited to post one initiative per day then a 5% minority may manage to post this many initiatives per day. 100 participants: 5 initiatives per day. 1,000 participants: 50 initiatives per day. 10,000 participants: 500 initiatives per day. 100,000 participants: 5000 initiatives per day.

Figure 1: Potential effect of individual posting limits (Table)

Obviously, in a system where already a minority of 5% might post 5000 initiatives per day, it can't be guaranteed that participants are able to browse through all initiatives that have been posted in the system. We must assume that users of the system will only read a certain amount of initiatives. The ordering of initiatives will determine which initiatives may gain attention and which initiatives won't gain attention. To maintain usability, early versions of LiquidFeedback sorted all initiatives that are competing with each other based on their supporter count (or “potential supporter” count in admission, discussion, and verification phase, see [PLF]). Thus, initiatives created and supported by a 1% minority, for example, never cause initiatives that are supported by a greater group of people to gain a bad display position when displaying a group of competing initiatives:

Initiative A with 60% supporters on position #1. Initiative B with 23% supporters on position #2. Initiative C with 11% supporters on position #3. Initiative D with 10% supporters on position #4. Initiative E with 8% supporters on position #5. Initiative F1 with 1% supporters on position #6. Initiative F2 with 1% supporters on position #7. Initiative F3 with 1% supporters on position #8.

Figure 2: Sorting initiatives based on supporter count

This approach, however, has a major shortcoming: As it needs to be possible for every participant to support multiple competing initiatives at the same time (for the reasons given in [PLF]), minorities of a smaller size would not be protected from noisy minorities with a bigger size. For example: Proposals supported by a minority consisting of 41% of the participants may “bury” proposals that are being supported by a minority of only 38%:

Initiative A with 60% supporters on position #1. Initiative B1 with 41% supporters on position #2. Initiative B2 with 41% supporters on position #3. Initiative B3 with 41% supporters on position #4. ⋮ more initiatives with 41% supporters on positions #5 through #99. ⋮ Initiative B99 with 41% supporters on position #100. Initiative B100 with 41% supporters on position #101. Initiative C with 38% supporters on position #102. Initiative D with 23% supporters on position #103. Initiative E with 11% supporters on position #104.

Figure 3: A noisy minority (41%) burying smaller minorities

This shortcoming doesn't necessarily arise in real-world scenarios where an administrator might still block users who flood the system obviously with malicious intent. However, it may be difficult to judge whether a number of proposals is legitimate or malicious flooding and requires in either case a judgment of an administrator or a jury with special privileges, hence violating the principle of a “moderator-less” process.

LiquidFeedback 2.2 and the Harmonic Weighting algorithm

Starting with LiquidFeedback version 2.2.0 (published on March 10, 2013) this shortcoming was addressed by introducing the so-called Harmonic Weighting algorithm to sort competing initiatives.

The Harmonic Weighting algorithm ensures that within an issue (i. e. within a group of competing initiatives) every group of participants that support a set of initiatives gains a display position that corresponds to the size of their group. More specifically: A group exceeding a size of P / (1+N), where P is the total number of participants supporting any initiative within the issue, will have one of their supported initiatives placed amongst the first N positions, as long as all members of the group support the same set of initiatives. This behavior is achieved by sorting all initiatives in the issue using the following algorithm:

1. 1. All initiatives are marked as unplaced (i. e. having no display position assigned yet).
2. 2. Each supporter which supports at least one unplaced initiative gets assigned a weight of 1/n, where n is the number of unplaced initiatives which this person supports.
3. 3. Each unplaced initiative gets assigned a weight equal to the sum of the weight of all its supporters.
4. 4. That unplaced initiative with the lowest weight is placed, starting from the worst position. [Note: If there are initiatives not admitted for voting (due to a lack of sufficient supporters) after final voting has started, then, as long as there are non-admitted initiatives which have not been assigned to a display position yet, only these initiatives are eligible for assignment during this step; i. e. the initiative with the lowest sum amongst the non-admitted initiatives is chosen to be assigned to the position.] In case of a tie, only the newest initiative with the least weight is chosen to be placed on the position in this round.
5. 5. Steps 2 through 4 are repeated until all initiatives are assigned a display position.

This algorithm will not only allow groups of size P / (1+N) to place one initiative amongst the first N positions if they support the same set of initiatives, but it allows any group of size P · M / (1+N) to place M initiatives of a set S amongst the first N positions, if all members of the group support all initiatives in that set (S), and no member of the group supports an initiative outside the set which gains a display position amongst the first N positions. In other words: If parts of a minority support an initiative that doesn't have a chance to be displayed amongst the first N positions, then this support doesn't affect the minority's ability to promote their commonly supported initiatives within the first N positions.

For a short outline of a proof, see [PLF].

Limitations of Harmonic Weighting and incorporation of Proportional Runoff algorithm

In LiquidFeedback, a group of competing initiatives is called an “issue”. Using the Harmonic Weighting algorithm, it is ensured that minorities will gain a fair display position within a single issue. Initiatives, however, are not the only text contribution that participants may create: it is also possible to write suggestions to existing initiatives. At first it seems attractive to extend the application of the Harmonic Weighting algorithm to also sort suggestions. But there are two reasons why the Harmonic Weighting algorithm is unsuitable to sort suggestions:

1. The Harmonic Weighting only considers one kind of support while it is possible to rank suggestions in different ways (e. g. “must be implemented” vs. “should be implemented”, see [PLF]). Thus, some participants consider the implementation of certain suggestions more important than the implementation of certain other suggestions. We should expect our sorting algorithm to take the voters' priorities into account; the Harmonic Weighting algorithm, however, only distinguishes between supporting and not supporting, and doesn't respect individual preferences.

2. Using Harmonic Weighting, supporting an initiative which is supported by a huge number of participants still reduces your voting weight given to other initiatives that are also supported by you; e. g. supporting a commonly supported initiative (which is supported by almost every participant and thus gains the first display position) will reduce your voting weight up to 50% (e. g. a weight of 1/2 instead of 1) regarding other initiatives that you also support. In case of initiatives, this behavior is intended: participants who gain a good display position with one of their supported initiatives get less voting weight for their other supported initiatives to increase other people's ability to be represented as well. In case of suggestions, however, this behavior is to be considered harmful. To name an example: If there is a suggestion to fix a comma mistake that is commonly considered as something that should be fixed, then ranking that suggestion as important could reduce your ability to give other suggestions a proper display position if Harmonic Weighting was used. Because of that, people might abstain from ranking important suggestions when they feel that enough other people would rank them. While this behavior can grant individuals an unfair personal advantage, it may backfire when too many people behave like that. In context of Single Transferable Voting, this is also referred to as the problem of Hylland Free Riding, see [Hylland, p.150–151] and [Schulze2]. People who successfully apply free riding techniques may gain an unfair advantage over other participants. While no proportional representation system can address the problem of Hylland free riding completely, the Harmonic Weighting algorithm is particularly vulnerable to it since it doesn't transfer any excessive voting weight to other initiatives at all.

For these two reasons, another algorithm named “Proportional Runoff” was incorporated into LiquidFeedback on March 18, 2013 (backend version 2.2.1 and frontend version 2.2.1). While, for good reasons, the Harmonic Weighting algorithm is still used to sort the (competing) initiatives within an issue, Proportional Runoff is used to sort the (potentially complementary) suggestions for an initiative.

The algorithm works as follows:

For each participant, a virtual “ballot” is created that indicates which suggestions are most important (or important, less important, etc.) for the participant, depending on his personal rating of the suggestion. The “ballot” thus contains preference sections, where all suggestions in the first preference section are more important than those in the next preference section, and so on. Each preference section of such “ballot” may contain more than one suggestion, in which case the suggestions in that preference section are considered to have the same priority for the voter. (For details, refer to [PLF].)

Those ballots just serve the purpose of being used for the calculation explained below and must not be confused with ballots for actually voting on an issue. In the following description of the algorithm, we will refer to the suggestions as “candidates”. We proceed as follows:

1. 1. All candidates which are mentioned on at least one ballot are marked as unplaced. (Candidates that are not mentioned on at least one ballot are excluded from this algorithm and sorted after all others.)
2. 2. All unplaced candidates are marked as remaining.
3. 3. The score of all candidates is (re-)set to zero.
4. 4. Store a temporary value for each candidate and (re-)set it to zero.
5. 5. For each ballot: Determine the first preference section containing a remaining candidate. If there is such a section, then for each remaining candidate in that section, increase these candidate's temporary values by the following amount: 1.0 divided by the number of remaining candidates in that section.
6. 6. Determine a factor such that multiplying that factor with the temporary value calculated in steps 4 and 5 and adding this product to the candidate's scores causes at least one candidate to reach a score of 1.0 but no candidate to exceed a score of 1.0.
7. 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. 8. Repeat steps 4 through 7 as long as there is more than one remaining candidate.
9. 9. If there is one remaining candidate, then this candidate is placed, starting from the worst position. 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 (in this case the newest candidate is assigned the worse position).
10. 10. Steps 2 through 9 are repeated until all candidates but one have been placed.
11. 11. The last unplaced candidate gets the first position.

The main difference between the Harmonic Weighting and the Proportional Runoff algorithm is that in every round the Harmonic Weighting divides one's voting weight equally amongst all supported non-placed initiatives independently of the other voter's choices, while in Proportional Runoff the distribution of voting weight in one round is dependent of the other voter's choices: If one suggestion or issue receives a lot of voting weight by other voters, then the Proportional Runoff Algorithm causes excessive voting weight to be transferred to other suggestions/issues (just like in “Single Transferable Vote” systems excessive voting weight is transferred to other candidates).

It should be noted that Proportional Runoff, like any other proportional voting algorithm, can't address the problem of Hylland free riding completely. While other algorithms have been proposed that are more resistant to this form of free riding (e. g. Schulze Proportional Ranking, see [Schulze2]), Proportional Runoff has been chosen for LiquidFeedback in order to keep computational complexity low.

Sorting issues in LiquidFeedback 3.0

While at this point of development (March 2013), the Proportional Runoff algorithm covered sorting suggestions to initiatives, and the Harmonic Weighting algorithm covered sorting initiatives in an issue, one problem was still unsolved: How to sort multiple issues within the system, such that minorities also gain proportional representation in a list of issues that do not compete but possibly complement each other?

Before we can answer this question, we shall have a more detailed look on the hierarchy regarding subject areas, issues, and initiatives within LiquidFeedback, as well as a look at the phases which an issue (i. e. a group of competing initiatives passes through). LiquidFeedback's hierarchy regarding organizational units, subject areas, issues, initiatives, and suggestions is structured as follows:

organizational unit “Example organization” { organizational unit “Northern branch”, organizational unit “Southern branch”, ⋮ } subject areas of organizational unit “Example organization” { subject area “finances of our organization”, subject area “national politics” } subject areas of organizational unit “Northern branch” { subject area “our club house and assets” { issue “resolution #343” { initiative “Paint the bike shelf red” by Bob { suggestion “Use weatherproof paint” }, initiative “Paint the bike shelf blue with yellow stars” by Chris, initiative “Build a new bike shelf” by Alice { suggestion “Make the new shed environment friendly”, suggestion “Let's build the shed with wood”, suggestion “Please make a plan of the costs” } }, issue “resolution #344” { initiative “Buy 10 bicycles” by Daisy, initiative “Rent the bicycles” by Chris { suggestion “Specify a company as rental company to use” }, initiative “Buy only 3 bicycles” by Ernie } }, subject area “local politics” }

Figure 4: Hierarchy of entities in LiquidFeedback

The organizational units are organized as tree, and each organizational unit may have several subject areas. In each subject area there may be multiple groups of initiatives, of which each initiative competes with all other initiatives in that group. Finally, each initiative can have multiple suggestions attached to it. Each issue (i. e. each group of competing initiatives) passes the following 4 phases:

1. admission phase (e.g. 4 weeks), <1st quorum for issue>, 2. discussion phase (e.g. 8 weeks), 3. verification phase (e.g. 4 weeks), <2nd quorum for each initiative>, 4. voting phase (e.g. 4 weeks).

Figure 5: The four phases in LiquidFeedback

The second supporter quorum was discussed already in the beginning of this article: it's that supporter quorum which an initiative needs to pass in order to be eligible for final voting.

The first supporter quorum, in contrast, is only required to be passed by one initiative within an issue, in order to let the issue proceed to discussion phase and to be potentially voted upon (if the second supporter quorum is passed by at least one initiative later).

LiquidFeedback 2.2.x sorts all issues within a subject area by their remaining time in the current phase. Even if the ordering is not done by a proportional representation algorithm, every minority has still a proportional representation within each issue (due to application of Harmonic Weighting).

We consider every issue that has passed the first supporter quorum to be of general interest as there is a realistic chance that this issue will reach final voting procedures. Participants who think that the issue is biased or may contain initiatives that are to be considered harmful need to post counter-proposals with different point of views. LiquidFeedback 3.0 thus keeps sorting these issues based on their remaining time in the current phase.

Issues that have not yet passed the first supporter quorum, however, are not of general interest. Assuming the participation system is used by a huge number of participants (e. g. 100,000 or 1,000,000 people), there might be a huge number of issues in admission phase that wait to gain enough supporter votes in order to proceed to discussion phase. If we want to grant minorities a fair chance to promote their positions, then we need to sort these issues in admission phase in such way that display positions are assigned in a proportional manner.

The backend of LiquidFeedback 3.0 (backend published on January 31, 2014) thus also applies the Proportional Runoff algorithm to those issues in a subject area that are in admission phase. More details on the application of the Proportional Runoff algorithm can be found in our book, The Principles of LiquidFeedback, see [PLF].

Outlook

Assuming every minority that wants to maliciously flood the system with proposals is small enough to fail the first supporter quorum, LiquidFeedback 3.0 would not need the contingent system (flood limit) anymore. Depending on the kind of organization and the people involved, this assumption, however, may be wrong. LiquidFeedback 3.0 will thus still retain the flood limit mechanism for two reasons:

1. to avoid that minorities which exceed a certain size (the first supporter quorum) can flood the system without limitation,

2. to prevent a system overload due to a (potentially) unlimited number of issues, initiatives, and suggestions.

In theory, this still limits the scalability of LiquidFeedback as previously explained: if the number of participants doubles, then, in the worst case, each participant dealing with a particular subject area may have to browse through the double amount of proposals. While we are not aware of any practical example where this theoretical problem has been an issue, future versions of LiquidFeedback may be improved to close this loophole.

One possible approach to fix this loophole is to not limit the number of proposals that are posted by each participant, but instead to limit the number of proposals that are allowed to proceed from admission phase to discussion phase for each subject area within a given time frame. In regard of the issues that are allowed to proceed, the limitation mechanism would need to provide a proportional representation of the participants. The development of such an algorithm may be interesting for future versions of LiquidFeedback and other electronic participation systems.