Analyse de modèles aléatoires pour les matchings stables

In a two sided matching market, two types of agents have preferences over one another. Examples include college admissions (students and colleges), residency programs (doctors and hospitals), job markets (workers and jobs) and, in the classical analogy, stable marriages (men and women). In a founding paper, Gale and Shapley introduced the deferred acceptance procedure, where one side proposes and the other disposes, which computes a stable matching. Stable matchings have been an extensive research topic in computer science and economics. Results in the computer science literature include the lattice structure of the set of stable matchings, and algorithms to compute it. In the economics literature, researcher have studied the incentives of agents taking part in two-sided matching markets, both from the theoretical and empirical point of views. A recent line of works study the properties of stable matchings, using stochastic models of two-sided matching markets where the preferences of agents are drawn at random. This thesis follows this direction of inquiry, and considers two main questions: ``who can manipulate?'' and ``who gets what?''. The first part, addressing the question ``who can manipulate?'', contains three different results. In a first result (Chapter 4), we show that when one side of the market has strongly correlated preferences, incentives to manipulate are reduced. In a second result (Chapter 5), we show that uncorrelated preferences is a worst case situation when compared to correlated preferences. Proofs of both results are based on a randomized analysis of the algorithm which computes the incentives agents have to manipulate. In a third result (Chapter 6), we study the incomplete information game where students must apply to a limited number of schools, and thus report their preferences strategically. We prove the existence of symmetric equilibria and design algorithms to compute equilibria in various special cases. The second part, addressing the question ``who gets what?'', also contains three different results. In a first result (Chapter 7), we show that under a certain input distribution of preferences, the two variants of deferred acceptance produce the same output distribution on matchings. Proofs use the lattice structure of stable matchings, show that a fixed matching has the same probability of being the top or bottom element, and give a closed formula for the probability of two agents being matched. In a second result (Chapter 8), we consider a model where the probabilities that agents like each are quantified by a ``popularity'' matrix, and we give evidences that the probabilities that deferred acceptance matches agents is asymptotically given by the scaled matrix where lines/columns sum up to 1. In a third result (Chapter 9), we study the time complexity of deferred acceptance, which relates to the rank people from the proposing side give to their partner. Proofs are based on a reduction to the coupon collector's problem.Dans un marché biparti, deux types d'agents ont des préférences sur les agents du côté opposé. Parmi les exemples classique on retrouve l'affectation d'étudiants dans des université, de docteurs dans les 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 des 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 littérature informatique décrivent la structure de treillis complet de l'ensemble des matchings stables, ainsi que des algorithme 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 vu théorique et empirique. Une série récente de travaux étudient 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 question : "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'école 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 condition sur la distribution d'entrée sur les préférences, les deux variantes de l'algorithme d'acceptance 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'acceptance 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