TYDRICHOVA Magdaléna
Supervision : Olivier SPANJAARD
Cosupervision : ESCOFFIER Bruno
Structural and algorithmic aspects of preference domain restrictions in collective decision making: contributions to the study of singlepeaked and Euclidean preferences
n this thesis, we study structural and algorithmic aspects of preference domain restrictions, namely singlepeaked preferences and Euclidean preferences.
Social choice is a field which, among other things, studies, analysis or aggregates individual opinions (called preferences), with the aim of reaching a common decisions which would be the "best one" in some sense. The preferences are called structured if they share some common underlying structure. Actually, realworld preferences are often more or less structured, as the voters often decide on the basis of the same (or similar) set of criteria. For instance, in a political context, the leftright axis is often given as an example of a structure around which preferences are built (at least up to some degree).
Identifying a structure of preferences helps us to better understand the behaviour of voters. From the computational point of view, some popular structures of preferences also help to simplify various problems (as, for instance, preference aggregation or elicitation), and to circumvent several famous paradoxes of social choice.
However, popular preference structures are often too restrictive, and it is nearly impossible to meet them in practice. That is why we try to weaken these common structures, while keeping, as many good properties as possible. And this is what my thesis is about.
In the first part of the thesis, we focus on socalled singlepeaked preferences. At the first time, we seek to weaken this structure by introducion a generalization of the notion of singlepeakedness on an arbitrary graph. We focus, in particular, on algorithmic aspects, namely the problem of recognition.
At the second time, we keep the structure of singlepeaked axis, but we allow the preferences to slightly deviate from it if necessary. This is known as nearly singlepeakedness. We introduce a new measure of nearly singlepeakedness, and we compare it with several existing measures of nearly singlepeakedness from both theoretical and practical point of view.
In the second part, the idea is to add more dimensions to make common structures less restrictive. In particular, this part is devoted to the study of dEuclidean preferences (where d is the dimension of the real space) with respect to different norms. Indeed, while other structures of preferences (like singlepeaked and singlecrossing preferences) are well understood, the domain of Euclidean preferences still resists  it is a rather unexplored research direction full of challenging questions. We propose here some insights into this domain that could help, we hope, in further studies.
More concretely, we first propose a heuristic algorithm for recognizing 2Euclidean preferences with respect to the l_2 norm, and study its practical efficiency. Finally, we focus on structural aspects of 2Euclidean preferences with respect to the norm l_1, by focusing mainly on similarities and differencies with 2Euclidean preferences with respect to the norm l_2.
Defence : 03/21/2023
Jury members :
Edith ELKIND, Oxford University
Jérôme LANG, Université Paris Dauphine
Jiehua CHEN, TU Wien
JeanPaul DOIGNON, Université Libre de Bruxelles
Nicolas MAUDET, Sorbonne Université
Bruno ESCOFFIER, Sorbonne Université
Olivier SPANJAARD, Sorbonne Université
20202024 Publications

2024
 B. Escoffier, O. Spanjaard, M. Tydrichová : “Recognizing singlepeaked preferences on an arbitrary graph: Complexity and algorithms”, Discrete Applied Mathematics, vol. 348, pp. 301319, (Elsevier) (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”, thesis, defence 03/21/2023, supervision Spanjaard, Olivier, cosupervision : Escoffier, Bruno (2023)
 B. Escoffier, O. Spanjaard, M. Tydrichová : “Algorithmic Recognition of 2Euclidean Preferences”, Proceedings of ECAI 2023, vol. 372, Frontiers in Artificial Intelligence and Applications, Krakow (Cracovie), Poland, pp. 637644, (IOS Press), (ISBN: 9781643684376) (2023)

2022
 B. Escoffier, O. Spanjaard, M. Tydrichová : “Weighted majority tournaments and Kemeny ranking with 2dimensional Euclidean preferences”, Discrete Applied Mathematics, vol. 318, pp. 612, (Elsevier) (2022)

2021
 B. Escoffier, O. Spanjaard, M. Tydrichová : “Measuring Nearly SinglePeakedness 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. 1934, (Springer) (2021)

2020
 B. Escoffier, O. Spanjaard, M. Tydrichová : “Recognizing SinglePeaked 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. 291306, (Springer) (2020)