Résumé en français

Le vote par approbation est une procédure de vote utilisée, entre autres, pour élire des comités et qui permet aux votants de voter pour (d’approuver) autant de candidats qu’ils le souhaitent. Deux règles de vote ont été particulièrement utilisées pour élire des comités à l’aide du vote par approbation. La règle habituelle, appelée aussi minisum, choisit l’ensemble des candidats (éventuellement soumis à une contrainte de cardinalité) ayant été approuvés par le plus grand nombre de votants. La règle minimax élit un ensemble de candidats qui minimise le maximum, sur l’ensemble des votants, de la distance de Hamming à chacun des votes. Comme ces deux règles semblent trop extrêmes, nous les généralisons en un ensemble continu de règles de vote, par l’utilisation de l’opérateur de moyenne pondérée ordonnée (ordered weighted averaging, ou OWA). Cette règle est paramétrée par un vecteur de poids, noté w, qui permet de définir des règles de vote entre minisum et minimax. Nous nous intéressons aux vecteurs de poids croissants, et en particulier aux vecteurs de la forme w(i) = (0, .., 0, 1, .., 1), où i représente le nombre de 0. Nous étudions la complexité algorithmique de la détermination d’un comité gagnant, et de l’ensemble des comités gagnants pour des règles associées aux vecteurs w(i). Nous montrons qu’il est difficile de trouver un comité gagnant pour ces règles alors que cela est facile pour minisum. Enfin, nous prouvons la manipulabilité de ces règles quand elles sont paramétrées par des vecteurs croissants, et strictement croissants.