Por qué el Voto Único Transferible (VUT) no es la panacea

Existe una corriente de gente que tenía una esperanza bastante alta en que el sistema de Voto Único Transferible (VUT) fuese el sistema por antonomasia a recomendar para cualquier votación entre un número alto de opciones (mayor que dos o tres). Un sistema que sirva desde para elegir un logo o lema hasta para realizar unas primarias.

Miniexplicación de cómo funciona VUT

VUT es un sistema de recuento de votos preferenciales. En el voto preferencial, el votante ante una lista de posibles opciones elige otra lista ordenada de las opciones que prefiere. Vale, pero luego ¿cómo hacemos el recuento, quienes son los ganadores? Pues hay muchos sistema para ello, y VUT es uno de ellos.

“Bajo el VUT, el voto de un elector se le asigna inicialmente a su candidato favorito, y si el candidato hubiera sido ya elegido o eliminado, todos los votos sobrantes se transfieren según las preferencias seleccionadas por cada votante.” (Wikipedia)

Funciona por rondas. En cada ronda, se establece una cuota, de manera que si alguna de las opciones candidatas obtiene ese número de votos automáticamente sale elegida. También es posible que en una ronda ninguna opción consiga llegar a la cuota; en ese caso, lo que se hace es eliminar la opción candidata con menos votos, y transferir sus votos.

Por último, he de decir que VUT no es un sistema concreto: es una clase de sistemas de recuento con estas características que he mencionado. Luego cambian los detalles: cómo se calculan las cuotas en cada ronda, cuantos votos se transfieren cuando una opción candidata gana o cuando se elimina una opción, etc.Como digo, esto es sólo una miniexplicación.

Listado de problemas

En Agoravoting soportamos VUT porque nos parece un sistema interesante y con aplicaciones, y sobretodo, porque nos lo solicitaron nuestros usuarios. No obstante, nuestra experiencia nos ha demostrado que no es la panacea. Diría aun más: no parecer existir un sistema de voto para muchas opciones que sea ideal y extensible a todas las situaciones, y en todo caso VUT desde luego no lo es.

Evidencia de ello fue la segunda ronda de las primarias para las elecciones al Parlamento Europeo de la Confederación Pirata. Los problemas que surgieron son los siguientes:

VUT sólo sirve para escoger ganadores

El VUT es un sistema pensado para que dado una lista de opciones y un conjunto de votos devuelva la lista de ganadores. Para escoger escaños en un parlamento, por ejemplo. Pero no ordena las opciones ganadoras.

Es cierto que normalmente es posible establecer un criterio sencillo para ordenar las opciones ganadoras, pero hemos de recalcar que eso ya es algo que no forma parte de VUT. El criterio más sencillo es que dado que en cada ronda normalmente sale sólo un ganador y las rondas sí que se hacen en un orden (ronda 1, ronda 2..), el orden de los ganadores se puede establecer según la ronda en que salieron.

Problemas de primera ronda

Como decía, VUT, El VUT funciona por rondas, y cualquier candidato que supere en una ronda cierta cuota es elegido. El primer problema con el criterio de ordenación sencillo que hemos explicado anteriormente es que en una ronda puede salir elegida más de una opción, simplemente porque varias opciones superen la cuota mínima en esa ronda.

No obstante, si habéis visto el recuento, seguramente diréis “¡no pasa nada! lo ordenamos según los votos que tenga cada ganador en esa ronda”.

Y es verdad, ese es un sistema casi infalible, porque como se transfieren votos entre opciones al pasar de ronda, cada opción candidata tiene un número decimal de votos y por tanto es muy complicado que haya ningún empate… menos en la primera ronda.

Y precisamente esa fue el primer gran problema que afrontamos en estas primarias piratas. Resulta que teníamos unos 60 candidatos y sólo 118 votos. El resultado que daba es que según la cuota de droop que es más o menos “(nº de votos / (nº candidatos + 1)) + 1” es que cualquier opción con dos votos en la primera ronda ganaba. Cataclismo: eso nos daba 21 ganadores en primera ronda, con un número de votos por opción candidata redondos porque aun no había habido aun transferencia de votos, y muchas opciones empatando.

Es por supuesto un caso poco usual. En una votación institucional con cientos de miles de votantes o millones de votantes no va a pasar esto. Pero son cosas que pueden pasar. Lo dicho: VUT no está pensado para ordenar ganadores y se nota.

