📊 statistics

Optimal Transport under Group Fairness Constraints

Cet article introduit une nouvelle notion d'équité de groupe pour le transport optimal et propose des méthodes de calcul efficaces, incluant un algorithme de Sinkhorn modifié et deux stratégies de relaxation avec des garanties théoriques, afin de concilier les contraintes d'équité et la qualité de l'appariement.

Auteurs originaux : Linus Bleistein, Mathieu Dagréou, Francisco Andrade, Thomas Boudou, Aurélien Bellet

Publié 2026-06-04

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Linus Bleistein, Mathieu Dagréou, Francisco Andrade, Thomas Boudou, Aurélien Bellet

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous soyez un entremetteur pour un événement massif. Vous avez deux groupes de personnes : des Candidats (comme des étudiants cherchant des écoles) et des Postes (comme les écoles elles-mêmes). Votre travail est de les associer.

Dans le monde des mathématiques, ce processus d'association est appelé Transport Optimal. Pensez-y comme à un service de livraison essayant de déplacer des colis de l'entrepôt vers les clients. L'objectif est généralement de le faire de la manière la moins coûteuse possible — c'est-à-dire que la « distance » ou le « coût » entre un candidat spécifique et un poste spécifique est minimisé.

Le Problème : Le Piège du « Riche qui s'enrichit »
L'article souligne une faille dans l'appariement standard. Si les étudiants riches ont tendance à vivre près des écoles d'élite, et que les étudiants pauvres vivent près d'écoles sous-financées, un algorithme standard de « chemin le plus court » associera naturellement les riches aux élites et les pauvres aux structures sous-financées. C'est efficace, mais c'est injuste. Cela renforce les divisions sociales existantes.

La Solution : Un Nouveau Règlement
Les auteurs proposent une nouvelle façon de gérer ce jeu d'association appelé Équité de Groupe. Au lieu de regarder seulement la distance entre les personnes, ils introduisent une « Cible d'Équité ».

Imaginez un planificateur central (comme un gouvernement ou un conseil scolaire) vous remettant une feuille d'instructions stricte :

« Nous voulons que 60 % des étudiants à faibles revenus soient associés à des écoles d'élite, peu importe où ils vivent. »

Cela transforme le problème de « trouver le chemin le moins cher » en « trouver le chemin le moins cher qui suit également cette carte spécifique de qui est associé à qui ».

Les Trois Stratégies
L'article explore trois façons de résoudre ce casse-tête :

L'Algorithme « Parfaitement Équitable » (FairSinkhorn) :
C'est comme un arbitre strict qui s'assure que la liste finale des correspondances atteint exactement les chiffres indiqués sur la feuille d'instructions. Cela fonctionne parfaitement, mais l'article note que cela peut être très coûteux. C'est comme forcer un camion de livraison à prendre un détour long et sinueux juste pour déposer un colis dans un quartier spécifique, même si un itinéraire direct existe. Le « coût » (l'efficacité) augmente considérablement.
L'Approche par « Pénalité » :
Puisque l'équité parfaite peut être trop coûteuse, les auteurs suggèrent une approche plus souple. Ils ajoutent une « amende » au système.
- Analogie : Imaginez que vous conduisez. Vous voulez arriver au travail rapidement (faible coût), mais vous voulez aussi respecter le code de la route (équité). Au lieu d'un policier strict qui vous arrête, vous acceptez de payer une amende si vous commettez un excès de vitesse. Plus vous dépassez la limite (déviiez de l'équité), plus l'amende est élevée.
- Cela permet au système de trouver un « point d'équilibre » où il est principalement équitable sans pour autant coûter une fortune. L'article prouve mathématiquement que cette méthode est stable et fiable, même avec des données limitées.
L'Approche par « Apprentissage du Coût » :
C'est la stratégie la plus créative. Au lieu de forcer les associations à être équitables, le système apprend à changer la carte elle-même.
- Analogie : Imaginez que les chauffeurs de livraison utilisent un GPS. Le GPS standard dit : « Prenez l'autoroute ; c'est le plus rapide. » Mais l'autoroute mène à un résultat injuste. Alors, ce nouveau système reprogramme le GPS. Il apprend à rendre les itinéraires « injustes » coûteux et les itinéraires « équitables » peu coûteux.
- Une fois le GPS reprogrammé, vous pouvez l'utiliser pour n'importe quel nouveau groupe de conducteurs sans avoir à recalculer les règles à chaque fois. L'article montre que cette « carte reprogrammée » fonctionne bien pour de nouvelles personnes qui ne faisaient pas partie du groupe d'entraînement initial.

Ce Qu'Ils Ont Trouvé

