Résumé technique : Représentation proportionnelle dans l'agrégation de rangs

Définition du problème

L'article traite du problème de l'agrégation de rangs, où l'objectif est de combiner un profil de classements d'entrée pondérés en un classement de sortie unique. Dans ce contexte, un profil $R$ consiste en un ensemble de candidats $C$ et une fonction associant à chaque classement possible $\succ$ un poids $R(\succ) \in [0, 1]$, tel que la somme de tous les poids est égale à 1. Ces poids représentent l'importance de différents critères (par exemple, le prix par rapport à la note lors d'une réservation d'hôtel) ou la part des électों soutenant un classement spécifique.

Le défi central identifié est que les fonctions de bien-être social (FBS) classiques, telles que la règle de Kemeny, le compte de Borda et les règles de type Condorcet, sont intrinsèquement majoritaires. Elles ont tendance à sélectionner le classement de sortie qui minimise la distance avec le classement le plus lourdement pondéré, ignorant ainsi les préférences minoritaires. Par exemple, si deux classements inverses ont des poids de 51 % et 49 %, les FBS standards renvoient souvent simplement le classement de 51 %, échouant ainsi à représenter le groupe de 49 %. L'article cherche à concevoir des FBS qui garantissent une représentation proportionnelle, assurant que chaque classement d'entrée influence la sortie proportionnellement à son poids.

Méthodologie et cadre

Les auteurs formalisent la proportionnalité en définissant l'utilité d'un classement d'entrée $\succ$ pour un classement de sortie $\triangleright$ comme le nombre d'accords par paires entre eux :
$$u(\succ, \triangleright) = |\{(x, y) \in C^2 : x \succ y \text{ et } x \triangleright y\}|$$
Puisqu'il y a $\binom{m}{2}$ comparaisons par paires au total pour $m$ candidats, un classement d'entrée avec un poids $\alpha$ devrait idéalement obtenir une utilité d'au moins $\lfloor \alpha \binom{m}{2} \rfloor$.

L'article introduit une hiérarchie d'axiomes de proportionnalité inspirés du vote par approbation de comités et de la budgétisation participative :

1. Représentation justifiée unanime (uJR) : Un affaiblissement exigeant que tout classement d'entrée avec un poids $\ge 1/\binom{m}{2}$ obtienne au moins un accord par paire.
2. Représentation proportionnelle justifiée unanime (uPJR) : L'axiome central exigeant qu'un classement d'entrée avec un poids $\alpha$ obtienne une utilité d'au moins $\lfloor \alpha \binom{m}{2} \rfloor$.
3. Représentation proportionnelle justifiée forte (sPJR) : Un renforcement étendant la garantie aux groupes de classements. Si un sous-profil $S$ possède un poids total $\alpha$, la sortie doit être en accord avec au moins $\lfloor \alpha \binom{m}{2} \rfloor$ comparaisons par paires issues de l'union des classements de $S$.

Pour atteindre ces axiomes, les auteurs adaptent le concept de prixabilité (priceability) issu de la budgétisation participative. Ils modélisent la construction du classement de sortie comme un processus d'achat séquentiel où les candidats (ou les paires de candidats) sont « achetés » en utilisant les budgets des classements d'entrée.

Contributions clés et résultats

1. Limites des méthodes existantes

L'article analyse d'abord la règle de Kemeny au carré (proposée par Lederer et al. [2024] pour le classement proportionnel). Les auteurs prouvent que pour $m \ge 5$, la règle de Kemeny au carré échoue même à l'axiome le plus faible, uJR. Plus précisément, ils construisent des profils où un classement d'entrée ayant un poids significatif reçoit une utilité nulle de la part de la sortie de la règle de Kemeny au carré, démontant ainsi la nécessité de nouveaux mécanismes.

2. La règle de Borda séquentielle proportionnelle (PSB)

Pour satisfaire l'uPJR, les auteurs proposent la règle de Borda séquentielle proportionnelle (PSB).

