Logo du site
  • English
  • Français
  • Se connecter
Logo du site
  • English
  • Français
  • Se connecter
  1. Accueil
  2. Université de Neuchâtel
  3. Publications
  4. Eliciting Kemeny Rankings
 
  • Details
Options
Vignette d'image

Eliciting Kemeny Rankings

Auteur(s)
George, Anne-Marie
Dimitrakakis, Christos 
Institut d'informatique 
Date de parution
2024
In
TheThirty-Eighth AAAI Conference on Artificial Intelligence (AAAI-24)
De la page
12164
A la page
12171
Résumé
We formulate the problem of eliciting agents’ preferences with the goal of finding a Kemeny ranking as a Dueling Bandits problem. Here the bandits’ arms correspond to alternatives that need to be ranked and the feedback corresponds to a pairwise comparison between alternatives by a randomly sampled agent. We consider both sampling with and without replacement, i.e., the possibility to ask the same agent about some comparison multiple times or not. We find approximation bounds for Kemeny rankings dependant on confidence intervals over estimated winning probabilities of arms. Based on these we state algorithms to find Probably Approximately Correct (PAC) solutions and elaborate on their sample complexity for sampling with or without replacement. Furthermore, if all agents’ preferences are strict rankings over the alternatives, we provide means to prune confidence intervals and thereby guide a more efficient elicitation. We formulate several adaptive sampling methods that use look-aheads to estimate how much confidence intervals (and thus approximation guarantees) might be tightened. All described methods are compared on synthetic data.
Nom de l'événement
AAAI
Lieu
Vancouver
Identifiants
https://libra.unine.ch/handle/123456789/32903
Type de publication
conference proceedings
Dossier(s) à télécharger
 main article: 29105-Article Text-33159-1-2-20240324.pdf (226.37 KB)
Eliciting Kemeny Rankngs
google-scholar
Présentation du portailGuide d'utilisationStratégie Open AccessDirective Open Access La recherche à l'UniNE Open Access ORCIDNouveautés

Service information scientifique & bibliothèques
Rue Emile-Argand 11
2000 Neuchâtel
contact.libra@unine.ch

Propulsé par DSpace, DSpace-CRIS & 4Science | v2022.02.00