SocialChoice-06 : Mobius sur le treillis des coalitions - aggregation, pouvoir et manipulation

Navigation : << SC-05 | README | GameTheory

Jusqu’ici, la serie a agrege des classements (SC-03) et exhibe la manipulation d’un electeur individuel (SC-05, Gibbard-Satterthwaite). Ce notebook ouvre l’autre face de l’agregation d’un collectif : celle ou ce que l’on agrege n’est pas une preference mais une valeur de coalition - une fonction \(v : 2^N \to \mathbb{R}\) qui dit ce que vaut chaque sous-groupe \(S\) de joueurs \(N\).

La loi centrale - celle que ce notebook atteste - est l’inversion de Mobius sur le treillis des coalitions :

\[v(S) \;=\; \sum_{T \subseteq S} m(T), \qquad m(T) \;=\; \sum_{R \subseteq T} (-1)^{|T|-|R|}\, v(R)\]

Le coefficient \(m(T)\) est le dividende de Harsanyi : la valeur pure que la coalition \(T\) apporte au-dela de ce que ses sous-coalitions produisent deja seules. Toute agregation cooperative se decompose de maniere unique en cette somme de jeux d’unanimite - c’est le theoreme de reconstruction que le lac Lean du depot prouve formellement (Shapley.lean, sections Mobius.mobiusCoeff et Mobius.mobiusReconstruction).

Le temoin, lui, reste celui de Gibbard-Satterthwaite : une strategie de manipulation profitable. Nous le mesurerons ici sur un electorat pondere, ou chaque votant porte un poids - exactement le cadre ou poids de vote et pouvoir reel divergent.

1. Le modele : jeux de vote ponderes et dividende de Harsanyi

Un jeu de vote pondere \([q; w_1, \dots, w_n]\) definit \(v(S) = 1\) si \(\sum_{i \in S} w_i \geq q\) (la coalition gagne), \(v(S) = 0\) sinon. C’est le modele du conseil, de l’assemblee, du Conseil europeen - et le pont exact entre le vote ordinal de SC-03/SC-05 et la theorie cooperative.

Sur ce jeu simple (a valeurs dans \(\{0, 1\}\)), l’inversion de Mobius reste definie : \(m(T)\) mesure la synergie pure de \(T\). Une coalition gagnante dont tous les sous-ensembles propres perdent porte \(m(T) = 1\) ; les grandes coalitions peuvent porter des dividendes negatifs - elles ajoutent moins que la somme de leurs parties, la synergie pure etant deja consommee par leurs sous-coalitions gagnantes.

Nous travaillerons sur l’exemple canonique \([6; 4, 3, 2, 1]\) (4 joueurs, quota 6).

Implementation : inversion de Mobius et reconstruction

from itertools import combinations
from math import factorial

N_PLAYERS = 4
WEIGHTS = [4, 3, 2, 1]     # joueurs 1..4
QUOTA = 6

def all_coalitions(n):
    """Toutes les coalitions de {0..n-1}, par taille croissante."""
    players = range(n)
    for size in range(n + 1):
        yield from combinations(players, size)

def v(S):
    """Jeu de vote pondere [6; 4, 3, 2, 1] : 1 si la coalition atteint le quota."""
    return 1 if sum(WEIGHTS[i] for i in S) >= QUOTA else 0

def mobius_coeff(S):
    """Dividende de Harsanyi m(T) = somme_{R subset T} (-1)^(|T|-|R|) v(R).

    Miroir Python exact de Mobius.mobiusCoeff (Shapley.lean, CooperativeGames).
    """
    total = 0
    for size in range(len(S) + 1):
        for R in combinations(S, size):
            total += (-1) ** (len(S) - size) * v(R)
    return total

def mobius_reconstruct(S):
    """Reconstruction v(S) = somme_{T subseteq S} m(T).

    Miroir Python exact de Mobius.mobiusReconstruction (Shapley.lean).
    """
    total = 0
    for size in range(len(S) + 1):
        for T in combinations(S, size):
            total += mobius_coeff(T)
    return total

