Résumé Technique : La Fin Justifie le Moyen : Une Règle de Classement Linéaire pour les Décisions Séquentielles Proportionnelles

1. Énoncé du Problème

L'article aborde le défi du choix collectif d'une règle de décision pour une utilisation répétée dans des contextes de conception démocratique, tels que l'alignement de l'IA, l'allocation de ressources (par exemple, l'échange de reins, le don d'aliments) et la conception participative. Plus précisément, les auteurs se concentrent sur les règles de classement linéaires, où un lot de $m$ éléments $X = (x_1, \dots, x_m)$, chacun décrit par un vecteur de caractéristiques $x \in \mathbb{R}^d$, est classé en fonction d'un score $s_\theta(x) = \langle \theta, x \rangle$ dérivé d'un vecteur de notation fixe $\theta$.

Le problème d'agrégation central est défini comme suit : Étant donné $n$ types d'électeurs avec des vecteurs de notation idéaux $\theta^{(1)}, \dots, \theta^{(n)}$ et des fractions de population $\alpha^{(1)}, \dots, \alpha^{(n)}$, comment doit-on sélectionner un vecteur de notation collectif $\theta^*$ ?

La préoccupation centrale est l'inégalité représentative dans le temps. Une règle fixe appliquée de manière répétée peut s'aligner systématiquement sur les préférences d'une majorité tout en écartant systématiquement les points de vue minoritaires. L'article cherche un mécanisme d'agrégation qui satisfait la Proportionnalité Individuelle (PI) : si le type d'électeur $i$ constitue une fraction $\alpha^{(i)}$ de la population, le classement collectif doit s'accorder avec le classement préféré du type $i$ sur au moins une fraction $\alpha^{(i)}$ des paires d'éléments.

L'article distingue deux notions de PI :

1. PI à Long Terme : La proportionnalité vaut en espérance sur des lots tirés d'une distribution $\mathcal{D}$.
2. PI par Lot : La proportionnalité vaut pour chaque lot spécifique $X$ (ou en espérance sur l'accord minimum au sein d'un lot).

2. Méthodologie et Cadre Théorique

2.1. L'Échec de la Moyenne Arithmétique

L'approche standard dans la littérature est la moyenne arithmétique ($\theta_{\text{arith}}$), définie comme la moyenne pondérée des vecteurs de notation individuels. Les auteurs citent Feffer et al. [2023] pour démontrer que $\theta_{\text{arith}}$ est sévèrement majoritaire. Dans les « Constructions Antipodales » (où deux types d'électeurs ont des vecteurs diamétralement opposés), la moyenne arithmétique peut converger entièrement vers le vecteur de la majorité, entraînant un accord nul pour la minorité, indépendamment de la taille du lot ou de la distribution.

2.2. La Moyenne Angulaire ($\theta_{\text{ang}}$)

La contribution méthodologique principale est la proposition de la moyenne angulaire comme règle d'agrégation alternative. Elle est définie comme le minimiseur de la somme pondérée des carrés des distances angulaires :
$$\theta_{\text{ang}} := \arg\min_{\theta \in S^{d-1}} \sum_{i=1}^n \alpha^{(i)} \angle(\theta, \theta^{(i)})^2$$
Contrairement à la moyenne arithmétique, qui minimise la distance euclidienne, la moyenne angulaire opère sur la sphère $S^{d-1}$, respectant la nature géométrique des directions de classement.

2.3. Analyse Théorique

Les auteurs analysent les propriétés de $\theta_{\text{ang}}$ sous l'hypothèse de distributions d'éléments à symétrie sphérique ($\mathcal{D}^\circ$).

• PI à Long Terme : Ils prouvent que $\theta_{\text{ang}}$ satisfait la PI à Long Terme (c'est-à-dire atteint un niveau de proportionnalité d'au moins 1) pour tout profil. Cela repose sur une propriété géométrique fondamentale : la moyenne angulaire se situe à l'intérieur d'un angle de $(1 - \alpha^{(i)})\pi$ par rapport au vecteur idéal $\theta^{(i)}$ de chaque électeur.
• PI par Lot : L'article établit un résultat d'impossibilité pour la PI par Lot. Aucune règle de classement linéaire fixe ne peut garantir la proportionnalité pour chaque lot individuel, même lorsque les droits sont entiers. Cela est dû à des lots « quasi-collinéaires » où les éléments s'alignent d'une manière qui force une règle linéaire à être en désaccord complet avec au moins un type d'électeur.
• Convergence : Cependant, les auteurs prouvent que l'écart entre la PI par Lot et la PI à Long Terme diminue rapidement à mesure que la taille du lot $m$ augmente. Plus précisément, l'écart est borné par $O(\sqrt{\frac{\min(\log n, d \log(m/d))}{m}})$.

