Heuristique de reconnaissance des préférences 2-Euclidiennes
Magdalena Tydrichova  1@  , Olivier Spanjaard  1@  , Bruno Escoffier  1@  
1 : Le laboratoire d'informatique de Sorbonne Université (LIP6)
Sorbonne Université, Centre National de la Recherche Scientifique : UMR7606

Nous proposons une heuristique de reconnaissance de préférences 2-Euclidiennes. U profil de préférences d'un ensemble de votants sur un ensemble de votants est 2-Euclidien si on peut placer les votants et les candidats dans un plan d'une manière à ce que la préférence de chaque votant diminue avec la distance euclidienne entre les positions (autrement dit, plus proche un votant se trouve d'un candidat, plus il préfère ce dernier).

Notre heuristique, basée sur des propriétés géométriques du problème, décide si le profil en entrée est 2-Euclidean ou pas, ou, si la réponse n'est pas trouvée dans le temps imparti, classe le profil en tant que "indécidé".

L'heuristique décide, pour 95% des profils du monde réel disponibles sur Preflib, s'ils sont Euclidiens ou non. Sa performance semble meilleure que celle des autres approches existantes: à titre de comparaison, nous avons conçu un programme quadratique sous Gurobi qui ne peut reconnaître qu'une très faible proportion des profils reconnus à l'aide de l'heuristique. En plus de cela, une transition de phase a été observée pour ce problème, et nous avons pu avoir quelques éléments de réponses à des questions plus théoriques.


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