# --- Verification de la loi : reconstruction exacte sur TOUTES les coalitions ---
roundtrip_ok = all(mobius_reconstruct(S) == v(S) for S in all_coalitions(N_PLAYERS))
print("Loi de reconstruction (v = somme des dividendes) verifiee sur les 16 coalitions :",
      roundtrip_ok)

# --- Table des dividendes non nuls ---
print()
print("Dividendes de Harsanyi non nuls du jeu [6; 4, 3, 2, 1] :")
print(f"{'coalition':<12}{'poids':<7}{'v(S)':<5}{'m(T)':<5}")
for S in all_coalitions(N_PLAYERS):
    m = mobius_coeff(S)
    if m != 0:
        poids = sum(WEIGHTS[i] for i in S) if S else 0
        nom = "{" + ",".join(str(i + 1) for i in S) + "}"
        print(f"{nom:<12}{poids:<7}{v(S):<5}{m:<5}")
Loi de reconstruction (v = somme des dividendes) verifiee sur les 16 coalitions : True

Dividendes de Harsanyi non nuls du jeu [6; 4, 3, 2, 1] :
coalition   poids  v(S) m(T) 
{1,2}       7      1    1    
{1,3}       6      1    1    
{1,2,3}     9      1    -1   
{2,3,4}     6      1    1    
{1,2,3,4}   10     1    -1

Lecture du resultat

La reconstruction est exacte sur les 16 coalitions : la loi \(v = \sum m(T) \cdot u_T\) tient, meme sur un jeu a valeurs binaires. La table des dividendes dit quelque chose que la table des poids ne dit pas :

  • les trois coalitions minimalement gagnantes - {1,3} (poids 6), {1,2} (poids 7) et {2,3,4} (poids 6) - portent chacune un dividende de \(+1\) : c’est la que vit la synergie pure ;
  • la coalition {1,2,3} porte un dividende de \(-1\) : elle ajoute moins que la somme de ses parties, car ses sous-coalitions {1,2} et {1,3} gagnent deja ;
  • la grande coalition porte aussi \(-1\), pour la meme raison.

C’est la promesse de la loi de Mobius : elle rend la structure de pouvoir lisible coefficient par coefficient, la ou la fonction \(v\) brute ne montre qu’un mur de 0 et de 1.

2. Le pouvoir via les dividendes : valeur de Shapley et indice de Banzhaf

Le pont vers la theorie cooperative passe par une identite remarquable : la valeur de Shapley d’un joueur est la somme de ses dividendes de Harsanyi, partages a parts egales au sein de chaque coalition,

\[\phi_i(v) \;=\; \sum_{T \ni i} \frac{m(T)}{|T|},\]

C’est exactement la structure que le lac Lean du depot prouve formellement (Shapley.lean) : phi_weightedUnanimity etablit qu’un jeu d’unanimite pondere \(c \cdot u_T\) distribue \(c/|T|\) a chaque membre de \(T\) (efficience + symetrie), puis shapley_uniqueness distribue toute solution axiomatique sur la decomposition \(G = \sum_T m(T) \cdot u_T\) (game_eq_mobius_sum). Ce notebook en est le miroir Python execute.

L’indice de Banzhaf, lui, compte les balanciers (swings) : les coalitions \(S \ni i\) gagnantes devenues perdantes quand \(i\) les quitte. Nous calculons la valeur de Shapley deux fois, par des voies independantes - via les dividendes (la loi de ce notebook), puis par enumeration directe des \(n!\) ordres d’entree (la definition classique) - puis nous confrontons a l’indice de Banzhaf.

