Les fréquences de violation de la symétrie inverse par les règles positionnelles 

Télécharger le fichier pdf d’un mémoire de fin d’études

Les options (candidats)

Cet ensemble est aussi habituellement connu sous le nom d’ »états so-ciaux », et ses éléments peuvent s’interpréter comme des candidats à une élection, des allocations dans une économie, des projets d’investissement, etc. Dans cette thèse, les termes « candidats », « options » ou encore « alternatives » sont utilisés de manière équivalente, et ils seront désignés par des lettres en minuscules.

La nature des préférences

La très grande majorité des travaux en théorie du choix social prennent pour hypothèse de base que les préférences exprimées par les individus peuvent être décrites à l’aide de relations binaires sur l’ensemble des options. Selon cette ap-proche, on suppose implicitement que les individus ont une perception des options en termes de classement. A côté de cette approche, d’autres travaux admettent que les individus sont capables de mesurer la distance qu’ils établissent entre les options. On a ainsi, en résumé, deux types d’approche :
– d’un côté une approche ordinale qui correspond à une mesure qualitative des préférences des individus ;
– et de l’autre côté une approche cardinale qui correspond à une mesure quantitative de ces préférences.
Nous nous inscrirons dans cette thèse dans le cadre de l’approche ordinale.
Cette approche des préférences individuelles est la plus courante en théorie du choix social, et elle peut se combiner avec la comparabilité ou avec la non-comparabilité entre les individus. Selon Hillinger [74] et Balinski et Laraki [6], les préférences or-dinales représentent la principale source des paradoxes de vote dans la théorie du choix social ; c’est la raison pour laquelle ces auteurs rejettent les systèmes de vote reposant sur les classements individuelles, et proposent des systèmes avec des préfé-rences cardinales qui prennent en considération les intensités des préférences entre les options, comme les méthodes d’agrégation basées sur le principe d’évaluation 1 (vote par note ou vote par valeur).
On notera ainsi que si les fonctions d’utilité collective de Bergson [9] et Samuelson [156] sont le point de départ de la réflexion d’Arrow, c’est l’occasion d’une rupture méthodologique importante où l’utilité ne s’exprime plus directement ; elle ne sert que a fondée les préférences.

Les relations binaires

Il est imposé aux votants d’exprimer leurs opinions en utilisant tous la même structure de préférences. Les préférences des votants sont généralement li-mitées à des structures assez simples, c’est-à-dire qu’un votant peut avoir un ou plusieurs candidats préférés, un classement avec ou sans ex æquo sur l’ensemble des candidats. Depuis les travaux d’Arrow [3, 4] dans le domaine de la théorie du choix social, les préférences sont fondées sur des relations binaires définies sur l’ ensemble des options, et ces relations possèdent des propriétés plus ou moins fortes. Les deux structures auxquelles nous allons nous intéresser plus particulièrement sont les ordres complets et les pré-ordres complets.
Nous allons utiliser les notations suivantes : N = {1, 2, . . . , n} est une société composée d’un ensemble fini d’individus ou vo-tants, avec n ≥ 2.
A = {a1, a2, a3, ……, am} est un ensemble fini d’options.
Par souci de simplicité, nous pourrons utiliser des lettres minuscules a, b, c… sans les indices pour désigner les options.

Une relation binaire

Une relation binaire R permet de créer un lien entre deux éléments d’un ensemble donné, le terme de relation binaire vient du fait que la relation considérée compare les éléments deux à deux. Définition 1.1.1 : une relation binaire R est un ensemble de couples (a, b) avec a, b ∈ A. Plus proprement dit, R est définie par une partie G du produit cartésien A×A.
Si (a, b) ∈ G, on dit que a est en relation avec b et on le note aRb, et si (a, b) ∈/ G, on dit que a n’est pas en relation avec b et on note ¬aRb .
Nous interpénétrons la relation aRb comme signifiant l’option « a est au moins aussi bonne que l’option b ».
Les relations binaires utilisées en choix social peuvent satisfaire, ou non, diverses propriétés, parmi lesquelles :
√ La réflexivité. Une relation binaire R sur un ensemble A est dite réflexive si : ∀a ∈ A, aRa.
C’est la situation dans laquelle une option est comparée avec elle-même, c’est-à-dire que l’option a est au moins aussi bonne qu’elle-même.
√ La complétude. Une relation binaire R sur un ensemble A est dite complète si : aRb ou aRb.

