Gouvernance multi-agents : scrutins, protocoles, choix social

[DISTILLATION / PÉDAGOGIE] Comment un collectif d’agents décide-t-il ? Ce notebook distille la consolidation du cœur EPITA (tronc argumentation_analysis/agents/core/governance/ + carnet sas docs/coursia_contrib/governance_voting_methods.ipynb) — pas le projet étudiant figé de juin 2025, dont le cœur a corrigé la doctrine.

Ce notebook est la re-fondation de PR #17353 (sous-grain 2 de l’EPIC #4960) sur le périmètre fixé le 22/09 : on distille les consolidations faites dans le cœur, pas les projets étudiants. Généalogie : 2.1.6_multiagent_governance_prototype (le tronc en est « Adapted from » et l’a corrigé — deltas documentés dans l’organe).

Une erreur de catégorie à défaire d’entrée : « 7 méthodes de vote » (#1981)

Le tronc l’interdit nommément : la surface consolidée n’est pas « 7 méthodes de vote ». Elle vaut 15 algorithmes en trois familles qui ne se comparent pas entre elles :

Famille Contenu Question posée
5 scrutins majority, plurality, borda, condorcet, quadratic « quelle option agrège le mieux des préférences sincères ? »
2 protocoles byzantine, raft « comment décider quand une fraction des agents est défaillante ? »
8 fonctions de choix social approval, stv, copeland, kemeny_young(+safe), schulze, condorcet_winner, pairwise_matrix « quel classement collectif minimise le désaccord sur un profil ? »

Un byzantin ou un Raft ne se comparent pas à Borda : ce sont des protocoles de tolérance aux pannes, pas des règles d’agrégation. Les confondre est l’erreur #1981, que le projet étudiant commettait et que le cœur a corrigée.

§1 — L’organe et le scénario du club

L’organe governance_methods.py (stdlib pure, déterministe) porte les 15 algorithmes + la classe Agent (personnalités, confiance, Q-learning) du tronc. Chargeons-le et vérifions la catégorisation.

import sys, random
sys.path.insert(0, ".")  # organe governance_methods.py dans le dossier de la serie
import governance_methods as g

print("SCRUTINS (5)   :", sorted(g.SCRUTINS))
print("PROTOCOLES (2) :", sorted(g.PROTOCOLES))
print("CHOIX SOCIAL (8):", sorted(g.SOCIAL_CHOICE))
total = len(g.SCRUTINS) + len(g.PROTOCOLES) + len(g.SOCIAL_CHOICE)
print(f"\nTotal = {total} algorithmes (pas « 7 methodes » — #1981 corrige)")

# Le scenario du carnet sas : le repas de fin d'annee du club de robotique.
# Sept membres, une destination a choisir, des preferences ordonnees.
OPTIONS = ["Pizza", "Burger", "Sushi", "Raclette"]
PROFIL_PREFS = [
    ("Alice",  ["Pizza", "Sushi", "Burger", "Raclette"]),
    ("Bruno",  ["Pizza", "Raclette", "Sushi", "Burger"]),
    ("Chloe",  ["Pizza", "Burger", "Sushi", "Raclette"]),
    ("Diego",  ["Burger", "Raclette", "Sushi", "Pizza"]),
    ("Emma",   ["Burger", "Sushi", "Raclette", "Pizza"]),
    ("Farid",  ["Sushi", "Burger", "Raclette", "Pizza"]),
    ("Gwen",   ["Raclette", "Burger", "Sushi", "Pizza"]),
]
def build_agents(personality="stubborn", seed=0):
    return [g.Agent(n, personality, p, rng=random.Random(seed + i))
            for i, (n, p) in enumerate(PROFIL_PREFS)]
print(f"\nScenario : {len(PROFIL_PREFS)} membres, {len(OPTIONS)} destinations")
SCRUTINS (5)   : ['borda', 'condorcet', 'majority', 'plurality', 'quadratic']
PROTOCOLES (2) : ['byzantine', 'raft']
CHOIX SOCIAL (8): ['approval', 'condorcet_winner', 'copeland', 'kemeny_young', 'kemeny_young_safe', 'pairwise_matrix', 'schulze', 'stv']

Total = 15 algorithmes (pas « 7 methodes » — #1981 corrige)

Scenario : 7 membres, 4 destinations

Lecture du compte : 15, pas 7

L’organe affiche ses trois familles séparément — la catégorisation est structurelle (trois dictionnaires distincts), pas un commentaire. Le scénario est celui du carnet sas : 7 membres aux préférences hétérogènes. La Pizza a 3 premières places sur 7 — elle gagne à la majorité simple. Mais est-ce le « bon » choix collectif ?

§2 — Les 5 scrutins : une même société, cinq vainqueurs possibles

Exécutons les 5 scrutins sur le même profil. C’est la première leçon du carnet sas.

resultats = {nom: fn(build_agents(), OPTIONS) for nom, fn in g.SCRUTINS.items()}
print(f"{'Scrutin':<12} {'Vainqueur':<10}")
print("-" * 24)
for nom, gagnant in resultats.items():
    print(f"{nom:<12} {gagnant:<10}")
print(f"\n{len(set(resultats.values()))} vainqueur(s) distinct(s) selon le scrutin : "
      f"{sorted(set(resultats.values()))}")

# Detail Borda : le score de chaque destination.
scores = {o: 0 for o in OPTIONS}
for _, p in PROFIL_PREFS:
    for i, o in enumerate(p):
        scores[o] += len(OPTIONS) - i - 1
print("\nScores de Borda :", dict(sorted(scores.items(), key=lambda kv: -kv[1])))
Scrutin      Vainqueur 
------------------------
majority     Pizza     
plurality    Pizza     
borda        Burger    
condorcet    Burger    
quadratic    Pizza     

2 vainqueur(s) distinct(s) selon le scrutin : ['Burger', 'Pizza']

Scores de Borda : {'Burger': 13, 'Sushi': 11, 'Pizza': 9, 'Raclette': 9}

Lecture : la majorité et Borda ne disent pas la même chose

La Pizza gagne à la majorité (3 premières places), mais le score de Borda raconte une autre histoire : les votes « en profondeur » (2e, 3e places) favorisent une option de compromis. Le scrutin choisit le vainqueur autant que les électeurs — c’est le théorème d’Arrow rendu visible sur 7 personnes.

# Duels pairwise : la Pizza gagne la majorite mais perd TOUS ses duels ?
print("Duels pairwise (ligne bat colonne) :")
print(f"{'':>10}", "  ".join(f"{o[:6]:>7}" for o in OPTIONS))
for a in OPTIONS:
    row = []
    for b in OPTIONS:
        if a == b:
            row.append("     --")
        else:
            w = sum(p.index(a) < p.index(b) for _, p in PROFIL_PREFS)
            row.append(f"{w:>7}")
    print(f"{a:>10}", "  ".join(row))

# Vainqueur de Condorcet (gagne tous ses duels) sur ce profil de bulletins.
ballots = [p for _, p in PROFIL_PREFS]
cw = g.condorcet_winner(ballots, OPTIONS)
print(f"\nVainqueur de Condorcet sur ce profil : {cw}")
Duels pairwise (ligne bat colonne) :
             Pizza   Burger    Sushi   Raclet
     Pizza      --        3        3        3
    Burger       4       --        4        5
     Sushi       4        3       --        4
  Raclette       4        2        3       --

Vainqueur de Condorcet sur ce profil : Burger

Lecture : le paradoxe du compromis

La Pizza gagne la majorité mais perd tous ses duels pairwise : une majorité de membres préfère chacune des trois autres destinations à la Pizza. Le vainqueur de Condorcet (celui qui gagne tous ses duels) existe-t-il ici ? La matrice le dit directement. C’est la leçon n° 1 du carnet sas : le scrutin majoritaire peut élire une option qu’une majorité de membres classe derrière chaque concurrente.

§3 — Le choix social formel : au-delà du vainqueur, le classement

Les scrutins donnent un gagnant. Le choix social formel (couche absente du projet étudiant — delta n° 4) donne un classement collectif ou une mesure de désaccord. Approval, STV, Copeland, Kemeny-Young, Schulze.

ballots = [p for _, p in PROFIL_PREFS]

w_app, counts_app = g.approval_voting(ballots, OPTIONS, approval_threshold=2)
print(f"Approval (top-2 approuves) : {w_app} — comptes {counts_app}")

winners_stv, rounds_stv = g.stv(ballots, OPTIONS, seats=1)
print(f"STV (1 siege, quota Droop) : {winners_stv} — {len(rounds_stv)} tour(s)")

w_cop, scores_cop = g.copeland(ballots, OPTIONS)
print(f"Copeland (duels +-)        : {w_cop} — scores {scores_cop}")

w_sch, paths_sch = g.schulze(ballots, OPTIONS)
print(f"Schulze (beatpath)         : {w_sch}")
Approval (top-2 approuves) : Burger — comptes {'Pizza': 3, 'Burger': 5, 'Sushi': 3, 'Raclette': 3}
STV (1 siege, quota Droop) : ['Burger'] — 3 tour(s)
Copeland (duels +-)        : Burger — scores {'Pizza': -3, 'Burger': 3, 'Sushi': 1, 'Raclette': -1}
Schulze (beatpath)         : Burger

Lecture : quatre méthodes formelles, et le consensus émerge

Sur ce profil, les méthodes de choix social convergent vers l’option de compromis — celle que la majorité simple avait éliminée. STV transfère les voix des éliminés ; Copeland compte les duels nets ; Schulze suit les plus forts chemins. Le vote quadratique et ces méthodes mesurent l’intensité ou la structure des préférences, pas seulement le premier choix.

# Kemeny-Young : le classement qui minimise le desaccord total (O(n!), <= 8 options).
ranking, score = g.kemeny_young(ballots, OPTIONS)
print(f"Classement Kemeny-Young optimal : {' > '.join(ranking)}")
print(f"Score (somme des preferences pairwise respectees) : {score}")

# Au-dela de 8 options : le wrapper safe rebascule sur Copeland (#971).
many = [f"opt{i}" for i in range(10)]
rank_safe, score_safe, approx = g.kemeny_young_safe(ballots, OPTIONS)
print(f"\nSur {len(OPTIONS)} options : approx = {approx} (exact ici, <= 8)")
try:
    g.kemeny_young(ballots, many)
except ValueError as e:
    print(f"Sur 10 options : ValueError levee -> {str(e)[:60]}...")
Classement Kemeny-Young optimal : Burger > Sushi > Raclette > Pizza
Score (somme des preferences pairwise respectees) : 25

Sur 4 options : approx = False (exact ici, <= 8)
Sur 10 options : ValueError levee -> Kemeny-Young impraticable pour 10 candidats (max 8) — utilis...

Lecture : le classement optimal a un coût combinatoire

Kemeny-Young donne le classement qui maximise le nombre de préférences pairwise respectées — mais en O(n!), impraticable au-delà de 8 options. Le wrapper safe le nomme honnêtement : au-delà, il rend une approximation Copeland et le dit (approx=True). C’est le fix d’honnêteté du cœur (#971) : une méthode qui ne peut pas calculer exact doit le dire, pas rendre un chiffre silencieux.

§4 — Quand les agents sont défaillants : les 2 protocoles

Les scrutins supposent des votes sincères. Les protocoles de tolérance aux pannes supposent des agents défaillants : une fraction vote au hasard (byzantin), ou un leader peut disparaître (Raft). Ce n’est pas comparable à Borda (#1981) — c’est une autre question.

import numpy as np

# Robustesse byzantine : le vainqueur survit-il a une fraction de votes aleatoires ?
print("Consensus byzantin selon la fraction de votes aleatoires (10 seeds chacune) :")
print(f"{'ratio':>6} {'vainqueurs observes':>30} {'majoritaire survit ?':>20}")
for ratio in (0.0, 0.15, 0.3, 0.45):
    gagnants = []
    for s in range(10):
        w = g.byzantine_consensus(build_agents(), OPTIONS,
                                   {"byzantine_ratio": ratio}, rng=random.Random(s))
        gagnants.append(w)
    from collections import Counter
    dist = dict(Counter(gagnants))
    survit = "oui" if dist.get("Pizza", 0) == 10 else f"{dist.get('Pizza', 0)}/10"
    print(f"{ratio:>6.2f} {str(dist):>30} {survit:>20}")
Consensus byzantin selon la fraction de votes aleatoires (10 seeds chacune) :
 ratio            vainqueurs observes majoritaire survit ?
  0.00                  {'Pizza': 10}                  oui
  0.15      {'Pizza': 6, 'Burger': 4}                 6/10
  0.30 {'Raclette': 1, 'Burger': 6, 'Pizza': 2, 'Sushi': 1}                 2/10
  0.45 {'Raclette': 1, 'Burger': 6, 'Pizza': 1, 'Sushi': 2}                 1/10

Lecture : le vainqueur majoritaire n’est pas le plus robuste

La Pizza gagne à la majorité sincère, mais elle est fragile au bruit byzantin : ses 3 partisans sont minoritaires face aux 4 autres membres, dont les votes dispersés + le bruit peuvent élire une autre destination dès que la fraction de défaillants monte. Un vainqueur de compromis (Borda/Condorcet) est plus robuste : il a des partisans « profonds ». La tolérance aux pannes et l’agrégation de préférences sont deux qualités distinctes — c’est pourquoi on ne les compare pas (#1981).

# Raft : election d'un leader, sa proposition doit etre acceptee par la majorite.
print("Raft (10 seeds) : leader elu -> proposition acceptee ou repli majoritaire")
gagnants_raft = [g.raft_consensus(build_agents(), OPTIONS, rng=random.Random(s)) for s in range(10)]
from collections import Counter
print(f"Vainqueurs Raft sur 10 seeds : {dict(Counter(gagnants_raft))}")
print("\n(Le repli majoritaire se declenche quand la proposition du leader n'a pas")
print(" la majorite des preferences top-2 des autres membres.)")
Raft (10 seeds) : leader elu -> proposition acceptee ou repli majoritaire
Vainqueurs Raft sur 10 seeds : {'Pizza': 8, 'Burger': 2}

(Le repli majoritaire se declenche quand la proposition du leader n'a pas
 la majorite des preferences top-2 des autres membres.)

Lecture : Raft dépend du leader tiré

Raft élit le vainqueur du leader si sa proposition est acceptée, sinon replie sur la majorité. Le résultat varie donc selon le leader tiré au sort : c’est un protocole de coordonnation, pas d’agrégation — il répond à « comment le groupe suit-il une décision cohérente malgré les pannes », pas à « quelle est la meilleure option ».

§5 — Mesurer une décision collective : justice et satisfaction

Dire « méthode plus juste » n’a de sens qu’avec un instrument. Le tronc porte les métriques (consensus_rate, fairness via Gini, satisfaction, stability) — avec le fix d’honnêteté #2576 : elles nomment ce qu’elles ne peuvent pas calculer au lieu d’un 0.0 silencieux.

def satisfaction_de(agent, vainqueur):
    # Satisfaction du port du tronc : rang relatif du vainqueur dans les preferences.
    if vainqueur not in agent.preferences:
        return 0.0
    return 1.0 - agent.preferences.index(vainqueur) / max(1, len(agent.preferences) - 1)

def gini(x):
    x = sorted(float(v) for v in x)
    n = len(x)
    if n == 0 or sum(x) == 0:
        return 0.0
    idx = range(1, n + 1)
    return sum((2 * i - n - 1) * v for i, v in zip(idx, x)) / (n * sum(x))

print(f"{'scrutin':<12} {'vainqueur':<10} {'satisfaction moy.':>18} {'Gini satisf.':>13}")
print("-" * 56)
for nom, fn in g.SCRUTINS.items():
    ag = build_agents()
    w = fn(ag, OPTIONS)
    sats = [satisfaction_de(a, w) for a in ag]
    print(f"{nom:<12} {w:<10} {np.mean(sats):>18.3f} {gini(sats):>13.3f}")
scrutin      vainqueur   satisfaction moy.  Gini satisf.
--------------------------------------------------------
majority     Pizza                   0.429         0.571
plurality    Pizza                   0.429         0.571
borda        Burger                  0.619         0.286
condorcet    Burger                  0.619         0.286
quadratic    Pizza                   0.429         0.571

Lecture : satisfaction et justice vont ensemble — ici

Sur ce profil, les méthodes qui choisissent l’option de compromis (Borda, Condorcet) obtiennent une satisfaction moyenne plus élevée et un Gini plus faible (moins d’inégalité de satisfaction entre membres). La Pizza, vainqueur majoritaire, laisse 4 membres sur 7 insatisfaits. Le scrutin qui « gagne » n’est pas celui qui rend le collectif le plus content — c’est le théorème de Gibbard-Satterthwaite en germe.

§6 — La manipulation : enterrer son adversaire (Gibbard-Satterthwaite)

Le théorème de Gibbard-Satterthwaite (1973) étend Arrow : tout scrutin non dictatorial sur ≥ 3 options est manipulable — un votant peut avoir intérêt à voter stratégiquement plutôt que sincèrement. Le carnet sas le démontre sur Borda : le bloc Pizza « enterre » Burger en le descendant en dernière place.

# Sincere : le bloc Pizza (Alice, Bruno, Chloe) vote ses vraies preferences.
ag_sincere = build_agents()
print("Vote sincere :")
print(f"  Borda    -> {g.borda_count(ag_sincere, OPTIONS)}")
print(f"  majorite -> {g.majority_voting(ag_sincere, OPTIONS)}")

# Manipulation : le bloc Pizza enterre Burger (le descend en dernier).
def build_manipulates():
    agents = []
    for i, (n, p) in enumerate(PROFIL_PREFS):
        if p[0] == "Pizza":
            # voter Pizza > Sushi > Raclette > Burger (Burger enterre)
            p = ["Pizza"] + [o for o in OPTIONS if o not in ("Pizza", "Burger")] + ["Burger"]
        agents.append(g.Agent(n, "stubborn", p, rng=random.Random(i)))
    return agents

ag_manip = build_manipulates()
print("\nVote strategique (le bloc Pizza enterre Burger) :")
print(f"  Borda    -> {g.borda_count(ag_manip, OPTIONS)}")
print(f"  majorite -> {g.majority_voting(ag_manip, OPTIONS)}")
Vote sincere :
  Borda    -> Burger
  majorite -> Pizza

Vote strategique (le bloc Pizza enterre Burger) :
  Borda    -> Sushi
  majorite -> Pizza

Lecture : la manipulation peut se retourner contre son auteur

En enterrant Burger, le bloc Pizza espérait consolider sa victoire à Borda. Mais enterrer un adversaire peut augmenter le score d’un autre : ici, la manipulation change le vainqueur Borda — pas forcément dans le sens espéré. C’est la leçon n° 3 du carnet sas : un scrutin manipulable est un jeu, et la stratégie a des effets de second ordre que le manipulateur ne contrôle pas.

§7 — Limites mesurées de la distillation

Une distillation n’est fidèle que si elle dit ce qu’elle a retenu, corrigé et laissé de côté.

Retenu du cœur : les 15 algorithmes (5 scrutins + 2 protocoles + 8 choix social), la classe Agent avec personnalités/confiance/Q-learning, les archétypes BDI/Reactive, la doctrine #1981.

Corrigé par le cœur (deltas mesurés, cf. docstring de l’organe) :

  1. la catégorie « 7 méthodes » → 15 algorithmes en 3 familles (#1981) ;
  2. consensus_rate traite les 3 formes de votes (#1273) ;
  3. les métriques nomment les non-calculables (#2576) — le prototype retournait 0.0/None silencieux ;
  4. Kemeny-Young > 8 options lève ValueError ou tombe sur Copeland en le disant (#971).

Laissé de côté : la boucle Simulation du prototype (son simulate_governance n’appelait jamais method_fn — code mort), le CLI, la visualisation matplotlib, les couches BDI/Reactive stubs de protocole vides.

Défaut conservé : quadratic_voting n’implémente pas le coût quadratique annoncé (aucune somme de carrés) — le tronc l’a conservé tel quel, et l’exercice 1 vous le fait corriger.

Exercices

Les trois exercices suivants vous font manipuler les concepts. Complétez les cellules : elles s’exécutent sans erreur même non complétées (résultat None à interpréter) — la solution est votre travail.

Exercice 1 — le VRAI vote quadratique

Le source (et le tronc qui l’a conservé) annonce un coût quadratique mais ne l’implémente pas : un agent flexible coupe juste son budget en deux. Le vrai vote quadratique : chaque agent a un budget, le coût d’allouer v voix à une option est v², et l’allocation optimale répartit les voix en racine carrée de l’intensité de préférence. Implémentez-le et mesurez s’il change le vainqueur sur le scénario du club.

def vrai_quadratique(agents, options, budget=9, intensite=None):
    # Etape 1 : pour chaque agent, calculer l'allocation optimale
    #           (voix proportionnelles a sqrt(intensite) sous contrainte somme v^2 <= budget).
    # Etape 2 : sommer les voix par option, retourner la gagnante.
    # Indice : sans intensite explicite, utiliser le rang dans les preferences
    #          comme proxy (premier choix = intensite maximale).
    # TODO etudiant
    return None  # TODO etudiant : nom de l'option gagnante
print("Exercice 1 a completer : vrai vote quadratique (cout = somme des carres)")
Exercice 1 a completer : vrai vote quadratique (cout = somme des carres)

Exercice 2 — construire la société où majorité et Borda se contredisent

Le scénario du club montre déjà une divergence majorité/Borda. Construisez un profil de préférences (votre propre « société ») où le vainqueur majoritaire est différent du vainqueur Borda, et vérifiez-le en exécutant les deux scrutins. Quelle structure de préférences produit cette contradiction ?

ma_societe = [
    # ("nom", [preferences ordonnees, 1er choix en tete]),
    # TODO etudiant : au moins 5 membres, 3 options
]
options_societe = []  # TODO etudiant : les options
# Indice : construire les agents avec g.Agent(n, "stubborn", p), puis comparer
# g.majority_voting(agents, options) et g.borda_count(agents, options).
resultat_majorite = None  # TODO etudiant
resultat_borda = None     # TODO etudiant
print("Exercice 2 a completer : societe ou majorite != Borda")
Exercice 2 a completer : societe ou majorite != Borda

Exercice 3 — STV contre le vote utile

Le vote unique transférable (STV) rend le « vote utile » moins nécessaire : si votre candidat favori est éliminé, votre voix se transfère à votre second choix. Sur le profil du club, simulez un électeur qui préfère Sushi mais vote « utile » pour Burger : son vote change-t-il le vainqueur STV ? Et à la majorité simple ?

# Indice : modifier UN bulletin de PROFIL_PREFS (un membre prefere Sushi mais vote Burger
# en premier), reconstruire les ballots, comparer g.stv(...) et g.majority_voting(...)
# avant/apres la manipulation.
ballots_avant = [p for _, p in PROFIL_PREFS]
ballots_apres = None  # TODO etudiant : copie de ballots_avant avec 1 bulletin manipule
stv_avant = None      # TODO etudiant : g.stv(ballots_avant, OPTIONS)
stv_apres = None      # TODO etudiant
maj_avant = None      # TODO etudiant : g.majority_voting(build_agents(), OPTIONS)
maj_apres = None      # TODO etudiant
print("Exercice 3 a completer : STV rend-il le vote utile inutile ?")
Exercice 3 a completer : STV rend-il le vote utile inutile ?

Conclusion

Ce notebook a mesuré, sur un même profil de préférences, ce que la théorie du choix social prédit : le scrutin choisit le vainqueur autant que les électeurs. La Pizza gagne la majorité et perd tous ses duels ; l’option de compromis gagne Borda, Condorcet, STV, Copeland, Schulze et la satisfaction moyenne ; la manipulation de Borda se retourne ; et les protocoles byzantins/Raft répondent à une autre question (tolérance aux pannes) que les scrutins ne posent pas.

La leçon d’ingénierie est celle du cœur EPITA (#1981) : ne jamais additionner dans un même compteur des algorithmes qui répondent à des questions différentes. 15 algorithmes, trois familles, une seule discipline — nommer ce qu’on mesure.

Distillation de la consolidation du cœur EPITA (tronc argumentation_analysis/agents/core/governance/ + sas docs/coursia_contrib/governance_voting_methods.ipynb), sous-grain 2 de l’EPIC #4960. Généalogie : 2.1.6_multiagent_governance_prototype (projet étudiant, juin 2025).

Retour au sommet