def shapley_via_dividends(i, n=N_PLAYERS):
    """Valeur de Shapley via les dividendes de Harsanyi, partages a parts egales.

    Miroir Python de la structure Lean (Shapley.lean) : phi_weightedUnanimity
    (jeu d'unanimite c.u_T -> c/|T| par membre) + distribution sur la
    decomposition de Mobius (game_eq_mobius_sum, shapley_uniqueness).
    """
    total = 0.0
    for size in range(1, n + 1):
        for T in combinations(range(n), size):
            if i in T:
                total += mobius_coeff(T) / size
    return total

def shapley_direct(i, n=N_PLAYERS):
    """Definition classique : contribution marginale moyenne sur les n! ordres d'entree."""
    from itertools import permutations
    total = 0
    for ordre in permutations(range(n)):
        k = ordre.index(i)
        avant = tuple(ordre[:k])
        total += v(avant + (i,)) - v(avant)
    return total / factorial(n)

def banzhaf_swings(i, n=N_PLAYERS):
    """Nombre de balanciers du joueur i : coalitions gagnantes S avec S prive de i perdante."""
    count = 0
    for size in range(1, n + 1):
        for S in combinations(range(n), size):
            if i in S:
                sans_i = tuple(p for p in S if p != i)
                if v(S) == 1 and v(sans_i) == 0:
                    count += 1
    return count

swings = [banzhaf_swings(i) for i in range(N_PLAYERS)]
total_swings = sum(swings)
print(f"{'joueur':<8}{'poids':<7}{'part poids':<12}{'Shapley (m(T))':<16}{'Shapley (ordres)':<18}{'Banzhaf norm.':<15}")
for i in range(N_PLAYERS):
    sh = shapley_via_dividends(i)
    sd = shapley_direct(i)
    bz = swings[i] / total_swings
    part = WEIGHTS[i] / sum(WEIGHTS)
    print(f"{i + 1:<8}{WEIGHTS[i]:<7}{part:<12.2%}{sh:<16.4f}{sd:<18.4f}{bz:<15.4f}")

# Double controle de coherence
phi_total = sum(shapley_via_dividends(i) for i in range(N_PLAYERS))
ecart_div_direct = max(abs(shapley_via_dividends(i) - shapley_direct(i)) for i in range(N_PLAYERS))
print()
print("Somme des valeurs de Shapley =", round(phi_total, 6), "| v(N) =", v(tuple(range(N_PLAYERS))))
print("Ecart max |Shapley via dividendes - Shapley par ordres| =", f"{ecart_div_direct:.2e}")
assert abs(phi_total - v(tuple(range(N_PLAYERS)))) < 1e-9, "Shapley doit etre efficiente"
assert ecart_div_direct < 1e-12, "les deux computations doivent coincider exactement"
print("Efficiency de Shapley et accord des deux voies : verifies.")
joueur  poids  part poids  Shapley (m(T))  Shapley (ordres)  Banzhaf norm.  
1       4      40.00%      0.4167          0.4167            0.4167         
2       3      30.00%      0.2500          0.2500            0.2500         
3       2      20.00%      0.2500          0.2500            0.2500         
4       1      10.00%      0.0833          0.0833            0.0833         

Somme des valeurs de Shapley = 1.0 | v(N) = 1
Ecart max |Shapley via dividendes - Shapley par ordres| = 5.55e-17
Efficiency de Shapley et accord des deux voies : verifies.

Lecture du resultat

