Résumé en français

Le choix social repose sur l’étude de la prise de décision collective, où un ensemble d’individus doit convenir d’une solution commune en fonction des préférences de ses membres. Le problème revient à déterminer comment agréger les préférences de différents agents en une décision acceptable pour le groupe. Typiquement, les agents interagissent dans des processus de décision collective, notamment en collaborant ou en échangeant des informations. Il est communément supposé que tout agent est capable d’interagir avec n’importe quel autre. Or, cette hypothèse paraît irréaliste pour de nombreuses situations. On propose de relâcher cette hypothèse en considérant que la possibilité d’interaction est déterminée par un réseau social, représenté par un graphe sur les agents. Dans un tel contexte, on étudie deux problèmes de choix social : le vote stratégique et l’allocation de ressources. L’analyse se concentre sur deux types d’interaction : la collaboration entre les agents, et la collecte d’information. On s’intéresse à l’impact du réseau social, modélisant une possibilité de collaboration entre les agents ou une relation de visibilité, sur la résolution et les solutions de problèmes de vote et d’allocation de ressources. Nos travaux s’inscrivent dans le cadre du choix social computationnel, en utilisant pour ces questions des outils provenant de la théorie des jeux algorithmique et de la théorie de la complexité.