Experimenting with liquid filtering

Previously we introduced the idea of liquid filtering and its motivation:

We have a situation where we have to collectively choose among many options. In the presentation this was referred to as scaling the solution space. It is infeasible to apply voting as is, because voters cannot consider all these options to make a judgement. So what we do is distribute the cognitive load in a way that reflects user delegation. The problem of liquid filtering is the assignment of voters to questions according to delegation choices, in an optimal way.

and we spoke of optimality which we defined as

minimize the number of questions that each voter has to answer while ensuring that every voter votes on each question

and its math equivalent

minimize |A| subject to ∃ (v, q) ∈ T ∀ q  Q, v ∈ V

The first step in implementing a liquid filtering algorithm is to convert this optimality criterion into an objective function. For simplicity we will modify our criterion slightly to

given a fixed number assignments, maximise the effective number of questions answered

which is saying basically the same thing but from the reverse point of view. With ‘effective’ we refer to the fact that  although voters may not answer a question directly, they can answer it by virtue of having one of their delegates answer it for them. The effective number of questions answered is thus the sum of questions answered directly or via delegation. Optimality is thus defned as

given some |A|  maximize |(v,q)| such that (v, q) ∈ T where q  Q, v ∈ V

We will also assume for simplicity that each voter answers the same number of questions. We referred to this possiblity before

even if the sum total of questions is minimzed, one does not want to overload specific voters with too many questions

One way to define an objective function could simply be the sum of questions effectively answered by each voter, over all voters:

f(A) = Σ t(v, q), where

t(v, q) =

1 if  (v, q) ∈ T and

0 otherwise

the maximum value that this function can attain is that in which every voter has effectively answered every question.

max f(A) = |V| x |Q|

Using this quantity we can define a more intuitive function, coverage, which corresponds to the fraction of all the question-voter pairs that have been effectively answered:

coverage(A) = Σ t(v, q) / |V| x |Q|

this ranges from 0 (no coverage) to 1 (full coverage).

What about delegation chain length?

The coverage function we just defined is the simplest case. One variation could address something we said in the previous post

one goal could be to reduce transitive chains lengths such that user delegates are in fact aligned with the user’s preferences

The intent here is to accomodate the fact that long delegation chains may potentially lead to results that are not representative of voter’s choices. This possibility is also considered in viscous democracy[1], and more generally in systems that penalize edge chain lengths with damping, such as PageRank[2]. So we can define a non-transitive coverage function

non-transitive coverage(A) = Σ t1(v, q) / |V| x |Q|, where

t1(v, q) =

1 if  (v, q) ∈ T1 and

0 otherwise

where we define T1 as equal to T but with a delegate chain cutoff of 1. A cutoff of 1 means we consider only direct delegates. Delegates of delegates, and so on, do not count in calculating a voter’s effective response. Thus T1 is the same as T but replacing D+ with its 1-cutoff equivalent:

T1 = { (v, q) |  ∃ (v’, q) ∈ A ∧ ∃ (v, v’) ∈ D1+ ∧ v, v’ ∈ V, q  Q }

where D1+ is the 1-cutoff equivalent of D+ (recall that Dis the transitive closure of D, the binary relation encoding delegation)

Generalizing, we could define a weighted coverage function which penalizes delegation lengths with values other than 0 or 1, and uses arbitrary cutoffs, but we won’t go into it in detail now.

Some experiments

Below are some results we’ve had running simulations on random graphs to get a feel of how the solution space looks like. The key parameters that define an instance of a random filtering problem are

voters: the number of voters that participate in the decisions

questions: the number of questions that must be decided on

average delegates: the average number of delegations each voter makes

questions asked: the number of questions each voter is presented

coverage function: a choice of objective function, such as those just described above

non-transitive coverage

The following plots were made with questions asked fixed to 1

transitive coverage function

The following plots were made adding an additional axis for the questions asked parameter, varying from 1 to 5. The average delegates was the other horizontal axis, whilst the vertical axis was the coverage function, using a delegate chain cutoff of 3. Additionally we show results of simple hill climbing optimizations (with the ‘X’ symbol) on the assignments.

here we show the same runs but using a weighted coverage function, again with a cutoff 3. The coverage function used here penalized delegation according to their length.

tentative conclusions

 Although these are early results in liquid filtering some conclusions are available.

  • participation is most sensitive to average degree and questions asked
  • population size has no effect provided it is much larger than questions
  • participation becomes saturated at high average degree due to graph topology
  • graph topology dominates optimization (at least using hill climbing)

Other observations to make

  • Secure voting precludes the possiblity of optimization, in these cases it is not possible to improve assignments beyond uniform distribution
  • Without transitivity, average degree must have a magnitude roughly comparable to questions in order to achieve high participation

The biggest flaw in these experiments is probably the purely random nature of the delegation graphs. In order to obtain more realistic results, the generator should produce graphs that, although still random, exhibit properties of those emerging in a practical liquid filtering system. For example, degree variance could be constrained in such systems. Another possibility is that these graphs could feature small world effects or power law degree distributions, as has been observed for social networks.


[1] http://dl.acm.org/citation.cfm?doid=1953122.1953154

[2] http://en.wikipedia.org/wiki/PageRank#Damping_factor

Liquid filtering