Préférences individuelles et décisions collectives

Une façon générale et abstraite de formuler le problème du choix social consiste à considérer l’ensemble des mécanismes qui permettent le passage des pré-férences individuelles à une décision collective. On s’intéresse alors aux propriétés que l’on souhaite voir ces mécanismes vérifier.
Une autre façon, plus pratique, consiste à examiner des procédures particulières, des procédures de vote par exemple, et à mettre en lumière les avantages et les incon-vénients de ces procédures.
Dans cette section, après quelques rappels rapides sur le premier type de méca-nismes, nous expliquerons le fonctionnement d’un certain nombre de procédures de vote.
Bergson et Samuelson ont introduit, de façon indépendante, vers la fin des années 1930 et au début des années 1940, la notion de fonction d’utilité collective (FUC), qui a pour variables les utilités u1, …, un des individus de 1, . . . , n. Cependant, en théorie du choix social la notion de fonction d’utilité collective la plus utilisée est celle proposée par Arrow [3, 4]. C’est le mécanisme qui permet de transformer les préférences individuelles (supposées être des pré-ordres complets) en un pré-ordre complet collectif. Par souci de simplicité, nous allons restreindre la définition de la fonction d’utilité aux relations d’ordre.
Plus formellement, on a la définition suivante :
Définition 1.2.6 Une fonction d’utilité collective FUC f sur l’ensemble A est une fonction définie sur L(A)n et à valeurs dans L(A) : f : L(A)n → L(A). (1.1)
Étant donné l’ensemble fini L(A) de tous les ordres linéaires possibles sur A et l’en-semble L(A)n des profils possibles sur l’ensemble A pour n individus, une fonction d’utilité collective f est une application qui à chaque liste de pré-ordres (ici des ordres) individuels complets associe un pré-ordre (ordre) complet au niveau collec-tif.
La fonction précédente ne fera pas l’objet d’étude dans cette thèse, nous nous inté-ressons seulement à la détermination d’une seule ou de plusieurs options gagnantes pour chaque profil. Pour choisir un sous-ensemble d’options, il faut opter pour une correspondance de choix collectif (CCC). Autrement dit, le mécanisme de décision collective désigne un ensemble d’options gagnantes appartenant à A.

Agrégation des préférences : les procédures de vote

Dans la plupart des sociétés modernes, le vote est une façon généralement admise de prendre des décisions qui concernent l’ensemble des membres de la société. Ces règles peuvent être regroupées selon des critères variés, mais un critère classique consiste à distinguer, ainsi que nous l’avons déjà mentionné dans l’introduction géné-rale, d’une part les règles dérivées de l’approche de Condorcet, et d’autre part celles qui reposent sur le principe de Borda. Nous présentons ci-dessous les principales règles qui vont constituer l’objet d’étude de cette thèse.

Le principe de la décision à la majorité.

Ce principe est considéré comme étant l’un des fondements de la réflexion sur les règles de vote. Il a joué dès l’origine un rôle très important dans l’histoire de la théorie du choix social ; son principe est basé sur une comparaison par paires. Par exemple, pour un ensemble d’individus qui doivent choisir entre uniquement deux options a et b, cette méthode constitue un processus attrayant pour désigner un vainqueur (voir le théorème de May évoqué dans l’introduction générale) ; on dit qu’une option a est préférée à la majorité à une option b si le nombre de votants qui préfèrent a à b est supérieur à celui de ceux qui préfèrent b à a. Dès les premières analyses systématiques des règles de vote, Condorcet [30] a utilisé ce principe dans le cas d’un nombre quelconque d’options, pour rechercher la meilleure option pour la société, avec la notion de vainqueur de Condorcet, présentée plus bas dans ce texte.
Le vainqueur de Condorcet
Le vainqueur de Condorcet est le candidat qui l’emporte contre chacun des autres candidats dans les duels majoritaires ; en d’autres termes, à partir des préférences exprimées par les individus, on prend les candidats deux à deux, et on les compare à la majorité ; une fois que ces « duels » sont terminés, on recherche le candidat qui l’emporte sur chacun des autres ; si candidat existe, alors c’est le vainqueur de Condorcet. Le paradoxe de Condorcet consiste précisément à dire que dans certains cas, même avec des préférences individuelles qui sont des ordres linéaires (ou ordres complets), un tel candidat peut ne pas exister. On a alors un cycle majoritaire. Nous apportons davantage de précisons sur ces possibilités dans des exemples présentés ci-dessous.
Définition 1.2.9 Soit un profil π. L’option a est désignée comme vainqueur de Condorcet si : ∀b ∈ A, nab(π) > nba(π). (1.4)

