Proportionality Degree in Participatory Budgeting

Cette étude initie l'analyse du degré de proportionnalité dans le budget participatif en démontrant que, malgré des garanties axiomatiques différentes, les règles de la Méthode des Parts Égales et de Phragmen offrent un degré de proportionnalité quantitativement équivalent, une conclusion validée par des expérimentations sur des données réelles.

L'essentiel

🗳️ Le Budget Participatif : Comment partager l'argent du quartier équitablement ?

Imaginez que votre ville a une grosse somme d'argent (disons 1 million d'euros) à dépenser pour améliorer le quartier. Au lieu que le maire décide seul, on demande aux habitants : « Qu'est-ce qu'on achète ? Un nouveau terrain de foot ? Des arbres ? Une bibliothèque ? ». C'est le budget participatif.

Mais il y a un problème : tout le monde ne veut pas la même chose.

• Le groupe des parents veut une école.
• Le groupe des sportifs veut un stade.
• Le groupe des artistes veut un mur de street-art.

Comment choisir les projets pour que chaque groupe se sente représenté, même s'il est plus petit que les autres ? C'est là que les mathématiciens entrent en jeu.

🎯 Le Problème : La "Proportionnalité"

Les chercheurs de ce papier (de l'Université d'Édimbourg et de l'IIT Hyderabad) se posent une question précise : Quelle est la meilleure méthode pour garantir que les petits groupes obtiennent leur juste part de l'argent ?

Ils appellent cela le degré de proportionnalité.

• Analogie : Imaginez un gâteau. Si un groupe représente 10 % des gens, il devrait obtenir environ 10 % du gâteau. Mais si le gâteau est découpé en gros morceaux (des projets très chers), un petit groupe pourrait ne jamais pouvoir s'en payer un seul. La proportionnalité mesure à quel point la méthode réussit à donner aux groupes ce qu'ils méritent, même dans le pire des cas.

⚔️ Les Deux Champions : MES vs Phragmén

Le papier compare deux méthodes célèbres pour répartir cet argent, comme deux champions de boxe qui s'affrontent :

1. La Méthode des Parts Égales (MES) :

   • L'idée : On donne à chaque habitant une part égale de l'argent (comme des pièces de monnaie virtuelles). Pour acheter un projet, les habitants qui le veulent doivent mettre leur propre argent dans la cagnotte.
   • Sa réputation : C'est le champion théorique. Il respecte des règles très strictes de justice (appelées axiomes). On pense qu'il est le "meilleur" parce qu'il est très juste sur le papier.

2. La Règle Séquentielle de Phragmén :

   • L'idée : Imaginez que l'argent coule comme de l'eau dans un tuyau. Dès qu'un groupe de gens a accumulé assez d'eau (de crédits) pour payer un projet, le robinet s'ouvre et le projet est acheté.
   • Sa réputation : Il est un peu moins strict sur les règles théoriques que le MES, mais il est très rapide et populaire.

🤯 La Grande Surprise

On s'attendrait à ce que le MES, qui a de meilleures règles théoriques, gagne haut la main et donne beaucoup plus de satisfaction aux petits groupes.

Mais la surprise du papier est là :
En regardant les chiffres réels (la "proportionnalité"), les deux méthodes sont pratiquement identiques !

• L'analogie : C'est comme si deux coureurs de marathon portaient des chaussures différentes. L'un porte des chaussures de course ultra-performantes (MES) et l'autre des baskets classiques (Phragmén). On pensait que le premier arriverait bien devant. Mais en réalité, ils arrivent à la même seconde près. Le papier prouve mathématiquement que leur "score de justice" est le même, même si leurs façons de fonctionner sont différentes.

🧪 L'Expérience Réelle

Les chercheurs ne se sont pas contentés de faire des calculs sur du papier. Ils ont pris 100 vrais cas de budgets participatifs (de vraies villes, de vrais habitants, de vrais projets) pour tester ces méthodes.

Les résultats de l'expérience :

1. Les deux champions sont excellents : Que ce soit le MES ou Phragmén, ils donnent tous les deux de très bons résultats pour les groupes de citoyens.
2. Le "Gourou" perd : Ils ont aussi testé une méthode très simple utilisée dans la vraie vie : la méthode "Gourou" (ou Greedy). Cette méthode consiste juste à choisir les projets les plus populaires, un par un, sans se soucier des groupes.
   • Résultat : La méthode Gourou est beaucoup moins juste. Elle ignore souvent les petits groupes au profit des gros.
3. La nuance : Parfois, Phragmén est légèrement meilleur que le MES, et vice-versa, mais la différence est minime.

💡 La Conclusion Simple

Ce papier nous apprend trois choses importantes :

1. La théorie ne dit pas tout : Même si une méthode (MES) a de meilleures règles écrites, elle n'est pas forcément "plus juste" en chiffres qu'une autre (Phragmén) qui semble plus simple.
2. Évitez la méthode "Gourou" : Si vous organisez un budget participatif, ne choisissez pas simplement les projets les plus votés. Utilisez des méthodes comme MES ou Phragmén pour protéger les minorités.
3. L'équité est atteignable : Les deux méthodes étudiées sont d'excellents outils pour s'assurer que chaque citoyen, qu'il soit dans un grand groupe ou un petit, a sa part du gâteau.

En résumé : Que vous utilisiez la méthode des parts égales ou celle du robinet qui coule, vous obtiendrez un résultat très équitable, bien meilleur que de simplement suivre la majorité aveuglément.

Résumé technique

Voici un résumé technique détaillé de l'article « Proportionality Degree in Participatory Budgeting » en français.

1. Problématique et Contexte

Le budget participatif (PB) est un processus démocratique permettant aux citoyens d'influencer l'allocation des fonds publics. Bien que des méthodes axiomatices (comme la Représentation Justifiée Étendue - EJR) aient été développées pour garantir l'équité, ces propriétés sont binaires (une règle les satisfait ou non). Pour quantifier dans quelle mesure une règle assure une représentation proportionnelle, les auteurs introduisent et étudient le degré de proportionnalité.

L'objectif de l'article est d'analyser ce degré pour deux règles populaires en PB :

1. La Méthode des Parts Égales (Method of Equal Shares - MES) : Connue pour satisfaire l'EJR (une garantie axiomatiche forte).
2. La Règle Séquentielle de Phragmèn : Satisfait la Représentation Justifiée Proportionnelle (PJR) mais échoue à satisfaire l'EJR.

Le défi central est de déterminer si la supériorité axiomatiche de la MES se traduit par un meilleur degré de proportionnalité quantitatif par rapport à la règle de Phragmèn, ou si les deux partagent des garanties similaires malgré leurs différences théoriques.

2. Méthodologie

Les auteurs adoptent une approche hybride combinant l'analyse théorique rigoureuse et l'évaluation expérimentale.

A. Cadre Théorique

• Définitions : Ils utilisent la notion de groupe $\mathcal{T}$-cohésif (un groupe de votants qui approuve unanimement un ensemble de projets $\mathcal{T}$ et dont la taille est proportionnelle au coût de ces projets par rapport au budget total).
• Degré de Proportionnalité ($d_f(\mathcal{T})$) : Défini comme la borne inférieure pire cas de la satisfaction moyenne des membres d'un groupe cohésif $\mathcal{T}$ sous une règle $f$.
• Preuves :
  • Pour la MES, ils développent un lemme bornant le paiement maximal d'un électeur dans un groupe cohésif, puis déduisent une borne inférieure et une borne supérieure (presque exactes) sur le degré de proportionnalité.
  • Pour Phragmèn, ils utilisent une argumentation par fonction potentielle (similaire à celle utilisée en vote multi-gagnants) pour établir des bornes inférieures et supérieures.
  • Ils prouvent également un résultat général pour toute règle satisfaisant l'EJR dans des instances « ordinaires » (où aucun projet n'est excessivement bon marché).

