Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Nous nous intéressons dans cette thèse à la problématique de la décision collective. L’objectif est de déterminer une solution de compromis pour des problèmes soumis à de multiples points de vue. Les problèmes considérés sont de nature combinatoire. Plus précisément, il s’agit de la classe des systèmes d’ensembles qui ont une structure de matroïde. La théorie des matroïdes est centrale en optimisation combinatoire, elle a permis d’unifier des structures apparemment séparées comme les arbres et les couplages dans les graphes et elle a engendré des algorithmes efficaces pour résoudre des problèmes d’optimisation non triviaux en temps polynomial. Nous nous intéressons à fournir des algorithmes d’approximation polynomiaux centralisés et décentralisés avec garantie de performance pour déterminer une solution de compromis qui est une base du matroïde. La solution de compromis doit également être équitable pour tous les membres de la collectivité. Nous portons un intérêt particulier au problème de partage équitable de biens indivisibles qui est une thématique importante en choix social computationnel et dont le problème se modélise par les matroïdes. / In this thesis, we are interested in collective decision-making. The objective is to find a tradeoff solution for problems that are evaluated by multiple points of view. We consider problems having a matroid structure. Matroid theory is significant in combinatorial optimization, it helped to unify apparently separated structures like forests and matchings in graphs and it includes efficient algorithms for solving non-trivial optimization problems in polynomial time. We are interested to provide polynomial time centralized and decentralized approximation algorithms for finding a tradeoff solution which is a base of the matroid. The tradeoff solution must also be fair for all the members of the community. We are particularly interested in the issue of the fair division of indivisible goods which is central in computational social choice and that can be modeled by matroids.

Cette thèse porte sur les mécanismes d’allocation de biens indivisibles en présence d’externalités dans les préférences individuelles. Ces externalités rendent difficile en pratique la collecte d’une information complète sur les préférences. Aussi, l’analyse normative des mécanismes d’allocation requiert de formuler des hypothèses sur la manière d’étendre l’information collectée aux préférences sur les allocations. Cette approche revient à définir des restrictions sur le domaine de préférences admissibles, une démarche bien connue de la théorie du choix social. Les trois premiers chapitres portent sur l’analyse du marché de Shapley-Scarf dans lequel les échanges sont organisés entre coalitions. Les chapitres 1 et 2 établissent des restrictions de domaine garantissant l’existence de différents types d’équilibre concurrentiel. Dans le chapitre 3, l’ensemble des biens est muni d’une géographie, ce qui permet de définir la distance entre partenaires comme source d’externalité. Nous identifions certains domaines de préférences qui assurent la non-vacuité de différents types de Coeur. Le chapitre 4 porte sur le cas de biens indivisibles publics purs. Nous montrons que le problème est formellement équivalent à celui du choix d’un comité dont les membres sont choisis dans des ensembles distincts. Nous caractérisons certains domaines de préférences sur les comités pour lesquels le choix majoritaire membre par membre est cohérent avec le choix majoritaire du comité dans son ensemble. / This thesis focuses on the allocation of indivisible goods in presence of externality in individual preferences. This externality creates a difficulty with collecting full information about preferences. Therefore, conducting a normative analysis of allocation mechanisms requires assumptions on how reported preferences can be extended to preferences over outcomes. This approach is in line with the literature on preference domain restriction well-known in Social Choice theory. The first three chapters focus on Shapley-Scarf markets where trades are organized among coalitions. Coalitional trade generates externalities in individual valuations of allocations. Chapters 1 and 2 investigate domain restrictions ensuring the existence of various types of competitive equilibrium. Chapter 3 endows the set of goods with a geographical structure and considers distance to partners as a source of externality in preference. We identify domains of preference extensions which guarantee the existence of various types of core allocations. Chapter 4 focuses the case of pure public indivisible goods, which is formally identical to choosing a committee formed by several members, each selected from a specific set. We characterize preference domains over committees for which a well-defined seat-wise choice procedure based on majority voting is consistent with choosing a committee at once from majority voting.