Category Archives: Uncategorized

Reddit-style filtering for e-democracy

When voting, people select among several options that have been predefined prior to the election. In more open scenarios of citizen participation, people are asked not only to vote for predefined options, but to contribute their own ideas before the final vote. This introduces another activity to the democratic process, we can call it filtering.

The aim of filtering is to select, out of a very large number of ideas, the very few best ones either to directly implement them or to put them to a formal vote. Filtering has to address the problem that voting cannot: How do we select out of potentially hundreds of ideas without having each voter evaluate them all? The solution provided by filtering is a common theme in many proposals to augment democracy: division of cognitive labour.

A single voter cannot rank hundreds of ideas, but the cognitive load of selecting the best ones can be spread across the many citizens that are contributing them. Filtering can scale because as the number of ideas grows with the number of people suggesting them, so too does the available cognitive effort available to evaluate them.

However, a key distinction must be noted between voting and filtering. The process of distributing cognitive labour allows filtering many ideas, but once we accept that not all people are evaluating everything, the information available is necessarily incomplete. In other words, the process of ranking ideas has an element of uncertainty, it is statistical.

Reddit-style filtering

When looking for tools to implement internet mediated filtering, sooner or later one runs into systems like reddit, slashdot, digg and the like. At an abstract level, we can pick out the following features which are relevant to the problem of filtering:

  1. Many users can submit a large amount of items as well as evaluate them
  2. Users evaluate items with a binary signal, eg voting up/down
  3. A ranking method exists that sorts items for some definition of better => worse.

At this level of description, these three properties fit filtering well. We have ideas that we wish to rank, and we cope with the large volume by having the users evaluate them, possibly using binary signal such as approval (or not approval). The meat of the matter lines in the third property, specifically in the phrase “for some definition of better => worse”.

Quality of ideas

Above we have used the abstract term “items”. In reddit, items can be stories or comments. The distinction is important because reddit uses different ranking algorithms for each. The key feature of filtering that departs from the reddit model is that reddit and similar sites are news aggregation tools. This is why stories in reddit include a novelty component in their ranking. Ceteris paribus, new items are better than old items.

Filtering on the other hand is not about news, but about ideas/proposals. Although novelty may still be a factor, it is not a central one. Idea quality must be mostly about voters evaluation through a binary signal, and not very much about its submission date. Filtering ranking is more like reddit’s ranking of comments than it is of stories.

The problem is simple then: we must rank ideas according to users’ binary evaluation in a way that deals with incomplete information. That is, we will not have a +/- judgement for every idea from every user, only subsets of this. Fortunately the problem as posed is directly an instance of binomial proportion estimation, an urn model.

We have, for every idea, an unknown quantity which represents the fraction of all users who would evaluate it positively. This quantity can be statistically inferred using the number voters that have in fact evaluated the idea and approved it. To do this we use the betabinomial model, see here for an introduction. Briefly, we choose a uniform uninformative prior distribution with parameters alpha = beta = 1. Because the beta is conjugate to the binomial, posterior distribution is also a beta given by

The mean of a beta distrubution is given by

If we plug this into the posterior we see that the mean is simply approvals / total, which makes sense. So a first approximation would be to rank ideas by the mean of the (posterior) probability distribution, which is just the fraction of approvals out of total evaluations.

What about uncertainty?

The problem with the above is that it ignores how confident we are about the estimation of an idea’s quality. For example, an idea evaluated 1000 times with 500 approvals would rank equally to an idea evaluated twice and approved once. In technical terms, using the mean throws away information about the probability distribution. This is what the author of this post realized:

suppose item 1 has 2 positive ratings and 0 negative ratings. Suppose item 2 has 100 positive ratings and 1 negative rating. This algorithm puts item two (tons of positive ratings) below item one (very few positive ratings). WRONG.

The author then goes on to suggest a lower bound wilson confidence interval, this is how reddit currently ranks comments. Another option along these lines is to use a lower bound on our beta posterior using its cumulative distribution function (I wont go into more details here). In either case, the spirit of this measure is to rank ideas that we are confident are good higher than ideas which have not been evaluated enough.

What about equality/winner takes all/sunk ideas/information gain?

This is where filtering departs strongly from systems like reddit. Consider:

  • Ideas should have an equal opportunity of being selected.
  • Once ideas are ranked highly there is a snowball effect as they are more visible and can accumulate approvals.
  • New good ideas will be lost and sunk as they cannot compete with the volume of older ones that have accumulated approvals.
  • By penalizing uncertainty you concentrate evaluation away from where its most needed, information gain is minimized.

All these objections follow a common theme, the theme of balancing two competing objectives:

  • We want to rank good ideas highly
  • We want to allow for the discovery of good yet unproven ideas

Thompson Sampling and multi-armed bandits

The above dilemma is another form of the exploration-exploitation tradeoff that appears in reinforcement learning, an area of machine learning. There is one specific problem in machine learning whose structure is very similar to the problem of rating items and filtering: multi-armed bandits. In this post James Neufeld first makes the connection between rating comments on reddit and muti-armed bandits.

The comment scoring problem on reddit is slightly different from the basic setting described above. This is because we are not actually choosing a single comment to present to the user (pulling one arm) but, instead, producing a ranking of comments. There are some interesting research papers on modelling this problem precisely, for example [Radlinski, et al.,2008], but, it turns out to be a combinatorial optimization (hard). However, rather than going down this complex modelling path, one could simply rank all of the μ¯iμ¯i samples instead of taking just the max, this gives us a full ranking and, since the max is still at the top, is unlikely to adversely affect the convergence of the algorithm.

He then goes on to propose adapting Thompson sampling, a solution applied to multiarmed bandits in reinforcement learning, to the case of rating comments in reddit. The method of Thompson Sampling (or probability matching) is simple given what we’ve seen above regarding the beta posterior. Instead of using the beta posterior mean, or a lower bound on its cumulative distribution, we simply sample from it. The procedure is:

  1. For each idea, sample from its posterior beta probability distribution
  2.  Construct a ranking according to the sampled value