Por supuesto, hay muchos posibles algoritmos aplicables para solucionar los empates. En el caso de las primarias piratas, optamos por aplicar una suerte de rondas de desempate entre los ganadores. La idea es sencilla: si hay empate en número de votos en primera opción, desempatar mirando el número de votos como segunda opción, o como tercera, etc. Lo hicimos así porque sigue el espíritu del VUT, pero por supuesto, podrían existir otras formas.

Problemas cocinando resultados

Incluso teniendo ya una lista de ganadores ordenada y superado los anteriores obstáculos, siguieron apareciendo problemas debido a la idiosincrasia de VUT. No fueron desde luego unas votaciones precisamente triviales, como podéis observar, aunque aprendimos mucho sobre VUT.

El siguiente problema fue la famosa “cocina”. La ley obliga a ordenar por paridad, de manera que en las listas electorales y mirando los candidatos según su orden, de cada grupo de cinco haya 3 de un sexo y 2 de otro.

Muy bien diréis, pues se re-ordena por cumplir con este imperativo legal y ya está. Pues no es tan sencillo, porque resulta que no existía tal paridad en la lista de ganadores, y por tanto para cumplir con la ley, hacía falta sacar mujeres de entre de los candidatos que no habían ganado.

¿el problema? que VUT no te da más que una lista de opciones ganadoras. Repito: que no, que no sirve para ordenar y menos para cocinar resultados. No te dice siquiera cual sería la opción que más cerca se ha quedado ¿la que tiene más votos en la última ronda o en la primera o en la tercera?

Algún avispado dirá: pues vuelve a ejecutar VUT con un ganador más. Eso puede no funcionar, porque no sólo puede ocurrirte que no sea mujer (y entonces qué, probar con otro ganador más y así hasta que salga el número de mujeres que necesites? pff) sino que además VUT no es estable. Si aumentas el número de opciones ganadoras, puede y es es de hecho bastante probable, que alguna de las opciones que antes se dieron por ganadoras ya no aparezca como tal. Paradojas de la vida.

Por supuesto, para casos como este puedes aplicar el criterio que consideres más oportuno, como mirar los votos como primera opción/en primera ronda (es lo mismo) y escoger al ganador de ahí. Si mal no recuerdo, eso hicimos en las primarias piratas.

.. y aun tiene más problemas

Me diréis: la mayoría de esos problemas afectan sólo a las primarias, y es cierto. Pero en realidad, VUT tiene muchas más irregularidades. Con esto no estoy diciendo que otros sistemas como Approval voting o los de clase Condorcet sean la panacea porque tampoco lo son.

En VUT puede haber candidatos que son opción más preferida que el último ganador y sin embargo no salir elegidos. Cuando sólo hay una opción ganadora es fácil de verlo.

También se critica y con razón la complejidad que requiere entender VUT, por no hablar de replicar el recuento. Que conste que lo que he explicado arriba de VUT es lo básico: existen muchos más detalles según qué algoritmo específico de VUT se utilice. También es difícil interpretar los resultados y hacer el recuento en otros algoritmos como los de método Condorcet, pero por ejemplo en Approval voting es todo mucho más sencillo.

Además si quieres usar VUT en colegios electorales, que sepas que no puedes hacer un recuento por mesa: debido a que el algoritmo no es estable como hemos comentado antes, no puedes simplemente sumar resultados. Tienes que contar todas las papeletas de forma centralizada en un solo sitio juntas. Un caos vamos.

Y como todo sistema de voto, existe el voto táctico, es decir no votar por preferencias sino según crees que pueda maximizar un resultado favorable a tus preferencias. De nuevo, al no ser VUT estable, es posible que al seleccionar una opción en tu papeleta estés quitándole posibilidades de salir ganadora. Todos estos problemas de los que estoy hablando están explicados (en inglés) en un caso práctico en este pequeño artículo.

Conclusiones

Por todo esto, creo que Podemos hicieron muy bien en optar por usar approval voting pese a que les ofrecimos también VUT como opción (chicos listos ;-), y desde luego para la Confederación Pirata recomendaré no volver a usar VUT para primarias, visto lo visto.

Liquid democracy and spectral theory

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: a 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

graph_decycled
Alice chooses Bob, Bob chooses Charlie

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:

M

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[1] 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 all 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

# construct graph
G = nx.DiGraph()
G.add_edges_from([("Alice", "Bob"), ("Bob", "Charlie")])
# draw it
nx.draw_spring(G)
plt.savefig("graph.png")

This generated the image shown earlier. Now to calculate the tally, we will run both Katz and PageRank.

# katz
centrality = nx.katz_centrality(G.reverse(), alpha=1.0, beta=1.0, normalized=False)
print("katz %s" % centrality)

