• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

Vote par approbation pour les élections à vainqueurs multiples. Une famille générale de règles, leur complexité algorithmique et leur manipulabilité

Barrot, Nathanaël; Lang, Jérôme; Ries, Bernard (2015), Vote par approbation pour les élections à vainqueurs multiples. Une famille générale de règles, leur complexité algorithmique et leur manipulabilité, Revue d'Intelligence Artificielle, 29, 3-4, p. 265-291. 10.3166/RIA.29.265-291

Type
Article accepté pour publication ou publié
Date
2015
Journal name
Revue d'Intelligence Artificielle
Volume
29
Number
3-4
Pages
265-291
Publication identifier
10.3166/RIA.29.265-291
Metadata
Show full item record
Author(s)
Barrot, Nathanaël
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Lang, Jérôme
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Ries, Bernard
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (FR)
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.
Abstract (EN)
Approval voting is a well-known voting procedure used, among others, for electing committees, where each voter casts a ballot consisting of a set of approved candidates (without any cardinality constraint). Two prominent rules for electing committees using approval voting are the standard rule (also called minisum), which selects the set of candidates (possibly subject to some cardinality constraint) with the highest number of approvals, and the minimax rule, where the set of elected candidates minimizes the maximum, over all voters, of the Hamming distance to the voter’s ballot. As these two rules are in some way too extreme, we generalize them into a continuum of rules, by using ordered weighted averaging operators (OWA). The rule is parameterized by a weight vector w, which allows us to model voting procedures between minisum and minimax. We focus on non decreasing weight vectors, and in particular, vectors of the form w(i) = (0; ::; 0; 1; ::; 1), where i is the number of 0’s. We address the computational aspects of finding a winning committee and all the winning committees for rules associated with the w(i) vectors. We show that finding a winning committee for these rules is NP-hard whereas it is computationally easy for minisum. Finally, we address the issue of manipulating the rules when parameterized by non decreasing and strictly increasing weight vectors.
Subjects / Keywords
computational social choice; approval voting; ordered weighted averaging; computational complexity; manipulation; choix social computationnel; vote par approbation; moyenne pondérée ordonnée; complexité algorithmique

Related items

Showing items related by title and author.

  • Thumbnail
    Multiple Referenda and Multiwinner Elections Using Hamming Distances: Complexity and Manipulability 
    Amanatidis, Georgios; Barrot, Nathanaël; Lang, Jérôme; Markakis, Evangelos; Ries, Bernard (2015) Communication / Conférence
  • Thumbnail
    Approval Voting for Committee Elections : a General Family of Rules 
    Barrot, Nathanaël; Lang, Jérôme; Ries, Bernard (2014) Communication / Conférence
  • Thumbnail
    Manipulation of Hamming-based Approval Voting for Multiple Referenda and Committee Elections 
    Barrot, Nathanaël; Lang, Jérôme; Yokoo, Makoto (2017) Communication / Conférence
  • Thumbnail
    Possible Winners in Approval Voting 
    Barrot, Nathanaël; Gourvès, Laurent; Lang, Jérôme; Monnot, Jérôme (2013) Communication / Conférence
  • Thumbnail
    Conditional and Sequential Approval Voting on Combinatorial Domains 
    Barrot, Nathanaël; Lang, Jérôme (2016) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo