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

Afficher

Cette collectionPar Date de CréationAuteursTitresSujetsNoms de revueToute la baseCentres de recherche & CollectionsPar Date de CréationAuteursTitresSujetsNoms de revue

Mon compte

Connexion

Statistiques

Afficher les statistiques d'usage

Possible and Necessary Winners of Partial Tournaments

Thumbnail
Date
2015
Indexation documentaire
Recherche opérationnelle
Subject
computational social choice
Nom de la revue
The Journal of Artificial Intelligence Research
Volume
54
Date de publication
12-2015
Pages article
493-534
Nom de l'éditeur
Morgan Kaufmann Publishers
DOI
http://dx.doi.org/10.1613/jair.4856
URI
https://basepub.dauphine.fr/handle/123456789/16161
Collections
  • LAMSADE : Publications
Métadonnées
Afficher la notice complète
Auteur
Aziz, Haris
134757 University of South Wales
Brill, Markus
status unknown
Fischer, Felix
Harrenstein, Paul
98120 Oxford University
Lang, Jérôme
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Seedig, Hans Georg
109286 Department of Informatics of the Technische Universität München
Type
Article accepté pour publication ou publié
Résumé en anglais
We study the problem of computing possible and necessary winners for partially specified weighted and unweighted tournaments. This problem arises naturally in elections with incompletely specified votes, partially completed sports competitions, and more generally in any scenario where the outcome of some pairwise comparisons is not yet fully known. We specifically consider a number of well-known solution concepts---including the uncovered set, Borda, ranked pairs, and maximin---and show that for most of them, possible and necessary winners can be identified in polynomial time. These positive algorithmic results stand in sharp contrast to earlier results concerning possible and necessary winners given partially specified preference 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

 Cette création est mise à disposition sous un contrat Creative Commons.