Résumé Technique : Une Théorie Générale de la Proportionnalité avec des Utilités Additives

1. Énoncé du Problème

L'article traite du problème de la sélection d'un sous-ensemble réalisable de candidats à partir d'un ensemble $C$ basé sur les préférences des votants, sous des contraintes de faisabilité générales définies par une famille de sous-ensembles $\mathcal{F} \subseteq 2^C$. Ce cadre généralise plusieurs modèles établis en théorie du choix social, notamment :

• Élections de comités : Sélectionner un nombre fixe de candidats.
• Budgétisation Participative (BP) : Sélectionner des projets dans un budget total.
• Prise de décision publique et agrégation de jugements : Prendre des décisions sur de multiples questions indépendantes.
• Contraintes de diversité : Garantir des propriétés structurelles spécifiques (par exemple, l'équilibre hommes-femmes) dans l'ensemble sélectionné.

Bien que des axiomes de proportionnalité (tels que la Représentation Justifiée) aient été définis pour ce modèle général, les règles existantes sont principalement conçues pour les bulletins d'approbation (où les votants assignent une utilité de 0 ou 1). L'article se concentre sur le cadre plus complexe des utilités additives, où chaque votant $i$ assigne une utilité numérique $u_i(c) \geq 0$ à chaque candidat $c$. L'objectif est de concevoir des règles qui garantissent une représentation équitable pour les groupes de votants cohésifs sous ces contraintes générales et utilités cardinales.

2. Méthodologie

Les auteurs proposent deux approches algorithmiques primaires inspirées par le concept de votants « achetant » des candidats avec une monnaie virtuelle.

2.1 La Règle PropRank

PropRank est une règle séquentielle inspirée de la règle séquentielle de Phragmén, mais adaptée aux utilités additives.

• Mécanisme : Les votants gagnent de l'argent virtuel à un taux constant au fil du temps. La règle simule un processus d'achat où les votants décident de combien ils dépensent pour les candidats.
• Mécanisme de prévoyance (Foresight) : Contrairement aux approches gourmandes (greedy) standards, PropRank permet aux votants d'anticiper les opportunités futures. Ils calculent un « facteur d'échelle » $\lambda_i$ basé sur le meilleur ratio paiement-utilité qu'ils pourraient obtenir s'ils attendaient qu'un candidat plus désirable devienne abordable.
• Fonction de dépense : Un votant $i$ accepte de dépenser au plus $x_i(c, r)$ pour le candidat $c$ au tour $r$, défini par une formule impliquant son budget actuel, l'utilité du candidat et le facteur d'échelle. Cela garantit que le ratio paiement-utilité ne dépasse pas le meilleur achat fractionnaire disponible.
• Classement : L'algorithme construit un classement complet des candidats par leurs horodatages d'achat (timestamps). Puisque les candidats infaisables ne sont pas supprimés pendant le processus (seulement à la fin de la construction du classement pour des tailles de comités spécifiques), chaque préfixe du classement satisfait la proportionnalité.

2.2 Méthode Généralisée des Parts Égales (MES)

Les auteurs étendent la Méthode des Parts Égales (originalement pour la BP) à des contraintes générales.

• Structure : L'algorithme opère en cycles (rounds). Dans chaque cycle, il détermine le montant maximal d'argent qui peut être alloué aux votants de telle sorte que la sous-routine « Parts Égales » puisse acheter un ensemble de candidats sans violer les contraintes de faisabilité.
• Prévoyance dans MES : Similaire à PropRank, la version généralisée de MES incorpore un mécanisme de prévoyance. Elle calcule des bornes supérieures de dépenses ($capi$) pour empêcher les votants de dépenser trop tôt sur des candidats qui pourraient être moins efficaces que ceux disponibles dans les itérations futures.
• Heuristiques de Backtracking : L'article introduit des variantes heuristiques (PropRankRem, PropRankBacktrack) qui redémarrent la procédure ou effectuent un retour en arrière (backtrack) lorsque des candidats sont supprimés, visant à réduire les budgets non dépensés et à améliorer les performances pratiques, bien qu'elles manquent des mêmes garanties théoriques que les règles de base.
• Dépassement de Budget Limité (BOS) : Une adaptation de la méthode BOS est proposée pour les contraintes générales, où l'algorithme identifie le plus grand horodatage valide pour l'achat avant que la faisabilité ne soit violée.

3. Contributions Clés

3.1 Cadre Théorique

• Axiomes de Proportionnalité pour les Utilités Additives : L'article généralise des axiomes comme la Représentation Justifiée Étendue (EJR) et la Représentation Justifiée Proportionnelle (PJR) aux utilités additives avec des contraintes générales.
• Degré de Proportionnalité : Les auteurs définissent et analysent le « degré de proportionnalité », quantifiant la satisfaction moyenne d'un groupe cohésif. Ils établissent la relation entre l'EJR et le degré de proportionnalité, montrant que pour les contraintes générales, la garantie dépend de la taille du groupe cohésif ($\gamma = |S|/n$).

3.2 Garanties Théoriques

• Garanties de PropRank :
  • Pour les contraintes de Budgétisation Participative, PropRank satisfait un degré de proportionnalité de $d(\alpha) = (\alpha - u_{max})/2$.
  • Pour les contraintes Générales, il satisfait un degré de $d(\alpha) \geq \alpha \cdot \frac{1-\gamma}{2} - \frac{u_{max}}{2}$.
  • Pour les contraintes de Matroïdes, il satisfait un faible degré de proportionnalité de $(\alpha - u_{max})/2$.
• Garanties de PJR : Les règles satisfont des garanties de degré de PJR de $d(\alpha) = (\alpha - u_{max})/(\kappa + 1)$, où $\kappa$ est un paramètre contrôlant la flexibilité de la dépense.

3.3 Extensions Algorithmiques

• L'article fournit la première généralisation de la Méthode des Parts Égales à des contraintes de faisabilité arbitraires avec des utilités additives.
• Il introduit des heuristiques (PropRankRem, PropRankBacktrack) pour traiter le problème des budgets non dépensés dans les scénarios pratiques.

4. Résultats Expérimentaux

Les auteurs ont évalué leurs règles sur plus de 1 300 instances réelles de budgétisation participative issues du jeu de données Pabulib.

• Métriques : L'évaluation a été basée sur les violations d'EJR+ (proportionnalité), le Ratio d'Exclusion (fraction de votants avec une utilité nulle) et le Coût-Satisfaction Moyen (efficacité utilitaire).
• Résultats :
  • Paramètre $\kappa$ : Les expériences indiquent que PropRank avec $\kappa = 1$ (permettant une dépense plus flexible) est nettement plus performant en termes de proportionnalité (moins de violations d'EJR+) que $\kappa = 0$.
  • Heuristiques : Les variantes heuristiques (PropRankRem, PropRankBacktrack) combinées à $\kappa = 0$ ont montré très peu de violations d'EJR+ et des ratios d'exclusion favorables, surpassant souvent le PropRank de base dans les métriques pratiques malgré l'absence de preuves formelles pour ces heuristiques spécifiques.
  • Adaptation BOS : La Méthode des Parts Égales adaptée avec Dépassement de Budget Limité (BOS) a extrêmement bien performé, surpassant l'original BOS-PB en violations d'EJR+ et égalant celui-ci en ratio d'exclusion et en utilité. Elle a également été notée comme la plus efficace en termes de calcul parmi les techniques proposées.
  • Comparaison : Les règles proposées ont généralement atteint un coût-satisfaction comparable ou supérieur aux règles existantes spécifiques à la BP (MES-PB, BOS-PB) tout en gérant des contraintes générales.

5. Signification et Revendications

L'article affirme fournir une théorie générale de la proportionnalité qui comble le fossé entre les modèles spécifiques (comme les élections de comités et la BP) et le paysage plus large des problèmes de sélection contrainte.

• Généralisation : Il démontre que les méthodes établies (Phragmén et Parts Égales) peuvent être étendues à des contraintes de faisabilité arbitraires et des utilités additives sans perdre leurs propriétés fondamentales de proportionnalité.
• Classement : Une contribution significative est la capacité de générer des classements proportionnels (où chaque préfixe est un comité proportionnel) dans le cadre des utilités additives, comblant ainsi une lacune dans la littérature.
• Praticité : Bien que les garanties théoriques soient fortes, les auteurs notent modestement que les variantes heuristiques, qui sacrifient une partie de la tractabilité théorique pour une meilleure performance pratique (réduction des budgets non dépensés), sont très efficaces dans les cas réels.
• Limites : L'article reconnaît que les techniques de preuve pour les algorithmes de base ne s'étendent pas directement aux variantes heuristiques, et que la complexité computationnelle des heuristiques de backtracking peut être exponentielle (atténuée par un paramètre $\sigma$).

En résumé, ce travail établit un fondement théorique robuste pour la représentation proportionnelle sous des contraintes générales et des utilités additives, offrant à la fois des algorithmes prouvables de proportionnalité et des heuristiques pratiques performantes sur des données réelles.