Trois lectures, trois pieges evites par la mesure :

  • poids ne veut pas dire pouvoir, dans les deux sens : le joueur 2 (poids 3, 30 % du total) et le joueur 3 (poids 2, 20 %) ont exactement le meme pouvoir (0,25 chacun) car ils sont interchangeables dans la structure des coalitions gagnantes ; le joueur 4 (10 % du poids) n’a que 8,3 % du pouvoir, mais il n’est pas un dummy : il est balancier dans {2,3,4} (poids 6 avec lui, 5 sans lui). Un oeil sur la seule table des poids aurait declare les rapports 4:3:2:1 ; le pouvoir mesure est 5:3:3:1.
  • la loi de Mobius porte bien le calcul : la valeur calculee via les dividendes et celle calculee par enumeration des 24 ordres d’entree coïncident exactement - deux voies independantes, un seul nombre. C’est le contenu du pont Lean phi_weightedUnanimity + shapley_uniqueness (Shapley.lean), execute ici au lieu d’etre prouve.
  • une coïncidence remarquable, a ne pas generaliser : sur ce jeu precis, Shapley et Banzhaf (normalise) rendent la meme distribution (5/12, 1/4, 1/4, 1/12). Ce n’est pas une loi : Shapley pondere chaque balancier par le nombre d’ordres d’entree qui l’activent, Banzhaf les compte tous egaux - sur un autre jeu les deux divergent (l’exercice du Conseil 1958 plus bas en donnera l’occasion).

C’est exactement la structure que le lac Lean atteste formellement (Shapley.lean, sections ShapleyValue puis Mobius) : meme loi, substrat different - ici mesuree, la-bas prouvee.

3. Exercice 1 : la loi sur un second jeu

Verifier une loi sur un seul exemple ne prouve rien - l’exercice est de la re-tester sur le jeu pondere \([8; 5, 4, 3, 2, 1]\) (5 joueurs, quota 8) : reconstruction exacte sur les \(2^5 = 32\) coalitions, puis lecture de la table des dividendes.

Attendu : le round-trip tient sur les 32 coalitions ; les dividendes positifs majeurs vivent sur les coalitions minimalement gagnantes ({1,2}, {1,3}, {1,4,5}, {2,3,4}, {2,3,5}) ; et la grande coalition porte un dividende de \(+2\) - a confronter au \(-1\) du jeu a 4 joueurs.

# --- Exercice 1 : re-verifier la loi de reconstruction sur [8; 5, 4, 3, 2, 1] ---
# TODO etudiant :
#   1. redefinir WEIGHTS_EX = [5, 4, 3, 2, 1] et QUOTA_EX = 8
#   2. definir v_ex(S) sur ce jeu, puis reutiliser le schema de la section 1
#      (mobius_coeff / mobius_reconstruct adaptes a v_ex)
#   3. verifier le round-trip sur les 32 coalitions et lister les dividendes non nuls
# Indice : factoriser v_ex en parametre des fonctions evite de dupliquer le code.
# Attendu : roundtrip_ok_ex = True ; dividendes positifs sur les 5 minimalement gagnantes ;
# m(grande coalition) = +2.

print("Exercice 1 a completer : loi de Mobius sur [8; 5, 4, 3, 2, 1]")
result_ex1 = None  # TODO etudiant
Exercice 1 a completer : loi de Mobius sur [8; 5, 4, 3, 2, 1]

Question 1

Pourquoi la grande coalition porte-t-elle un dividende de \(+2\) sur \([8; 5, 4, 3, 2, 1]\) alors qu’elle portait \(-1\) sur \([6; 4, 3, 2, 1]\) ? (Compter, par taille, les coalitions gagnantes de chacun des deux jeux.) Que dit ce signe sur la synergie pure de la cooperation complete dans chaque cas ?

# --- Question 1 : decomposer m(N) par taille de coalition ---
# TODO etudiant : pour chaque jeu, compter les coalitions gagnantes par taille (2, 3, 4, 5)
# et verifier que m(N) = somme des (-1)^(n-|S|) * nb_gagnantes(|S|).
# Attendu : [6;4,3,2,1] -> 2 gagnantes de taille 2, 4 de taille 3, 1 de taille 4 : m(N) = -1 ;
# [8;5,4,3,2,1] -> 2 de taille 2, 8 de taille 3, 5 de taille 4, 1 de taille 5 : m(N) = +2.

print("Exercice (question 1) a completer : decomposer m(N) par taille")
result_q1 = None  # TODO etudiant
Exercice (question 1) a completer : decomposer m(N) par taille

