La règle de Kemeny est une règle de vote cherchant à retourner un classement complet des candidats le plus proche possible des préférences des votants. Pour cela, chaque votant donne ses préférences sous la forme d'un classement complet des candidats. Le classement de consensus de Kemeny, noté C*, est le classement qui minimise la distance totale aux préférences, exprimée comme le nombre de paire de candidats ordonnés différemment dans C* et dans les préférences. La règle de Kemeny possèdent beaucoup de propriétés intéressantes d'un point du vue théorique, cependant, il est difficile de trouver le classement de Kemeny de consensus et les algorithmes de résolution exacte sont de complexité exponentielle. Une approche semble cependant permettre de résoudre certaines instances de grande taille : l'approche par décomposition.
Les étudiants devront implémenter dans un langage de programmation au choix les méthodes de décomposition suivantes : règle des 3/4 et critère de Condorcet étendu. Ces deux critères séparent l'instance de base, i.e., l'ensemble des candidats à classer, en sous-groupes. Il suffit alors de résoudre le problème sur les sous-groupes puis de concaténer les résultats pour obtenir un classement complet. Il faudra également implémenter des méthodes pour résoudre le problème sur les sous-groupes en utilisant la programmation linéaire et la programmation dynamique. Une fois ces méthodes implémentées, il faudra les tester sur des instances réelles et synthétiques afin de tester leur efficacité et les comparer entre elles.
Adresse mail de contact: martin.durand@lip6.fr