Here’s how Thompson sampling relates to the two objetives stated above

  • We want to rank good ideas highly

Sampling from a high quality posterior will tend to produce larger values.

  • We want to allow for the discovery of good yet unproven ideas

Because we are sampling there is a chance that unproven ideas will be ranked highly. Furthermore this possibility is greater for better ideas and for ideas with high uncertainty. There is more to be investigated here about the relationship between Thompson sampling and maximizing information gain (eg Kullback Leibler divergence).

Extensions

The base Thompson sampling model can be extended in several ways. For example:

  • Time: we can incorporate time factors by having decays on the beta distribution parameters.
  • Collaborative filtering: we can apply weight factors on beta parameters depending on affinity with the user.
  • Boosting newly submitted ideas: we can choose non uniform priors to ensure high exposure to new ideas.

Receta para el cálculo estadístico del voto fraudulento y de calidad del censo

Introducción

Este post va a explicar muy someramente una metodología para realizar un cálculo de probabilidad de voto fraudulento utilizando métodos estadísticos de inferencia bayesiana. Este es un documento informativo muy básico con un enfoque práctico, por lo que no entra a valorar cuales son los diferentes tipos de algoritmos aplicables (ni los parámetros de configuración de dichos algoritmos).

El cálculo estadístico que aquí se propone permite realizar una afirmación como:

La probabilidad de que más del 5% del censo sea fraudulento es menor o igual al 4%

Este procedimiento es aplicable a un censo, pero puede contextualizarse en una votación. Si por ejemplo tenemos una votación con una única candidatura ganadora, y la diferencia en votos entre la candidatura ganadora y la candidatura perdedora que más votos obtuvo es mayor al 5%, entonces podría realizarse la siguiente afirmación:

La probabilidad de que el voto fraudulento haya afectado al resultado es menor o igual al 4%

Nota: en una afirmación como la anterior se está asumiendo que cada votante sólo puede emitir 1 punto/voto y que el sistema de votación se comporta predeciblemente. Dicha afirmación habría que corregirla convenientemente en el caso de que se utilice un sistema de votación en el que dicha suposición no se de, como por ejemplo en el Borda tradicional (donde el votante tiene más de un punto para repartir) o en sistemas como por ejemplo VUT donde los resultados pueden variar con un sólo voto de forma bastante difícil de predicir a priori.

Contexto y ámbito de aplicación

El análisis estadístico como método de auditoría es utilizado en votaciones oficiales en todo el mundo, por ejemplo en Estados Unidos [6], país en el que se aplica en algunos estados ya de forma habitual. En USA se llegó a poner en cuestión la presidencia de Estados Unidos por fallos en el recuento de votos en un proceso electoral. Aprender de la experiencia de otros es muchas veces difícil, pero nunca está de más utilizarlo de forma ejemplarizante. La verificación de los resultados y en general aplicar técnicas de limitación de riesgos son prácticas altamente recomendables en procesos electorales donde se deciden materias importantes, ya sean en procesos de voto en papel o electrónico.

Este tipo de análisis en la terminología académica se suele conocer como “risk-limiting audit” o “auditoría de limitación de riesgo” y hay muchas publicaciones al respecto en la red. En este documento se explica un método para analizar un censo de votantes, sin embargo tradicionalmente el análisis en votaciones en papel se realiza sobretodo para verificar el recuento. Esto es debido a que a diferencia de lo que ocurre en el voto electrónico, los recuentos manuales son costosos en tiempo y recursos, y precisamente lo que un análisis estadístico permite es tener cierto grado de certeza sin llegar a hacer un costoso segundo recuento completo.

Limitaciones

La variable que más limita a la hora de poder tener certeza sobre la probabilidad de que el fraude haya afectado al resultado de una votación es el llamado margen de votos, es decir la diferencia entre cualesquiera dos candidaturas si al menos una de ellas es ganadora. Por tanto, en general cuantos más votos y menos candidaturas haya, más fácil es que la diferencia de votos entre candidaturas sea mayor, pero incluso en ese caso puede que haya sólo dos candidaturas y el margen de diferencia en votos sea ajustado.

El peor de los casos que sin embargo es típico en partidos políticos es la confección de listas electorales mediante primarias, porque hay muchas opciones, muchos puestos ganadores y por tanto una alta probabilidad no ya sólo de que la diferencia en votos de dos candidaturas con posibilidades de ganar sea bajo, sino incluso de que haya empates en votos.

Este tipo de análisis matemático estadístico presupone el peor de los casos, lo cual le permite ser a la par cautoloso y riguroso en los datos que arroja. En contrapartida, si un único voto (o un número de votos pequeño) puede alterar el resultado de una votación porque la diferencia en votos entre dos candidaturas es de muy pocos votos), si se quiere tener una probabilidad de que el voto fraudulento haya afectado al resultado baja, implica contactar con prácticamente todo el censo de votantes.

No obstante, incluso en el peor de los casos también hay que poner en valor otra cuestión, y es que incluso a pesar de que un único voto pueda afectar a uno de los puestos ganadores, un análisis estadístico permite limitar cuánto podrían bailar los resultados en el peor de los casos, y además también es de rigor apuntar que a priori es difícil adivinar cuales son las candidaturas que van a estar empatadas. Si por ejemplo de 200 candidaturas sólo hay un caso de dos candidaturas donde la diferencia de votos entre ellas es de un voto, habría que analizar cual es la probabilidad de que un atacante acierte a escoger una de esas 2 candidaturas para alterar el resultado. Ese análisis no se tiene en cuenta en el modelo simplificado que aquí se propone.

Por último, ha de remarcarse que este tipo de análisis estadístico es un método de seguridad enmarcado en el ámbito de la detección y obtención de información, pero no de la prevención ni de la actuación: permite averiguar información y poder sacar conclusiones acerca de la validez de un censo, pero no está pensado para mejorar la calidad del censo ni permite prevenir problemas en él.

