Salut,

Tu peux nous expliquer ce qu'est le paradoxe de Condorcet ? Ou alors donner un lien qui explique.

Voilà un très bon lien:

http://fr.wikipedia.org/wiki/Paradoxe_de_Condorcet

Ca n'a pas l'air inintéressant. Je regarderai peut-être ça ce week.

Remarque : quand tu donnes un lien http sur le forum, mets-le entre des balises "url", à l'aide de l'icône avec la petite maison jaune, ça donne ça :

Ah oui, effectivement, j'avais oublié. C'est noté pour la prochaine fois.

bonjour,je voulais juste savoir si tu t'etais propose l'exercice a toi_meme.parce que je n ai jamais vu le resultat dans le cas de 4 candidats.Je ne sais pas si les relations de transitivite reste valables.
ca m'interesserait de savoir ce que ca donne dans le cas de 4 candidats.

Bonjour,

on trouve aussi un site sur ce paradoxe ici :

En fait, c'est dans le cadre d'un stage de recherche en mathématiques, donc la question revêt une certaine importance. J'ai repris complètement mon programme et j'en ai écrit une nouvelle version; cela ne change strictement rien, je n'ai toujours pas les résultats demandés.
Dans un article de 1975, 4 candidats:
3 votants 1/9
5  0.13888
7  0.15003
9  0.15595
11  0.15963
13  0.16214
limite: 0.17458
Pour mon programme première version (toujours réalisé avec 10 000 itérations):
3  0.1748
5  0.2119
7  0.2220
9  0.2326
11 0.2370
deuxième version (10 000 itérations):
3 0.1699
5 0.2112
7 0.2209
9 0.2307
11 0.2486
Bref,on ne trouve pas les bons résultats.
Pour ceux que cela intéresse, voici les codes de la première version:
function s=votcond(m,n,p) %m alternatives, n votants p itérations
compteurgeneral=0;
for k=1:p
matrice=zeros(n,m);
for e=1:n*m
matrice(e)=floor((e-1)/n)+1;
end;
for f=1:n
for g=1:m
z=floor((m+1-g)*rand+g);
c=matrice(f,z);
matrice(f,z)=matrice(f,g);
matrice(f,g)=c;
end;
end;
A=zeros(m,m);
for e=1:m-1
for f=e+1:m
a=0;
for g=1:n
a=a+sign(matrice(g,f)-matrice(g,e));
end;
A(e,f)=-sign(a);
A(f,e)=sign(a);
end;
end;
y=1;
if (A(1,2)==A(2,3)&A(2,3)==A(3,4)&A(3,4)==A(4,1)),y=0;end;
if (A(1,2)==A(2,4)&A(2,4)==A(3,1)&A(3,1)==A(4,3)),y=0;end;
if (A(1,3)==A(2,4)&A(2,4)==A(3,2)&A(3,2)==A(4,1)),y=0;end;
if (A(1,3)==A(2,1)&A(2,1)==A(3,4)&A(3,4)==A(4,2)),y=0;end;
if (A(1,4)==A(2,3)&A(2,3)==A(3,1)&A(3,1)==A(4,2)),y=0;end;
if (A(1,4)==A(2,1)&A(2,1)==A(3,2)&A(3,2)==A(4,3)),y=0;end;
if (A(1,2)+A(1,3)==0&A(1,3)+A(2,3)==0),y=0;end;
if (A(1,2)+A(1,4)==0&A(1,4)+A(2,4)==0),y=0;end;
if (A(2,3)+A(2,4)==0&A(2,4)+A(3,4)==0),y=0;end;
if (A(1,3)+A(1,4)==0&A(1,4)+A(3,4)==0),y=0;end;
compteurgeneral=compteurgeneral+y;
end;
s=compteurgeneral;

