Institut de Recherche sur l'Enseignement des Mathématiques de Paris

Les structures ordonnées sont souvent utilisées, en théorie du vote, pour représenter les préférences individuelles des votants, mais aussi pour modéliser le type de préférence collective que l'on souhaite établir à partir des préférences des votants. Ainsi, la structure bien connue d'ordre total permet de représenter un classement de l'ensemble des candidats sans ex aequo ni incomparabilité.
Dans cet exposé, on s'intéressera plus généralement au problème suivant. Etant donné un ensemble fini X de n candidats et une collection C de m relations binaires définies sur le produit cartésien de X avec lui-même et représentant les préférences de m votants (par exemple des ordres totaux), comment déterminer le vainqueur de l'élection ou, mieux encore, comment établir un classement des candidats traduisant le mieux possible les préférences des votants ?
Un exemple introductif permettra à la fois de donner un bref aperçu historique de la question et de montrer que le mode de scrutin retenu joue un rôle non négligeable dans la détermination du vainqueur. On rencontrera au passage un certain nombre de "paradoxes", dont le fameux "effet Condorcet" (aussi appelé "paradoxe du vote") qui correspond au fait que l'agrégation d'ordres totaux selon la règle majoritaire n'aboutit pas toujours en un ordre total, mais en une autre structure appelée "tournoi" (quand il n'y a pas d'ex aequo). Outre les tournois, on décrira aussi d'autres types de structures ordonnées pouvant être utilisées pour modéliser des préférences, par exemple les "préordres totaux" (modélisant des classements dans lesquels on admet des ex æquo mais non l'incomparabilité). On évoquera ensuite le théorème d'Arrow, parfois appelé "théorème d'impossibilité" puisqu'il indique qu'il est impossible de satisfaire simultanément certains axiomes pourtant souvent considérés comme tout à fait souhaitables.
On finira par quelques approches classiques permettant d'échapper au résultat d'impossibilité d'Arrow. On abordera ainsi le cas où les préférences des votants sont supposées appartenir à une catégorie particulière d'ordres totaux, appelés "ordres unimodaux", catégorie qui échappe systématiquement au paradoxe du vote mis en évidence par Condorcet. On décrira aussi la procédure médiane, consistant à minimiser le nombre total de désaccords entre le résultat cherché et les préférences exprimées par les votants. Si le temps le permet, on établira un résultat récent stipulant que, si les préférences individuelles sont des ordres totaux, il existe toujours un préordre total médian qui soit un ordre total.