Mariage stable avec préférence incomplètes // Stable Matching with Incomplete Preferences

Le sujet de thèse est fortement inspiré des problématiques liées à l'affectation des lycéens dans les universités, qui est effectuée en France par Parcoursup. Toutefois, ces problématiques peuvent être élargies à toute procédure centralisée d'affectation de candidats à des institutions, où les candidats expriment des préférences sur les différentes institutions auxquelles ils peuvent être affectés, et où les institutions ont également des préférences sur les candidats qu'elles peuvent recruter. Dans le cadre de l'affectation des lycéens aux universités, l'objectif est de trouver une affectation stable, c'est-à-dire telle qu'il n'existe pas un lycéen préférant une autre université à celle qui lui a été attribuée et que cette autre université soit prête à l'accepter. La littérature sur les algorithmes permettant de trouver des affectations stables est très riche, à la fois dans le domaine de l'économie et de l'informatique [5, 6]. La méthode standard pour calculer ce type d'affectation est l'algorithme de Gale-Shapley [4]. Cette procédure possède de nombreuses propriétés intéressantes. Elle garantit une affectation optimale pour les étudiants, c'est-à-dire qu'il n'existe pas d'autre affectation stable qui soit meilleure pour eux. De plus, elle est non-manipulable pour les étudiants [3], ce qui signifie qu'un étudiant ne peut pas améliorer son affectation en déclarant des préférences qui diffèrent de ses préférences réelles. Cette propriété est particulièrement appréciable lorsqu'on cherche à garantir une procédure équitable, qui ne favorise pas les lycéens capables de manipuler le système au détriment des autres.

Ce sont les bonnes propriétés de l'algorithme de Gale-Shapley qui rendent cette procédure attrayante et qui expliquent son adoption large dans l'affectation des étudiants aux universités. Néanmoins, ces propriétés reposent sur le postulat que les préférences des lycéens sur les universités et celles des universités sur les candidats sont entièrement connues. Autrement dit, chaque lycéen doit classer l'ensemble des universités par ordre de préférence, et chaque université doit en faire de même pour tous les lycéens. Or, le nombre d'universités est trop important pour exiger des lycéens qu'ils les classent toutes, et ce problème est encore plus marqué pour les universités, qui devraient classer l'ensemble des lycéens. C'est pourquoi la plupart des systèmes reposant sur Gale-Shapley demandent aux étudiants de classer un nombre limité d'universités. Cependant, cette version tronquée de Gale-Shapley ne conserve pas les mêmes propriétés. Elle n'est plus non-manipulable, ne garantit pas nécessairement une solution optimale pour les étudiants et peut même conduire à une affectation instable, car un étudiant peut ne pas candidater à une université qu'il ne connaît pas.

Dans l'optique de pallier ce problème structurel, nous souhaitons étudier la possibilité d'enrichir les préférences partielles des lycéens sur les universités en utilisant des mesures de similarité entre universités, qui indiquent à quel point certaines universités sont perçues comme proches dans les préférences des étudiants. Ces mesures de similarité sont bien connues dans les systèmes de recommandation [1] et peuvent être apprises à partir des données historiques contenant les préférences déjà révélées par les lycéens des années précédentes. Elles peuvent également être induites à partir de caractéristiques intrinsèques des universités, telles que leur position géographique, les programmes offerts, etc. Une autre approche, qui peut compléter l'utilisation des mesures de similarité entre universités, consiste à proposer explicitement aux étudiants de classer des universités qui n'apparaissent pas encore dans leurs préférences, afin d'améliorer l'affectation qui pourra leur être proposée. Ce processus, qui consiste à poser des questions pour inférer des préférences, est appelé élicitation [2].
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------

The research line of this proposal is inspired by the French system used to match high school students to universities. However, this topic applies to any centralized two-sided matching procedure where both sides of the market have preferences. Usually, these centralized procedures aim to select a matching that is stable, i.e., such that no student prefers another university over the one they are matched with, while that university would also be willing to accept the student. The literature on stable matching is extensive and includes contributions from both economics and computer science [5, 6]. The standard procedure used to assign students to universities is the well-known Gale-Shapley algorithm (https://en.wikipedia.org/wiki/Gale-Shapley_algorithm) [4]. In addition to ensuring stability, this procedure possesses several attractive properties. For instance, the matching it produces is optimal for students, meaning that no other stable matching is better for any student. Furthermore, this procedure is strategy-proof for students [3], meaning that no student can manipulate the outcome by misreporting their true preferences to obtain a better match (e.g., by strategically ranking a university higher because they have a greater chance of being accepted there). Strategy-proofness for students is a particularly desirable property, as it is closely related to fairness: it prevents well-informed students from gaining an advantage by manipulating the system, ensuring a more equitable process.

The desirable properties of the Gale-Shapley algorithm are the main reasons why this procedure is widely adopted for assigning students to universities. However, these properties rely on the assumption that the preferences of students over universities and those of universities over students are fully known. In other words, each student would need to provide a complete ranking of all universities. This task becomes impractical when the number of universities is very large, as it would require students to be fully informed about all university programs, sometimes across the entire country. For this reason, most systems based on the Gale-Shapley procedure ask students to rank only a limited set of universities, typically their top choices. However, this restricted version of Gale-Shapley does not preserve all the desirable properties described above. It is not strategy-proof, does not necessarily produce an optimal matching for students, and may even result in an unstable matching, as some students might fail to rank certain universities simply because they are unaware of them before the application deadline.

In order to address these issues, we plan to study how similarity measures can help enrich revealed preferences. These similarity measures are well known in recommender systems [1] and can model common patterns in students' preferences. They can be derived from historical data on preferences already revealed by past students. Another approach, which may be used in combination with similarity measures, is to elicit students' unrevealed preferences, i.e., asking a limited number of targeted questions to assess their preferences over relevant universities [2].
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Début de la thèse : 01/10/2026
WEB : https://www.lamsade.dauphine.fr/fr/collaborer-avec-nous/offres-demploi-stages-sujets-de-theses.html

Public funding alone (i.e. government, region, European, international organization research grant)

Concours pour un contrat doctoral

UNIVERSITE PARIS DAUPHINE - PSL

543 SDOSE Sciences de la Décision, des Organisations, de la Société et de l'Echange

Le ou la candidat.e devra être titulaire d'un Master en informatique ou en mathématiques appliquées, avec une spécialisation en intelligence artificielle et/ou en recherche opérationnelle.
We are looking for candidates holding (or about to complete) a Master's degree in Computer Science or Applied Mathematics, with a specialization in artificial intelligence and/or operations research.