| Resumé |
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. |