Soit r un reel entre 1/2 et 1. Soit V un ensemble de votants et
E un ensemble d'elus. Chaque votant propose une permutation de E (liste
de preference).
Le resultat du vote consiste en un graphe oriente D dans lequel on
ajoute les aretes (e,e') lorsque e et e' sont des
elus pour lesquels e a ete prefere a e' dans plus de r|V| permutations.
Le cas r=1/2 correspondant a la majorite
simple.
Je ferai d'abord un petit survol sur les graphes de majorite pour r
quelconque. Ensuite, dans le cas de majorite simple avec nombre impair
de votant, i.e. lorsque D est un tournoi, je montrerai qu'il
est NP-difficile de trouver une liste L qui s'accorde le plus possible
avec le choix des votants, en ce sens qu'elle maximise le nombre
d'aretes (e,e') de D pour lesquelles e est avant e' dans L.
Travail en collaboration avec A. Yeo et P. Charbit, en reponse
a une question de J. Bang-Jensen et C. Thomassen.