• Mécanisme : La règle PSB opère de manière séquentielle. À chaque tour, elle sélectionne le candidat maximisant le score de Borda pondéré basé sur les budgets actuels. Elle met ensuite à jour les budgets des classements d'entrée proportionnellement à leur contribution au score du candidat sélectionné, effectuant ainsi un « paiement » pour le placement du candidat.
• Garantie théorique : Les auteurs introduisent un axiome structuré appelé prixabilité de rang (rank-priceability), qui reflète la prixabilité dans la budgétisation participative. Ils prouvent que la prixabilité de rang implique l'uPJR.
• Résultat : Le théorème 4.5 établit que la PSB satisfait la prixabilité de rang et, par conséquent, l'uPJR.
• Garantie quantitative : Au-delà de la satisfaction axiomatique, le théorème 4.6 prouve que la PSB garantit à chaque sous-profil $S$ une utilité moyenne d'au moins $\frac{|S|}{4}\binom{m}{2} - \frac{3}{16}$. Cela fournit une borne inférieure linéaire d'utilité par rapport au poids du groupe.

3. La règle de Borda avec ajustement de flux (FB)

Les auteurs montrent que la PSB échoue à l'sPJR car son schéma de paiement ne protège pas adéquatement les groupes de classements agissant de concert. Pour y remédier, ils introduisent la prixabilité de paire (pair-priceability), un axiome raffiné où les paiements sont effectués pour des paires spécifiques de candidats plutôt que pour de simples rangs.

• Mécanme : La règle de Borda avec ajustement de flux (FB) est un raffinement de la PSB. Comme la PSB, elle sélectionne le gagnant de Borda séquentiellement. Cependant, au lieu d'un simple paiement proportionnel, la FB détermine les paiements en résolvant un problème de flot maximum dans un réseau construit. Ce réseau garantit que le ratio coût par utilité est minimisé tout en respectant les contraintes de budget et de paires.
• Résultat : Le théorème 5.5 prouve que la FB satisfait la prixabilité de paire, ce qui implique l'sPJR (Théorème 5.3).
• Garantie quantitative : Le théorème 5.6 montre que la FB fournit la même garantie d'utilité moyenne linéaire que la PSB ($\frac{|S|}{4}\binom{m}{2} - \frac{3}{16}$), assurant une forte équité tant pour les individus que pour les groupes.

4. Variantes additionnelles

Dans l'appendice, les auteurs discutent de la Méthode des Parts Égales par Rang (RMES), une variante inspirée de la Méthode des Parts Égales (MES) de la budgétisation participative. Ils montrent que la RMES satisfait la prixabilité de rang (et donc l'uPJR) et offre un profil utilitaire légèrement différent, sélectionnant les $\lfloor m/4 \rfloor$ premiers candidats uniquement sur la base des scores de Borda initiaux.

Signification et revendications

L'article affirme présenter les premières fonctions de bien-être social véritablement proportionnelles pour l'agrégation de rangs. Sa principale importance réside dans :

• Le pont entre les domaines : Il transfère avec succès des résultats profonds du vote par approbation de comités et de la budgétisation participative (spécifiquement la PJR et la prixabilité) au domaine de l'agrégation de rangs.
• La résolution d'un problème ouvert : Il résout le problème ouvert de la conception de FBS satisfaisant l'uPJR et l'sPJR, là où les tentatives précédentes (comme la Kemeny au carré) ont échoué.
• Force axiomatique et quantitative : Les règles proposées (PSB et FB) ne sont pas seulement prouvées pour satisfaire des conditions d'équité axiomatiques fortes, mais elles fournissent également des garanties quantitatives robustes sur l'utilité moyenne pour tout groupe d'électeurs, garantissant que les préférences minoritaires ne sont pas systématiquement ignorées.

Les auteurs notent que bien que leur travail se concentre sur l'accord par paire comme métrique d'utilité, il s'agit d'une approche standard dans la littérature. Ils suggèrent que des travaux futurs pourraient explorer des notions d'équité plus fortes (comme l'EJR ou la stabilité du noyau) et des fonctions d'utilité plus générales tenant compte de la valeur variable des différentes positions de classement.