Procedimiento

Es recomendable realizar el análisis del censo con la mayor antelación y previsión, una vez exista dicho censo. La razón es que toma tiempo, y que además el tiempo exacto que pueda tomar no se conoce completamente a priori, y concretamente depende de tres variables:

  1. el volumen de fraude que se vaya encontrando (desconocido a priori)
  2. el tamaño del censo (conocido a priori si es censo cerrado, e incluso si es censo abierto se puede tener una estimación)
  3. margen de error aceptable (desconocido a priori aunque se puede tener una estimación a priori)

Como hemos dicho anteriormente, con estas variables, y con la información que nos proporciona el análisis, al final el dato que se obtiene es una afirmación tan sencilla como la que sigue:

La probabilidad de que más del 5% del censo sea fraudulento es menor o igual al 4%

En el peor de los casos, se termina haciendo un análisis de todo el censo, por lo que la estimación de la cantidad de tiempo/recursos necesarios puede dimensionarse teniendo ese caso como límite superior.

Si existe un censo previo, se puede realizar un análisis de ese censo incluso antes de comenzar la votación. De hecho, puede que ese análisis se haya realizado previamente si lo hacemos a menudo. En el caso de que el censo esté abierto pero exista un censo previo, es recomendable comenzar con ese trabajo hecho, y luego seguir haciendo comprobaciones censales durante la votación sobre los nuevos elementos del censo.

El cálculo estadístico se puede ir realizando en cualquier momento y en tiempo real a medida que se van conociendo más datos. Por poner un ejemplo, si la votación no ha empezado aun, no se sabrá con certeza cual es el margen de error aceptable, porque ese dato depende de cuan ajustados sean los resultados, pero sí se puede tener una estimación. De igual manera, se puede ir actualizando el tamaño de la muestra estadística y el número de casos donde se ha detectado fraude.

El procedimiento es el siguiente:

1. Establecer un porcentaje de fraude aceptable

Por ejemplo un 5%. Si vamos a hacer unas primarias, si estimamos que vamos a tener alrededor de 2000 votos y creemos que es razonable pensar que los resultados no van a verse afectados si menos de 100 votos son fraudulentos, entonces el margen de error aceptable es de 100/2000 = 0.05 (es decir, un 5%). Por supuesto, si ya conocemos los resultados, ese dato ya no tendrá porqué ser una estimación, y podrá calcularse en base a los resultados reales.

2. Establecer el límite de la probabilidad que consideramos aceptable de que ese porcentaje anterior sea fraudulento

Por ejemplo, podemos establecer que “la probabilidad de que más del 5% del censo sea fraudulento no debe superar el 5%”.

3. Escoger una muestra del censo que se pretende analizar

Es muy importante hacerse de forma aleatoria, ya que el modelo estadístico asume un muestreo aleatorio. Se puede tener numerado el censo y generar números aleatorios con un generador de números aleatorios, como por ejemplo un dado o la web https://www.random.org/

NOTAS:

  • Cuanto menor sea el tamaño del censo más representativo será el muestreo para una muestra de igual tamaño. Por tanto usar como censo al conjunto de votantes, y no el censo de electores que siempre será mayor.
  • Los seres humanos somos MUY malas fuentes de aleatoriedad y en ningún caso se recomienda generar esos números “de cabeza”.
  • Si se está haciendo el análisis de forma iterativa a medida que va cambiando el censo, garantizar que la suma de los muestreos equivale a un muestreo aleatorio es más complicado de lo que parece y por ello en principio no vamos a analizar ese caso en este documento.

4. Verificar el fraude en la muestra elegida

Para verificar el fraude debe establecese previamente una forma muy concreta de actuación y valoración. En concreto, si por ejemplo se tiene el teléfono de la persona, se propone llamar a esta persona, informarle que se está verificando el censo y que nos diga sus datos censales y si ha participado en la votación. Es muy importante que sea la persona la que aporte los datos censales y no el verificador, porque de otra forma se adulteraría el resultado. Al final de la llamada, que deben ser cortas y al grano para ser eficientes y para eso lo recomendable es ir con un “script” de antemano, el verificador debe de clasificar a la persona como fraude o no-fraude, a efectos de luego realizar el cómputo de cuantos elementos fraudulentos hay. Si se quiere, podría afinarse más asignando una probabilidad de fraude con valores intermedios entre 0 y 1.

5. Calcular la probabilidad de fraude con los datos anteriormente obtenidos

Para eso se propone utilizar el formulario de [0]. Una vez introducidos los datos, la calculadora ofrece una frase de este estilo:

The probability that more than 3.00% of the votes/census are fraudulent is less or equal than 5.15%, according to a bayesian inference done using a sample size of 300 and having 4 invalid elements.

Si el censo ya está cerrado (porque era cerrado o porque la votación ha terminado y por tanto el censo de votantes está cerrado) y la probabilidad de fraude es menor al límite previamente marcado en el punto 2, entonces el análisis ha terminado exitosamente. Si esto ocurre cuando el censo no está cerrado, cuando varíe sustancialmente el censo (por ejemplo, si varía más de X votos o Y% porcentaje, o bien cada X días) se puede realizar de nuevo el procedimiento, a modo iterativo.

Si el porcentaje de fraude es superior al admisible según el punto 2, entonces debemos de aumentar el tamaño del muestreo con el objetivo de hacerlo más representativo y así reducir la probabilidad de que sea simplemente un error de muestreo. Debido a que el cálculo de la probabilidad de fraude se hace en tiempo real, se puede iterar todo este proceso de forma muy ágil, de manera que por ejemplo cada vez que se hace un muestreo de 50 personas elegidas aleatoriamente del censo se recalcula la probabilidad de fraude y se decide si seguir o no analizando.

Referencias

El formulario para calcular la probabilidad de fraude:

[0] http://jsfiddle.net/op1r411L/37/

