TYDRICHOVA Magdaléna

PhD student at Sorbonne University
Team : DECISION
https://webia.lip6.fr/~tydrichova

Supervision : Olivier SPANJAARD

Co-supervision : ESCOFFIER Bruno

Structural and algorithmic aspects of preference domain restrictions in collective decision making: contributions to the study of single-peaked and Euclidean preferences

n this thesis, we study structural and algorithmic aspects of preference domain restrictions, namely single-peaked 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, real-world 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 left-right 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 so-called single-peaked preferences. At the first time, we seek to weaken this structure by introducion a generalization of the notion of single-peakedness 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 single-peaked axis, but we allow the preferences to slightly deviate from it if necessary. This is known as nearly single-peakedness. We introduce a new measure of nearly single-peakedness, and we compare it with several existing measures of nearly single-peakedness 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 d-Euclidean preferences (where d is the dimension of the real space) with respect to different norms. Indeed, while other structures of preferences (like single-peaked and single-crossing 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 2-Euclidean preferences with respect to the l_2 norm, and study its practical efficiency. Finally, we focus on structural aspects of 2-Euclidean preferences with respect to the norm l_1, by focusing mainly on similarities and differencies with 2-Euclidean 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
Jean-Paul DOIGNON, Université Libre de Bruxelles
Nicolas MAUDET, Sorbonne Université
Bruno ESCOFFIER, Sorbonne Université
Olivier SPANJAARD, Sorbonne Université

Departure date : 04/04/2023

2020-2024 Publications