• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Possible Winners in Approval Voting

Thumbnail
Date
2013
Dewey
Intelligence artificielle
Sujet
Computational social choice; Approval voting; Voting under incomplete knowledge; Computational complexity
DOI
http://dx.doi.org/10.1007/978-3-642-41575-3_5
Conference name
Third International Conference, ADT 2013
Conference date
11-2013
Conference city
Bruxelles
Conference country
Belgium
Book title
Algorithmic Decision Theory
Author
Perny, Patrice; Pirlot, Marc; Tsoukiàs, Alexis
Publisher
Springer
Publisher city
Berlin Heidelberg
Year
2013
Pages number
439
ISBN
978-3-642-41574-6
Book URL
10.1007/978-3-642-41575-3
URI
https://basepub.dauphine.fr/handle/123456789/16124
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Barrot, Nathanaël
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Gourvès, Laurent
status unknown
Lang, Jérôme
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Monnot, Jérôme
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Type
Communication / Conférence
Item number of pages
57-70
Abstract (EN)
Given the knowledge of the preferences of a set of voters over a set of candidates, and assuming that voters cast sincere approval ballots, what can we say about the possible (co-)winners? The outcome depends on the number of candidates each voter will approve. Whereas it is easy to know who can be a unique winner, we show that deciding whether a set of at least two candidates can be the set of co-winners is computationally hard. If, in addition, we have a probability distribution over the number of candidates approved by each voter, we obtain a probability distribution over winners; we study the shape of this probability distribution empirically, for the impartial culture assumption. We study variants of the problem where the number of candidates approved by each voter is upper and/or lower bounded. We generalize some of our results to multiwinner approval voting.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.