Les paradoxes produits sans aucune modification

Ces paradoxes apparaissent sans aucune modification dans les notions fondamentales définies par Nurmi, c’est-à-dire ni dans les préférences individuelles ni dans l’ensemble des options. Le profil en lui-même contient un paradoxe : ce sont donc les défauts intrinsèques des règles qui conduisent à des résultats inattendus.
Le paradoxe de Condorcet, pour rappel, peut se produire lorsque l’utilisation de la méthode de décision à la majorité (vote à la majorité sur toutes les paires possibles d’options) conduit à l’intransitivité des préférences collectives formées par l’agrégation des préférences individuelles transitives.
Le paradoxe de Borda se réfère à deux défauts dans la règle de la pluralité :
(i) il peut mener à l’élection d’un candidat qui serait battu par tous les autres can-didats dans une comparaison par paires avec une majorité de votes (le perdant de Condorcet) et (ii) il peut échouer à élire un candidat qui battrait tous les autres avec une majorité de votes (le vainqueur de Condorcet).
La violation de critère de Pareto concerne la situation dans laquelle un candidat est élu, alors que tous les votants lui préfèrent un autre candidat. Pour illustrer cette situation, considérons la règle de vote par amendements. Cette procédure fonctionne de la manière suivante :
On prend les options deux à deux selon un ordre prédéterminé appelé agenda ; par exemple, pour l’agenda abcd, on compare d’abord a et b à la majorité, puis le vain-queur de ce duel est opposé à c, et enfin le vainqueur de cette confrontation rencontre d dans un dernier duel majoritaire ; le vainqueur final est l’option qui remporte le dernier duel majoritaire.
Exemple 1.3.4 Soit un nombre de votants n = 3 et quatre options {a, b, c, d}, les préférences des votants sont présentées dans le profil π.

Les paradoxes liés à une modification qui affecte les votants

Ces paradoxes se produisent lorsque des changements sont portés sur les votants mêmes comme par exemple leur nombre ou bien leur comportement.
Le paradoxe de l’abstention (No-show paradox dans la terminologie anglo-saxonne) proposé par S. Brams et P. Fishburn [59] il est possible qu’une partie de l’électorat soit satisfaite du résultat de vote en s’abstenant plutôt qu’en participant au vote. En d’autres termes, ce paradoxe met en question la rationalité de la participation au vote. Il faut signaler qu’en théorie du choix social, le terme No-show est utilisé pour regrouper plusieurs paradoxes, comme le paradoxe de la participation positive, de la participation négative, de l’abstention positive ou de l’abstention négative (voir par exemple Mbih Zhao [100]).
Pérez [131] et Nurmi [121] considèrent deux cas spéciaux de No-Show paradox ; le premier cas se produit lorsqu’un bulletin de vote qui classe un candidat premier cause la perte de l’élection de ce dernier. L’autre surgit lorsqu’un bulletin de vote qui classe un candidat dernier conduit à le désigner comme vainqueur de l’élection. L’un ou les deux cas spéciaux sont aussi traités par Richelson [141], Smith [166], Brams et Fishburn [59], Saari [148] ou Lepelley et Merlin [93].
Moulin définit ce paradoxe comme étant une situation où l’addition d’un bulle-tin de vote qui classe le candidat a au-dessus du candidat b peut remettre en cause la victoire de a et faire gagner b. Moulin [1988] a démontré que ce paradoxe est susceptible de se produire lorsqu’on applique une règle qui respecte le principe de Condorcet (elle sélectionne le vainqueur de Condorcet quand celui-ci existe) dans le cas de quatre candidats ou plus ; en d’autres termes, cela conduit soit à rejeter le vainqueur de Condorcet, soit à s’exposer à ce paradoxe. Cependant, ce paradoxe n’apparait pas avec les règles positionnelles simples.
Une variante de ce paradoxe a été développée par Bouyssou et Perny [16] et qui l’ont appelé le paradoxe du pêcheur à la ligne : un votant peut être satisfait du résultat en choisissant d’aller se faire plaisir (pêcher par exemple) que d’aller voter.
Ces paradoxes se produisent à la suite d’une addition ou une élimination des préfé-rences d’un certain nombre de votants, par conséquent, cela affecte le profil lui même.
L’homogénéité est vérifiée par une règle de vote si la réplication du nombre de votants d’un profil donné permet toujours d’avoir le même vainqueur qu’avec le pro-fil initial (avant réplication). Certaines procédures de vote violent cette propriété et conduisent à avoir un phénomène inattendu. Le dernier chapitre de cette thèse est consacré à l’examen de cette propriété sur la règle de Dodgson.

