Essays on matching and preference aggregation

Abstract

Cette thèse est une collection de trois articles dont deux portent sur le problème d’appariement et un sur le problème d’agrégation des préférences. Les deux premiers chapitres portent sur le problème d’affectation des élèves ou étudiants dans des écoles ou universités. Dans ce problème, le mécanisme d’acceptation différée de Gale et Shapley dans sa version où les étudiants proposent et le mécanisme connu sous le nom de mécanisme de Boston sont beaucoup utilisés dans plusieurs circonscriptions éducatives aux Etats-Unis et partout dans le monde. Le mécanisme de Boston est sujet à des manipulations. Le mécanisme d’acceptation différée pour sa part n’est pas manipulable mais il n’est pas efficace au sens de Pareto. L’objectif des deux premiers chapitres est de trouver des mécanismes pouvant améliorer le bien-être des étudiants par rapport au mécanisme d’acceptation différée ou réduire le dégré de vulnérabilité à la manipulation par rapport au mécanisme de Boston. Dans le Chapitre 1, nous étudions un jeux inspiré du système d’admission précoce aux Etats-Unis. C’est un système d’admission dans les collèges par lequel un étudiant peut recevoir une décision d’admission avant la phase générale. Mais il y a des exigences. Chaque étudiant est requis de soumettre son application à un seul collège et de s’engager à s’inscrire s’il était admis. Nous étudions un jeu séquentiel dans lequel chaque étudiant soumet une application et à la suite les collèges décident de leurs admissions dont les étudiants acceptent. Nous avons montré que selon une notion appropriée d’équilibre parfait en sous-jeux, les résultats de ce mécanisme sont plus efficaces que celui du mécanisme d’acceptation différée. vi Dans le Chapitre 2, nous étudions un mécanisme centralisé d’admissions dans les universités françaises que le gouvernement a mis en place en 2009 pour mieux orienter les étudiants dans les établissements universitaires. Pour faire face aux écoles dont les places sont insuffisantes par rapport à la demande, le système défini des priorités qui repartissent les étudiants en grandes classes d’équivalence. Mais le système repose sur les préférences exprimées pour départager les ex-aequos. Nous avons prouvé que l’application du mécanisme d’acceptation différée avec étudiant proposant aprés avoir briser les ex-aequos est raisonable. Nous appelons ce mécanisme mécanisme français. Nous avons montré que le mécanisme français réduit la vulnérabilité à la manipulation par rapport au mécanisme de Boston et améliore le bien-être des étudiants par rapport au mécanisme standard d’acceptation différée où les ex-aequos sont brisés de façon aléatoire. Dans le Chapitre 3, nous introduisons une classe de règles pour combiner les préférences individuelles en un ordre collectif. Le problème d’agrégation des préférences survient lorsque les membres d’une faculté cherchent une stratégie pour offrir une position sans savoir quel candidat va accepter l’offre. Il est courant de classer les candidats puis donner l’offre suivant cet ordre. Nous avons introuduit une classe de règles appélée règles de dictature sérielle augmentée dont chacune est paramétrée par une liste d’agents (avec répétition) et une règle de vote par comité. Pour chaque profile de préférences, le premier choix de l’agent en tête de la liste devient le premier choix collectif. Le choix du deuxème agent sur la liste, parmi les candidats restants, devient le deuxième choix collectif. Et ainsi de suite jusqu’à ce qu’il reste deux candidats auquel cas le comité vote pour classer ces derniers. Ces règles sont succinctement caractérisées par la non-manipulabilité et la neutralité sous l’extension lexicographique des préférences. Nous avons montré aussi que ces règles sont non-manipulables sous une variété d’extensions raisonable des préférences. Mots-clés : Appariement, mécanisme d’acceptation différée, mécanisme de Boston, mécanisme français, agrégation des préférences, règle non-manipulable, règle de dictature sérielle augmentée.

This thesis is a collection of two papers on matching and one paper on preference aggregation. The first two chapters are concerned with the problem of assigning students to schools. For this problem, the student proposing version of Gale and Shapley’s deferred acceptance mechanism and a mechanism known as Boston mechanism are widely used in many school districts in U.S and around the world. The Boston mechanism is prone to manipulation. The deferred acceptance mechanism is not manipulable ; however, it is not Pareto efficient. The first two chapters of this thesis deal with the problem of either improving the welfare of students over deferred acceptance or reducing the degree of manipulation under Boston. In Chapter 1, we study a decentralized matching game inspired from the early decision system in the U.S : It is a college admission system in which students can receive admission decisions before the general application period. But there are two requirements. First, each student is required to apply to one college. Second, each student commits to attend the college upon admitted. We propose a game in which students sequentially make one application each and colleges ultimately make admission decisions to which students commit to accept. We show that up to a relevant refinement of subgame perfect equilibrium notion, the expected outcomes of this mechanism are more efficient than that of deferred acceptance mechanism. In Chapter 2, we study a centralized university admission mechanism that the French government has implemented in 2009 to better match students to viii university schools. To deal with oversubscribed schools, the system defined priorities that partition students into very coarse equivalence classes but relies on student reported preferences to further resolve ties.We show that applying student-proposing deferred acceptance mechanism after breaking ties is a reasonable procedure. We refer to this mechanism as French mechanism. We show that this mechanism is less manipulable than the Boston mechanism and more efficient than the standard deferred acceptance in which ties are broken randomly. In Chapter 3, we introduce a class of rules called augmented serial rules for combining individual preferences into a collective ordering. The aggregation problem appears when faculty members want to devise a strategy for offering an open position without knowing whether any given applicant will ultimately accept an offer. It is a commonplace to order the applicants and make offers accordingly. Each of these augmented serial rules is parametrized by a list of agents (with possible repetition) and a committee voting rule. For a given preference profile, the collective ordering is determined as follows : The first agent’s most preferred alternative becomes the top-ranked alternative in the collective ordering, the second agent’s most preferred alternative (among those remaining) becomes the second-ranked alternative and so on until two alternatives remain, which are ranked by the committee voting rule. The main result establishes that these rules are succinctly characterized by neutrality and strategy-proofness under the lexicographic extension. Additional results show that these rules are strategy-proof under a variety of other reasonable preference extensions.