Compromis : On ne peut pas toujours avoir les correspondances les moins chères et une équité parfaite. Vous devez choisir le niveau d'équité que vous êtes prêt à « payer ».
Réutilisabilité : La méthode de « l'Apprentissage du Coût » est la grande gagnante en termes de rapidité. Une fois que vous avez appris la « nouvelle carte », vous pouvez l'appliquer instantanément à de nouvelles données, alors que les autres méthodes nécessitent un recalcul lourd à chaque fois.
Test en conditions réelles : Ils ont testé cela sur des données fictives (comme des étudiants et des écoles) et sur un ensemble de données semi-réelles (une application de rencontre). Dans le scénario de l'application de rencontre, ils ont essayé de garantir que les personnes de différents niveaux de revenus aient une chance équitable de se rencontrer, plutôt que de simplement les faire correspondre avec des personnes de même niveau de revenus.

En Résumé
Cet article nous offre une nouvelle boîte à outils pour corriger les systèmes d'association injustes. Il propose une façon de dire à un algorithme : « Ne sois pas seulement efficace ; sois équitable », et fournit trois manières différentes de le faire : une qui est stricte mais coûteuse, une qui équilibre le coût et l'équité, et une qui apprend de nouvelles règles pour faire de l'équité le résultat naturel.

Résumé Technique : Transport Optimal sous Contraintes d'Équité de Groupe

1. Énoncé du Problème

Le papier traite du défi consistant à assurer l'équité de groupe dans les mécanismes d'appariement algorithmique, qui sont de plus en plus utilisés pour allouer des ressources rares (ex. : emplois, admissions scolaires, échanges de reins). Bien que le Transport Optimal (OT) standard fournisse un cadre puissant pour apparier deux distributions basées sur la similitude des caractéristiques, il peut involontairement renforcer ou amplifier les disparités existantes si les caractéristiques sont corrélées avec des attributs sensibles (ex. : statut socio-économique ou origine ethnique).

Les auteurs formalisent une nouvelle notion d'équité de groupe pour l'OT. Contra à les travaux précédents se concentrant sur l'équité individuelle ou des contraintes spécifiques (comme la participation minimale), cette approche permet à un planificateur central de spécifier une matrice de cible d'équité $F$ . Cette matrice définit la probabilité souhaitée d'apparier des individus de n'importe quel groupe $s$ de la population source à n'importe quel groupe $w$ de la population cible. L'objectif est de trouver un plan d'OT qui minimise le coût de transport tout en satisfaisant ces contraintes de masse inter-groupes explicites.

2. Méthodologie

Le papier propose une hiérarchie d'approches pour résoudre ce problème, allant des contraintes exactes aux formulations relaxées.

2.1. Équité Exacte : FairSinkhorn

Pour les scénarios exigeant une adhésion stricte aux cibles d'équité, les auteurs définissent le problème de l'OT équitable sous $F$ ( $F$ -fair Optimal Transport). Cela implique de minimiser l'objectif d'OT entropique sous des contraintes linéaires où la masse marginale entre les groupes $(s, w)$ doit être égale à $F_{sw}$ .

Algorithme : Ils dérivent un algorithme Sinkhorn modifié, nommé FairSinkhorn. En analysant la formulation duale, ils montrent que la solution conserve la structure multiplicative des itérations Sinkhorn standard mais inclut une étape de projection supplémentaire pour imposer les contraintes de groupe.
Garantie Théorique : Sous l'hypothèse de mesures à support compact, ils prouvent l'existence et l'unicité du plan d'OT équitable.

2.2. Stratégies d'Équité Approchée

Reconnaissant que l'équité exacte peut considérablement dégrader la qualité de l'appariement (le "prix de l'équité"), les auteurs proposent deux stratégies de relaxation :

A. OT Pénalisé par l'Équité

Cette approche incorpore la violation de l'équité comme un terme de pénalité dans la fonction objectif :
$\min_{\Pi} \text{Tr}[\Pi^\top C] + \varepsilon \text{KL}(\Pi) + \lambda L_F(\Pi)$
où $L_F(\Pi)$ est l'erreur quadratique entre les probabilités d'appariement de groupe réelles et la cible $F$ , et $\lambda$ contrôle le compromis.

Optimisation : Le problème reste convexe. Il est résolu à l'aide d'un algorithme de gradient conditionnel généralisé, où chaque itération linéarise la pénalité d'équité et résout un sous-problème (un OT entropique avec un coût modifié) via l'algorithme Sinkhorn standard.
Complexité d'Échantillonnage : Les auteurs dérivent une nouvelle borne de complexité d'échantillonnage fin pour ce problème pénalisé. Ils montrent que l'erreur d'estimation suit une échelle en $O(n^{-1/2})$ , rejoignant l'OT entropique standard, ce qui implique que l'ajout de la pénalité d'équité ne réduit pas l'efficacité statistique.

B. Apprentissage de Coût via Optimisation Bilével

Cette stratégie apprend une fonction de coût de base $c_\theta$ telle que le plan d'OT résultant satisfait naturellement les cibles d'équité.