4. Exercice 2 : chasser un dummy - le Luxembourg du Conseil de 1958

Un joueur est un dummy quand il n’est balancier dans aucune coalition (indice de Banzhaf nul). Le jeu de vote du Conseil europeen de la communaute economique europeenne, 1958 (traite de Rome) : France, Allemagne, Italie 4 voix chacune, Belgique et Pays-Bas 2, Luxembourg 1 - quota 12 : \([12; 4, 4, 4, 2, 2, 1]\).

Attendu : le Luxembourg (joueur 6) est un dummy - un poids de vote reel, un pouvoir de zero - tandis que la Belgique (joueur 4) ne l’est pas (balancier dans {F, D, B, N} : 12 avec elle, 10 sans elle). C’est l’exemple historique qui a fonde la lecture « poids ne veut pas dire pouvoir ».

# --- Exercice 2 : identifier le dummy du Conseil 1958 [12; 4, 4, 4, 2, 2, 1] ---
# TODO etudiant :
#   1. definir v_tq(S) pour ce jeu (poids [4, 4, 4, 2, 2, 1], quota 12)
#   2. adapter banzhaf_swings et lister les balanciers de chaque joueur
#   3. identifier le(s) joueur(s) a zero balancier
# Indice : un balancier pour le Luxembourg exige une coalition de poids exactement 12 le contenant,
# donc 11 pour les cinq autres - or {4, 4, 4, 2, 2} ne produit que des sommes paires.
# Attendu : Luxembourg = 0 balancier (dummy) ; Belgique >= 1 balancier.

print("Exercice 2 a completer : dummy du Conseil 1958")
result_ex2 = None  # TODO etudiant
Exercice 2 a completer : dummy du Conseil 1958

5. Exercice 3 : le temoin - manipulation d’un electorat pondere

Le temoin exige par la loi de ce notebook n’est pas une courbe : c’est une strategie de manipulation profitable (Gibbard-Satterthwaite). Cadre : les 4 joueurs du jeu \([6; 4, 3, 2, 1]\) votent sur 3 alternatives \(A, B, C\) au Borda pondere - chaque bulletin donne 2, 1, 0 points a ses alternatives rangees, multiplies par le poids du votant.

Profil sincere :

Votant Poids Classement sincere
V1 4 \(B > A > C\)
V2 3 \(A > C > B\)
V3 2 \(C > B > A\)
V4 1 \(C > A > B\)

La question : V3 (poids 2, sincere \(C > B > A\)) peut-il obtenir un resultat strictement meilleur en votant autrement ? Enumerer ses \(3! = 6\) bulletins possibles, calculer le gagnant Borda pondere pour chacun, et ne garder que les bulletins insinceres strictement profitables au sens du classement sincere de V3 - c’est-a-dire faisant elire une alternative qu’il prefere au gagnant sincere.

Attendu : au moins un bulletin insincere strictement profitable - le temoin constructif de Gibbard-Satterthwaite, cette fois sur substrat pondere : manipuler, c’est deplacer son poids a travers les coalitions que la decomposition de Mobius rend visibles.

ALTS = ["A", "B", "C"]
PROFILS_SINCERES = {
    "V1": (4, ["B", "A", "C"]),
    "V2": (3, ["A", "C", "B"]),
    "V3": (2, ["C", "B", "A"]),
    "V4": (1, ["C", "A", "B"]),
}

def borda_pondere_gagnant(bulletins):
    """Gagnant au Borda pondere ; bulletins = dict votant -> (poids, classement)."""
    scores = {a: 0 for a in ALTS}
    for poids, classement in bulletins.values():
        for position, alt in enumerate(classement):
            scores[alt] += poids * (len(ALTS) - 1 - position)
    gagnant = max(scores, key=lambda a: (scores[a], -ord(a)))
    return gagnant, scores

