Recently I had a short exchange on twitter on the subject of feminism. Reflecting on the nature of the disagreement, I realized that the structure of the arguments conformed to a pattern I had seen many times before, but never identified. It is a pattern that arises frequently in ideological disputes, I will mnemonically call it the “Straw-Scotsman” pattern.
Suppose Alice and Bob are debating about ideology X. Alice is a supporter of X, whereas Bob is a detractor.
Bob proceeds to criticize X:
Bob: I find ideology X unsatisfactory because of its properties a, b, c.
Alice retorts that Bob is mischaracterizing X:
Alice: Ideology X does not in fact have the properties a,b,c that you are wrongly assigning to it. You should inform yourself about what X really is before criticizing it.
Bob finds this to be a disingenuous answer:
Bob: You’re just dodging my criticisms by redefining X in a way that suits your argument. It seems to me that whatever criticism one could make of X you would simply reply that the real X is not like that.
In the language of fallacies, the pattern can be succintly described with
From Alice’s point of view, Bob is committing the straw man fallacy by attacking a position that does not in fact correspond to X.
From Bob’s point of view, Alice is committing the no true scotsman fallacy, by responding to any criticism of X by saying that the real X is not at all like that.
I offer no resolution here. From both points of view the opponent is engaging in fallacies, the argument is a stalemate and leads nowhere. The pattern typically also takes the following form when discussing the merits of ideologies in terms of historical outcomes.
Alice criticizes X using historical examples:
Alice: Ideology X is flawed, one only needs to look at what happened in the following examples a,b,c where it was applied and led to disastrous results.
Bob: I disagree, examples a,b,c only show that the implementation of X was flawed. X was applied incorrectly or not at all, and it is this that led to bad results. However, if one applies X correctly, the results would be satisfactory.
A response which Alice finds unsatisfactory:
Alice: You could always dodge any critcism of a real world case of X by insisting that the implementation was wrong, rather than X is itself faulty.
In this manifestation the Straw-Scotsman pattern is best summed up as
When criticizing opposing ideologies people refer to their real world implementations, whereas when defending their own, they insist on its idealized form.
I realize now that I have seen this pattern occur many times when people debate, for example, communism and libertarianism.
In this post we will show some practical examples of how liquid democracy can be understood in terms of, and make use of results from spectral graph theory. For more background please see [Vigna2009]. Wikipedia says:
In mathematics, spectral graph theory is the study of properties of a graph in relationship to the characteristic polynomial, eigenvalues, and eigenvectors of matrices associated to the graph, such as its adjacency matrix or Laplacian matrix.
What does this have to do with liquid democracy? To answer this, let’s remember what defines liquid democracy is: system of transitive proxy voting. Proxy in that I can delegate my vote to some entity. Transitive because that entity can itself delegate the vote, and so on. Imagine a simple case with three voters, Alice, Bob, and Charlie. Alice delegates to Bob, and Bob delegates to Charlie. It is very natural to represent this as a graph, this is what we call the delegation graph
Assuming each voter starts with one vote, this would give us the following weights for each voter:
Alice = 1, Bob = 2, Charlie = 3
Because Alice and Bob have delegated their votes, Charlie will end up casting three votes, one for himself, one for Bob and one for Alice. What determines these weights is the structure of the graph; who is voting for who is encoded in the connections between vertices. In graph theory, the object that encodes this information is the adjacency matrix. Here’s the adjacency matrix for our example:
Where each row shows who each voter delegated to. Alice (A) delegated to Bob (B), hence the 1 in the second position of the first row. Similarly, Bob (B) delegated to Charlie, (C) as can be seen in the second row. Because Charlie did not delegate, the third row is all zeroes.
We can express the liquid tally above with these equations (1’s represent voter’s initial weights)
0*A + 0*B + 0*C + 1 = A
1*A + 0*B + 0*C + 1 = B
0*A + 1*B + 0*C + 1 = C
Note how the 0’s and 1’s above correspond to the columns of the adjacency matrix. The above can be represented in matrix form:
(A B C) * AdjacencyMatrix = (A B C)
This is an eigenvalue equation, whose eigenvector (the (A B C) row vector) corresponds to the result of the liquid tally. Note how the equation is recursive, which fits the recursive nature of transitive delegation. Vote weights are calculated in terms of vote weights themselves, the same way each delegate transmits votes that result from previous delegations.
When the adjacency matrix is used to evaluate the importance or influence of nodes in a graph in this way we are speaking of eigenvector centrality. Our example shows that calculating centrality is basically equivalent to tallying in liquid democracy. This is what makes the connection between spectral theory and liquid democracy.
Eigenvector centrality, Katz and Pagerank
Yes, that’s PageRank as in google, in case you thought this whole talk of centrality was a bit abstract, it’s what made google what it is today. Eigenvector centrality, Katz centrality, and PageRank are related methods to measure the importance of a node in a network. We won’t go into the differences between each measure, besides noting that both Katz and PageRank include an attenuation factor that decreases contributions from distant nodes, whereas eigenvector centrality does not.
In order to run some examples we will use the networkX library, which includes several functions for calculating centrality as well as many other useful features. If you want to play along with this code you will need to install the library as well as its dependencies, including matplotlib and numpy. If you’re on windows I suggest downloading the comprehensive WinPython package which includes everything you need here.
Let’s first create the graph corresponding to our example with Alice, Bob and Charlie. Here’s the code that does that
Both results match the tally we showed before. A couple of minor points above. First, the PageRank result was rescaled to make it match Katz. Second, the adjacency matrix for Katz was reversed as the networkx 1.8.1 Katz implementation is using a right eigenvector (this has been changed to left eigenvector in master).
More importantly, the alpha parameter is a damping factor. In the language of liquid democracy it modulates just how transitive delegation is by reducing contributions the further away the originate. For example, let’s change the above to alpha = 0.5:
Now Charlie receives 25% of Alice’s vote and 50% of Bob’s vote. So alpha quantifies the fraction of the vote that is effectively delegated. We can interpret then that a liquid democracy tally is a special case of Katz centrality and PageRank. In fact, liquid democracy is the limiting case of Katz and PageRank when alpha = 1.0, ie no damping (which is why you get viscous democracy in [Boldi2011]).
What about cycles?
One of the first things you have to deal with if you’ve implemented a liquid tallying algorithm is the possibility of cycles in the delegation graph, otherwise the procedure will blow up. Having detected a cycle at tally time the standard treatment is to consider votes that enter it as lost. In order to prevent that undesirable situation you can do cycle detection at vote time to warn the user that his/her vote may produce such a cycle.
What happens if we add a cycle to our example? Let’s try it
The reason this happens has to do with the details of the algorithm that calculates eigenvectors; in particular the relationship between its convergence and the attenuation factor alpha. The short story is this: using an attenuation factor of 1.0 on a graph with cycles may cause problems.
Just as liquid tally algorithms have to deal with cycles, so do we in order to make centrality work correctly. Fortunately there are fast algorithms to detect cycles in graphs. NetworkX offers an implementaton of an improved version of Tarjan’s strongly connected components algorithm, we will use it to define a function that removes cycles in a graph
print("remove %s -> %s"%(source,target))
# quick and dirty side-effecting use of reduce, see proper 2-batch iteration: http://stackoverflow.com/questions/5764782/iterate-through-pairs-of-items-in-python-list
Using this function we can obtain liquid tallies for any delegation graph correctly, using either Katz or PageRank. See the bottom of this post for the full python script demonstrating this.
Liquid democracy and degree (or branching factor)
Before we said that liquid democracy is the limiting case of Katz centrality and PageRank when alpha = 1.0. In the last section we saw another requirement besides that of alpha = 1.0: that the delegation graph must be acyclic, in other words a DAG. There is one more property that we can consider, degree.
A node’s degree is the number of (in our case, outward) connections with other nodes. In terms of delegation, it is the number of delegates that a voter chooses. Standard liquid democracy uses degree = 1, but such a requirement could in theory be relaxed. How does this fit in with Katz and PageRank? Lets construct a graph where voters may choose one or two delegates.
We see how Katz centrality does not yield a correct tally as it is not dividing outgoing weights for voters who split their delegation among two delegates, instead we get inflated weights. But the PageRank result does work, Bob’s two votes are split correctly, and the delegation proceeds normally from then on.
Liquid democracy is a special case of Katz centrality given
a damping factor alpha = 1.0
a directed acyclic graph of degree d = 1
Liquid democracy is a special case of PageRank given
a damping factor alpha = 1.0
a directed acyclic graph of degree d >= 1
That’s it for our quick tour of the relationship between liquid democracy and spectral theory. We have also seen how liquid democracy could be extended to include damping (as in [Boldi2011]), or to allow “multi delegation”.
[Page1998] The PageRank Citation Ranking: Bringing Order to the Web http://ilpubs.stanford.edu:8090/422/1/1999-66.pdf
[Boldi2011] Viscous Democracy for Social Networks http://chato.cl/papers/boldi_bonchi_castillo_vigna_2011_viscous_democracy_social_networks.pdf
 For simplicity, I have ignored the initial weights associated with each voter in the matrix equation. These initial weights are what makes liquid tallying equivalent to undamped Katz centrality rather than eigenvector centrality.
 For details as to alpha and PageRank See http://vigna.di.unimi.it/ftp/papers/PageRankFunctional.pdf section 5 Limit behaviour.
In the case of the networkX implementation of Katz centrality an alpha of 1.0 is guaranteed to converge as all eigenvalues of an acyclic graph are 0 (see http://www.emis.de/journals/JIS/VOL7/Sloane/sloane15.pdf and http://networkx.github.io/documentation/latest/reference/generated/networkx.algorithms.centrality.katz_centrality.html#networkx.algorithms.centrality.katz_centrality)
Python Script: Random liquid Tallying with Katz/PageRank