Les problèmes d'allocation de ressources, allant de l'affectation scolaire à la publicité en ligne en passant par les soins de santé, privilégient traditionnellement l'efficacité et la maximization d'utilité, en négligeant souvent les considérations éthiques. L'introduction de contraintes d'équités dans des problèmes d'allocation classiques requiert de nouveaux méthodes algorithmiques, impacte les performances, et engendre de nouveaux compromis entre optimalité et respect des contraintes. Cette thèse étudie quatre modèles classiques d'allocation — apprentissage en ligne, inégalités de prophète, enchères, et allocation sous contraintes de matroïdes — sous l'angle de l'équité, et examine comment l'imposition de critères d'équités affecte la qualité de l'allocation à travers des bornes de regret, des ratios de competitions, des mesures d'inégalité et des notions de prix d'équité. Nous montrons que, dans certains cas, les compromis sont inévitables ; dans d'autres, la perte peut devenir arbitrairement faible asymptotiquement ; et dans des cas spécifiques, l'équité peut être atteinte sans aucun coût. En caractérisant quand et comment les contraintes d'équités influencent les résultats d'allocation, cette thèse apporte des éléments de réponse utiles tant aux concepteurs d'algorithmes qu'aux décideurs publics souhaitant mettre en œuvre des algorithmes équitables dans des contextes d'allocation.
Mathieu Molina (Tue,) studied this question.