Les paradoxes liés à une modification qui affecte les candidats

Un paradoxe qui appartient à cette classe, connu sous le nom de pa-radoxe de l’ordre inverse (« The inverted-order paradox »), a été introduit par Davidson et Odeh [33], et touche en particulier la méthode de Borda. Ce paradoxe est susceptible de se produire si la suppression d’un candidat vainqueur et la répé-tition de la même procédure de vote conduit à inverser complètement l’ordre des candidats restants sans pour autant modifier les préférences initiales des votants. L’exemple suivant vient illustrer ce paradoxe.
Exemple 1.3.7 Soit un nombre de votants n = 7 et quatre options {a, b, c, d}, les préférences des votants sont présentées dans les profil π.

Les fréquences de violation de l’axiome de symétrie inverse sous les règles positionnelles en domaine universel

Aprés avoir défini les différentes structures des systèmes d’inéquations concernant chacune des règles de vote postionnelles simples et à deux tours, il sera question dans cette sous-section de calculer le nombre de situations dans lesquelles le vainqueur dans le profil π est le même dans le profil inverse π−1, avec trois candidats {a, b, c} et le domaine universel.
Pour calculer le nombre de situations conduisant au paradoxe, et les fréquences cor-respondantes, nous procédons de la manière suivante. Chaque système est écrit de façon à former un ensemble disjoint avec les autres systèmes du même sous-problème (a vainqueur, b vainqueur ou c vainqueur). La technique utilisée consiste à calculer le nombre de solutions entière de chaque système d’inéquations. Nous suivons en cela la méthode initiée par Gehrlein et Fisburn [67], méthode dont Mbih, Moyouwou et Andjiga [1] montrent les relations avec les polynômes d’Ehrhart. A ce sujet, il faut aussi signaler le travail de Lappeley, Louichi et samaoui [89]. En 2007, Moyouwou a ensuite écrit l’ensemble de la procédure de calcul sous la forme des codes dans le logiciel Maple, ce qui permet de faire des calculs en un temps relativement réduit ( quand ces calculs sont possibles).

Table des matières

Introduction générale
1 Une typologie des paradoxes du vote 
1.1 Introduction
1.1.1 La présentation des préférences
1.1.2 La nature des préférences
1.1.3 Les relations binaires
1.1.4 Profil et situation de vote
1.2 Préférences individuelles et décisions collectives
1.2.1 Agrégation des préférences : les procédures de vote
1.3 Quelques paradoxes de la théorie du choix social
1.3.1 Les paradoxes produits sans aucune modification
1.3.2 Les paradoxes liés à une modification qui affecte le profil
1.3.3 Les paradoxes liés à une modification qui affecte les votants
1.3.4 Les paradoxes liés à une modification qui affecte les candidats
1.4 Conclusion
2 Chapitre 2 : Les fréquences de violation de la symétrie inverse par les règles positionnelles 
2.1 Introduction
2.2 Notation et présentation
2.2.1 Préférences
2.2.2 Les règles de vote
2.3 Domaine universel
2.3.1 Cas de trois candidats
2.3.2 Cas de quatre candidats
2.3.3 Cas infini
2.4 Domaine restreint
2.4.1 Cas de trois candidats
2.4.2 Cas de quatre candidats
2.4.3 Cas infini
2.5 Conclusion
3 Chapitre 3 : Axiome d’homogénéité et règle de Dodgson 
3.1 Introduction
3.2 Notation et définitions
3.2.1 La règle de vote
3.3 Le calcul du score de Dodgson
3.3.1 Un seul duel majoritaire perdu
3.3.2 Deux duels majoritaires perdus
3.3.3 Trois duels majoritaires perdus
3.4 Violation de l’homogénéité par la règle de Dodgson
3.4.1 Résultats préliminaires
3.4.2 Domaine universel
3.4.3 Domaine restreint
3.5 Conclusion
Conclusion générale 
Annexes 
Références 

Télécharger le rapport complet