Queda fuera del ámbito, eminentemente práctico de este documento, explicar la lógica matemática que sustenta la metodología aplicada. No obstante, sí que queremos referenciar material donde se explica en más detalle:

[1] https://blog.agoravoting.org/index.php/2014/06/04/voter-fraud-and-bayesian-inference/

[2] https://blog.agoravoting.org/index.php/2014/06/04/voter-fraud-and-bayesian-inference-part-2/

[3] http://www.cs.cmu.edu/~10701/lecture/technote2_betabinomial.pdf

[4] http://projecteuclid.org/download/pdf_1/euclid.ss/1009213286

Nuestra propuesta es utilizar el método bayesiano beta-binomial porque lo consideramos quizás el más adecuado, pero existen otros métodos estadísticos que en realidad al final dan resultados bastante parecidos. Algunos de ellos pueden verse aquí:

[5] http://epitools.ausvet.com.au/content.php?page=CIProportion

Existe una página hecha por expertos en la materia y bastante instructiva que contiene una numerosa cantidad de utilidades e información sobre cómo se debe realizar auditorías de limitación de riesgo, que como hemos explicado no es exactamente lo mismo que lo que estamos intentando hacer aquí pero la metodología es parecida:

[6] http://arstechnica.com/tech-policy/2012/07/saving-american-elections-with-10-sided-dice-one-stats-profs-quest/2/

[7] http://www.stat.berkeley.edu/~stark/Vote/auditTools.htm

Colaboración entre Agora Voting y la Universidad de Sevilla

Desde Agora Voting, y gracias al apoyo de David Benavides, profesor titular de la Universidad de Sevilla en la ETSIIl, el Director Técnico de Agora Voting Eduardo Robles ha impartido dos charlas a varios grupos de alumnos de máster y doctorado sobre el funcionamiento interno de Agora Voting, con la intención de que algunos de estos alumnos se hagan partícipes en un proyecto de software libre real, y puedan aportar su granito de arena.

En estas charlas, Eduardo Robles, fundador de Wadobo y Agora Voting, ha explicado en que consisten los subproyectos de Agora Voting y como se enlazan unos con otros, hasta llegar al funcionamiento completo, para así facilitar a los alumnos una primera toma de contacto con nuestro software.

Por otra parte, decir que este año, junto con Wadobo, Agora Voting patrocinará la 10ª edición del Concurso de Software Libre, el cual, cuando algunos de los fundadores de Agora Voting eran estudiantes, nos ha ayudado para llegar donde estamos.

IMG_20150924_124516

The pairwise-bradleyterry model for pairwise voting

In a previous post we discussed pairwise voting and the pairwise-beta model as a way to obtain a global ranking over candidates using bayesian inference with the beta distribution. In that post we remarked in the final paragraph that the pairwise-beta model is not perfect:

In particular, it does not exploit information about the strength of the opposing item in a pairwise comparison.

In this post we will look at a better model which addresses this particular problem, albeit at a computational cost. To begin we present a pathological case which exhibits the problem when using the pairwise-beta.

Consider the following set of pairwise ballots, where A, B, C, D, E and F are options, and A > B indicates that A is preferred to B. There are 5 ballots:

A > B

B > C

C > D

D > E

F > E

Applying the pairwise-beta algorithm method to this set of ballots yields the following output (options A-F are referred to as numbers 0-5):

[(0, {'wins': 1, 'losses': 0, u'score': 0.6666666666666666}), 
(5, {'wins': 1, 'losses': 0, u'score': 0.6666666666666666}), 
(1, {'wins': 1, 'losses': 1, u'score': 0.5}), 
(2, {'wins': 1, 'losses': 1, u'score': 0.5}), 
(3, {'wins': 1, 'losses': 1, u'score': 0.5}), 
(4, {'wins': 0, 'losses': 2, u'score': 0.25})]

which is equivalent to the following ranking:

  1. A, F
  2. B, C, D
  3. E

A and F share the first position. B, C and D share the second position. E is last.

Hopefully the problem in this ranking is apparent: the strength of the opposing option in a pairwise comparison is not affecting the global ranking. This is why option F, which only beats the last option, is ranked at the same position as A, which “transitively” beats every other option. Similarly, options B, C and D are ranked at the same level, even though presumably option B should be stronger as it beats option C which beats option D.

In other words, beating a strong option should indicate more strength than beating a weak option. Similarly, being beaten by a strong option should indicate less weakness than being beaten by a weak option.

We can resort to the Bradley-Terry [1] model to address these shortcomings. The Bradley-Terry is a probabilistic model that can be used to predict the outcome of pairwise comparisons, as well as to obtain a global ranking from them. It has the following form:

and in logit form[2]:

logit2

The parameters (p’s and lambdas) can be fit using maximum likelihood estimation. One can consider these to represent the relative strength of options and therefore give a global ranking, although strictly speaking their interpretation is rooted in probabilities of outcomes of comparisons.

In order to apply this model we can use the BradleyTerry2 R package by Turner and Firth[2], which fits the model using tabular input data. Armed with this package all we need is some extra plumbing in our Agora Voting tallying component and we’re ready to go. Let’s run it against the same ballots we did above, we get:

[(0, {'score': 73.69821}),
 (1, {'score': 49.13214}),
 (2, {'score': 24.56607}),
 (3, {'score': 1.186101e-06}),
 (5, {'score': 0.0}),
 (4, {'score': -24.56607})]

which is equivalent to the following ranking:

  1. A
  2. B
  3. C
  4. D
  5. F
  6. E

Notice how this ranking does away with all the problems we mentioned with the pairwise-beta result. In particular, note how option F, which above was ranked joint first, is in this case ranked fifth. This is because it beat option E, which is last, and therefore not much strength can be inferred from that comparison.

Before concluding that the pairwise-beta model is terrible, remember that the results we got here correspond to a handpicked pathological set of ballots. In general it seems reasonable to expect results from both models to converge as more data accumulates and the strength of opponents is evened out. This hypothesis seems to match that stated in work by Salganik[3], where the pairwise-beta and a more robust model are compared saying:

