Forum du Parti Pirate

Bonjour,

Nous envisageons de mettre en place un nouveau mode de scrutin au cours de l'Assemblée générale du 16 octobre. Nous nous intéressons notamment aux méthodes de Condorcet, et plus particulièrement à la méthode de Schulze, employée par d'autres partis pirates ou projets notamment autour du logiciel libre.

La fondation Gentoo, entre autres, l'utilise pour ses élections internes. Le résultat donne par exemple le fichier suivant.

Nous souhaiterions mettre en place la méthode de Schulze pour l'AG du 16, mais il nous faudrait expliciter l'algorithme exact très rapidement afin que chacun puisse avoir le temps de choisir voire de programmer un logiciel de comptabilisation des votes d'ici-là.

Pour cela, nous avons besoin d'un coup de main. Si vous avez quelques minutes, pourriez-vous faire une recherche sur les projets de logiciel libre comme Gentoo pour en sortir l'algorithme exact (suffisamment détaillé pour que deux personnes différentes l'implémentant obtiennent toujours le même résultat) et/ou le logiciel utilisé pour le décompte ?

Merci d'avance.

Sympa cette méthode, je vais essayer de décrire l'algo, par contre je suis une pine en programmation, je sais pas si je pourrais le coder.
Après reste le pb de la saisie, il y a n! ordres de classement possible.

(voir même ? (n-k)!*{k parmi n-1} , k=0..n-1 si on autorise les égalités dans le classement.)


ça fait selon le nb de candidats :
1 -> 1 (1)
2 -> 2 (3)
3 -> 6 (11)
4 -> 24 (49)
5 -> 120 (261)

ça devient donc vite très galère pour le comptage, sauf si le vote est directement électronique bien sûr.

Edit : Bon je vais dvp au fur et à mesure que j'avance, ça risque d'être un peu incompréhensible par moments : j'utilise l'heuristique de Schwartz, je commence par raisonner de façon matricielle pour ensuite adapter avec un algorithme
1/création d'une matrice de résultats des matchs R tq Rij=d[i,j]-d[j,i] c'est donc une matrice antisymétrique.
2/permutation de vecteurs afin de créer une matrice par bloc R' séparant l'ensemble de Schwartz des autres vecteurs. Le bloc situé "sous" le bloc Schwartz doit être négatif, c'est une condition nécessaire et suffisante à la présence d'un bloc Schwartz. *on doit pouvoir en sortir une méthode de détection de l'ensemble de schwartz et de formation de la matrice par bloc
3/on remplace la matrice R' par le bloc Schwartz
4/si R'=[0], on a égalité entre ceux qui restent, ce sont nos gagnants (on espère notre)!
sinon on remplace les plus petites valeurs de |Rij| par 0 (ce qui revient à supprimer l'arc), et on réitère le processus (fonction récursive ?)

-Le gros du travail va se faire sur l'étape 2 !
-Bien penser à garder en mémoire les matrices permutations (ou qui est quelle colonne) afin de pouvoir déterminer le gagnant, via un tableau par exemple.

J'ai jeté un oeil aux pages wikipedia, comment les gens votaient avec cette méthode, et il en ressort un projet open-source : vote.sourceforge.net. Le logiciel est pas trop mal, simpliste mais il fait ce qu'il faut. Et il peut prendre en entrée des fichiers csv ou txt.

Après je ne suis pas sur de ce que tu voudrais:

• Est-ce qu'avoir un logiciel de comptage vous suffit ?
• Ou il faut dans tous les cas un pseudo-algo pour valider les logiciels qu'on utiliserait.
• Ou vous voulez votre propre programme pour être sur qu'il n'y ai pas d'erreurs.

Drenskin a écrit :Après je ne suis pas sur de ce que tu voudrais:

• Est-ce qu'avoir un logiciel de comptage vous suffit ?

Peut-être, mais il faut absolument un logiciel libre.

Drenskin a écrit :

Ou il faut dans tous les cas un pseudo-algo pour valider les logiciels qu'on utiliserait.

Ce serait préférable.

Drenskin a écrit :

Ou vous voulez votre propre programme pour être sur qu'il n'y ai pas d'erreurs.

Ce serait l'idéal.


En fait, j'ai déjà commencé à développer un programme pour classer selon la méthode de Schulze. Pour le moment, il prend en entrée un fichier texte simple avec les différents votes, et calcule la matrice des duels et le tableau des chemins les plus forts.

Implémenter l'heuristique de l'ensemble de Schwarz n'a pas l'air bien compliqué.

En revanche, il y a une incertitude en cas d'égalité, et l'article Wikipedia n'est pas clair là-dessus. J'aimerais savoir s'il existe un algorithme pour départager les cas d'égalité, ou au moins les signaler qu'on puisse utiliser une procédure pour départager les ex-aequo ne reposant pas sur la fonction rand d'un ordinateur à un temps donné.

J'aimerais également avoir des détails sur la méthode dite de Schulze STV, sur laquelle je n'ai pas encore trouvé d'informations précises :

• S'agit-il simplement de remplir siège après siège avec le meilleur selon Schulze tout court, puis d'enlever ledit meilleur et de refaire les calculs avec les autres sans rien changer ?
• S'agit-il de remplir siège après siège avec le meilleur selon Schulze tout court, puis de l'enlever mais en diminuant en plus le pouvoir de vote de ceux dont un candidat préféré a été élu ?
• S'agit-il de quelque chose de totalement différent ?

Dans le premier cas, ça va être simple à faire. Mais dans les autres ça risque d'être plus délicat, et en tous les cas j'ai besoin d'informations sur les cas d'ex-aequo.

marou a écrit :Peut-être, mais il faut absolument un logiciel libre.

Alors le logiciel est bien libre, j'ai vérifié il est sous licence GNU-GPL.

marou a écrit :

Drenskin a écrit :[*]Ou il faut dans tous les cas un pseudo-algo pour valider les logiciels qu'on utiliserait.

Ce serait préférable.

Ok. Ca me parait faisable, une bonne partie étant très bien décrite sur les différents articles Wikipedia.

marou a écrit :

Drenskin a écrit :[*]Ou vous voulez votre propre programme pour être sur qu'il n'y ai pas d'erreurs.[/list]

Ce serait l'idéal.


En fait, j'ai déjà commencé à développer un programme pour classer selon la méthode de Schulze. Pour le moment, il prend en entrée un fichier texte simple avec les différents votes, et calcule la matrice des duels et le tableau des chemins les plus forts.

Ben là dessus je peux me lancer aussi sur un soft. Et on pourra toujours comparer les résultats avec une batterie de tests avec le programme que j'ai cité plus haut.

marou a écrit :En revanche, il y a une incertitude en cas d'égalité, et l'article Wikipedia n'est pas clair là-dessus. J'aimerais savoir s'il existe un algorithme pour départager les cas d'égalité, ou au moins les signaler qu'on puisse utiliser une procédure pour départager les ex-aequo ne reposant pas sur la fonction rand d'un ordinateur à un temps donné.

Alors, je citerai l'article wikipedia :

Wikipedia a écrit :Although ties in the Schulze ranking are unlikely,[2] they are possible. Schulze's original paper[1] proposed breaking ties in accordance with a voter selected at random, and iterating as needed.

An alternative, slower, way to describe the winner of the Schulze method is the following procedure:

draw a complete directed graph with all candidates, and all possible edges between candidates
iteratively delete all candidates not in the Schwartz set (i.e. any candidate which cannot reach all others) and delete the weakest link
the winner is the last non-deleted candidate.

Donc, je ferai dans tous les cas la seconde méthode pour départager, mais, en sachant que statistiquement, il est toujous possible qu'il y ai une égalité parfaite, il faut implémenter un random au cas où. Même s'il est vrai que le random informatique n'est pas parfait, il me parait suffisant dans ce cas. L'autre solution, c'est de sortir les deux ex-æquo comme tels.

marou a écrit :J'aimerais également avoir des détails sur la méthode dite de Schulze STV, sur laquelle je n'ai pas encore trouvé d'informations précises :

Alors là : j'ai trouvé çà http://home.versanet.de/~chris1-schulze/schulze2.pdf, mais j'ai pas encore eu le temps de bien lire. Mais je pense que ça répondra à tes interrogations. Les pdf vont de 1 à 5 btw, il y a de tout.

La méthode de schultz ne garanti absolument pas un unique gagnant, c'est son défaut !
La seule chose à faire c'est d'ajouter une condition en cas d'égalité, il y a plusieurs possibilités :
-l'âge (comme au sénat)
-le tirage au sort (j'aime pas)
-le bras de fer chinois
-on peut éventuellement intégrer
-ou d'autres (j'aime bien l'idée d'un match de sumo)

marou a écrit :S'agit-il simplement de remplir siège après siège avec le meilleur selon Schulze tout court, puis d'enlever ledit meilleur et de refaire les calculs avec les autres sans rien changer ?

Je ne connais pas la méthode Std mais ça m'a l'air assez horrible !
Grosso modo, dans le cas de deux "courants" s'affrontants, le courant majoritaire aura l'ensemble des sièges.

marou a écrit :S'agit-il de remplir siège après siège avec le meilleur selon Schulze tout court, puis de l'enlever mais en diminuant en plus le pouvoir de vote de ceux dont un candidat préféré a été élu ?

ça m'a l'air mieux, on peut se baser pour ça sur la méthode du vote d'approbation proportionnel, faut juste voir ce que ça donne
http://fr.wikipedia.org/wiki/Vote_d%27a ... portionnel
la décroissance du poids des voix ne peut cependant pas s'appuyer seulement sur ceux qui ont eu leur préféré, cela risque d'engendrer des distorsions elle devrait être dépendante de la position dans le classement du candidat élu en première place (on multiplie par une fonction "croissante en n" le poids des votes,un truc genre 1-a^(-n) avec n la position du gagnant dans le classement et a>1).
Je vais voir ce que ça donne.

Le-Dore a écrit :Je ne connais pas la méthode Std mais ça m'a l'air assez horrible !
Grosso modo, dans le cas de deux "courants" s'affrontants, le courant majoritaire aura l'ensemble des sièges.

Effectivement, pour voter à des municipales sans système de liste (donc maire + conseil) mais en sélectionnant ses préférences de candidat, si tout le monde votait uniquement selon le parti, çà ne marcherai pas. Donc ce système de vote ne serait pas à utiliser.

Mais par exemple, pour l'élection des X candidats pour N places au CAP du PP : quand une place a été attribuée à un candidat, on refait le calcul sans prendre en compte tous les votes attribués à ce candidat, donc X-1 candidats pour N-1 places.

Drenskin a écrit :Mais par exemple, pour l'élection des X candidats pour N places au CAP du PP : quand une place a été attribuée à un candidat, on refait le calcul sans prendre en compte tous les votes attribués à ce candidat, donc X-1 candidats pour N-1 places.

Ben oui c'est sûr que c'est fonctionnel, mais c'est loin de permettre la meilleure représentativité.
Je pense faire un truc du genre :
1/ appliquer la méthode de Schulze pour déterminer le premier candidat parmi X (reste X-1) candidats
2/ on supprime le candidat gagnant et tout les votes qui lui sont attribués
3/ (ce qu'on rajoute à ta méthode) on réévalue la valeur des votes en fonction de la satisfaction liée au nouveau candidat
4/on reprend jusqu'à ce qu'on ait plus de places

l'intérêt c'est que les gens non représentés ont de plus en plus de chance de l'être jusqu'à ce qu'ils le soient, ce qui entraîne à nouveau la dévaluation de leur vote.
plusieurs fonctions de réévaluation possibles :
-valeur divisée par deux pour ceux qui ont eu leur premier choix, on change rien pour les autres, le plus simple mais incomplet.
-fonctions dépendantes de la place du candidat élu (p) (croissantes et positives) :

concave :
f(p)=1-a^(-p) avec a>1, 2 par exemple
f(p)=p^(a) avec 0<a<1
identité :
f(p)=p
convexe

les concaves sont plus adaptés, le poids des gens satisfaits est fortement affectés, celui des gens peu satisfaits ne change pas beaucoup.

La problématique étant qu'il faut fixer l'algorithme exact cette semaine, sinon on devra se contenter d'utiliser une des méthodes de vote du Règlement intérieur (qui sont beaucoup moins bonnes amha).

Comme l'a dit Drenskin, je ne pense pas de toute manière qu'il y ait de courants au sein du PP qui pourraient amener au problème que tu signales Le-Dore…

Voici l'algorithme que je proposerais pour cette élection, dites-moi ce que vous en pensez.

Soit S sièges et C candidats. Les votants attribuent une valeur de 1 à leur candidat(e) préféré(e), puis 2 au second, etc. Les ex-aequo sont autorisés. (Les candidats sans classement sont considérés comme ayant la valeur la plus haute du bulletin de vote, +1.)

Début de la boucle :
On applique la méthode des ensembles de Schwartz à l'ensemble des candidats et on détermine les N gagnants potentiels parmi les C candidats.

• Si (N < S) alors on attribue N sièges aux N gagnants potentiels. On enlève les N gagnants de la liste C et on leur attribue un siège. Puis on relance la boucle avec (C-N) candidats pour (S-N) sièges.
• Si (N = S) alors on attribue les S sièges aux N gagnants potentiels et on passe à la suite.
• Si (N > S) alors on attribue les S sièges restants à S parmi les N en les départageant selon les modalités de résolution des ex-aequo définies au Règlement intérieur.

Il y a autre chose : le seuil minimum. Dans les élections des conseils précédentes, nous avions un seuil d'un tiers des voix pour être admissible. Les candidats ne dépassant pas le seuil ne pouvaient pas obtenir un siège, même lorsqu'il y avait des sièges de disponibles (c'était le cas au CN où tous les candidats n'ont pas été pris bien que le CN ne soit pas rempli).

Avec Schulze, il n'est pas prévu de seuil minimum. Mais on pourrait ajouter une procédure de blocage : on ajouterait un vote de blocage ("0", "-1", symbole infini ?), et celui-ci vaudrait non seulement moins que tous les autres (y compris ceux auxquels ont n'a attribué aucune valeur) mais en plus il empêcherait le candidat d'accéder au conseil – quel que soit son classement – s'il est sanctionné de plus de deux tiers de ces votes de blocage.

Votre avis sur ces deux questions ?

Donc pour ta première question çà me semble très bien.

marou a écrit :Avec Schulze, il n'est pas prévu de seuil minimum. Mais on pourrait ajouter une procédure de blocage : on ajouterait un vote de blocage ("0", "-1", symbole infini ?), et celui-ci vaudrait non seulement moins que tous les autres (y compris ceux auxquels ont n'a attribué aucune valeur) mais en plus il empêcherait le candidat d'accéder au conseil – quel que soit son classement – s'il est sanctionné de plus de deux tiers de ces votes de blocage.

Qu'entends tu pas "il vaudrait moins que les autres" ? Juste qu'il serait placé en dernier dans la liste ? Ou lors du calcul de la matrice des duels, les valeurs seront modifiés en fonction du nombre de blocages ? Si c'est le premier cas ok, mais sinon j'ai peur que çà fausse tout le système.

-1 me semble bien pour un blocage, ou juste 'B'. Mais en tout cas c'est une très bonne solution.

Juste, si un candidat est bloqué, est-ce qu'on le retire de la matrice avant ou après les votes ? C'est à dire, est-ce qu'il peut être virtuellement élu, puis on annonce qu'en fait non (comme çà il peut avoir son score s'il le désire), ou est-ce que dès que les votes de blocage sont comptés, les candidats concernés sont écartés avant même le tirage des gagnants.

Drenskin a écrit :Qu'entends tu pas "il vaudrait moins que les autres" ? Juste qu'il serait placé en dernier dans la liste ? Ou lors du calcul de la matrice des duels, les valeurs seront modifiés en fonction du nombre de blocages ? Si c'est le premier cas ok, mais sinon j'ai peur que çà fausse tout le système.

Premier cas. Exemple : je classe ABCDE avec les scores 1 2 2 3 B. Ca donne pour le calcul de Schulze le classement : A > B = C > D > E.

Drenskin a écrit :Juste, si un candidat est bloqué, est-ce qu'on le retire de la matrice avant ou après les votes ?

Je suis pour calculer et annoncer son résultat, mais qu'on l'écarte du siège et qu'on prenne le suivant au dernier moment dans la liste des résultats pour remplir le conseil.

Ca me semble parfait

Et du coup il te faut quoi maintenant ? Toujours le pseudo algo, des données de tests ? Pour quand ?

Ce qu'il reste c'est formaliser le mode de scrutin pour le règlement intérieur et l'implémenter.

Je vais tâcher de m'occuper des deux d'ici dimanche, mais si vous voulez commencer à réfléchir à une rédaction adéquate pour le RI d'ici-là, feel free .

1 2 2 3 ou 1 2 2 4 comme c'est usuellement la façon dont on numérote les candidats suivants un ex-æquo ?

Dans les faits, çà ne devrait avoir aucune influence sur le résultat que l'on numérote d'une façon ou d'une autre.