Formulation : Un problème d'optimisation bilével est posé où la boucle externe minimise la perte d'équité $L_F(\Pi_\varepsilon(c_\theta))$ par rapport aux paramètres de coût $\theta$ , et la boucle interne résout le problème d'OT pour un coût fixé.
Paramétrages : La fonction de coût peut être paramétrée comme une distance de Mahalanobis (transformation linéaire des caractéristiques) ou via des réseaux de neurones (plongements non linéaires).
Généralisation : Un avantage clé est la réutilisabilité ; une fois $c_\theta$ appris, il peut être appliqué à de nouveaux échantillons non vus en utilisant l'OT standard sans ré-optimisation.
Garantie Théorique : Les auteurs établissent une borne uniforme sur l'écart de l'équité entre la solution de la population et les approximations par échantillons finis pour tout coût dans la famille paramétrée. La borne dépend de la taille de l'échantillon et de la bornitude de la fonction de coût.

3. Contributions Clés

Nouvelle Notion d'Équité : Introduction d'une définition d'équité de groupe flexible et basée sur des cibles pour l'OT, permettant aux planificateurs de spécifier des probabilités d'appariement inter-groupes arbitraires.
Algorithmes :
- FairSinkhorn : Un solveur exact pour les plans d'OT équitables.
- OT Pénalisé : Une relaxation convexe permettant des compromis ajustables entre coût et équité.
- Apprentissage de Coût : Un cadre d'optimisation bilével pour apprendre des coûts qui induisent des appariements équitables, permettant la généralisation à de nouvelles données.
Analyse Théorique :
- Preuve d'existence/unicité pour l'OT équitable exact.
- Dérivation d'une borne de complexité d'échantillonnage pour l'OT entropique pénalisé (montrant une convergence en $O(n^{-1/2})$ ).
- Dérivation d'une borne de déviation uniforme pour l'approche d'apprentissage de coût, garantissant l'équité sur des données non vues.
Validation Empirique : Des expériences sur des données synthétiques (mélanges gaussiens et distributions circulaires) et un jeu de données semi-synthétique d'application de rencontre démontrent l'efficacité des approches et les compromis coût-équité.

4. Résultats

Contrôle du Compromis : L'approche pénalisée parvient à interpoler avec succès entre l'OT classique (faible coût, haute injustice) et FairSinkhorn (équité parfaite, coût élevé), permettant un contrôle précis via le paramètre de pénalité $\lambda$ .
Sensibilité Géométrique : Sur les jeux de données synthétiques, l'approche pénalisée atteint généralement un meilleur compromis coût-équité que l'apprentissage de coût lorsque la géométrie des données est complexe (ex. : distributions circulaires), car l'OT pénalisé n'impose aucune restriction structurelle sur la carte de transport. Cependant, l'apprentissage de coût avec des réseaux de neurones peut approximer des cibles complexes là où les coûts linéaires (Mahalanobis) échouent.
Généralisation : Dans l'expérience de "réutilisabilité", les coûts appris (tant Mahalanobis que MLP) maintiennent des niveaux d'équité sur de nouveaux échantillons de test comparables aux performances d'entraînement, surpassant nettement l'OT classique. Le temps d'inférence pour appliquer un coût appris était nettement inférieur à la résolution d'un nouvel OT pénalisé pour chaque nouveau lot.
Application au Monde Réel : Sur le jeu de données d'application de rencontre (haute dimension, multiples groupes), les méthodes ont reproduit le compromis convexe coût-équité observé dans les contextes synthétiques, validant leur applicabilité à des scénarios réels complexes.

5. Signification et Revendications

Le papier prétend fournir un cadre principled pour les régulateurs et les concepteurs de marchés afin d'imposer des cibles d'équité dans les mécanismes d'appariement. En formulant l'équité comme des contraintes de masse explicites entre les groupes, ce travail comble le fossé entre le transport optimal théorique et les exigences politiques pratiques (ex. : quotas, objectifs de diversité).

Les auteurs soulignent que leur travail :

Offre une définition flexible de l'équité capable de s'adapter à divers objectifs législatifs ou politiques (ex. : la règle des quatre cinquièmes ou les quotas de diversité).
Fournit des garanties théoriques tant sur l'efficacité statistique de l'approche pénalisée que sur la capacité de généralisation de l'approche d'apprentissage de coût.
Met en évidence le compromis entre efficacité (coût de transport) et équité, démontant que si l'équité exacte est possible, les approches relaxées offrent souvent un équilibre plus pratique.

Le papier conclut en notant des limites : le cadre actuel se concentre sur l'équité de groupe et ne s'étend pas directement à l'équité individuelle. De plus, bien que les méthodes optimisent le processus d'appariement, les auteurs reconnaissent que la conception de la cible d'équité elle-même reste une décision politique et éthique située en dehors du champ de l'algorithme. Des travaux futurs sont suggérés pour explorer l'équité individuelle, une analyse plus profonde du compromis équité-biais, et la modélisation de l'impact des appariements sur les résultats individuels.