In the cases considered in the paper, the two estimates of the score were very similar; there was a correlation of about 0.95 in both cases.

In summary, in this and the previous post we have described two models that can be used for pairwise elections, where candidates are asked to compare options in pairs. We have seen how one of the models works well and is easy to calculate, but can potentially give unrealistic rankings when data is sparse. We then considered a second more robust model which addresses this problem, but is computationally more expensive. Further work is required to determine exactly how computationally demanding our pairwise-bradleyterry implementation is.

 


[1] BRADLEY, R. A. and TERRY, M. E. (1952). Rank analysis of incomplete block designs. I. The method of paired comparisons.  – http://www.jstor.org/stable/2334029

[2] Bradley-Terry Models in R: The BradleyTerry2 Package – http://www.jstatsoft.org/v48/i09/paper

[3] Wiki surveys: Open and quantifiable social data collection -http://arxiv.org/pdf/1202.0500v2.pdf

The pairwise-beta model for pairwise voting

In a pairwise vote, voters are asked to repeatedly pick between pairs of options, selecting the one they favor of the two. The procedure then combines all these pairwise choices in order to establish a global ranking for all options. A pairwise vote is statistical in nature, it must infer preference data that voters have not explicitly stated in order to obtain a result.

This statistical property allows obtaining an approximate preference ordering over a large list of options without overwhelming the voter with too much work. For example, if each voter was asked to establish a preference over 50 items, they would be exhausted and participation would suffer.

The pairwise-beta is a simple bayesian method used to rank items in pairwise votes. It is based on the beta-binomial model [1], which is composed of a beta prior and a binomial likelihood. This model is very tractable: because the beta distribution is conjugate to the binomial, the posterior also has beta form and is easily obtained:

bb1

I will not present a formal justification of the pairwise-beta model for pairwise comparisons, rather I will present some intuitions that should convey how and why the model works.

The key bridge to interpret pairwise comparisons in terms of the beta-binomial model is to realise that the better-worse binary relation between options maps directly onto the success/failure outcomes of a bernoulli trial. We can thus establish a correspondence[4] between pairwise comparisons and bernoulli trials:

  • each item i corresponds to a sequence of bernoulli trials, Bi
  • a comparison in which i wins corresponds to a success in Bi
  • a comparison in which i loses corresponds to a failure in Bi

The question we are trying to answer is

Given the proportion of comparisons in which i wins, what is the proportion of items that are globally better than i?

that reformulated in terms of our correspondences becomes

Given a sequence of bernoulli trials Bi, what is the proportion of successes/losses for i?

Which is a case of standard binomial proportion estimation[2]. As we noted before, the posterior of the beta binomial is also a beta distribution, given by

bb3

If we want a point estimate we just use the mean for this distribution which is

bb2

This gives us, for each item i, an estimation for the number of items that are better/worse than itself. This leads directly to a global ranking: the best ranked items will be those which are estimated to be better than most other items.

 In summary, the procedure is

  1. For each item i, obtain the corresponding sequence of bernoulli trials Bi
  2. For each item i, calculate the posterior beta distribution mean given the data from 1)
  3. Create a global ranking based on the proportions for each item, as calculated in 2)

The pairwise-beta model is simple but not perfect. In particular, it does not exploit information about the strength of the opposing item in a pairwise comparison. However, despite this drawback it performs well in practice. Please refer to [3] for details.

 


[1] http://www.cs.cmu.edu/~10701/lecture/technote2_betabinomial.pdf

[2] http://homepage.ntu.edu.tw/~ntucbsc/%A5%CD%AA%AB%C2%E5%BE%C7%B2%CE%ADp[email protected]/[3]%20Chapter%208.pdf

[3] http://arxiv.org/pdf/1202.0500v2.pdf

[4] The correspondence is two to one, as each comparison yields two bernoulli trials

2014 en Agora Voting

Ha sido un año muy intenso para Agora Voting, en 2014 se han superado récords de participación, se han realizado grandes avances de desarrollo y ha nacido también la empresa AgoraVoting SL de la mano de los principales contribuyentes del proyecto y con Podemos, el gran fenómeno político del año, como principal cliente.
Pero no todo ha sido Podemos en 2014.

Al igual que hicimos el año pasado vamos a intentar resumir un poco lo acontecido. Con todos estos avances es difícil saber por donde empezar, así que empezaremos por el principio.

ENERO

No hay más que remontarse a principios de año para ver los humildes orígenes de este proyecto.  En enero se constataba la creación del partido PACO en la plataforma online de Agora Voting, con voluntad de practicar la democracia líquida en Orihuela. Fue también una de las semillas que nos permitirá cerrar el año con los mismos protagonistas con los que comienza.

Los avances técnicos también fueron modestos, se propuso por ejemplo el uso de bitcoin para distribuir las autoridades, pero a día de hoy es un proyecto en el tintero. También recibimos algunas aportaciones voluntarias con nuevos diseños de logotipos para la plataforma.

 

FEBRERO

Pero ya en febrero se dio un paso fundamental en el desarrollo del proyecto, la Confederación Pirata celebró sus primarias con Agora Voting para elegir a los candidatos a las elecciones europeas y Multireferendum lo utilizó accesoriamente para su consulta popular en un inmenso esfuerzo voluntario no carente de errores y que sirvió como base para las primarias de Podemos que tan revolucionarias resultaron.

En el aspecto técnico, la organización ONCE nos proporcionó un estudio para mejorar la accesibilidad.
En febrero también se realizaron los primeros crowdfunding para implementar y seguir desarrollando la herramienta. Podemos utilizó su propia plataforma para financiar unos 1.500 €  y Multirreferendum dedicó una pequeña partida a la implementación en Goteo.

MARZO

En marzo pudimos ver el impacto que podía y llegó a tener Podemos en la política nacional, Pablo Iglesias anunciaba primarias y el actor Alberto San Juan nos enseñaba a votar con Agora Voting.

