📊 statistics

Maximin Relative Improvement: Fair Learning as a Bargaining Problem

Cet article propose un cadre de théorie des jeux pour l'équité de groupe qui interprète les sous-populations comme des agents de négociation et introduit un objectif d'« amélioration relative maximin », lequel récupère la solution de Kalai-Smorodinsky afin d'assurer un apprentissage équitable, invariant à l'échelle et monotone, entre des groupes présentant des prévisibilités variables.

Auteurs originaux : Jiwoo Han, Moulinath Banerjee, Yuekai Sun

Publié 2026-06-17

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Jiwoo Han, Moulinath Banerjee, Yuekai Sun

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 êtes un entraîneur essayant de concevoir un plan d'entraînement unique pour une équipe composée de deux groupes d'athlètes très différents : le Groupe A (qui est naturellement très en forme et peut améliorer sa vitesse de beaucoup avec de l'entraînement) et le Groupe B (qui est naturellement moins en forme et a beaucoup plus de mal à progresser, peu importe l'entraînement fourni).

Le document pose une question simple mais délicate : Comment créer un plan d'entraînement unique qui soit « équitable » pour les deux groupes ?

L'ancienne méthode : L'approche « absolue »

La plupart des méthodes actuelles tentent d'être équitables en se basant sur des chiffres absolus. Elles disent : « Assurons-nous que les deux groupes s'améliorent exactement de la même quantité, par exemple 5 secondes. »

Le document soutient que c'est comme essayer de forcer un marathonien et un bambin à courir exactement la même distance.

Le Groupe A (le marathonien) pourrait n'avoir besoin de courir qu'un petit peu pour obtenir cette amélioration de 5 secondes.
Le Groupe B (le bambin) pourrait devoir courir jusqu'à l'épuisement total juste pour obtenir ces mêmes 5 secondes.

Dans le pire des cas, l'approche « absolue » pourrait pousser le Groupe B à un tel point qu'il devient plus lent qu'au départ, simplement pour satisfaire la règle selon laquelle le Groupe A doit aussi gagner 5 secondes. Le document appelle cela « extraire tout le signal disponible » du groupe facile tout en « mal servir » le groupe difficile.

La nouvelle idée : L'approche « relative »

Les auteurs proposent une nouvelle façon de penser la loyauté, en utilisant un concept de la théorie des jeux appelé la Négociation (Bargaining).

Imaginez que les deux groupes sont assis à une table pour négocier un accord.

Le point de désaccord : S'ils ne parviennent pas à un accord, ils reviennent tous deux à leur plan « par défaut » (ne rien faire de spécial). C'est leur base de référence.
Le point idéal : Si chacun pouvait avoir son propre plan personnalisé, ils atteindraient leur amélioration maximale possible.
L'accord : Ils doivent s'entendre sur un seul et même plan partagé.

Au lieu de demander : « Qui s'est amélioré le plus en secondes ? », le document demande : « Quel pourcentage de son propre potentiel chaque groupe a-t-il capturé ? »

Si le Groupe A avait le potentiel de s'améliorer de 10 secondes, et que le plan partagé lui donne 5 secondes, il a capturé 50 % de son potentiel.
Si le Groupe B n'avait le potentiel de s'améliorer que de 2 secondes, et que le plan partagé lui donne 1 seconde, il a également capturé 50 % de son potentiel.

C'est ce qu'on appelle l'Amélioration Relative. L'objectif du document est de trouver le plan où le groupe ayant le plus faible pourcentage de potentiel capturé est le plus élevé possible. C'est comme dire : « Assurons-nous que le groupe qui reçoit le moins bon marché par rapport à ses propres limites reçoit tout de même une part équitable de ses propres possibilités. »

La métaphore de la « Négociation »

Le document relie ce calcul à une solution célèbre en économie appelée la solution de Kalai–Smorodsky.

Imaginez que l'on partage une pizza, mais que les parts sont de tailles différentes car les groupes ont des appétits différents (des potentiels différents) :

