TYDRICHOVA Magdaléna

PhD student
Team : DECISION
Arrival date : 10/01/2019
    Sorbonne Université - LIP6
    Boîte courrier 169
    Couloir 26-00, Étage 4, Bureau 413
    4 place Jussieu
    75252 PARIS CEDEX 05
    FRANCE

Tel: +33 1 44 27 87 38, Magdalena.Tydrichova (at) nulllip6.fr
https://lip6.fr/Magdalena.Tydrichova
Algorithmique des préférences structurées en décision collective : reconnaissance et optimisation

Préférences structurées. Une base de préférences consiste en la donnée d'un ensemble de vecteurs caractéristiques, décrivant typiquement des individus, et des préférences de ces individus sur un même ensemble d'objets (ouvrages, films, produits technologiques, candidats à une élection, etc.), préférences exprimées sous la forme d'un rangement. Les préférences sont dites structurées si elles s'articulent autour d'une structure commune sur les objets. Par exemple, dans un contexte politique, il est classique de supposer que les préférences de chaque individu sont décroissantes lorsque l'on s'éloigne de son candidat préféré le long d'un axe gauche-droite sur les candidats, axe sur lequel les individus s'accordent tous.
Les préférences structurées ont fait l'objet de nombreux travaux en théorie du choix social. La contribution la plus célèbre est dûe à Duncan Black [1], qui a introduit les préférences unimodales, s'articulant autour d'un axe commun comme décrit dans le paragraphe précédent. Black a montré que si les préférences sont unimodales, alors le théorème d'impossibilité d'Arrow ne s'applique plus (c'est-à-dire qu'il existe une règle de vote satisfaisant un ensemble de propriétés souhaitables, et pourtant impossibles à satisfaire simultanément sans hypothèse sur les préférences). Par la suite, d'autres structures de préférences ont été proposées et étudiées : préférences unimodales sur un arbre [3], sur un cycle [7], préférences Euclidiennes [6]...
Objectifs de la thèse. Cette thèse vise à étudier les structures de préférences du point de vue de l'algorithmique, tant au niveau de la complexité de la reconnaissance d'une structure que de la complexité de problèmes de vote ou d'allocation de ressources avec préférences structurées (par exemple, problèmes de détermination d'un vainqueur, d'élection d'un comité, de couplages avec préférences, de partage équitable).
Reconnaissance. Même si divers travaux dans la littérature ont abordé le problème de la reconnaissance de structures [3,5,6,7], les structures de préférences étudiées, malgré leur pertinence théorique, se rencontrent rarement en pratique car elles supposent que les préférences vérifient des conditions très fortes. Par exemple, pour remettre en cause une structure unimodale de préférences, il suffit d'un individu dont les préférences divergent très légèrement d'un axe sur lequel tous les autres individus s'accordent. La plupart des algorithmes de reconnaissance proposés jusqu'à aujourd'hui ne permettent pas d'identifier une structure de préférences si elle n'est pas vérifiée au sens strict. Une des directions de recherche de la thèse visera à remédier à cet inconvénient, par l'introduction d'une fonction objectif mesurant la distance à une structure. Des travaux récents existent dans cette direction [4], mais il reste beaucoup à faire.
Optimisation. Certains problèmes de décision collective qui sont NP-difficiles dans le cas général peuvent devenir de complexité polynomiale pour des structures particulières de préférences [2,7]. Ce type de résultats est d'autant plus utile si les structures étudiées se rencontrent facilement en pratique. Il sera donc intéressant d'étudier si les structures proposées dans cette thèse permettent de réduire la complexité de certains problèmes de décision collective. De plus, quand bien même le statut de complexité d'un problème reste inchangé, il reste possible d'envisager de tirer parti d'une structure de préférences pour développer des algorithmes plus efficaces de résolution.
Références [1] D. Black (1948) "On the rationale of group decision making". Dans The Journal of Political Economy, 56(1):23-34. [2] D. Cornaz, L. Galand et O. Spanjaard (2012) "Bounded single-peaked width and proportional representation". Dans Proceedings of the 20th European Conference on Artificial Intelligence (ECAI), 270-275. [3] G. Demange (1982) "Single-peaked orders on a tree". Dans Mathematical Social Sciences, 3(4):389-396. [4] G. Erdélyi, M. Lackner et A. Pfandler (2017) "Computational aspects of nearly single-peaked electorates". Dans Proceedings Journal of Artificial Intelligence Research, 58:297-337. [5] B. Escoffier, J. Lang et M. Öztürk (2008) "Single-peaked consistency and its complexity". Dans Proceedings of the 18th European Conference on Artificial Intelligence (ECAI), 366-370. [6] D. Peters (2017) "Recognizing multidimensional Euclidean Preferences". Dans AAAI-17, 642-648. [7] D. Peters et M. Lackner (2017) "Preferences single-peaked on a circle". Dans AAAI-17, 649-655.

2020 Publications