Surgen también colaboraciones clave para dar mayor la legitimidad de los procesos, Civio ofrece apoyo técnico para actuar como autoridad de votación, un testigo neutral para garantizar el proceso. También lo haría más adelante OpenKratio.

ABRIL – MAYO

Se celebran las primarias de Podemos, la figura de Pablo Iglesias resulta clave para una participación que alcanzó las 33.000 personas, un récord para la plataforma.

El éxito es rotundo y el primero de muchos, la plataforma avanza en todos los sentidos. En el aspecto técnico, la herramienta avanza considerablemente, Podemos aporta nuevas necesidades y funciones, se genera documentación y el proyecto recibe la aportación de decenas de miles de “beta-testers”.

JUNIO

Tras el éxito de Podemos en las elecciones europeas, la participación ciudadana crece exponencialmente, y también se refleja en Agora Voting, se celebran varios encuentros de programación

y la abdicación del rey lleva a la iniciativa Referéndum Real Ya con una participación de más de 80.000 personas.

JULIO – AGOSTO

Izquierda Unida se suma a las primarias online y organiza las primarias de IU Andalucía con Agora Voting, la democracia interna online promete convertirse en un nuevo estándar.

Por otro lado, Podemos sigue creciendo vertiginosamente, sus círculos y apoyos son cada vez mayores y Agora Voting colabora con el círculo TIC de Podemos para avanzar en el desarrollo de la herramienta.

SEPTIEMBRE

En septiembre los principales programadores de la plataforma dan un salto crucial, se constituye la empresa AGORA VOTING SL,
su objetivo es claro, poder dar continuidad y sostenibilidad al proyecto.

OCTUBRE

En octubre se concreta este objetivo, se trata de desarrollar la versión 3.0 de Agora Voting. Hasta el momento las implementaciones más avanzadas del programa requieren de una intervención manual mayor de lo que sería satisfactorio, con el elevado coste que supone. Edulix y David ambicionan llevar esta plataforma a la web para que sea accesible para cualquiera.


Para alcanzar este objetivo se lanza un Crowdfunding, sin embargo, el crowdfunding no resulta exitoso y el desarrollo de la herramienta depende de los clientes de Agora Voting SL. Los trabajos para Podemos y otras organizaciones siguen financiando el avance de la herramienta, al fin y al cabo esa es la ventaja del software libre, todo suma.

Mientras tanto, Podemos sigue superando sus propias cifras, 112.070 personas votan los documentos fundacionales de Podemos.

NOVIEMBRE

En noviembre se producen varios encuentros relevantes donde participa Agora Voting, en Austria se celebra el encuentro EVOTE2014 sobre voto electrónico a nivel europeo. También Julia Reda, europarlamentaria pirata, celebra un encuentro para impulsar el uso de la democracia líquida.

La difusión del proyecto también es notable en España, artículos como este  del diario.es ensalzan sus virtudes y este otro de Ricardo Galli demuestran la importancia de los observadores externos.

DICIEMBRE

El año cierra en círculo, Podemos celebra las elecciones internas en los círculos municipales, que bien podría servir para vislumbrar cómo será Agora Voting 3.0.

municipales_podemos

 

La plataforma muestra ya una gran madurez y profesionalidad, es el fruto de un gran trabajo donde 85.000 votantes participan en la elección de candidatos para 769 municipios en otras tantas votaciones simultaneas. Allí vemos a algún viejo conocido que apostaba ya hace un año por la democracia online.

2015

Aún no hemos descubierto los taquiones pero ya estamos cocinando 2015.  La primera noticia es la presencia de Agora Voting en Fosdem a finales de Enero. Se trata del mayor encuentro europeo de software libre y se intentará difundir el proyecto en Europa.

Por lo demás, los objetivos e ilusiones siguen siendo los mismos, por un año más libre y democrático, ¡salud!

EVOTE2014 – Agora Voting in the Austrian castle of electronic voting

Last week was a special one for us at Agora Voting. On Monday we were present at the press conference where the Podemos spanish political party presented the results of our most participated election yet (more than 112000 votes cast), and the same day we flew to Austria to attend the biannual evoting EVOTE2014 conference.

The conference took place during the whole week, and was held in the Schlosshofen castle in Austria. During this event, we got to meet many people involved in national electronic elections, election officials, and also cryptographers and in general academics that are improving the state of the art.

Group photo at EVOTE2014

We also had the opportunity to meet the people from Scytl who were very friendly with us. David Ruescas from Agora Voting discussed a few ideas with them regarding secure liquid democracy and listened to some of their interesting suggestions. We also had a few meetings with Rolf Haenni and his team from the University of Berne, who are doing important work in open source secure voting and kindly took the time to discuss some avenues of collaboration with us. Our plan is to help them develop their library and mixnet, and if things go well we may even be able to build a complete system together in the mid term. Rolf also mentioned the VOTEID conferece taking place next year, we may try to publish a paper there.

It was also nice to finally meet Douglas Wikstrom, the author of Verificatum, and the person who presented one of the most interesting papers in the conference. Towards the end of the week we got the chance to show our software in a demo session. Overall it’s been exciting and very important for us to be part of this event. This week, we’re back in Spain, working in the next Podemos internet election.

Integer encoding of multiple-choice ballots (2)

In the last post we saw how simple arithmetic with the right choice of base can encode integer lists for multiple ballot choices in an elegant and compact way. A couple of points were mentioned in the notes section, one of them was

our scheme allows encoding repeated choices, which are usually not legal ballots. For example, one can encode the choice 1,1,1 but that would be an illegal vote under all the voting systems we mentioned as examples. The fact that legal ballots are a subset of all possible encodings means that the encoding is necessarily suboptimal with respect to those requirements. We will look at an alternative scheme in the next post.