B. Évaluation Expérimentale

• Données : Utilisation de 100 instances réelles issues de la bibliothèque Pabulib.
• Règles comparées :
  1. MES (standard).
  2. Phragmèn Séquentiel (standard).
  3. MES avec épuisement du budget (ajout de projets restants via une règle gloutonne).
  4. Phragmèn avec épuisement.
  5. Règle gloutonne (Greedy Approval) : sélectionne les projets par ordre de score d'approbation (référence pratique courante).
• Protocole : Échantillonnage aléatoire de sous-ensembles de projets pour calculer le degré de proportionnalité moyen, car le calcul exhaustif est exponentiel.

3. Contributions Clés et Résultats

Résultats Théoriques

• Équivalence Quantitative : La contribution majeure est la preuve que, malgré le fait que la MES satisfait l'EJR (plus fort) et que Phragmèn ne le fait pas, les deux règles possèdent le même degré de proportionnalité (à des facteurs constants près).
• Bornes Établies : Pour un ensemble de projets $\mathcal{T}$, le degré de proportionnalité est borné par :
  $$d(\mathcal{T}) \approx \frac{1}{2} \left( \frac{\text{cost}(\mathcal{T})}{\max_{t \in \mathcal{T}} \text{cost}(t)} - 1 \right)$$
  Cela indique une similarité structurelle profonde entre les deux méthodes du point de vue de la proportionnalité quantitative.
• Limites Supérieures : Ils montrent qu'aucune règle ne peut dépasser une borne supérieure de $\frac{\text{cost}(\mathcal{T})}{\max \text{cost}(t)} - 1$, suggérant que MES et Phragmèn sont potentiellement optimales pour ce problème.

Résultats Expérimentaux

• Performance Supérieure : Les règles MES et Phragmèn (avec ou sans épuisement) surpassent nettement la règle gloutonne sur la majorité des jeux de données réels.
• Comparaison MES vs Phragmèn :
  • En pratique, les performances sont très comparables.
  • La règle Phragmèn avec épuisement tend à performer légèrement mieux que la MES avec épuisement sur plusieurs jeux de données.
  • Même sans épuisement, Phragmèn se comporte souvent mieux que la MES standard.
• Rôle de l'épuisement : L'ajout d'une phase d'épuisement (remplir le budget restant avec des projets restants) améliore généralement le degré de proportionnalité pour toutes les règles.

4. Signification et Conclusion

• Réconciliation Théorie/Pratique : L'article démontre que la supériorité axiomatiche de la MES (EJR) ne se traduit pas nécessairement par un avantage quantitatif en termes de degré de proportionnalité par rapport à Phragmèn. Les deux règles offrent des garanties de proportionnalité équivalentes.
• Recommandation Pratique : Les résultats soutiennent l'utilisation de la MES et de la règle de Phragmèn dans les applications réelles de budget participatif, les recommandant fortement par rapport à la règle gloutonne (souvent utilisée par défaut pour sa simplicité), car ces dernières assurent une meilleure représentation des groupes de citoyens.
• Optimalité Conjecturée : Les auteurs conjecturent que ces deux règles sont optimales pour le problème du degré de proportionnalité, car leurs performances correspondent aux bornes théoriques supérieures dérivées.

En résumé, ce travail comble un vide dans la littérature en quantifiant la proportionnalité en PB, établissant que deux approches algorithmiques distinctes (basées sur le partage de budget vs accumulation de crédits temporels) convergent vers les mêmes garanties de performance quantitative.