Procédures de décision incrémentales pour la décision collective sur domaine combinatoire

L'objet du stage est d'étudier l'apport potentiel de méthodes d'élicitation incrémentales en décision collective. La détermination de la solution optimale dans des problèmes de décision multiagents sur domaine combinatoire est complexe car il faut d'une part éliciter les préférences agents et d'autre part déterminer efficacement une solution "socialement optimale" parmi un ensemble combinatoire de solutions potentielles. Au-delà du traitement séparé de ces deux sujets, il s'agit ici de proposer des procédures incrémentales de décision permettant d'intégrer et combiner l'élicitation des préférences individuelles et la construction de la solution collectivement préférée de manière à identifier la solution optimale avant d'avoir dû complètement spécifier le modèle de décision. Dans ces nouveaux schémas de résolution interactive, le fait de poser des questions sur les préférences des agents en cours de résolution permet de focaliser l'élicitation des préférences sur les informations vraiment utiles pour séparer des solutions concurrentes lors de l'exploration et ainsi de réduire considérablement le nombre de questions nécessaires.

L'élicitation incrémentale est particulièrement intéressante pour la décision sur domaine combinatoire, car on ne peut attendre des agents qu'ils spécifient complètement leurs préférences sur l'ensemble des alternatives. On souhaite donc être capable de construire une solution optimale sur la base d'une spécification partielle des préférences individuelles, en s’efforçant de collecter l'information la plus utile pour discriminer les solutions potentielles du problème. Mais la détermination d'une vainqueur nécessaire ainsi que la l'apprentissage actif des préférences utiles est rendue difficile en raison de la définition implicite de l'ensemble des alternatives. Quelques travaux ont été proposés récemment pour l'élicitation de préférences sur domaine combinatoire (voir par exemple [1]) mais principalement pour des problèmes mono-agent. L'objet du stage est de travailler à l'extension de cette approche sur des problèmes de décision multi-agents. Un certain nombre de travaux récents concernent la détermination de vainqueurs possibles ou nécessaire en décision collective lorsque les préférences des agents sont partiellement connues (voir par exemple [7]). On cherchera ici plus spécifiquement à concevoir et tester des procédures de décision incrémentales visant à enrichir progressivement l'information proférentielle tout en minimisant les coûts de communication avec les agents pour parvenir rapidement à déterminer une solution optimale. Ces approches qui ont déjà montré leur efficacité pour la décision collective sur domaine non-combinatoire [6,3] commencent à être étendues sur domaine combinatoire [2,4,5] Les problèmes combinatoire que l'on envisage d'étudier sous cet angle pourront être par exemple le sac-à-dos multi-agents, le problème de l'élection d'un comité de taille fixée, les problèmes d'affectation équitable.

Bibliographie
--------------

[1] Benabbou N. (2017), "Procédures de décision par élicitation incrémentale de préférences en optimisation multicritère, multi-agents et dans l'incertain", thèse de doctorat, UPMC.

[2] Benabbou, N., Perny, P.: Solving multi-agent knapsack problems using incremental approval voting. In: 22nd European Conference on Articial Intelligence (ECAI'16) (2016).

[3] Benabbou, Di Sabatino Di Diodoro S. , Perny P., Viappiani P.: Incremental Preference Elicitation in Multi-attribute Domains for Choice and Ranking with the Borda Count. SUM 2016: 81-95.

[4] Drummond, J., Boutilier, C.: Elicitation and approximately stable matching with partial preferences. In: IJCAI (2013).

[5] Gelain, M., Pini, M.S., Rossi, F., Venable, K.B., Walsh, T.: Elicitation strategies for soft constraint problems with missing preferences: Properties, algorithms and experimental studies. Articial Intelligence Journal 174(3-4), 270{294 (2010).

[6] Lu, T., Boutilier, C.: Multi-winner social choice with incomplete preferences. In: Proceedings of IJCAI'13. pp. 263{270 (2013).

[7] Xia, L., Conitzer, V.: Determining possible and necessary winners given partial orders. Journal of Articial Intelligence Research (JAIR) 41, 25{67 (2011).