Direction de recherche : Olivier SPANJAARD

Co-encadrement : ESCOFFIER Bruno

Aspects structurels et algorithmiques des restrictions de domaines de préférences dans la prise de décision collective : contributions à  l'étude des préférences unimodales et Euclidiennes

Cette thèse étudie des aspects structurels et algorithmiques des restrictions de domaines de préférences, en se focalisant sur les préférences unimodales et les préférences Euclidiennes.
Dans la première partie de la thèse, nous introduisons d'abord une généralisation des préférences unimodales sur des graphes quelconques, en nous focalisant sur des aspects algorithmiques, notamment le problème de reconnaissance. Dans un deuxième temps, nous nous intéressons aux préférences presque unimodales. Plus précisément, nous proposons une nouvelle métrique d'unimodalité approchée et nous étudions ses propriétés théoriques et computationnelles.
La deuxième partie de la thèse est consacrée à  l'étude des préférences d-Euclidiennes (où d est la dimension) par rapport à  différentes normes. Nous proposons d'abord une heuristique de reconnaissance des préférences 2-Euclidiennes par rapport à  la norme l_2, et étudions son efficacité en pratique. Enfin, nous étudions des aspects structurels des préférences 2-Euclidiennes par rapport à  la norme l_1.

Publications 2020-2024

• 2024
  • B. Escoffier, O. Spanjaard, M. Tydrichová : “Recognizing single-peaked preferences on an arbitrary graph: Complexity and algorithms”, Discrete Applied Mathematics, vol. 348, pp. 301-319, (Elsevier) (2024)
  • B. Escoffier, O. Spanjaard, M. Tydrichová : “Euclidean preferences in the plane under $\ell_1$, $\ell_2$ and $\ell_\infty$ norms”, Social Choice and Welfare, (Springer Verlag) (2024)
• 2023
  • M. Tydrichova : “Aspects structurels et algorithmiques des restrictions de domaines de préférences dans la prise de décision collective : contributions à  l’étude des préférences unimodales et Euclidiennes”, soutenance de thèse, soutenance 21/03/2023, direction de recherche Spanjaard, Olivier, co-encadrement : Escoffier, Bruno (2023)
  • B. Escoffier, O. Spanjaard, M. Tydrichová : “Algorithmic Recognition of 2-Euclidean Preferences”, Proceedings of ECAI 2023, vol. 372, Frontiers in Artificial Intelligence and Applications, Krakow (Cracovie), Poland, pp. 637-644, (IOS Press), (ISBN: 978-1-64368-437-6) (2023)
• 2022
  • B. Escoffier, O. Spanjaard, M. Tydrichová : “Weighted majority tournaments and Kemeny ranking with 2-dimensional Euclidean preferences”, Discrete Applied Mathematics, vol. 318, pp. 6-12, (Elsevier) (2022)
• 2021
  • B. Escoffier, O. Spanjaard, M. Tydrichová : “Measuring Nearly Single-Peakedness of an Electorate: Some New Insights”, Algorithmic Decision Theory 7^th International Conference, ADT 2021, Toulouse, France, November 3–5, 2021, Proceedings, vol. 13023, Lecture Notes in Computer Science, Toulouse, France, pp. 19-34, (Springer) (2021)
• 2020
  • B. Escoffier, O. Spanjaard, M. Tydrichová : “Recognizing Single-Peaked Preferences on an Arbitrary Graph: Complexity and Algorithms”, Proceedings of the 13^th International Symposium on Algorithmic Game Theory, SAGT 2020, vol. 12283, Lecture Notes in Computer Science, Augsburg, Germany, pp. 291-306, (Springer) (2020)