Les anciennes méthodes essaient de donner la même taille de part à tout le monde (équité absolue). Si une personne est affamée et l'autre est rassasiée, cela ne fonctionne pas bien.
La nouvelle méthode regarde à quel point la faim de chaque personne est satisfaite. Elle garantit que si une personne est remplie à 50 %, l'autre l'est aussi à 50 %, quelle que soit la taille de son estomac.

Pourquoi cela importe

Le document démontre trois points principaux :

C'est plus équitable : Cela empêche le groupe « difficile » d'être écrasé simplement pour aider le groupe « facile ». Cela garantit qu'aucun groupe ne finit dans une situation pire qu'avant le début de la négociation (une règle appelée « rationalité individuelle »).
C'est mathématiquement solide : Les auteurs montrent que cette méthode est la seule qui satisfait un ensemble spécifique de règles logiques (axiomes) qui font sens pour une négociation équitable, telles que l'« invariance d'échelle » (peu importe si l'on mesure la vitesse en secondes ou en minutes, l'équité reste la même).
Cela fonctionne dans la réalité : Ils ont testé cela sur des données réelles (prédiction des revenus en fonction de l'âge, de l'éducation, etc., à travers différents États américains et groupes raciaux). Ils ont constaté que dans de nombreux scénarios réels, les différents groupes ont des « potentiels » de prédictibilité très différents. Les anciennes méthodes échouaient ici, nuisant souvent au groupe le plus difficile à prédire, tandis que la nouvelle méthode d'« Amélioration Relative » équilibrait le succès de manière équitable.

Résumé

En bref, le document suggère que lorsqu'on construit des modèles d'IA pour des groupes divers, nous ne devrions pas seulement regarder qui s'est amélioré le plus en chiffres bruts. Au lieu de cela, nous devrions regarder quel pourcentage de leur propre potentiel chaque groupe a pu utiliser. En traitant l'équité comme une négociation où chaque groupe obtient un pourcentage équitable de son propre succès possible, nous évitons de laisser les groupes les plus vulnérables de côté.

Résumé Technique : L'Amélioration Relative Maximin comme Problème de Négociation

1. Formulation du Problème

L'article traite du défi du déploiement d'un prédicteur unique et unifié à travers plusieurs sous-populations (groupes), où l'optimisation pour un groupe dégrade souvent les performances sur les autres. Les approches existantes, telles que la minimisation du risque du pire groupe (Group DRO) ou la minimisation du regret du pire groupe (Minimax Regret), reposent sur des comparaisons absolues de risque ou de regret entre les groupes.