# pagerank
centrality = nx.pagerank(G, alpha=1.0)
print("pagerank %s" % dict(zip(centrality.keys(), denormalize(centrality.values()))))

which gives us

katz {'Charlie': 3.0, 'Bob': 2.0, 'Alice': 1.0}
pagerank {'Charlie': 3.0, 'Bob': 2.0, 'Alice': 1.0}

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:

katz {'Charlie': 1.75, 'Bob': 1.5, 'Alice': 1.0}
pagerank {'Charlie': 1.75, 'Bob': 1.5, 'Alice': 1.0}

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

G = nx.DiGraph()
G.add_edges_from([("Alice", "Bob"), ("Bob", "Charlie"), ("Charlie", "Donna"), ("Donna", "Bob")])

graph

and we get

File "katz.py", line 70, in 
  centrality = nx.pagerank(G, alpha=1.0, max_iter=1000)
File "C:	oolsWinPython-64bit-2.7.6.4python-2.7.6.amd64libsite-packages
etworkxalgorithmslink_analysispagerank_alg.py", line 143, in pagerank
  'in %d iterations.'%(i-1))
networkx.exception.NetworkXError: pagerank: power iteration failed to converge in 1000 iterations.

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[2]. 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

def de_cycle(G):
    def r(source, target):
        print("remove %s -> %s" % (source, target))        
        G.remove_edge(source, target)
        return target

    cycles = list(nx.simple_cycles(G))
    if(len(cycles) > 0):
        for cycle in cycles:
            print ("cycle %s" % cycle)
            # 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            
            reduce(r, cycle)

    return G

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.

G = nx.DiGraph()
G.add_edges_from([("Alice", "Bob"), ("Bob", "Charlie")])
G.add_edges_from([("Bob", "Florence"), ("Charlie", "Donna"), ("Florence", "Edward")])

which gives

graph

resulting values

pagerank {'Charlie': 2.0, 'Alice': 1.0, 'Edward': 3.0, 'Donna': 3.0, 'Bob': 2.0, 'Florence': 2.0}
katz {'Charlie': 3.0, 'Bob': 2.0, 'Edward': 4.0, 'Florence': 3.0, 'Alice': 1.0, 'Donna': 4.0}

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.

In summary

  • 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”.


Notes/References

[Vigna2009] Sebastiano Vigna – Spectral Ranking  http://arxiv.org/abs/0912.0238

[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

[1] 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.

[2] 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

import networkx as nx 
import matplotlib.pyplot as plt
from random import randrange

def simple_graph():
	G = nx.DiGraph()
	G.add_edges_from([("Alice", "Bob"), ("Bob", "Charlie")])
	# with cycle
	G.add_edges_from([("Alice", "Bob"), ("Bob", "Charlie"), ("Charlie", "Donna"), ("Donna", "Bob")])

	return G

def random_graph(n):
    G = nx.DiGraph()
    G.add_nodes_from(range(0,n - 1))
    for node in G.nodes():
        target = randrange(n - 2)
        if(target == node):
            target = n - 1
        G.add_edge(node, target)

    return G  

# denormalizes page rank scores 
def denormalize(array):
    m = min(array)
    factor = 1 / m
    return map(lambda x: round(x*factor, 5), array)

def de_cycle(G):
    def r(source, target):
        print("remove %s -> %s" % (source, target))        
        G.remove_edge(source, target)
        return target

    cycles = list(nx.simple_cycles(G))
    if(len(cycles) > 0):
        for cycle in cycles:
            print ("cycle %s" % cycle)
            # proper 2-batch iteration: http://stackoverflow.com/questions/5764782/iterate-through-pairs-of-items-in-python-list            
            reduce(r, cycle)

    return G

import sys
if(len(sys.argv) != 2):
	nodes = 10
else:
	nodes = int(sys.argv[1])

# G = simple_graph()
G = random_graph(nodes)
nx.draw_spring(G)
plt.savefig("graph.png")
de_cycle(G)

centrality = nx.pagerank(G, alpha=1.0, max_iter=1000)
print("pagerank %s" % dict(zip(centrality.keys(), denormalize(centrality.values()))))

cycles = list(nx.simple_cycles(G))
print("cycles %s" % cycles)
centrality = nx.katz_centrality(G.reverse(), alpha=1.0, beta=1.0, normalized=False)
print("katz %s" % centrality)

# draw graph without cycles
plt.clf()
nx.draw_spring(G)
plt.savefig("graph_decycled.png")