Social ranking : élicitation pour la détermination du vainqueur nécessaire à partir d'information incomplète
Sébastien Konieczny  1@  , Stefano Moretti  2@  , Ariane Ravier  3@  , Paolo Viappiani  3@  
1 : Centre de Recherche en Informatique de Lens
Université d'Artois : UMR8188, Centre National de la Recherche Scientifique : UMR8188
2 : Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision
Université Paris-Dauphine, Centre National de la Recherche Scientifique : UMR7024
3 : Laboratoire dánalyse et modélisation de systèmes pour láide à la décision
Centre National de la Recherche Scientifique : UMR7243 / FRE3234 / UMR7024, Université Paris Dauphine-PSL, Centre National de la Recherche Scientifique : UMR7024, Centre National de la Recherche Scientifique

Le problème de \textit{social ranking}, appliqué à une population donnée $X$, se base sur un ordre total $\mathcal{R}$ sur l'ensemble des coalitions pouvant être formées à partir de cette population (noté $\mathcal{P}(X)$). Cet ordre représente des préférences à partir desquelles on cherche ensuite à déterminer un ordre total sur les individus de la population. Plusieurs méthodes de résolution ont été proposées dans divers travaux antérieurs \cite{HaHoMoOz, khani2019ordinal}, notamment la \textit{lex-cel} \cite{algaba2021lexicographic, beal2021exicographic}, qui valorise la présence d'éléments dans les meilleures coalitions de l'ordre exprimé.\par
Dans certaines situations, il peut être considéré suffisant de pouvoir déterminer l'individu préféré, \textit{i.e.} le meilleur élément du classement sur les individus \cite{SUM22}.\par
La principale limite de ce problème est relative à la taille des données d'entrée. En effet, l'ensemble $\mathcal{P}(X)$ croît de manière exponentielle avec la taille de $X$. Aussi, demander à une personne d'exprimer ses préférences sur un ensemble si large représente rapidement un lourd effort cognitif. Plus généralement, il peut être plus facile de manipuler plusieurs sous-ordres partiels de petite taille que l'ordre total de taille $2^X$. Pour cette raison, on choisit de se placer dans un cadre particulier du problème de \textit{social ranking}, où l'on suppose qu'il existe un ordre total sur $\mathcal{P}(X)$, mais que l'on ne dispose que de sous-ensembles de cet ordre, appelés \textit{sous-classements}. Dans le cas où ceux-ci ne seraient pas assez informatifs pour déterminer le vainqueur nécessaire dans notre population, on propose d'étudier différentes méthodes d'élicitation pour atteindre une connaissance suffisante pour déterminer l'individu vainqueur.


Personnes connectées : 2 Vie privée
Chargement...