J'ai le plaisir de vous inviter à ma soutenance de thèse, le mercredi 15 décembre, à 14h00.

• La soutenance aura lieu à Paris, en Amphithéatre Gouges 1 (voir carte ci-dessous).
• Si vous préférez y assister en ligne, une rediffusion sera disponible sur YouTube.
• Mon manuscrit (en anglais) est disponible ici.

Agrandir la carte

Dans un marché biparti, deux types d'agents ont des préférences sur les agents du côté opposé. Parmi les exemples classiques on retrouve l'affectation d'étudiants dans des universités, de docteurs dans des hôpitaux, de travailleurs à des offres d'emploi et, dans l'analogie historique des mariages stables, l'appariement d'hommes et de femmes. Dans un article fondateur, Gale et Shapley introduisent la procédure d'acceptation différée, dans laquelle un côté propose et l'autre côté dispose, permettant de calculer un matching stable.

Les matchings stables constituent un sujet de recherche important en informatique et en économie. Des résultats issus de la littérature informatique décrivent la structure de treillis complet de l'ensemble des matchings stables, ainsi que les algorithmes permettant de le calculer. Dans la littérature économique ont été étudiées les questions de manipulabilité par les agents participant à un marché biparti, à la fois du point de vue théorique et empirique.

Une série récente de travaux étudie les propriétés des matchings stables, en utilisant des modèles stochastiques dans lesquels les préférences des agents sont générées aléatoirement. Cette thèse poursuit cette approche, et considère deux questions : “qui peut manipuler ?” et “qui obtient quoi ?”.

La première partie, abordant la question “qui peut manipuler”, contient trois résultats différents. Dans un premier résultat (Chapitre 4), nous montrons que lorsque les agents d'un des côtés du marché ont des préférences très corrélées, les opportunités de manipulabilité sont réduites. Dans un second résultat (Chapitre 5), nous montrons que des préférences décorrélées constituent un pire cas. Les preuves de ces deux résultats sont basées sur une analyse probabiliste de l'algorithme calculant les opportunités de manipulabilité. Dans un troisième résultat (Chapitre 6), nous étudions le jeu à information incomplète où des étudiants peuvent postuler à un nombre limité d'écoles et, par conséquent, choisissent leur liste de préférence de manière stratégique. Nous prouvons l'existence d'un équilibre symétrique et proposons des algorithmes permettant de le calculer dans plusieurs cas particuliers.

La seconde partie, abordant la question “qui obtient quoi ?”, contient également trois résultats. Dans un premier résultat (Chapitre 7), nous montrons que sous certaines conditions sur la distribution d'entrée sur les préférences, les deux variantes de l'algorithme d'acceptation différée produisent exactement la même distribution de sortie sur les matchings. Les preuves utilisent la structure de treillis de l'ensemble des matchings stables, montrent qu'un matching fixé a la même probabilité d'être la borne inférieure ou supérieure, et donnent une formule pour la probabilité que deux agents soient appariés. Dans un second résultat (Chapitre 8), nous considérons un modèle dans lequel la probabilité que deux agents s'apprécient est quantifiée par une matrice de “popularités”, et nous expliquons que les probabilités d'appariement sont asymptotiquement données par la matrice renormalisée dont les lignes/colonnes ont une somme égale à 1. Dans un troisième résultat (Chapitre 9), nous étudions la complexité de l'algorithme d'acceptation différée, qui se rapporte à l'étude du rang que chaque agent donne à son partenaire. Les preuves sont basées sur une réduction au problème de collection de coupons.