Abstract (FR)

Cet article s’intéresse à un problème particulier d’allocation de ressources où chaque agent reçoit un unique objet. Initialement dotés d’un objet, les agents peuvent effectuer des échanges afin d’obtenir un objet qui leur plaît mieux. Seulement, tous les échanges ne sont pas plausibles en raison de l’incapacité de certains agents à communiquer entre eux. En considérant un réseau social sur les agents, on propose d’étudier les allocations possibles obtenues pardes séquences d’échanges entre paires de voisins dans le réseau. Ce modèle soulève des questions naturelles concernant (i) la possibilité pour une allocation complète d’être atteignable par une séquence d’échanges dans le réseau, (ii) la possibilité pour un agent d’obtenir un objet donné, et (iii) la recherche d’allocations Pareto-efficaces. On se concentre sur la complexité de ces questions en déterminant, selon la structure du réseau social, des cas polynomiaux ou NPcomplets.