deuxième version:
function s=votcond(m,n,p) %m alternatives, n votants p itérations
compteurgeneral=0;
for k=1:p
matrice=zeros(n,m);
for e=1:n*m
matrice(e)=floor((e-1)/n)+1;
end;
for f=1:n
for g=1:m
z=floor((m+1-g)*rand+g);
c=matrice(f,z);
matrice(f,z)=matrice(f,g);
matrice(f,g)=c;
end;
end;
A=zeros(m,m);
for e=1:m-1
for f=e+1:m
a=0;
for g=1:n
a=a+sign(matrice(g,f)-matrice(g,e));
end;
A(e,f)=-sign(a);
A(f,e)=sign(a);
end;
end;
y=1;
a=0;
c=0;
for u=1:m
b=0;
d=0;
for v=1:m
b=max(b,A(u,v));
d=max(d,A(v,u));
end;
a=[a b];
c=[c d];
end;
ggg=0;
vec=a+c;
for w=2:m+1
if vec(w)==2,ggg=ggg+1;end;
end;
if ggg>2,y=0;end;
compteurgeneral=compteurgeneral+y;
end;
s=compteurgeneral;

Les débuts des deux versions sont pareil: on simule la création d'une matrice n*m, avec dans chaque ligne, les chiffres de 1 à m dans le désordre. C'est le choix du votant de la ligne correspondante. Exemple s'il y a cinq électeurs et trois candidats:
3 1 2
1 2 3
2 1 3
3 2 1
1 3 2
Ainsi, le premier votant préfère le candidat numéro 1 (il lui a donné trois points), ensuite c'est le candidat numéro trois (qui a deux points) ensuite c'est le candidat numéro deux (un point seulement).
Ensuite, je créée une matrice de préférence, de taille m*m, pour regarder si tel candidat est préféré à tel autre.
Est-ce que le candidat un est préféré au candidat deux?
Le premier électeur préfère le candidat 1 au candidat 2, le deuxième électeur non, le troisième oui, le quatrième oui, le cinquième non. Bref, globalement, le premier candidat est préféré au deuxième. On met donc un 1 dans la première ligne deuxième colonne et un -1 dans la deuxième ligne première colonne. On trouve finalement comme matrice (e mettant arbitrairement des zéros sur la diagonale):
0 1 -1
-1 0 -1
1 1 0
Iln'y pas de cycle de condorcet. En effet, un cycle de condorcet implique au moins trois personnes, et le deuxième candidat n'est préféré à personne (-1 dans la deuxième ligne).
Donc pour trois candidats, c'est simple, il suffit de rajouter un compteur, et c'est bon. Pour quatre candidats, la grande question est: comment identifier un cycle de condorcet (ou montrer qu'il n'en existe pas) à partir de la matrice de préférence de taille 4*4?
Et c'est là que cela coince.
pour la première version, je me suis embêté à écrire tous les cycles possibles, à voir ce que cela donnait comme condition, et à les écrire mathématiquement. Il y a 9 conditions possibles, 9 cas possibles, six cycles de quatre, quatre conditions sur les cycles de trois (en fait il y a huit cycles possibles mais je les ai regroupés deux par deux).
Pour la deuxième version, (mais c'est peut être faux), je me suis aperçu qu'en écrivant les conditions détaillées, cela revenait à prendre le vecteur du maximum de chaque ligne, prendre le vecteur du maximum de chaque colonne, additionner les deux, et on avait cycle de Condorcet si et seulement si il y avait au moins 3 fois le chiffre 2 dans le vecteur somme (attention, ce n'est plus vrai avec cinq candidats). Ce qui est rassurant c'est que les résultats coïncident grosso modo. Donc c'est pour cela que je me suis dit qu'en 1975 ils ne devaient pas avoir de machines perfectionnées et que c'était cet article qui était faux. Alors, c'est vrai, il y a peut être une erreur dans ces programmes (d'ailleurs, en rédigeant, j'en ai repéré une, cela ne m'a pas permis de trouver des résultats collant à l'article, mais au moins grâce à la correction de l'erreur, mes résultats concordent à peu près entre eux).

Essaye de faire bref quand tu demandes de l'aide...

Ecris plutôt l'algorithme de ton prog en français.

Moi je ferais ça, pour 3 candidats qu'on code par 1, 2, 3:

n <- nombre de candidats
M <- matrice n lignes 3 colonnes
POUR(i de 1 à n){
   simuler un triplet aléatoire (1,2,3) ou (2,3,1).. [[6 triplets possibles]]
   stocker ce triplet dans la ligne i de M
}
P <- matrice 3 lignes 3 colonnes [[
POUR(i de 1 à 3){
   POUR(j de i+1 à 3){
      nb <- nombre de lignes de M telles que i est avant j
      SI(nb > n/2){P(i,j) <- 1 & P(j,i) <-0}
      SI(nb < n/2){P(i,j) <- 0 & P(j,i) <-1}
   }
}

Ensuite je déterminerais à la main les matrices P possibles pour lesquelles il y a paradoxe de condorcet, et je testerais si la matrice P obtenue fait partie de celle ci.

Puis je fais ça en boucle 10000 fois et je fais x/10000 où x est le nombre de fois où il y a eu paradoxe.

Quelle est la difficulté à implémenter cela ? (qui s'adapte à + de 3 candidats)

... petite correction :

Désolé pour la longueur du message, mais je tenais à publier non seulement le code mais également les commentaires nécessaires au déchiffrage du code.
Tes propositions sont pleines de bon sens, c'est quasi exactement ce que j'ai fait. Seule différence: tu mets 0 et 1 quand je mets 1 et -1, et que je réserve 0 à la diagonale. Pour l'étape 3, c'est exactement ce que j'ai fait. Le problème, est que quand le nombre de candidats augmente, le nombre de cycles possibles augmente.
Pour trois candidats notés A, B, C, il y a deux cycles:
ABCABC...
ACBACB...
Quatre candidats, A, B, C, D:
ABCDABCD...
ABDCABDC...
ACBDACBD...
ACDBACDB...
ADBCADBC...
ADCBADCB...
ABCABC...
ACBACB...
ABDABD...
ADBADB...
ACDACD...
ADCADC...
BCDBCD...
BDCBDC...
C'est à dire 14 cycles, avec pour chacun plusieurs critères à trouver, à programmer, et donc le risque d'erreur est très important. Et il est possible que l'erreur soit là.
Et quand on est à 5 candidats, cela devient impossible, car il y a 74 cycles, et donc 74 matrices à écrire, et donc beaucoup de critères.

Pourquoi des cycles ??

Chaque votant donne un ordre de préférence : (A,B,C) ou (B,C,A) ou (C,A,B) ou (A,C,B) ou (B,A,C) ou (C,B,A).

Pourquoi des cycles ?? Que représentent ces cycles ?

Justement, quand se produit un de ces cycles, il y a paradoxe de Condorcet. Le vainqueur de Condorcet, c'est celui qui bat tout le monde. par exemple si A bat B et A bat C, alors A est le vainqueur de Condorcet. S'il n'y a pas vainqueur de Condorcet, c'est que A bat B, B bat C, C bat A ou A bat C, C bat B, B bat A. Dans tous les autres cas, il y a vainqueur de Condorcet.
Examinons l'ensemble des cas:
1)entre A et B: A bat B ou B bat A
2)entre A et C: A bat C ou C bat A
3)entre B et C: B bat C ou C bat B
Pour avoir un ordre, il faut prendre pour chacun des numéros 1, 2 ,3 une des deux propositions. Vous avez donc 8 cas au total, il y en a 6 où on peut dégager un vainqueur.

... je ne vois pas ce que tu dis, j'ai l'impression que tu compliques tout, mais peut-être que je me trompe.

Je n'ai guère le temps de m'y pencher.

Moi je programmerais l'algo que j'ai écrit, voilà.

J'ai programmé la chose, tout ce que je veux, c'est vérifier mes résultats et voir s'ils sont bons. Mais je n'ai pas trouvé les vrais résultats sur le web.

Google : "probability condorcet paradox"

... si tu veux bien faire l'effort de lire un peu d'anglais.

Je ne comprends pas ce qu'est p :

Abstract

Let P(n,p) be the probability that there is a Condorcet winner on three alternatives for n (odd) voters. The vector p defines the probability that a randomly selected voter will have any of the six linear rankings on three alternatives as his or her preference ranking. It is shown that if all p vectors are equally likely, the expected value of P(n,p) is given by 15(n+3)2/[16(n+2)(n+4)].

... ah ok on a 3 candidats si j'ai bien compris, et dans le cas auquel tu t'intéresses c'est p uniforme, donc ce serait la formule pour 3 candidats.

Que donne la formule en comparaison à tes résultats ?

Merci du lien, mais la formule est fausse.
Démonstration:  Prenons le cas de trois votants. Avec la formule on trouve 27/28. il y a 6 ordres possibles avec 3 candidats: ABC, ACB, BAC, BCA, CAB, CBA. On a donc 6 choix pour le premier, 6 choix pour le deuxième votant, 6 choix pour le troisième, soit 216. Si on note X le nb de cas où il n'y a pas paradoxe de condorcet, le résultat est de la forme X/216. Or si 27/28=x/216 on a 27/28*216=1458/7=208.286 non entier donc X n'est pas entier, donc c'est idiot et la formule est fausse.
Par contre, en tapant probability paradox condorcet je suis tombé sur des probabilités (donc merci du conseil), hélàs pas pour 4 alternatives (dommage c'était le cas intéressant), je vais donc programmer pour 5 alternatives et vérifier. Car j'ai compris comment on pouvait programmer en 5 alternatives. L'astuce (je ne comprends pas pourquoi je n'ai pas trouvé plus tôt), c'est que s'il y a un cycle de 5, il y a forcément un cycle de trois.
Démonstration: supposons que le cycle est ABCDEA...(A préféré à B préféré à C etc)
Si C est préféré à A, on a le cycle ABCA...  
Si A est préféré à C, on a le cycle ACDEA...
Et on recommence. Si D est préféré à A on a le cycle ACDACD...
Si A préféré à D on a le cycle ADEADE...
Donc dans tous les cas si on a un cycle de n, on a un cycle de trois par récurrence descendante sur n.
Je vous aurais bien mis les résultats, le problème c'est que j'ai enregistré la page, mais pas l'adresse internet du site.

Salut mon gars,

En effet je sais pas trop ce que c'est cette formule : the expected value of P(n,p).

Bon! J'ai tout programmé pour 5 candidats, et je viens enfin de comprendre comment on peut rapidement déceler s'il y a vainqueur de Condorcet. Problème: je n'arrive toujours pas à trouver les résultats attendus. Pour 5 candidats, 3 électeurs et 100 000 itérations, au lieu de 0.16, je trouve 0.32632. Vu le nombre d'itérations, il est absolument impossible que l'écart soit dû à une malchance dans l'expérimentation. Pourtant, j'ai écrit les 10 triplets, j'ai regardé ce que cela donnait comme conditions sur la matrice, et j'ai programmé le tout.
Je sais ce que je vais faire: je vais calculer à la main, en écrivant tous les cas pssibles, la probabilité pour 4 candidats et trois électeurs, car je commence à en avoir par dessus la tête. J'y passerais peut être deux ou trois heures, mais au moins ce sera réglé.

Salut,

Tu sais je ne l'ai lu qu'en diagonale tout ça car j'ai pas trop le temps, et je suis pas sûr d'avoir compris "vainqueur de condorcet". Ce serait un candidat qui est préféré à tous ? Quelle relation avec le paradoxe de Condorcet ? Paradoxe de Condorect ça voudrait dire qu'il n'y a pas de vainqueur de Condorcet, c'est ça ? J'ai pas l'impression.

A part ça je t'encourage à passer quelques heures à te convaincre, c'est comme ça.

Vainqueur de Condorcet: un des candidats qui opposé à chacun des autres est préféré.
Exemple avec 3 candidats et 3 votants, si les préférences sont:
ABC (le votant 1 préfère A à B et B à C)
BAC
CAB
A est vainqueur car si A est opposé à B, A a deux voix, celles des votants un et trois, et si A est opposé à C, A a deux voix, celles des votants un et deux.
Il y a paradoxe de Condorcet quand il n'y a pas vainqueur de Condorcet, par exemple si les préférences sont ABC, BCA, CAB.
Sans vouloir être désagréable, pour quelqu'un qui est en doctorat, cela devrait pourtant être simple.
Quant à moi, je me suis lancé vaillamment avec un papier et un crayon pour étudier les 13824 possibilités et décréter s'il ya apradoxe de Condorcet ou pas. J'ai finalement abandonné, plongé dans les problèmes de comptage.
J'ai décidé alors de programmer en Matlab un truc, mais je suis en train de m'apercevoir qu'il est très probablement faux. J'y retourne.

J'ai repris mes calculs papier crayon. Je vous les soumets.
Le principe est simple: on prend trois quadruplets parmi les 24 possibles, cela représente les préférences.
D'après moi, il y en a 5184 triplets composés de quadruplets commençant par des lettres différentes, 5184=24*18*12
Sur ces 5184, 192 triplets sont composés de quadruplets ayant tous les trois la même deuxième lettre. En effet, on a 24 choix pour le premier quadruplet, le deuxième quadruplet doit avoir la même deuxième lettre et une première lettre différente, cela fait 4 possibilités, et le dernier n'a plus que deux possibilités, 24*4*2=192.
Parmi ceux qui restent, 2880 triplets ont deux quadruplets ayant la même deuxième lettre, et le troisième ayant une lettre différente: cette classe se décompose comme suit en deux groupes:
un groupe de 1728 triplets, dont le quadruplet qui n'a pas la même deuxième lettre que les autres commence par cette lettre en question. Exemple: ACBD, BCAD, CABD (la deuxième lettre commune aux deux triplets est C et le troisième triplet commence par la lettre en question)
Un deuxième groupe de 1152 triplets, dont aucun triplet ne commence par la deuxième lettre commune à deux triplets, exemple: ADBC BDAC CABD (le troisème triplet ne commence pas par D, deuxième lettre des deux triplets, mais par C)
Enfin, 2112 triplets sont composés de quadruplets ayant tous des deuxième lettre différentes. Cette classe se décompose en deux groupe:
384 triplets sont composés de quadruplets où une des quatre lettres figure dans chacun des triplets au troisième ou au quatrième rang. Exemple: ABCD BCAD CABD la lettre D est reléguée à chaque fois dans les deux dernières positions
1728 triplets forment le reste, exemple: ABCD BACD CDBA
Auriez vous l'amabilité de vérifier ces ô combien passionnants calculs?
Maintenant, il reste à prendre chaque classe, et à regarder dans quels cas il y a vainqueur de Condorcet. La suite au prochain numéro.

Hourrah! J'ai la réponse à ma question: ayant terminé mes calculs, je viens de m'apercevoir que le vieil article de 1976....suspens incroyable...avait raison. On a exactement 1536 cas où il y a paradoxe de Condorcet, soit très exactement 1/9. C'est fantastique. Je ne suis quand même pas mécontent d'être arrivé à examiner les 13824 triplets de quadruplets posibles afin de voir s'il y a vainqueur de Condorcet. Reste maintenant à comprendre pourquoi ce programme à la con s'obstine à afficher autre chose. Suite au prochain numéro.

Je crois que j'ai enfin trouvé. Je teste la présence de cycle de Condorcet, mais la présence n'est pas incompatible avec le fait qu'il y ait un vainqueur. En effet, prenons 4 candidats. Supposons que D bat A, B, et C, et qu'entre ABC il y ait un cycle ABCABC...Alors mon programme affichera stupidement qu'il y a cycle, tandis que les tables indiquent qu'il y a vainqueur de Condorcet. Je fais les modifications de ce pas.

Miracle! Cela fonctionne.
Je trouve avec 100 000 itérations 0.11187 pour 1/9, ce qui me va parfaitement.
Je me suis aperçu d'ailleurs d'un truc tout bête auquel je n'ai même pas pensé. Je me suis em***dé à écrire ces fichues matrices pour voir à quelle condition il y avait un cycle de condorcet. En fait, il faut raisonner avec l'événement inverse: il n'y a pas cycle de Condorcet quand il y a un vainqueur, et s'il y a vainqueur cela veut dire que la ligne de la matrice est remplie de 1...Il reste, et c'est l'affaire de deux minutes, à programmer le truc pour n'importe quel nombre de candidats et de votants.

Programmation terminée.
Voilà le code définitif pour ceux que cela intéresse:
function s=votcond(m,n,p)%m alternatives, n votants p itérations
compteurgeneral=0;
for k=1:p
matrice=zeros(n,m);
for e=1:n*m
matrice(e)=floor((e-1)/n)+1;
end;
for f=1:n
for g=1:m
z=floor((m+1-g)*rand+g);
c=matrice(f,z);
matrice(f,z)=matrice(f,g);
matrice(f,g)=c;
end;
end;
A=zeros(m,m);
for e2=1:m-1
for f2=e2+1:m
a=0;
for g=1:n
a=a+sign(matrice(g,f2)-matrice(g,e2));
end;
A(e2,f2)=-sign(a);
A(f2,e2)=sign(a);
end;
end;
y=1;
for a1=1:m
    kk=0;
    for a2=1:m
        kk=kk+A(a1,a2);
    end;
    if kk==m-1,y=0;end;
end;
compteurgeneral=compteurgeneral+y;
end;
s=compteurgeneral;

Je sens que je ne vais plus rien faire en maths, ce soir; ah si, les énigmes du forum.

Si! Encore une ultime modif; après, c'est promis, je ne vous embêterai plus.
On devrait rempacer la dernière ligne par: s=compteurgeneral/p pour avoir une proba. En fait, c'est que je travaille avec p=10^m, m entier.

Re,

Sûrement que c'est pas dur à comprendre mais comme je te l'ai dit je n'ai lu qu'en diagonale.

Le fait qu'il y a paradoxe de Condorcet si et seulement si il n'y a pas vainqueur de Condorcet est-il évident ? Dans ce cas en effet, ça correspond à une ligne de 1 pour le vainqueur...

Cette équivalence est évidente ? Pour un nombre quelconque de candidats ?

"Le fait qu'il y a paradoxe de Condorcet si et seulement si il n'y a pas vainqueur de Condorcet est-il évident ?"

En fait c'est douteux. S'il y a paradoxe de Condorcet,A bat B bat C bat A par exemple, il n'y a bien évidemment aucun vainqueur de Condorcet. La réciproque est fausse, à moins de préciser les choses: par exemple, si D bat A, B et C, et qu'il y a cycle entre A, B et C, il y a bien un cycle et un paradoxe entre A, B et C, mais pourtant il y a vainqueur de Condorcet (D). L'ambiguité vient également du fait que je n'ai précisé nulle part ce qu'était précisément le paradoxe de Condorcet. Si on prend l'exemple suivant, y a t-il paradoxe ou non?
Si l'on définit le paradoxe comme existence d'un cycle comprenant tous les candidats, alors on a l'équivalence.
Si on définit qu'il y a paradoxe quand il existe seulement un cycle, alors c'est non.
Mon programme final donne la probabilité qu'il y ait vainqueur de Condorcet, ce qui n'exclut pas l'existence de cycles comprenant une partie des perdants.
Mon programme précédent donnait la probabilité qu'il y eût un cycle de Condorcet, mais cela n'empêchait pas qu'une des personnes ne faisant pas partie du cycle fût vainqueur de Condorcet.
Compris cette fois là?

ah ben ouais il aurait fallu commencer par définir l'événement duquel tu voulais calculer la probabilité...

C'est une remarque pertinente et judicieuse. A ma décharge, pour moi, c'était clair dans mon esprit.