gagnant_sincere, scores_sinceres = borda_pondere_gagnant(PROFILS_SINCERES)
print("Scores Borda ponderes sous vote sincere :", scores_sinceres)
print("Gagnant sincere :", gagnant_sincere)

# --- Exercice 3 : enumerer les 6 bulletins de V3 et trouver une manipulation profitable ---
# TODO etudiant :
#   1. pour chaque classement possible de V3 (6 permutations de A, B, C),
#      construire le profil modifie et calculer le gagnant Borda pondere
#   2. ne garder que les bulletins ININCERES strictement profitables au sens du
#      classement sincere de V3 (C > B > A) : le gagnant manipule doit etre mieux
#      classe que le gagnant sincere dans ["C", "B", "A"]
#   3. exhiber le bulletin manipulateur et le couple (gagnant sincere, gagnant manipule)
# Indice : comparer les positions des deux gagnants dans ["C", "B", "A"] - l'indice
# le plus petit gagne au sens de V3.
# Attendu : au moins une manipulation profitable ; l'annoter explicitement.

print("Exercice 3 a completer : temoin de manipulation de V3 sous Borda pondere")
result_ex3 = None  # TODO etudiant
Scores Borda ponderes sous vote sincere : {'A': 11, 'B': 10, 'C': 9}
Gagnant sincere : A
Exercice 3 a completer : temoin de manipulation de V3 sous Borda pondere

Lecture attendue du temoin

Ce que le temoin doit montrer une fois complete :

  1. le vote sincere produit un gagnant mesure (scores calcules, pas intuition) ;
  2. il existe un bulletin insincere de V3 qui fait elire une alternative que V3 prefere au sens de son classement sincere - la definition exacte de la manipulabilite ;
  3. le mecanisme du gain se lit dans la structure ponderee : le poids 2 de V3 bascule les coalitions gagnantes d’une alternative vers une autre. La decomposition de Mobius de la section 1 etait la carte ; la manipulation est le deplacement du poids sur cette carte.

Noter l’asymetrie que le cadre pondere ajoute a SC-05 : V1 (poids 4) et V2 (poids 3) n’ont pas les memes capacites de manipulation que V3 (poids 2) - la strategie profitable n’est pas distribuee uniformement, elle epouse la geometrie du pouvoir. Gibbard-Satterthwaite garantit qu’aucune regle raisonnable n’echappe au temoin ; il ne dit pas que tous les votants y ont le meme acces.

6. Conclusion : ce que la loi et le temoin attestent

Trois resultats a retenir :

  1. La loi tient, mesuree : la reconstruction \(v = \sum_T m(T) \cdot u_T\) est exacte sur chaque coalition testee - l’agregation d’un collectif cooperatif se decompose de facon unique en dividendes de Harsanyi. Le lac Lean du depot (Shapley.lean) prouve cette meme loi formellement (Mobius.mobiusCoeff, Mobius.mobiusReconstruction, sorry-free) ; ce notebook en est le temoin Python execute - meme loi, deux substrats independants (EPIC #12204, operation 14 « Agreger un collectif »).

  2. Le pouvoir ne se lit pas dans les poids : sur \([6; 4, 3, 2, 1]\), joueurs 2 et 3 ont le meme pouvoir malgre des poids de 3 et 2 ; sur le Conseil de 1958, le Luxembourg pesait 1 voix pour un pouvoir nul - un dummy a poids non nul, l’illustration historique de l’ecart poids/pouvoir.

  3. Le temoin est constructif, y compris sous pondération : une strategie de vote insincere strictement profitable existe et s’exhibe par enumeration - Gibbard-Satterthwaite instancie sur un electorat pondere, ou manipuler revient a deplacer son poids a travers le treillis des coalitions.

Prolongements : l’indice de pouvoir des membres du Conseil europeen actuel (a double majorite), les jeux composes ou des dummies redeviennent actifs, et la formalisation Lean complete dans le notebook SC-02.

Retour au sommet