In our talk presented here we listed several problems involved in scaling democracy, one of them was the problem of having voters decide from many possibilities, which we referred to with

I can’t decide from too many options

Information overload “the difficulty a person can have understanding an issue and making decisions that can be caused by the presence of too much information.” (Toffler)

Here we will present an idea towards fixing this problem. Briefly, the aim is to combine ideas from collaborative filtering with liquid democracy. Wikipedia on collaborative filtering:

The growth of the Internet has made it much more difficult to effectively extract useful information from all the available online information. The overwhelming amount of data necessitates mechanisms for efficient information filtering. One of the techniques used for dealing with this problem is called collaborative filtering.

This description fits very well with our problem. If you haven’t heard of collaborative filtering before, think amazon/lastfm/netflix recommendations, or digg filtering of stories. Here’s a quote from Anton Kast, lead scientist at Digg

The idea of collaborative filtering is simply to combine the input from many different people to filter information better than would otherwise be possible. In particular, you use information from many independent judgements by many people… On Digg anyone can submit a story. And anyone can vote on any story – that’s the filtering part, and whatever is most popular wins. It’s a giant collaborative filter in the simplest, classic sense

With that out of the way, how do we combine collaborative filtering with liquid democracy? The answer is simple, whereas in classic collaborative filtering user affinities are implicit in user behaviour and are inferred statistically by CF systems, liquid filtering makes user affinities explicit, in the form of delegation. After all, ‘user affinity’ is nothing but ‘delegation’ in different clothes. And as in liquid democracy, transitivity can be mixed in; the interpretation is straightforward: If I trust A’s judgement who trusts B’s judgement, then I trust B’s judgement.

So, let’s get back to the probem we started with. We have a situation where we have to collectively choose among many options. In the presentation this was referred to as scaling the solution space. It is infeasible to apply voting as is, because voters cannot consider all these options to make a judgement. So what we do is to distribute the cognitive load in a way that reflects user delegation. The problem of liquid filtering is the assignment of voters to questions according to delegation choices, in an optimal way.

Where’s the math?

Here’s a simple formalization. Note that things can be made more sophisticated to reach specific criterions of optimality. For example, one objective could be to reduce transitive chains lengths such that user delegates are in fact aligned with the user’s judgement. But in this post we will restrict optimality to mean:

minimize the number of questions that each voter has to answer while ensuring that every voter votes on each question

Some definitions follow. A set of questions to be made

Q = { q1, q2, q3 … }

A set of voters to make a decision

V = { v1, v2, v3 … }

Voter delegation choices define a binary relationship over V

D = { (v, v’) | v,v’ ∈ V }

The transitive closure of D is defined as D+. It encodes transitive delegation information, we will use it shortly. Now, what we want is to produce an assignment of voters to questions. Assignment is a binary relationship over V and Q

A = { (v, q) | v ∈ V, q ∈ Q }

However, assignment as is does not consider delegation. So we define a transitive assigment set T according to the following set comprehension

T = { (v, q) |  ∃ (v’, q) ∈ A ∧ ∃ (v, v’) ∈ D+ ∧ v, v’ ∈ V, q  Q }

T is the meat of liquid filtering. It encodes the fact that although voters may not answer a question directly, they can answer it by virtue of having one of their delegates answer it for them. In this way T is the liquid filtering equivalent of a liquid democracy algorithm that walks the nodes to determine a user’s vote when that user does not vote directly.

We can finally state the aim of liquid filtering in terms of our definitions. Recall:

minimize the number of questions that each voter has to answer while ensuring that every voter votes on each question

which we can decompose into

minimize the number of questions that each voter has to answer

minimize |A|

and

while ensuring that every voter votes on each question

∃ (v, q) ∈ T  ∀ q  Q, v ∈ V

In short

minimize |A| subject to ∃ (v, q) ∈ T  ∀ q  Q, v ∈ V

 How does this address the initial problem? The answer is that by virtue of delegation (T), we have:

|A| ≤ |V| x |Q|

The number of questions necessary to make a decision is less than that if all voters had to decide one every single question (hence this slide). With no delegation, the above equation reduces to equality. The degree to which the reduction of questions occurs is hard to foresee. It depends on how many delegation choices are made, and how those choices are made. Different delegation graphs can lead to different results. Then there’s the matter of implementation.

Where’s the code?

What remains is to write an algorithm that obtains A from the inputs V, Q and D. This algorithm should be optimal in that it minimizes |A|, but other optimality constraints can be added. One is delegation chain length[1]. Another is a threshold such that even if the sum total of voters is minimzed, one does not want to overload specific voters with too many questions. There are many possibilites.

Two other considerations to note.

First, in the above we have assumed that all voters must have a choice for all questions. If we relax this constraint, and use statistics to infer probable choices, we are talking about sampling[2], as in a poll. But even if we are doing sampling, delegation information can still be used to improve the quality of the results, or equivalently reduce the number of questions necessary for a given quality.

Second, it could be possible to write an algorithm that adaptively calculates assignments of voters to questions using results as they become available. This would probably use statistical inference to determine which questions can lead to a final result more quickly,  something along the lines of bayesian experimental design comes to mind.


[1] We could also define a distance matrix over V as specified by D. This would encode the distance between voters in terms of the delegation jumps. The distance matrix is a useful if we are interested in limting delegation chains as described earlier

[2] See appgree