3. Contributions Clés

1. Existence d'une Règle Linéaire Proportionnelle : L'article prouve que la moyenne angulaire est une règle linéaire fixe, simple et interprétable qui garantit la Proportionnalité Individuelle à Long Terme pour les distributions à symétrie sphérique. Cela résout la question ouverte de savoir si une règle linéaire fixe peut équilibrer des opinions disparates sans être intrinsèquement majoritaire.
2. Propriété Géométrique Fondamentale : Les auteurs établissent un nouveau théorème (Théorème 3.3) concernant la moyenne angulaire en $d$ dimensions : pour tout profil, la moyenne angulaire est garantie de se situer à l'intérieur d'un angle de $(1 - \alpha^{(i)})\pi$ par rapport au vecteur de tout électeur $i$. Cela généralise les résultats connus en 2D à des dimensions supérieures.
3. Bornes d'Impossibilité et de Convergence : L'article prouve formellement que la PI par Lot est impossible pour les règles linéaires fixes (Théorème 4.3) mais démontre que la perte encourue en se restreignant aux règles fixes est négligeable pour de grandes tailles de lot (Théorème 4.5).
4. Robustesse : Il est démontré que la moyenne angulaire est robuste ; si un vecteur de notation est proche de $\theta_{\text{ang}}$ en distance angulaire, ses garanties de proportionnalité ne se dégradent que de manière additive.

4. Résultats Empiriques

Les auteurs évaluent cinq mécanismes d'agrégation sur trois jeux de données réels (Moral Machine, Échange de Reins, Sauvetage d'Aliments) et leurs variantes synthétiques 2D conçues pour augmenter l'hétérogénéité des électeurs :

• Règles Testées : Moyenne Arithmétique ($\theta_{\text{arith}}$), Moyenne Angulaire ($\theta_{\text{ang}}$), Médiane Géométrique, Méthode de Borda, et Borda Séquentiel Proportionnel (PSB).
• Régimes Homogènes : Sur les jeux de données originaux où les préférences des électeurs sont relativement similaires, toutes les règles (y compris la moyenne arithmétique) fonctionnent de manière similaire et satisfont la proportionnalité.
• Régimes Hétérogènes (Données 2D) : Lorsque les vecteurs d'électeurs sont répartis sur un large arc (simulant un fort désaccord) :
  • La moyenne arithmétique et la médiane géométrique échouent de manière significative, tombant souvent en dessous du droit proportionnel (PI-Long < 1).
  • La moyenne angulaire surpasse considérablement la moyenne arithmétique et la médiane géométrique, maintenant une PI-Long $\ge 1$.
  • Le PSB (une règle non linéaire, non fixe) fonctionne le mieux, confirmant que l'assouplissement de la contrainte « linéaire fixe » permet d'obtenir des gains supplémentaires, mais la moyenne angulaire reste la meilleure règle linéaire fixe.
• Convergence : Les résultats empiriques confirment que la PI par Lot converge très rapidement vers la PI à Long Terme à mesure que la taille du lot $m$ augmente, même pour de petites valeurs de $m$.

5. Importance et Revendications

L'article revendique fournir une référence de cas optimal pour l'agrégation des règles de décision. En montrant qu'une règle linéaire fixe (la moyenne angulaire) peut satisfaire la proportionnalité à long terme, les auteurs soutiennent que les pipelines à faible information (qui doivent apprendre des règles à partir de données bruyantes) devraient viser à préserver la structure de la moyenne angulaire.

L'importance réside dans :

• Correction d'un Défaut Majoritaire : Il identifie une alternative simple et interprétable à la moyenne arithmétique qui évite la « tyrannie de la majorité » dans la prise de décision répétée.
• Garanties Théoriques : Il fournit la première preuve qu'une règle linéaire fixe peut satisfaire la proportionnalité individuelle à long terme, une propriété précédemment considérée comme difficile ou impossible pour les règles fixes.
• Applicabilité Pratique : La moyenne angulaire est calculable (via une optimisation basée sur le gradient) et robuste aux distributions non sphériques en pratique, ce qui en fait un candidat viable pour des applications réelles dans l'alignement de l'IA et la conception participative.

Les auteurs restent modestes quant aux limites, reconnaissant que si $\theta_{\text{ang}}$ résout le problème à long terme, il ne peut atteindre la garantie plus forte par lot sans sacrifier la contrainte « linéaire fixe », un compromis qui diminue avec des tailles de lot plus grandes.