Les auteurs soutiennent que les critères absolus échouent lorsque les groupes diffèrent en termes de prédictibilité inhérente (le « potentiel d'amélioration » disponible par rapport à un prédicteur de référence). Si le Groupe A possède un large potentiel d'amélioration et que le Groupe B en possède un faible, une approche de regret minimax absolue peut allouer la quasi-totalité de la capacité du modèle au Groupe A pour minimiser son regret absolu, laissant potentiellement le Groupe B avec une performance pire que celle de la référence. Cela se produit car une unité de réduction de risque absolue n'est pas équivalente d'un groupe à l'autre lorsque les rapports signal/bruit diffèrent.

2. Méthodologie : L'Apprentissage Équitable comme Problème de Négociation

Le Cadre de Négociation

Les auteurs recadrent l'équité de groupe comme un problème de négociation coopérative entre des sous-populations.

Joueurs : Les sous-populations (groupes).
Point de Désaccord ( $d$ ) : Le risque encouru par un prédicteur de référence $f_0$ (par exemple, la moyenne inconditionnelle en régression ou la classe majoritaire en classification). Cela représente le résultat si les groupes ne parviennent pas à coopérer.
Point Idéal ( $u^{max}$ ) : Le risque encouru par le prédicteur optimal pour chaque groupe $f^*_g$ .
Ensemble Faisable : L'ensemble des vecteurs de risque réalisables $\mathcal{R}(\mathcal{F})$ induits par la classe de fonctions $\mathcal{F}$ .

L'optimisation recherche un compromis où les groupes sacrifient une partie de leurs performances individuelles optimales pour atteindre une solution mutuellement acceptable.

Critère d'Amélioration Relative

L'article propose l'Amélioration Relative ( $\rho_g$ ) comme métrique d'équité. Pour un groupe $g$ , elle est définie comme le ratio de la réduction de risque réelle obtenue par un prédicteur $f$ par rapport à la réduction de risque maximale possible (l'écart entre la référence et l'optimal du groupe) :

$\rho_g(f) = \frac{R_g(f_0) - R_g(f)}{R_g(f_0) - R_g(f^*_g)}$

L'objectif d'apprentissage proposé est l'Amélioration Relative Maximin (MMRI) :
$f_{RI} = \arg \max_{f \in \mathcal{F}} \min_{g \in \mathcal{G}} \rho_g(f)$

Connexion Théorique : La Solution de Kalai–Smorodinsky

Les auteurs établissent que le critère MMRI correspond exactement à la solution de négociation de Kalai–Smorodinsky (KS) (Kalai & Smorodinsky, 1975).

Interprétation Géométrique : Dans l'espace d'utilité (où l'utilité est le risque négatif), la solution KS est l'unique point sur la frontière de Pareto qui égalise les gains relatifs par rapport au point de désaccord pour tous les joueurs.
Justification Axiomatique : La solution KS est caractérisée de manière unique par quatre axiomes :
1. Optimalité de Pareto (PO) : Aucun groupe ne peut être amélioré sans nuire à un autre.
2. Symétrie (SYM) : Les groupes ayant des ensembles faisables et des points de désaccord identiques sont traités de la même manière.
3. Invariance d'Échelle (SI) : La solution est invariante aux transformations affines de l'échelle d'utilité (crucial lorsque les groupes ont des prédictibilités de base différentes).
4. Monotonie Individuelle (IM) : Si l'ensemble faisable s'étend (plus d'options disponibles) tout en gardant les optima des autres groupes fixes, aucun groupe ne devrait être lésé.

L'article prouve que pour $m=2$ groupes, le MMRI satisfait les quatre axiomes. Pour $m > 2$ , il utilise le raffinement leximin (maximin lexicographique) pour assurer l'unicité et l'optimalité de Pareto, satisfaisant des versions modifiées de ces axiomes.

Comparaison avec les Méthodes Existantes

L'article cartographie les méthodes d'optimisation robuste existantes vers d'autres solutions de négociation classiques :

Group DRO (Minimax Risk) : Correspond à une solution rawlsienne (maximisant l'utilité absolue minimale).
Maximin Explained Variance : Correspond à une solution égalitaire (égalisant les gains absolus par rapport au point de désaccord).
Minimax Regret : Correspond à une solution de perte égale (Equal Loss) (égalisant les écarts absolus par rapport au point idéal).

Contrairement au MMRI, ces méthodes manquent généralement d'Invariance d'Échelle, ce qui conduit aux échecs observés lorsque les groupes présentent une prédictibilité hétérogène.

Bien-poséité et Convergence

Les auteurs vérifient que le problème d'apprentissage induit un problème de négociation bien posé en établissant les conditions sous lesquelles l'ensemble de risque faisable $\mathcal{R}(\mathcal{F})$ est compact et son enveloppe convexe ne contient aucun point Pareto non réalisable. Ces conditions sont remplies pour :

Les contextes paramétriques (espace de paramètres compact et convexe, perte continue convexe).
Les contextes non paramétriques RKHS (classe de fonctions convexe et compacte, applications continues).

De plus, l'article établit une garantie de convergence en échantplonnage fini de $O(1/\sqrt{n})$ pour l'estimateur empirique de l'amélioration relative maximin, correspondant aux taux des méthodes basées sur le regret sous des conditions de régularité standard (perte Lipschitz, conditions d'entropie).

3. Principales Contributions

L'Amélioration Relative comme Critère d'Équité : Propose une métrique qui normalise la réduction de risque par le potentiel d'amélioration spécifique au groupe, assurant la comparabilité entre des groupes ayant des prédictibilités inhérentes différentes.
Cadre de Négociation Unifié : Démontre que les méthodes d'équité robuste existantes (Group DRO, Minimax Regret, etc.) sont équivalentes à des solutions de négociation classiques spécifiques, permettant une comparaison axiomatique de leurs engagements normatifs.
Caractérisation Axiomatique : Prouve que l'Amélioration Relative Maximin est l'unique solution satisfaisant l'Optimalité de Pareto, la Symétrie, l'Invariance d'Échelle et la Monotonie Individuelle (ou ses raffinements leximin pour $m>2$ ).
Garantie de Non-Nuisance (No-Harm) : Montre que si le prédicteur de référence est dans la classe de fonctions ( $f_0 \in \mathcal{F}$ ), la solution MMRI garantit qu'aucun groupe ne performe moins bien que la référence (Rationalité Individuelle), une propriété que le Minimax Regret viole.
Garanties en Échantplonnage Fini : Fournit des taux de convergence pour l'estimateur empirique.

4. Résultats Empiriques

Les auteurs évaluent la méthode sur les données de l'American Community Survey (ACS) 2018, prédisant le logarithme des revenus à travers 50 États américains avec des partitions binaires (sexe, race) et diverses caractéristiques (âge, éducation, statut matrimonial, statut de chef de ménage).

Observation de l'Asymétrie : L'étude constate que la prédictibilité différentielle est omniprésente. Le « ratio d'écart » (ratio des améliorations potentielles entre les groupes) varie de 0,04 à 3,48. Dans 73 % des configurations, l'asymétrie est modérée à extrême ; dans la partition de la race, 86 % des États montrent une asymétrie extrême pour le statut de chef de ménage.
Comparaison de Performance :
- Minimax Regret (MMR) : Dans les cas de forte asymétrie (ex: Dakota du Nord, partition de la race, caractéristique de l'âge), le MMR alloue presque toute la capacité du modèle au groupe ayant le plus haut potentiel d'amélioration, ce qui fait que l'autre groupe performe moins bien que la référence (ex: -74 % d'amélioration relative).
- Maximin Relative Improvement (MMRI) : Équilibre systématiquement l'amélioration relative entre les groupes (ex: atteignant 57 % pour les deux groupes dans l'exemple du Dakota du Nord), évitant ainsi de « nuire » au groupe moins prédictible.
- Autres Méthodes : Le Group DRO et le Maximin Explained Variance s'écartent également de la ligne d'amélioration relative égale dans les contextes asymétriques.

5. Signification et Revendications

L'article affirme que l'interprétation de l'équité comme un problème de négociation fournit une base axiomatique et fondée pour choisir les critères d'équité.

L'Invariance d'Échelle est Critique : Les auteurs soutiennent que lorsque les groupes diffèrent par leur prédictibilité inhérente, des critères invariants d'échelle (comme KS/Amélioration Relative) sont nécessaires pour éviter d'extraire des fractions inégales du signal disponible.
Guide de Décision : Le cadre ne prétend pas qu'un critère est universellement supérieur. Au contraire, il sert de guide de décision : les praticiens doivent identifier quels axiomes (ex: Invariance d'Échelle vs Monotonie Forte) sont les plus pertinents dans leur contexte. Si les groupes ont une prédictibilité hétérogène, les propriétés axiomatiques du MMRI en font le choix naturel.
Pont Théorique : Ce travail jette un pont entre la théorie des jeux coopératifs et l'apprentissage équitable, prouvant que les hypothèses standards de l'apprentissage (compacité, convexité) sont suffisantes pour importer les solutions de négociation classiques dans le machine learning sans recours à des choix de pénalités ad hoc.

Les auteurs notent des limites, notamment la complexité computationnelle de trouver les solutions leximin pour de nombreux groupes et les défis liés à l'extension de ce cadre aux régimes sur-paramétrés où la convexité stricte et les contrôles de complexité standards peuvent échouer.