The alternative scheme we show below attempts to optimize the encoding by using a variable base as digits are encoded. The main idea is that as chosen integers in the list are encoded, the remaining ones are constrained since they cannot be repeated. Thus the base can be reduced as less choices are possible. In practice the process is complicated by the need to keep track of what digits correspond to what, as gaps form in the remaining integers and the corresponding meaning of digits changes. Here is a python implementation

def encode2(digits, choices = 9):
  radix = choices + 1
  present = range(0, radix)
  digits2 = deque()
  radix = radix - len(digits) + 2
  for d in digits:
    index = present.index(int(d))
    present.remove(int(d))
    digits2.appendleft(index)

  number = 0
  print(digits2)
  for d in digits2:
    number += d
    number = number * radix
    # print(d, radix, number)
    radix = radix + 1

  return number / (radix - 1)

def decode2(number, choices = 9):
  radix = choices + 1
  print("decode %d" % number)
  digits = deque()
  present = range(0, radix)
  tmp = number
  while(number > 0):
    # print(number, radix, number % radix)
    digits.append(number % radix)
    number = number / radix
    radix = radix - 1

  print(digits)
  ret = deque()
  for d in digits:
    # print(d, present, ret)
    val = present[d - 0]
    ret.append(val)
    present.remove(val)

  return ret

and a sample session using both encoders

>>> execfile("encoder.py")
>>> decode(encode([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20], 21), 21)
decode 14606467545964956303452810
deque([1L, 2L, 3L, 4L, 5L, 6L, 7L, 8L, 9L, 10L, 11L, 12L, 13L, 14L, 15L, 16L, 17L, 18L, 19L, 20L])
>>> decode2(encode2([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20], 21), 21)
decode 36697695360790800022
deque([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20])

Note the shorter value produced by the second encoder

encode: 14606467545964956303452810

encode2: 36697695360790800022

Despite the reduction, the second encoder is not optimal (the first encoder is optimal given repeatable choices); the range of output numbers is larger than that of legal ballots. It would be interesting to see how to obtain the most compact solution, a detailed analysis could compare these schemes systematically to get quantitive measures of space efficiency.


 

Integer encoding of multiple-choice ballots

Secure voting systems supporting privacy through encryption must encode ballot contents into integers before they can be encrypted[1]. This encoding step is mostly trivial. For example, imagine a yes-no-abstain ballot. One can simply apply the following mapping to yield integer plaintexts for corresponding ballots:

Yes => 1
No => 2
Abstain => 3

But things can get a bit more involved when dealing with multiple-selection ballots. These are ballots where the voter makes more than one choice. They can be either ranked ballots, where the voter specifies a preference relation over the selections, or unranked ballots where no such a preference exists. Examples of voting systems using the former are single transferable vote or instant runoff voting.  Systems like approval voting or plurality at large are examples of the second type, using unranked ballots.

Imagine we are using one of these systems to elect a candidate out of a field four: Alice, Bob, Charlie, and Donna. We first apply the trivial mapping:

Alice => 1
Bob => 2
Charlie => 3
Donna => 4

But how do we encode a complete ballot, for example, a ballot with (X corresponds to marked choices)

Alice X
Bob X
Charlie O
Donna O

Unlike the yes-no-abstain ballot above, the content of the ballot corresponds to a list of integers: 1 and 2. We could use the following mapping

encode: Alice, Bob => 1, 2 => 12

The ballot is encoded as the number 12, resulting from the concatenation of the string representations of each of the integers. But what if there are more candidates, and we need to encode something like:

encode: 11, 3 => 113

That won’t work, because 113 could represent either 11 and 3, or 1 and 13.

decode: 113 => ?

We can remedy this by adding some padding such that each choice is well separated:

encode: 11, 3 => “1103” => 1103

Then when decoding, we convert the integer to a string, split it every 2 characters, and finally obtain integers for each of the candidates:

decode: 1103 => “1103” => “11”, “03” => 11, 03

But there’s still a problem, what about this choice:

encode: 1, 13 => “0113” => 113

We run into trouble here, because the string “0113” corresponds to the integer 113; there is no mathematical difference between “0113” and “113”. To fix this, when decoding we can first check that the string length is a multiple of 2 (since we are using 2 chars per candidate integer), if it is not we prepend the required zeros. The encode-decode process would be

encode: 1, 13 => “0113” => 113
decode: 113 => “113” (prepend zero) => “0113”  => “01”, “13” => 1, 13

I hear you complain that all this concatenation, padding, and prepending looks a bit hackish, can we do better?

Let’s go back to our first example, when we simply wanted to do

encode: Alice, Bob => 1, 2 => 12

This looked very nice and simple. Can’t we do something like this in general, without any string hackery? The first step is to go back to the definition of decimal numbers.

Decimal numbers (cplusplus.com)

In these terms, the encoding 1, 2 => 12 corresponds to

(10^1) * 1 + (10^0) * 2 = 12

Here we have expressed the encoding of 1, 2 using arithmetic, no string operations involved. The ballot choices are interpreted as digits according to the mathematical definition of decimal numbers. (In fact, this is what goes on under the covers when you convert a string like “12” into the number 12.) This gives us a a purely arithmetical description of the simple mapping we started with. Things then got complicated when we considered the possiblity of more choices (candidates) in the ballot. Let’s apply our mapping to that problematic ballot:

encode: 11, 3 => (10^1) * 11 + (10^0) * 3 = 113

Our new procedure fails the same way: the simple scheme where each digit represents one choice cannot be accommodated by the decimal digit representation of choices, and the result 113 is ambiguous. But wait, who says we have to encode according to a decimal representation? What if we were to map choices to hexadecimal digits,:

encode: 11, 3 => (10^1) * B + (10^0) * 3 = B3

And we’ve restored simplicity and correctness to our scheme. B3 encodes the choice 11, 3 with one choice per digit and no ambiguity! If the B3 looks like cheating, just remember, B3 is a representation of a number that in decimal format turns out to be 179. The encode-decode process could just as well be written as

encode: 11, 3 => 179
decode: 179 => 11, 3

