Liquid democracy and loop detection

Liquid democracy features transitive delegation, delegates themselves can delegate their votes. If voter A delegates his vote to voter B and voter B delegates his vote to voter C, then voter C casts three votes, his own, plus that of A and B[1]. Or if you want to be more precise, vote C’s vote has a weight of 3, as if voter A and B’s made the same choice as C.

Transitive delegation

Transitivity raises an important issue, the possibility of cycles, or loops, in the voting graph. A cycle will prevent votes entering it from being counted correctly, those votes will traverse the cycle forever. So a system supporting liquid democracy must include a mechanism to handle this possibility.

The first feature such a system must include is a loop detection procedure as part of the tallying algorithm. When running the liquid tally, the algorithm must not crash or hang due to the existence of loops. The loop must be detected an the traversal aborted. With simple caching such a liquid tally algorithm runs in time linear in the number of voters. The algorithm is pretty trivial so I won’t describe it.

Adding loop detection to the tally ensures it completes correctly, but there are still undesirable outcomes. Let’s assume the scheme is a single unconditional transitive delegation. This means that a delegation vote is unique (rather than multiple), transitive, and does not depend on vote categorisation (whatever the mechanism chose for determining categories). Under this scheme votes that reach a cycle in the voting graph will be lost. Although this is not fatal for the tally, it is undesirable, those voters whose choice was discarded will not be represented.

Oh oh, a loop!

So, a second mechanism must be added. We can call this vote-time loop detection. This is a mechanism that detects cycles just as they are formed, and prevents them from being established. A feedback message instructs the voter that his/her choice is invalid as it would create a loop, the user must make another selection. How does this detection algorithm work? Well essentially in the same way as it does in the tally algorithm, except that it only checksĀ  loops starting from delegation choices just as they are made by a user, on demand.

My simple liquid tool app features vote-time loop detection and marks cycles in red so that the user makes the relevant correction. In fact the algorithm is a bit more complicated than necessary because it allows the loop to be established, and must keep track of subsequent changes that revalidate the voting graph.

Finally, some extra care must be taken to ensure that vote-time loop detection is accurate, as stale data may result in inaccuracies. This is especially important in the face of concurrent modification of the voting graph as users progressively emit votes. But the problem is still pretty trivial in this scenario, things can get somewhat more complicated with more sophisticated delegation schemes.

 


[1] In this post I am not distinguishing voters from delegates, all voters play the double role of voter and delegate. Any voter can delegate to anybody other voter. This type of scheme is only applicable with public voting, where delegate accountability does not require a special treatment.

2 thoughts on “Liquid democracy and loop detection

Leave a Reply

Your email address will not be published. Required fields are marked *