Navigation : << 15-CooperativeGames (track principal)) | Index
Autres side tracks : 15b-Lean-CooperativeGames
Kernel : Python 3
Ce notebook compagnon du notebook 15b (Lean) fournit les illustrations Python des concepts formalises :
Pour les implementations completes de Shapley et Core, voir le notebook 14.
A l’issue de ce notebook, vous saurez :
# Configuration
import numpy as np
import matplotlib.pyplot as plt
from itertools import permutations, combinations
from math import factorial
from collections import defaultdict
print("Notebook Python compagnon pour les jeux cooperatifs (Lean)")Notebook Python compagnon pour les jeux cooperatifs (Lean)La valeur de Shapley est la contribution marginale moyenne d’un joueur sur toutes les permutations :
\[\phi_i(v) = \sum_{S \subseteq N \setminus \{i\}} \frac{|S|!(n-|S|-1)!}{n!} [v(S \cup \{i\}) - v(S)]\]
def shapley_value_exact(v, n):
"""Calcul exact de la valeur de Shapley.
Args:
v: Fonction caracteristique v(S) ou S est un frozenset
n: Nombre de joueurs
Returns:
Liste des valeurs de Shapley pour chaque joueur
"""
shapley = [0.0] * n
for perm in permutations(range(n)):
coalition = set()
for i in perm:
marginal = v(frozenset(coalition | {i})) - v(frozenset(coalition))
shapley[i] += marginal
coalition.add(i)
return [s / factorial(n) for s in shapley]
print("Fonction shapley_value_exact definie.")Fonction shapley_value_exact definie.Lecture de la sortie — l’instrument s’installe avant de jouer. La ligne « Fonction shapley_value_exact definie. » n’affiche aucun resultat : la cellule pose l’outil, pas encore son usage. Ce que le contrat installe : le calcul exact par enumeration des n! permutations (chaque ordre d’arrivee des joueurs, contribution marginale moyenne), exact au sens ou aucune variance de sondage ne s’y glisse — a la difference des estimations Monte Carlo qu’on rencontre dans d’autres series du depot. La section suivante l’appliquera aussitot au jeu de gants : la premiere valeur chiffree viendra de la, pas d’ici.
Exercice 1 du notebook 15b Lean : Trois joueurs L1, L2 ont chacun un gant gauche, R1 a un gant droit. Une paire de gants vaut 1.
# Jeu de gants : L1=0, L2=1, R1=2
def glove_game(coalition):
"""Fonction caracteristique du jeu de gants.
Joueurs 0,1 ont des gants gauches, joueur 2 a un gant droit.
Valeur = nombre de paires completes.
"""
left_gloves = sum(1 for i in coalition if i in {0, 1})
right_gloves = sum(1 for i in coalition if i == 2)
return min(left_gloves, right_gloves)
# Verification de la fonction caracteristique
print("JEU DE GANTS")
print("=" * 40)
print("Joueurs : L1=0, L2=1 (gants gauches), R1=2 (gant droit)")
print("\nFonction caracteristique :")
all_coalitions = [frozenset(c) for r in range(4) for c in combinations(range(3), r)]
for S in sorted(all_coalitions, key=lambda x: (len(x), tuple(sorted(x)))):
labels = {0: 'L1', 1: 'L2', 2: 'R1'}
coalition_str = '{' + ', '.join(labels[i] for i in sorted(S)) + '}' if S else '{}'
print(f" v({coalition_str}) = {glove_game(S)}")JEU DE GANTS
========================================
Joueurs : L1=0, L2=1 (gants gauches), R1=2 (gant droit)
Fonction caracteristique :
v({}) = 0
v({L1}) = 0
v({L2}) = 0
v({R1}) = 0
v({L1, L2}) = 0
v({L1, R1}) = 1
v({L2, R1}) = 1
v({L1, L2, R1}) = 1La fonction caractéristique encode la structure de complementarite du jeu :
| Type de coalition | Valeur | Raison |
|---|---|---|
| Vide ou singletons | 0 | Aucune paire possible |
| {L1, L2} (deux gauches) | 0 | Pas de gant droit pour completer |
| {L1, R1} ou {L2, R1} | 1 | Une paire complete |
| {L1, L2, R1} | 1 | Une seule paire possible (1 gant droit) |
Point cle : Le gant droit est la ressource limitante. Même avec deux gants gauches, on ne peut former qu’une seule paire. Cette asymetrie aura un impact majeur sur les valeurs de Shapley.
# Calcul de Shapley pour le jeu de gants
shapley_glove = shapley_value_exact(glove_game, 3)
print("\nVALEURS DE SHAPLEY :")
labels = ['L1 (gant gauche)', 'L2 (gant gauche)', 'R1 (gant droit)']
for i, (label, val) in enumerate(zip(labels, shapley_glove)):
print(f" {label}: {val:.4f} = {int(val*6)}/6")
print(f"\nTotal : {sum(shapley_glove):.4f} (= v(N) = 1)")
VALEURS DE SHAPLEY :
L1 (gant gauche): 0.1667 = 1/6
L2 (gant gauche): 0.1667 = 1/6
R1 (gant droit): 0.6667 = 4/6
Total : 1.0000 (= v(N) = 1)Les valeurs de Shapley revelent un principe economique fondamental :
| Joueur | Ressource | Shapley | Explication |
|---|---|---|---|
| L1, L2 | Gant gauche (abondant) | 1/6 chacun | Competition entre detenteurs de la même ressource |
| R1 | Gant droit (rare) | 4/6 | Monopole sur la ressource complementaire |
Analyse des contributions marginales : - Quand R1 rejoint {L1} ou {L2}, il apporte 1 (creation d’une paire) - Quand L1 rejoint {R1}, il apporte 1 (creation d’une paire) - Quand L1 rejoint {L2, R1}, il apporte 0 (une paire existe déjà)
Lecon economique : La valeur d’une ressource ne depend pas seulement de son utilite intrinseque, mais de sa rarete relative par rapport aux ressources complementaires.
Objectif : Etendre le jeu de gants a 4 joueurs : L1, L2 (gants gauches) et R1, R2 (gants droits). Définir la fonction caractéristique, calculer les valeurs de Shapley, et interpreter comment le marche 2-vs-2 repartit la valeur.
Contexte : Le jeu a 3 joueurs montre que le detenteur de la ressource rare obtient 4/6. Avec 2 gants de chaque cote, le marche est equilibre.
def exercice_shapley_glove_etendu() -> dict:
"""
Jeu de gants etendu a 4 joueurs (2 gauches, 2 droites).
Returns:
dict avec :
'shapley_values': liste des 4 valeurs de Shapley
'total': somme des valeurs (= v(N))
'interpretation': texte d'interpretation
"""
return {"shapley_values": [], "total": 0.0, "interpretation": ""} # TODO etudiant
result_glove4 = exercice_shapley_glove_etendu()
labels_4 = ['L1', 'L2', 'R1', 'R2']
for label, val in zip(labels_4, result_glove4['shapley_values']):
print(f" {label}: {val:.4f}")
print(f"\nTotal: {result_glove4['total']:.4f}")
print(f"Interpretation: {result_glove4['interpretation']}")
print("Exercice a completer")
Total: 0.0000
Interpretation:
Exercice a completerLire la sortie d’un exercice non rempli. « Exercice a completer » avec Total: 0.0000 : le squelette exercice_shapley_glove_etendu rend l’etat vide, la ligne Total etant le format d’affichage attendu, pas un resultat. Le contrat, pose par l’enonce ci-dessus : etendre le jeu de gants de 3 a 4 joueurs (deux gants gauches L1, L2, deux droits R1, R2 selon le meme schema de gains) et recalculer les valeurs de Shapley exactes. La sortie remplie affichera quatre allocations sommant a v(N), et la question interessante de lecture : la rarete change-t-elle de camp quand les deux cotes passent a deux detenteurs ? L’indice de l’enonce oriente sans reveler.
# Visualisation
fig, ax = plt.subplots(figsize=(8, 5))
players = ['L1\n(gauche)', 'L2\n(gauche)', 'R1\n(droit)']
colors = ['steelblue', 'steelblue', 'coral']
bars = ax.bar(players, shapley_glove, color=colors, edgecolor='black')
# Ajouter les valeurs sur les barres
for bar, val in zip(bars, shapley_glove):
ax.text(bar.get_x() + bar.get_width()/2, bar.get_height() + 0.02,
f'{val:.3f}', ha='center', va='bottom', fontsize=11)
ax.set_ylabel('Valeur de Shapley')
ax.set_title('Jeu de Gants : La ressource rare a plus de valeur')
ax.set_ylim(0, 0.8)
ax.axhline(y=1/3, color='gray', linestyle='--', alpha=0.5, label='Partage egal (1/3)')
ax.legend()
plt.tight_layout()
plt.show()
Exemple guide 3 du notebook 15b Lean : Montrer que le jeu de majorite simple a 3 joueurs a un Core vide.
def majority_game_3(coalition):
"""Jeu de majorite simple a 3 joueurs.
v(S) = 1 si |S| >= 2, 0 sinon.
"""
return 1 if len(coalition) >= 2 else 0
print("JEU DE MAJORITE SIMPLE A 3 JOUEURS")
print("=" * 50)
print("\nFonction caracteristique :")
for S in sorted(all_coalitions, key=lambda x: (len(x), tuple(sorted(x)))):
coalition_str = '{' + ', '.join(str(i+1) for i in sorted(S)) + '}' if S else '{}'
print(f" v({coalition_str}) = {majority_game_3(S)}")JEU DE MAJORITE SIMPLE A 3 JOUEURS
==================================================
Fonction caracteristique :
v({}) = 0
v({1}) = 0
v({2}) = 0
v({3}) = 0
v({1, 2}) = 1
v({1, 3}) = 1
v({2, 3}) = 1
v({1, 2, 3}) = 1La fonction caractéristique revele une symetrie parfaite entre les joueurs :
Cette structure est celle d’un jeu simple symetrique : tous les joueurs sont interchangeables, et le résultat ne depend que de la taille de la coalition.
Propriete importante : Dans ce jeu, chaque joueur est critique (pivotal) dans exactement 2 coalitions gagnantes minimales. Par exemple, le joueur 1 est critique dans {1,2} et {1,3}.
# Preuve du Core vide, verifiee sur la fonction caracteristique calculee ci-dessus
v_N = majority_game_3({1, 2, 3})
paires = [c for c in all_coalitions if len(c) == 2]
somme_paires = sum(majority_game_3(c) for c in paires)
print("Sommation des contraintes de paire :")
print(f" v(N) = {v_N}, somme des v(S) sur les {len(paires)} paires = {somme_paires}")
print(f" Chaque joueur apparait dans 2 paires, donc 2 * v(N) = {2 * v_N} devrait couvrir cette somme")
print(f" Or {2 * v_N} < {somme_paires} -> CONTRADICTION : le Core est vide")Sommation des contraintes de paire :
v(N) = 1, somme des v(S) sur les 3 paires = 3
Chaque joueur apparait dans 2 paires, donc 2 * v(N) = 2 devrait couvrir cette somme
Or 2 < 3 -> CONTRADICTION : le Core est videLa preuve utilise une technique classique de sommation des contraintes :
Consequence pratique : Dans un jeu de majorite simple, aucun partage ne peut satisfaire toutes les coalitions. Toute proposition sera bloquee par une coalition de 2 joueurs qui peut obtenir plus en faisant secession.
Cette situation illustre le concept d’instabilite coalitionnelle : même si la grande coalition est efficace, elle ne peut pas se former de maniere stable.
# Shapley du jeu de majorite (tous egaux)
shapley_majority = shapley_value_exact(majority_game_3, 3)
print("\nVALEURS DE SHAPLEY :")
for i, val in enumerate(shapley_majority):
print(f" Joueur {i+1}: {val:.4f} = 1/3")
# Verification chiffree du blocage : l'allocation de Shapley n'est pas dans le Core
print(f" x1 + x2 = {shapley_majority[0] + shapley_majority[1]:.4f} < 1 = v({{1,2}})")
VALEURS DE SHAPLEY :
Joueur 1: 0.3333 = 1/3
Joueur 2: 0.3333 = 1/3
Joueur 3: 0.3333 = 1/3
x1 + x2 = 0.6667 < 1 = v({1,2})Lecture chiffree — equitable et instable : les deux diagnostics tiennent ensemble. La sortie affiche Joueur 1: 0.3333 = 1/3 (et pareil pour les deux autres), puis la verification chiffree du blocage, x1 + x2 = 0.6667 < 1 = v({1,2}) : l’allocation de Shapley est juste mais n’est pas dans le Core. Les deux nombres se lisent ensemble : 1/3 chacun est l’equite au sens des contributions marginales moyennes (symetrie parfaite des roles), et 2/3 < 1 est le blocage au sens du Core (n’importe quelle paire peut quitter la table avec 1). Ni l’un ni l’autre ne degonfle l’autre : c’est la coexistence des deux criteres, l’un distributif, l’autre strategique, qui fait tout l’interet du jeu de majorite — la preuve de vacuite de la section precedente dit qu’aucun partage ne peut gagner les DEUX.
Un jeu de vote pondere \([q; w_1, w_2, ..., w_n]\) ou une coalition gagne si \(\sum_{i \in S} w_i \geq q\).
def weighted_voting_game(weights, quota):
"""Cree une fonction caracteristique pour un jeu de vote pondere."""
def v(coalition):
return 1 if sum(weights[i] for i in coalition) >= quota else 0
return v
def banzhaf_index(v, n):
"""Calcule l'indice de Banzhaf (normalise).
Compte le nombre de coalitions ou chaque joueur est critique.
"""
critical_counts = [0] * n
# Pour chaque coalition
for r in range(1, n + 1):
for S in combinations(range(n), r):
S_set = frozenset(S)
if v(S_set) == 1: # Coalition gagnante
for i in S:
# i est critique si S\{i} perd
S_minus_i = frozenset(j for j in S if j != i)
if v(S_minus_i) == 0:
critical_counts[i] += 1
# Normaliser
total = sum(critical_counts)
if total == 0:
return [0.0] * n
return [c / total for c in critical_counts]
# Exemple : Conseil de securite de l'ONU simplifie [39; 7,7,7,7,7, 1,1,1,1,1]
# 5 membres permanents (poids 7), 10 non-permanents (poids 1)
# Simplification : [9; 7,7,1,1,1] (2 permanents, 3 non-permanents)
weights_un = [7, 7, 1, 1, 1]
quota_un = 9
v_un = weighted_voting_game(weights_un, quota_un)
print("JEU DE VOTE PONDERE : Mini-ONU")
print("=" * 50)
print(f"[{quota_un}; {', '.join(map(str, weights_un))}]")
print("P1, P2 = permanents (poids 7), N1, N2, N3 = non-permanents (poids 1)")
shapley_un = shapley_value_exact(v_un, 5)
banzhaf_un = banzhaf_index(v_un, 5)
print("\nComparaison Shapley vs Banzhaf :")
labels = ['P1', 'P2', 'N1', 'N2', 'N3']
print(f"{'Joueur':<10} {'Poids':<10} {'Shapley':<10} {'Banzhaf':<10}")
print("-" * 40)
for label, w, s, b in zip(labels, weights_un, shapley_un, banzhaf_un):
print(f"{label:<10} {w:<10} {s:<10.4f} {b:<10.4f}")JEU DE VOTE PONDERE : Mini-ONU
==================================================
[9; 7, 7, 1, 1, 1]
P1, P2 = permanents (poids 7), N1, N2, N3 = non-permanents (poids 1)
Comparaison Shapley vs Banzhaf :
Joueur Poids Shapley Banzhaf
----------------------------------------
P1 7 0.3000 0.2857
P2 7 0.3000 0.2857
N1 1 0.1333 0.1429
N2 1 0.1333 0.1429
N3 1 0.1333 0.1429 Les résultats revelent un paradoxe classique de la théorie du vote :
| Joueur | Poids nominal | Pouvoir reel (Shapley) | Ratio pouvoir/poids |
|---|---|---|---|
| P1, P2 | 7 (41%) | 0.30 (30%) | 0.73 |
| N1-N3 | 1 (6%) | 0.13 (13%) | 2.17 |
Observations cles :
Application pratique : Dans le vrai Conseil de Securite de l’ONU, le droit de veto des permanents leur confere un pouvoir absolu (indice = 1 si veto, 0 sinon pour certaines decisions).
# Visualisation comparative
fig, ax = plt.subplots(figsize=(10, 5))
x = np.arange(len(labels))
width = 0.35
bars1 = ax.bar(x - width/2, shapley_un, width, label='Shapley', color='steelblue')
bars2 = ax.bar(x + width/2, banzhaf_un, width, label='Banzhaf', color='coral')
ax.set_ylabel('Indice de pouvoir')
ax.set_title('Comparaison Shapley vs Banzhaf (jeu de vote pondere)')
ax.set_xticks(x)
ax.set_xticklabels(labels)
ax.legend()
# Ajouter les poids en annotation
for i, w in enumerate(weights_un):
ax.annotate(f'poids={w}', xy=(i, 0), xytext=(i, -0.05),
ha='center', fontsize=9, color='gray')
plt.tight_layout()
plt.show()
print("Note : Le pouvoir reel (Shapley/Banzhaf) peut differer du poids nominal!")
Note : Le pouvoir reel (Shapley/Banzhaf) peut differer du poids nominal!Lecture de la figure — le renversement se voit avant de se calculer. Les barres cote a cote tracent, pour chaque joueur, le poids nominal contre les indices de pouvoir reel (Shapley et Banzhaf) : la note de la sortie resume ce que l’oeil capte — « Le pouvoir reel (Shapley/Banzhaf) peut differer du poids nominal! ». Le tableau chiffre de l’interpretation precedente donne les valeurs exactes ; la figure ajoute le diagnostic visuel : les barres poids et pouvoir ne sont PAS alignees, le desequilibre change de sens selon les joueurs (le grand poids est surcote en apparence, les petits poids surindexes en pouvoir). C’est la lecture a retenir d’un coup d’oeil avant toute negotiation de quota : on negocie des poids, on exerce du pouvoir.
Un jeu est convexe (supermodulaire) si les contributions marginales sont croissantes. Pour les jeux convexes, la valeur de Shapley est dans le Core.
def is_convex(v, n):
"""Verifie si un jeu est convexe.
Un jeu est convexe si pour tout S, T : v(S) + v(T) <= v(S u T) + v(S n T)
"""
for r1 in range(n + 1):
for S in combinations(range(n), r1):
S = frozenset(S)
for r2 in range(n + 1):
for T in combinations(range(n), r2):
T = frozenset(T)
lhs = v(S) + v(T)
rhs = v(S | T) + v(S & T)
if lhs > rhs + 1e-10: # Tolerance numerique
return False
return True
# Test sur le jeu de gants
print("TEST DE CONVEXITE")
print("=" * 40)
print(f"Jeu de gants convexe ? {is_convex(glove_game, 3)}")
print(f"Jeu de majorite convexe ? {is_convex(majority_game_3, 3)}")
# Jeu d'unanimite (toujours convexe)
def unanimity_game(T):
"""Jeu d'unanimite : v(S) = 1 si T inclus dans S, 0 sinon."""
def v(coalition):
return 1 if T <= coalition else 0
return v
v_unan = unanimity_game(frozenset({0, 1}))
print(f"Jeu d'unanimite u_{{1,2}} convexe ? {is_convex(v_unan, 3)}")TEST DE CONVEXITE
========================================
Jeu de gants convexe ? False
Jeu de majorite convexe ? False
Jeu d'unanimite u_{1,2} convexe ? TrueLes résultats revelent une propriete fondamentale des jeux cooperatifs :
| Jeu | Convexe ? | Explication |
|---|---|---|
| Gants | Non | Le joueur R1 (ressource rare) a des rendements decroissants quand il rejoint de grandes coalitions |
| Majorite | Non | Deux joueurs quelconques suffisent pour gagner - pas de synergie supplementaire |
| Unanimite | Oui | Les contributions marginales sont nulles sauf pour les coalitions contenant T |
Intuition economique : Un jeu est convexe lorsque “plus on est nombreux, plus chaque nouvel arrivant apporte de valeur”. C’est le cas des jeux avec fortes complementarites entre joueurs.
# Verification que Shapley est dans le Core pour un jeu convexe
def is_in_core(allocation, v, n):
"""Verifie si une allocation est dans le Core."""
# Efficacite
if abs(sum(allocation) - v(frozenset(range(n)))) > 1e-10:
return False, "Pas efficace"
# Stabilite
for r in range(1, n):
for S in combinations(range(n), r):
S_set = frozenset(S)
coalition_value = sum(allocation[i] for i in S)
if coalition_value < v(S_set) - 1e-10:
return False, f"Coalition {S} peut bloquer"
return True, "Dans le Core"
# Jeu convexe simple
def convex_game(coalition):
"""Un jeu convexe : v(S) = |S|^2 / 9."""
return len(coalition) ** 2 / 9
print("\nJEU CONVEXE : v(S) = |S|^2 / 9")
print("=" * 40)
print(f"Convexe ? {is_convex(convex_game, 3)}")
shapley_convex = shapley_value_exact(convex_game, 3)
print(f"\nShapley : {shapley_convex}")
in_core, msg = is_in_core(shapley_convex, convex_game, 3)
print(f"Shapley dans le Core ? {in_core} - {msg}")
# Verification du jeu de majorite (non convexe, Shapley hors Core)
print(f"\nJeu de majorite :")
in_core_maj, msg_maj = is_in_core(shapley_majority, majority_game_3, 3)
print(f"Shapley dans le Core ? {in_core_maj} - {msg_maj}")
JEU CONVEXE : v(S) = |S|^2 / 9
========================================
Convexe ? True
Shapley : [0.3333333333333333, 0.3333333333333333, 0.3333333333333333]
Shapley dans le Core ? True - Dans le Core
Jeu de majorite :
Shapley dans le Core ? False - Coalition (0, 1) peut bloquerLecture chiffree — le theoreme verifies sur ses deux cotes. La sortie aligne le jeu convexe v(S) = |S|^2 / 9 puis son contre-exemple. Cote theoreme : Convexe ? True et Shapley : [0.3333, 0.3333, 0.3333] avec Dans le Core ? True — sur un jeu convexe, la valeur de Shapley APPARTIENT au Core, l’allocation equitable est ici aussi stable. Cote contre-exemple : le jeu de majorite repond False avec la cause nominmee — Coalition (0, 1) peut bloquer. La paire de verdicts fait le travail pedagogique : la convexite est precisement l’hypothese qui soude equite et stabilite, et le jeu de majorite (non convexe) montre les deux critieres se separer a nouveau, comme en section 3.
Objectif : Définir un jeu cooperatif a 3 joueurs avec une fonction caractéristique de votre choix. Tester la convexite avec is_convex, calculer la valeur de Shapley avec shapley_value_exact, puis verifier si Shapley appartient au Core avec is_in_core.
Contexte : Pour les jeux convexes, Shapley est garanti dans le Core. Pour les jeux non convexes, ce n’est pas certain.
def exercice_convexite_et_core() -> dict:
"""
Analyse convexite et Core pour deux jeux cooperatifs.
Returns:
dict avec :
'game1': {'convex': bool, 'shapley': list, 'in_core': bool}
'game2': {'convex': bool, 'shapley': list, 'in_core': bool}
"""
return {
"game1": {"convex": False, "shapley": [], "in_core": False},
"game2": {"convex": False, "shapley": [], "in_core": False}
} # TODO etudiant
result_cc = exercice_convexite_et_core()
print("Jeu 1 (convexe attendu):")
print(f" Convexe: {result_cc['game1']['convex']}")
print(f" Shapley: {result_cc['game1']['shapley']}")
print(f" Dans Core: {result_cc['game1']['in_core']}")
print("\nJeu 2 (non convexe attendu):")
print(f" Convexe: {result_cc['game2']['convex']}")
print(f" Shapley: {result_cc['game2']['shapley']}")
print(f" Dans Core: {result_cc['game2']['in_core']}")
print("Exercice a completer")Jeu 1 (convexe attendu):
Convexe: False
Shapley: []
Dans Core: False
Jeu 2 (non convexe attendu):
Convexe: False
Shapley: []
Dans Core: False
Exercice a completerLire la sortie d’un exercice non rempli — et reconnaitre un artefact. Les lignes Convexe: False sur le Jeu 1 (convexe attendu) ne sont pas un verdict mathematique : Shapley: [] le revele, le squelette ne calcule rien, et le False par defaut s’affiche pour les deux jeux a l’identique. L’etat reel est « Exercice a completer ». Le contrat : construire deux jeux de 3 joueurs (un convexe, un non convexe), appliquer is_convex puis le test d’appartenance au Core, et lire la PAIRE de verdicts — convexe attendu True/True a la maniere de la cellule precedente, non convexe attendu False/False. La sortie remplie devra rompre la symetrie artefactuelle des deux False actuels : c’est justement le signe que la solution vit.
Les sections précédentes ont raisonne sur le Core au cas par cas : la section 3 a prouve a la main que le Core du jeu de majorite est vide, et la section 5 a verifie l’appartenance de la valeur de Shapley au Core en enumerant les coalitions. Deux questions générales restent ouvertes pour un jeu quelconque :
Les deux questions se ramenent a des programmes lineaires (LP) que l’on resout avec un vrai solveur SOTA, scipy.optimize.linprog (backend HiGHS).
On relache les contraintes de stabilite du Core par une marge epsilon et on maximise cette marge :
\[\max_{x,\,\epsilon}\ \epsilon \quad \text{s.c.} \quad \sum_{i\in S} x_i \ge v(S) + \epsilon \ \ \forall S \subsetneq N,\ S\neq\varnothing,\qquad \sum_{i\in N} x_i = v(N).\]
Le signe de la marge optimale epsilon* decide la vacuite du Core :
epsilon* > 0 : le Core a un interieur (toutes les coalitions sont satisfaites avec du jeu) ;epsilon* = 0 : le Core est non vide mais reduit a sa frontiere ;epsilon* < 0 : le Core est vide ; l’ensemble des solutions optimales est le least-core, la meilleure approximation stable.from scipy.optimize import linprog
def proper_coalitions(n):
# Toutes les coalitions S non vides et strictement incluses dans N.
from itertools import combinations
return [frozenset(S) for r in range(1, n) for S in combinations(range(n), r)]
def least_core_epsilon(v, n):
# LP : max epsilon s.c. x(S) >= v(S) + epsilon (S propre) et x(N) = v(N).
# Renvoie (epsilon*, x*, resultat_scipy). epsilon* >= 0 <=> Core non vide.
coals = proper_coalitions(n)
c = [0.0] * n + [-1.0] # on minimise -epsilon
A_ub, b_ub = [], []
for S in coals:
row = [0.0] * (n + 1)
for i in S:
row[i] = -1.0 # -x(S)
row[n] = 1.0 # + epsilon
A_ub.append(row); b_ub.append(-v(S)) # -x(S) + epsilon <= -v(S)
A_eq = [[1.0] * n + [0.0]]
b_eq = [v(frozenset(range(n)))]
res = linprog(c, A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=b_eq,
bounds=[(None, None)] * (n + 1), method="highs")
return res.x[n], res.x[:n], res
jeux = [("Jeu de gants", glove_game), ("Jeu de majorite", majority_game_3),
("Jeu convexe |S|^2/9", convex_game)]
print("DIAGNOSTIC DU CORE PAR LEAST-CORE (LP HiGHS)")
print("=" * 56)
for nom, v in jeux:
eps, x, res = least_core_epsilon(v, 3)
verdict = "Core NON VIDE" if eps > -1e-9 else "Core VIDE"
print(f"\n{nom} (statut LP : {res.message.split('.')[0].lower()})")
print(f" epsilon* = {eps:+.4f} -> {verdict}")
print(f" point least-core x* = {[round(float(xi), 4) for xi in x]}")DIAGNOSTIC DU CORE PAR LEAST-CORE (LP HiGHS)
========================================================
Jeu de gants (statut LP : optimization terminated successfully)
epsilon* = -0.0000 -> Core NON VIDE
point least-core x* = [-0.0, -0.0, 1.0]
Jeu de majorite (statut LP : optimization terminated successfully)
epsilon* = -0.3333 -> Core VIDE
point least-core x* = [0.3333, 0.3333, 0.3333]
Jeu convexe |S|^2/9 (statut LP : optimization terminated successfully)
epsilon* = +0.2222 -> Core NON VIDE
point least-core x* = [0.3333, 0.3333, 0.3333]Le solveur retrouve par le calcul ce que les sections précédentes avaient etabli a la main, et le generalise :
epsilon* = 0 – le Core est non vide mais reduit a son unique point (0, 0, 1) (le detenteur du gant droit rafle tout). Marge nulle : on est sur la frontiere.epsilon* = -1/3 < 0 – le Core est vide, exactement la conclusion de la preuve manuelle de la section 3, ici obtenue automatiquement pour n’importe quel jeu. La marge -1/3 quantifie l’instabilite : chaque paire recoit 2/3 alors qu’elle peut exiger 1.epsilon* = +0.22 > 0 – le Core a un interieur, conforme au theoreme (les jeux convexes ont un Core non vide), section 5.C’est le test computationnel de vacuite du Core, valable pour tout jeu, la ou la preuve manuelle devait etre refaite a chaque fois.
Le least-core repond a la question numeriquement (le signe de epsilon* decide la vacuite). Bondareva-Shapley donne la caracterisation theorique qui explique pourquoi ce signe repond :
Le Core est non vide si et seulement si le jeu est equilibre (balanced).
Un jeu est equilibre si, pour toute famille de poids w(S) >= 0 sur les coalitions propres verifiant sum_{S \ni i} w(S) = 1 pour chaque joueur i, on a :
sum_S w(S) * v(S) <= v(N)Autrement dit : aucune coalition de coalitions (chaque joueur y participant a cheval sur plusieurs coalitions, au sens ou la somme des poids vaut 1) ne peut reclamer plus que la grande coalition N. Si une telle famille satisfait sum_S w(S) v(S) > v(N), alors le Core est vide – c’est un certificat de vacuite.
La machinerie est deja en place : maximiser sum_S w(S) v(S) sous sum_{S \ni i} w(S) = 1, w >= 0, est le dual du programme de faisabilite du Core. On le construit directement ci-dessous, puis on le relie au LP de least-core.
def balanced_weights(v, n):
"""Construit les poids d'equilibrage w(S) >= 0 sur les coalitions propres
avec sum_{S \ni i} w(S) = 1 pour chaque joueur i, en maximisant
sum_S w(S) * v(S). C'est le dual du programme de faisabilite du Core.
Renvoie un dict {coalition: poids}."""
coals = proper_coalitions(n)
c = [-v(S) for S in coals] # minimiser -sum = maximiser sum w(S)v(S)
A_eq = [[1.0 if i in S else 0.0 for S in coals] for i in range(n)]
b_eq = [1.0] * n
res = linprog(c, A_eq=A_eq, b_eq=b_eq, bounds=[(0, None)] * len(coals), method="highs")
return {S: float(wk) for S, wk in zip(coals, res.x)}
def is_balanced(v, n, tol=1e-9):
"""Bondareva-Shapley : Core non vide <=> jeu equilibre.
Renvoie (equilibre, poids, somme_S w(S)v(S), v(N))."""
w = balanced_weights(v, n)
somme = sum(w[S] * v(S) for S in w)
vN = v(frozenset(range(n)))
return (somme <= vN + tol), w, somme, vN
def format_coalition(S):
return "{" + ", ".join(str(i + 1) for i in sorted(S)) + "}"
print("BONDAREVA-SHAPLEY : CERTIFICAT D'EQUILIBRAGE (LP dual du Core)")
print("=" * 62)
for nom, v in jeux:
eq, w, somme, vN = is_balanced(v, 3)
print(f"\n{nom}")
print(f" v(N) = {vN}")
print(f" somme_S w(S)*v(S) = {somme:+.4f} -> equilibre ? {eq}")
cert = {format_coalition(S): round(val, 4) for S, val in w.items() if val > 1e-9}
print(f" collection equilibree (poids > 0) : {cert}")BONDAREVA-SHAPLEY : CERTIFICAT D'EQUILIBRAGE (LP dual du Core)
==============================================================
Jeu de gants
v(N) = 1
somme_S w(S)*v(S) = +1.0000 -> equilibre ? True
collection equilibree (poids > 0) : {'{1, 2}': 0.5, '{1, 3}': 0.5, '{2, 3}': 0.5}
Jeu de majorite
v(N) = 1
somme_S w(S)*v(S) = +1.5000 -> equilibre ? False
collection equilibree (poids > 0) : {'{1, 2}': 0.5, '{1, 3}': 0.5, '{2, 3}': 0.5}
Jeu convexe |S|^2/9
v(N) = 1.0
somme_S w(S)*v(S) = +0.6667 -> equilibre ? True
collection equilibree (poids > 0) : {'{1, 2}': 0.5, '{1, 3}': 0.5, '{2, 3}': 0.5}Le jeu de majorite n’est pas equilibre. La collection des trois paires {1,2}, {1,3}, {2,3} avec w = 1/2 chacune verifie sum_{S \ni i} w(S) = 1 pour chaque joueur (chacun apparait dans deux paires : 2 * 1/2 = 1), mais donne :
sum_S w(S) * v(S) = 3 * (1/2) * 1 = 3/2 > 1 = v(N)C’est le certificat de la vacuite du Core : toute allocation x avec x(N) = 1 laisserait une paire a x(S) < 1 = v(S) – les trois paires ne peuvent pas etre satisfaites simultanement, exactement la contradiction de la section 3 (2 >= 3).
| Jeu | least-core epsilon* |
equilibre ? | Concordance |
|---|---|---|---|
| Gants | -0.0000 (Core non vide) |
oui | cohérent |
| Majorite | -0.3333 (Core vide) |
non | cohérent |
Les deux diagnostics coincident : epsilon* >= 0 si et seulement si le jeu est equilibre. C’est le theoreme de Bondareva-Shapley, vu numeriquement.
# Les variables duales du LP de least-core (res.ineqlin.marginals) sont, a
# normalisation pres, les poids d'equilibrage du certificat de la cellule
# precedente : prendre |marginal| puis renormaliser pour que chaque joueur somme a 1.
print("LIEN PRIMAL/DUAL : les marges du least-core sont le certificat d'equilibrage")
print("=" * 72)
for nom, v in jeux:
eps, x, res = least_core_epsilon(v, 3)
coals = proper_coalitions(3)
marg = res.ineqlin.marginals
absm = [abs(m) for m in marg]
# renormalisation uniforme k : somme_{S \ni 0} k*|m(S)| = 1
k = 1.0 / sum(absm[j] for j in range(len(coals)) if 0 in coals[j])
w_dual = {S: k * absm[j] for j, S in enumerate(coals)}
somme_dual = sum(w_dual[S] * v(S) for S in w_dual)
vN = v(frozenset(range(3)))
print(f"\n{nom} : epsilon* = {eps:+.4f}")
print(" |marginal| brut (paires) : " + ", ".join(
f"|m({format_coalition(S)})| = {absm[j]:.4f}" for j, S in enumerate(coals) if absm[j] > 1e-9))
print(" renormalise (k = {:.4f}, somme_{{S \ni i}} w(S) = 1) : ".format(k) + ", ".join(
f"w({format_coalition(S)}) = {w_dual[S]:.4f}" for S in w_dual if w_dual[S] > 1e-9))
print(f" somme_S w(S)*v(S) = {somme_dual:+.4f}")
print(" -> meme verdict que la cellule precedente : " + (
"equilibre (Core non vide)" if somme_dual <= vN + 1e-9 else "non equilibre (Core vide)"))LIEN PRIMAL/DUAL : les marges du least-core sont le certificat d'equilibrage
========================================================================
Jeu de gants : epsilon* = -0.0000
|marginal| brut (paires) : |m({1, 2})| = 0.3333, |m({1, 3})| = 0.3333, |m({2, 3})| = 0.3333
renormalise (k = 1.5000, somme_{S
i i} w(S) = 1) : w({1, 2}) = 0.5000, w({1, 3}) = 0.5000, w({2, 3}) = 0.5000
somme_S w(S)*v(S) = +1.0000
-> meme verdict que la cellule precedente : equilibre (Core non vide)
Jeu de majorite : epsilon* = -0.3333
|marginal| brut (paires) : |m({1, 2})| = 0.3333, |m({1, 3})| = 0.3333, |m({2, 3})| = 0.3333
renormalise (k = 1.5000, somme_{S
i i} w(S) = 1) : w({1, 2}) = 0.5000, w({1, 3}) = 0.5000, w({2, 3}) = 0.5000
somme_S w(S)*v(S) = +1.5000
-> meme verdict que la cellule precedente : non equilibre (Core vide)
Jeu convexe |S|^2/9 : epsilon* = +0.2222
|marginal| brut (paires) : |m({3})| = 0.5000, |m({1, 2})| = 0.5000
renormalise (k = 2.0000, somme_{S
i i} w(S) = 1) : w({3}) = 1.0000, w({1, 2}) = 1.0000
somme_S w(S)*v(S) = +0.5556
-> meme verdict que la cellule precedente : equilibre (Core non vide)Lecture chiffree — le solveur rend le certificat gratuitement. La sortie part des marges duales du LP de least-core (res.ineqlin.marginal) et les transforme en certificat de Bondareva-Shapley. Jeu de gants : epsilon* = -0.0000, les trois paires portent |m| = 0.3333 chacune ; la renormalisation k = 1.5000 (chaque joueur apparait dans deux paires) donne w({i,j}) = 0.5000 et somme_S w(S)*v(S) = +1.0000 — pile v(N) : la collection equilibree explicite de la cellule precedente, reconstruite par le dual sans qu’on la fournisse. Jeu de majorite : epsilon* = -0.3333 et la meme mecanique conduit a la somme 3/2 > 1 de la preuve manuelle. La lecon d’ingenierie : primal et dual d’un meme LP livrent le verdict ET son certificat — deux preuves pour le prix d’un solve.
Soit le jeu a 3 joueurs de fonction caracteristique : v({1}) = v({2}) = v({3}) = 0, v({1,2}) = v({1,3}) = v({2,3}) = 1, et v({1,2,3}) = 1.5 (le jeu de majorite dont la grande coalition vaut 1.5).
Objectif : montrer que le Core est vide en exhibant la collection equilibree qui le certifie, comme a la section precedente.
w(S) >= 0 avec sum_{S \ni i} w(S) = 1 pour chaque joueur, dont sum_S w(S) * v(S) > v(N).w = 1/2.sum_S w(S) * v(S) et comparer a v(N) = 1.5.is_balanced) sur la vacuite du Core.def exercice_collection_equilibree() -> dict:
"""Exhiber la collection equilibree qui prouve que le Core est vide.
Jeu : v(singletons) = 0, v(paires) = 1, v(N = {1,2,3}) = 1.5.
Returns:
dict avec :
'w': collection equilibree {coalition: poids}
'somme': somme_S w(S) * v(S)
'vN': v(N)
'core_vide': bool (somme > vN)
"""
return {"w": {}, "somme": 0.0, "vN": 0.0, "core_vide": False} # TODO etudiant
res_ce = exercice_collection_equilibree()
print("Collection equilibree :", res_ce["w"])
print(f"somme_S w(S)*v(S) = {res_ce['somme']:+.4f} vs v(N) = {res_ce['vN']}")
print("Core vide ?", res_ce["core_vide"])
print("Exercice a completer")Collection equilibree : {}
somme_S w(S)*v(S) = +0.0000 vs v(N) = 0.0
Core vide ? False
Exercice a completerLire la sortie d’un exercice non rempli — l’artefact du jeu nul. Collection equilibree : {} avec somme_S w(S)*v(S) = +0.0000 vs v(N) = 0.0 puis Core vide ? False : tout vient du jeu par defaut (nul) et de la collection vide — le verdict False mesure un objet absent, pas le jeu de majorite. L’etat reel : « Exercice a completer ». Le contrat : exhiber une collection equilibree qui prouve la vacuite du Core du jeu de majorite, c’est-a-dire des poids w sur des coalitions avec somme_{S contient i} w(S) = 1 pour chaque joueur et somme_S w(S) v(S) > v(N). La reponse existe deja dans ce notebook — les trois paires a 1/2 de la section precedente ; l’exercice demande de la retrouver par la methode, pas de la recopier.
Le least-core peut encore contenir plusieurs allocations. Le nucleole (Schmeidler, 1969) selectionne la plus equitable d’entre elles : il minimise lexicographiquement le vecteur des exces trie par ordre decroissant, ou l’exces d’une coalition S pour une allocation x est e(S, x) = v(S) - x(S) (le “mecontentement” de S). On rend d’abord le plus grand mecontentement aussi petit que possible, puis le deuxieme, etc.
Proprietes (Schmeidler) : le nucleole existe toujours, il est unique, et il appartient au Core des que celui-ci est non vide. Il se calcule par une suite finie de programmes lineaires (algorithme de Maschler) : on resout le LP du least-core, on fige les coalitions devenues serrees comme egalites, puis on recommence sur les coalitions restantes jusqu’a determiner entierement l’allocation.
def nucleolus(v, n):
# Nucleole par LPs sequentiels (Maschler) : maximise puis fige les exces,
# par marges decroissantes. Renvoie (x*, nombre_de_LP).
coals = proper_coalitions(n)
vN = v(frozenset(range(n)))
fixed = [] # (coalition, epsilon fige) -> contraintes d'egalite
remaining = list(coals)
x_star, rounds = None, 0
while remaining:
rounds += 1
c = [0.0] * n + [-1.0]
A_ub, b_ub = [], []
for S in remaining:
row = [0.0] * (n + 1)
for i in S:
row[i] = -1.0
row[n] = 1.0
A_ub.append(row); b_ub.append(-v(S))
A_eq = [[1.0] * n + [0.0]]; b_eq = [vN]
for (S, eps_fix) in fixed:
row = [0.0] * (n + 1)
for i in S:
row[i] = 1.0
A_eq.append(row); b_eq.append(v(S) + eps_fix)
res = linprog(c, A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=b_eq,
bounds=[(None, None)] * (n + 1), method="highs")
if not res.success:
break
eps = res.x[n]; x_star = res.x[:n]
newly = [S for S in remaining
if abs(sum(x_star[i] for i in S) - v(S) - eps) < 1e-6]
if not newly:
break
fixed += [(S, eps) for S in newly]
remaining = [S for S in remaining if S not in newly]
return x_star, rounds
print("NUCLEOLE vs VALEUR DE SHAPLEY")
print("=" * 56)
for nom, v in jeux:
nuc, nlp = nucleolus(v, 3)
sh = shapley_value_exact(v, 3)
in_core_nuc, _ = is_in_core(nuc, v, 3)
in_core_sh, _ = is_in_core(sh, v, 3)
print(f"\n{nom} ({nlp} LP resolus)")
print(f" Nucleole = {[round(float(z), 4) for z in nuc]} -> dans le Core : {in_core_nuc}")
print(f" Shapley = {[round(float(z), 4) for z in sh]} -> dans le Core : {in_core_sh}")NUCLEOLE vs VALEUR DE SHAPLEY
========================================================
Jeu de gants (2 LP resolus)
Nucleole = [-0.0, -0.0, 1.0] -> dans le Core : True
Shapley = [0.1667, 0.1667, 0.6667] -> dans le Core : False
Jeu de majorite (2 LP resolus)
Nucleole = [0.3333, 0.3333, 0.3333] -> dans le Core : False
Shapley = [0.3333, 0.3333, 0.3333] -> dans le Core : False
Jeu convexe |S|^2/9 (1 LP resolus)
Nucleole = [0.3333, 0.3333, 0.3333] -> dans le Core : True
Shapley = [0.3333, 0.3333, 0.3333] -> dans le Core : TrueLecture chiffree — trois jeux font un banc complet pour le nucleole. La sortie croise nucleole et Shapley sur les trois jeux du notebook. Jeu de gants : Nucleole = [-0.0, -0.0, 1.0] -> Core : True contre Shapley = [0.1667, 0.1667, 0.6667] -> False — le nucleole selections l’unique point du Core (le detenteur du gant droit rafle tout), la Shapley equitable reste dehors : stabilite contre equite, tranchees. Jeu de majorite : les DEUX valent (0.3333, 0.3333, 0.3333) et TOUS DEUX hors Core — la symetrie force l’egalite des deux concepts, et le nucleole existe meme sans Core (propriete « existe toujours » verifiee sur ce cas). Jeu convexe : les deux coincident encore, cette fois DANS le Core. Le detail final compte : « 2 LP resolus » pour gants et majorite contre « 1 LP resolus » pour le convexe — l’algorithme sequentiel de Maschler s’arrete des la premiere etape quand le Core a un interieur, il ne s’y enlise que sur les cas limites.
import numpy as np
import matplotlib.pyplot as plt
fig, axes = plt.subplots(1, 2, figsize=(12, 4.5))
for ax, (nom, v) in zip(axes, [("Jeu de gants (Core = {(0,0,1)})", glove_game),
("Jeu de majorite (Core vide)", majority_game_3)]):
nuc, _ = nucleolus(v, 3)
sh = shapley_value_exact(v, 3)
idx = np.arange(3); w = 0.38
ax.bar(idx - w/2, sh, w, label="Shapley", color="steelblue", edgecolor="black")
ax.bar(idx + w/2, nuc, w, label="Nucleole", color="coral", edgecolor="black")
in_sh, _ = is_in_core(sh, v, 3); in_nuc, _ = is_in_core(nuc, v, 3)
ax.set_title(f"{nom}\nShapley dans Core : {in_sh} | Nucleole dans Core : {in_nuc}",
fontsize=10)
ax.set_xticks(idx); ax.set_xticklabels(["Joueur 1", "Joueur 2", "Joueur 3"])
ax.set_ylabel("Part allouee"); ax.legend(); ax.axhline(0, color="gray", lw=0.6)
plt.tight_layout(); plt.show()
print("Lecture : a gauche, Shapley sort du Core (le gant droit devrait tout rafler),")
print("le nucleole y reste. A droite (Core vide), les deux coincident par symetrie.")
Lecture : a gauche, Shapley sort du Core (le gant droit devrait tout rafler),
le nucleole y reste. A droite (Core vide), les deux coincident par symetrie.| Concept | Ce qu’il optimise | Toujours défini ? | Dans le Core ? | Cout de calcul |
|---|---|---|---|---|
| Valeur de Shapley | contribution marginale moyenne (equite) | oui | non (cf. jeu de gants) | enumeration des permutations |
| Nucleole | minimise lexicographiquement le mecontentement maximal (stabilite) | oui | oui des que le Core est non vide | suite finie de LP |
Least-core (epsilon*) |
marge de stabilite maximale | oui | diagnostique vide / non vide | un seul LP |
Le jeu de gants est le cas discriminant : la valeur de Shapley (1/6, 1/6, 2/3) recompense les deux gants gauches alors qu’ils sont en surnombre, et sort du Core ; le nucleole (0, 0, 1) donne tout au gant droit – la seule allocation stable. Sur le jeu de majorite (Core vide) le nucleole reste défini et coincide avec Shapley par symetrie. Le nucleole est donc le concept de solution canonique quand on exige la stabilite plutot que l’equite marginale – au prix d’une sequence de programmes lineaires plutot que d’une simple moyenne.
| Concept | Implementation Python |
|---|---|
| Shapley exact | shapley_value_exact(v, n) |
| Banzhaf | banzhaf_index(v, n) |
| Vote pondere | weighted_voting_game(weights, quota) |
| Test convexite | is_convex(v, n) |
| Test Core | is_in_core(allocation, v, n) |
Lien avec le notebook 15b Lean :
| Notebook 15b (Lean) | Notebook 15c (Python) |
|---|---|
| Axiomes de Shapley | Calcul numérique |
| Theoreme d’unicite | Verification empirique |
| Definition du Core | Test d’appartenance |
| Jeux de vote | Banzhaf et comparaison |
Navigation : ← GameTheory-15b-Lean-CooperativeGames-Lean | Index | [Fin de la serie]
Trois compagnies aeriennes partagent un aeroport. Les couts de construction selon les coalitions (en M€) sont : - v({A})=10, v({B})=20, v({C})=30 - v({A,B})=25, v({A,C})=35, v({B,C})=40, v({A,B,C})=50
Calculez la valeur de Shapley pour chaque compagnie.
Quatre partis (A=40%, B=30%, C=20%, D=10%) doivent former une coalition majoritaire (>50%). Calculez les indices de Banzhaf pour determiner le pouvoir de vote reel.
Trois entreprises ont des valeurs solo (v({1})=100, v({2})=150, v({3})=200). En fusion elles valent v({1,2})=350, v({1,3})=400, v({2,3})=450, v({1,2,3})=700. Le Core est-il non-vide ? Calculez Shapley et verifiez s’il appartient au Core.
# Espace pour les exercices
# Exemple guide 1 : Jeu de l'aeroport
def airport_value(coalition):
# TODO etudiant : definir la fonction caracteristique
return None # TODO etudiant : remplacer par les valeurs
# TODO etudiant : calculer shapley_value_exact(airport_value, 3)
# Exemple guide 2 : Partis politiques
def political_game(coalition):
# TODO etudiant : renvoyer 1 si la coalition est majoritaire (>50%), 0 sinon
weights = {0: 40, 1: 30, 2: 20, 3: 10} # poids en %
return None # TODO etudiant
# TODO etudiant : calculer banzhaf_index(political_game, 4)
# Exemple guide 3 : Fusion d'entreprises
def merger_value(coalition):
# TODO etudiant : definir les valeurs de coalition
return None # TODO etudiant
# TODO etudiant : is_convex(merger_value, 3), core, shapley
print("Exercice a completer")Exercice a completerLire la sortie d’un exercice non rempli. La ligne « Exercice a completer » ouvre l’espace des exemples guides de la section Exercices : le premier (jeu de l’aeroport, enonce ci-dessus) attend sa solution ici. Le terrain est pose par le notebook entier : shapley_value_exact (section 1) calcule les allocations, le LP de least-core (section 6) teste l’appartenance au Core, et le modele du jeu de gants montre comment encoder une fonction caracteristique par petites regles. Une solution remplie affichera la fonction de cout de l’aeroport, les parts Shapley par joueur, et leur lecture — qui paie quoi du runway commun quand les avions n’ont pas la meme taille.
Ce notebook compagnon a illustre les concepts fondamentaux de la théorie des jeux cooperatifs a travers des implementations Python concretes. La valeur de Shapley, calculee exactement par enumeration des permutations, a revele le principe de rarete dans le jeu de gants ou le detenteur de la ressource complementaire rare obtient 4/6 de la valeur totale. La preuve du Core vide pour le jeu de majorite simple a 3 joueurs a montre comment la sommation des contraintes de stabilite mene a une contradiction (2 >= 3), illustrant l’instabilite coalitionnelle inhierente a ce type de jeu. Les indices de pouvoir de Shapley et Banzhaf ont ensuite demontre que le pouvoir reel peut differer significativement du poids nominal dans les jeux de vote ponderes, les non-permanents du Conseil de securite disposant d’un ratio pouvoir/poids plus eleve que les permanents.
La propriete de convexite s’est revelee determinante pour la stabilite des allocations : dans les jeux convexes (supermodulaires), la valeur de Shapley est garantie d’appartenir au Core, tandis que les jeux non convexes comme celui de la majorite ou des gants ne beneficient pas de cette garantie. Cette distinction entre “juste” (Shapley) et “stable” (Core) est au coeur de la théorie cooperative, et les exercices proposes permettent d’approfondir ces concepts sur des applications concretes (aeroport, fusion d’entreprises, jeux politiques).
Les concepts de valeur de Shapley, de Core et d’indices de pouvoir trouvent des applications directes en economie (repartition des couts), en sciences politiques (analyse du pouvoir de vote) et en intelligence artificielle (explicabilite des modèles via les valeurs de Shapley en ML). Le passage a l’echelle vers des jeux a un grand nombre de joueurs necessite des méthodes d’approximation Monte Carlo de la valeur de Shapley, constituant un domaine de recherche actif.
Lien avec la formalisation Lean : Les concepts de ce notebook — jeux cooperatifs TU, valeur de Shapley, Core, convexite — sont construits formellement dans le notebook compagnon GT-15b-Lean-CooperativeGames et la librairie
game_theory_lean/. Le moduleBasic.lean(0 sorry) définitTUGame, les coalitions, le Core et la convexite, et prouve le theoreme de Bondareva-Shapley (condition necessaire et suffisante pour le Core non-vide). Le moduleShapley.lean(0 sorry) formalise les 4 axiomes de Shapley (efficacite, symetrie, joueur nul, additivite) et prouve l’unicite de la valeur. Le jeu de gants (Glove Game) et le jeu de majorite illustres numeriquement ci-dessus y sont également traites.
Lien numerique : ce que
bondareva_shapley_forwardetbondareva_shapley_backwardprouvent pour tout jeu, la cellulegt15c-bal-code(section 6) le verifie sur ceux-ci : sur le jeu de majorite, la collection equilibreew = 1/2sur les trois paires certifie la vacuite du Core (sum_S w(S) v(S) = 3/2 > 1 = v(N)), en concordance avecepsilon* < 0.
Notebook précédent: GameTheory-15b-Lean-CooperativeGames-Lean
Notebook suivant: GameTheory-16-MechanismDesign-Python