The bottom line is we can encode lists of integers into an integer provided we use the optimal base, which is equal to the number of possible choices in the ballot plus one.

Let’s revisit our original example, with Alice, Bob, Charlie and Donna. Since we have four candidates, our base is 4 + 1 = 5. The encoding is thus:

encode: Alice, Bob => 1, 2 => (10^1) * 1 + (10^0) * 2 = 12 (base 5) = 7 (decimal)

in short:

encode: 1, 2 => 7
decode: 7 => 1, 2

Note that not only is this method simpler with no string operations or padding, but the encoded values are smaller. Compare:

encode: 1, 2 => 12
encode: 11, 3 => 1103

with

encode: 1, 2 => 7
encode: 11, 3 => 179

Which should not come as a surprise, encoding with the specified base is the most compact[2] encoding possible (proof left as excercise for the reader). A larger base wastes space encoding ballot contents that are not possible, whereas a smaller base is insufficient to encode all possible ballots.

Finally, here is a python implementation of the encoder we have proposed

def encode(choices, max_choices):
    radix = max_choices + 1
    number = 0
    for d in choices:
        number += int(d)
        number = number * radix

    return number / radix

def decode(number, max_choices):
    radix = max_choices + 1
    choices = deque()
    while(number > 0):
       choices.appendleft(number % radix)
       number = number / radix

    return choices

In the next post we will further discuss details as to the compactness of the encoding mentioned in [2].


[1] In the case of ElGamal encryption used in Agora Voting, the plaintext must be encoded into an element of the multiplicative subgroup G of order q of the ring Zp, where p and q are suitably chosen prime numbers. In order to do this, the plaintext must be first encoded into an integer, after which it is mapped to a member of G, and subsequently encrypted.

[2] A few caveats must be mentioned. First, we are using 1-based indices to represent choices, which means some values are unused. Second, our scheme allows encoding repeated choices, which are usually not legal ballots. For example, one can encode the choice 1,1,1 but that would be an illegal vote under all the voting systems we mentioned as examples. The fact that legal ballots are a subset of all possible encodings means that the encoding is necessarily suboptimal with respect to those requirements. We will look at an alternative scheme in the next post.

Hackatón con Podemos TIC

El próximo sábado 12 de julio celebraremos un hackatón en Madrid sobre el proyecto Ágora Voting. ¿Tienes ganas de colaborar? este es el momento. Nuestra intención con estos hackatones es fomentar la comunidad de este proyecto de software libre.

BARBacoa

El hackatón se realizará en colaboración con el círculo TIC de Podemos que nos cede el lugar donde celebrarlo y también dará publicidad al evento. Invitamos a todas las personas con los siguientes perfiles a participar en el desarrollo de la herramienta:

Se busca

  • Programadores con experiencia en java/networking/multithreading
  • Programadores con experiencia en python/django/flask/threads/unit-testing
  • Administradores de sistemas con experiencia en debian/puppet/nginx/proxmox

Objetivos

  • recoger feedback sobre agora-ciudadana (el software que se ve en agoravoting.com) y que los desarrolladores de python que vengan se lo instalen localmente como entorno de desarrollo y puedan trabajar en junior-jobs en ese código en base a las incidencias reportadas.
  • trabajar en election-orchestra, que es la parte de backend que ejecutan las autoridades para hacer recuentos seguros.
  • trabajar en junior jobs de election-orchestra, para mejorar su documentación, el script de despliegue, incidencias.
  • hacer algunas pruebas y mejorar verificatum, que es el software escrito en java que lanza election-orchestra para hacer el recuento.
  • establecer una política de backups y de administración de la máquina que Podemos gestiona para votaciones.
  • montar una autoridad en los servidores de Podemos administrada por gente del círculo de Podemos TIC y hacer pruebas
  • diseñador que se encargue de hacer una github-pages sencilla para la comunidad de Agora Voting

 

Recompensas

  • Comida grasienta y bebidas estimulantes
  • Socializar con (otros) frikis
  • Formar parte de la comunidad de un proyecto de software libre que está revolucionando la democracia

Dónde, cuándo

El hackathon comenzará a las 11:00 de la mañana el sábado 12 de julio y se planea que dure hasta la noche. Se realizará en la siguiente dirección: Calle Nanclares de Oca, 3 (el metro más cercano es Canillejas).

El lugar está un poco apartado, te recomendamos venir en coche. Para cualquier duda, contáctanos en nuestra lista de correo: https://groups.google.com/group/agora-ciudadana-devel

¿Qué me llevo?

Tu portátil, el cable de alimentación, y muchas ganas de hackear.

Antecedentes

La colaboración entre Agoravoting y Podemos está siendo muy fructífera, además de los crowdfunding de Podemos para la aplicación de mejoras, el apoyo mostrado por el movimiento a favor de esta herramienta https://podemos.info/participa/herramientas/ ha propiciado:

  • innumerables pruebas de círculos de podemos en agora-ciudadana, (la versión web de la aplicación), que han sacado a relucir las vergüenzas del programa y que pretendemos abordar en el hackatón
  • recursos humanos y materiales para continuar con el desarrollo, principalmente la colaboración con el círculo TIC (técnología de la información y la comunicación) que nos produce una sana envidia por su gran número de participantes y los conocimientos de los mismos
  • la cesión desinteresada de un excelente espacio de coworking donde poder trabajar en el desarrollo de esta herramienta y otras.

El 15 de junio, después de la primera gran asamblea de podemos, donde se realizó un taller TIC, se celebró una barbacoa en este espacio con el fin de conocer el lugar, romper el hielo, discutir ideas y comer salchicas (recomendación: no llevar camisa blanca a una barbacoa).


También se aprovechó la ocasión para celebrar la primera asamblea del círculo TIC en la misma mesa de pingpong en la que intentamos jugar infructuosamente, por el viento. En este hackatón nos centraremos más en el código y menos en la comida grasienta y otros divertimentos, que por otra parte no pueden faltar en un evento como este ¿quieres venir?