• 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

Winner determination in voting trees with incomplete preferences and weighted votes

Thumbnail
Date
2012
Dewey
Recherche opérationnelle
Sujet
Social choice; Voting trees; Incompleteness; Winner determination
JEL code
C44
Journal issue
Autonomous Agents and Multi-Agent Systems
Volume
25
Number
1
Publication date
07-2012
Article pages
130-157
Publisher
Kluwer Academic Publishers
DOI
http://dx.doi.org/10.1007/s10458-011-9171-8
URI
https://basepub.dauphine.fr/handle/123456789/16412
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Lang, Jérôme
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Pini, Maria Silvia
status unknown
Rossi, Francesca
status unknown
Salvagnin, Domenico
status unknown
Venable, Kristen Brent
status unknown
Walsh, Toby
status unknown
Type
Article accepté pour publication ou publié
Abstract (EN)
In multiagent settings where agents have different preferences, preference aggregation can be an important issue. Voting is a general method to aggregate preferences. We consider the use of voting tree rules to aggregate agents’ preferences. In a voting tree, decisions are taken by performing a sequence of pairwise comparisons in a binary tree where each comparison is a majority vote among the agents. Incompleteness in the agents’ preferences is common in many real-life settings due to privacy issues or an ongoing elicitation process. We study how to determine the winners when preferences may be incomplete, not only for voting tree rules (where the tree is assumed to be fixed), but also for the Schwartz rule (in which the winners are the candidates winning for at least one voting tree). In addition, we study how to determine the winners when only balanced trees are allowed. In each setting, we address the complexity of computing necessary (respectively, possible) winners, which are those candidates winning for all completions (respectively, at least one completion) of the incomplete profile. We show that many such winner determination problems are computationally intractable when the votes are weighted. However, in some cases, the exact complexity remains unknown. Since it is generally computationally difficult to find the exact set of winners for voting trees and the Schwartz rule, we propose several heuristics that find in polynomial time a superset of the possible winners and a subset of the necessary winners which are based on the completions of the (incomplete) majority graph built from the incomplete profiles.

  • 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.