GameTheory-15 — Jeux Coopératifs (Twin C#)

Jumeau C# (.NET Interactive) de GameTheory-15-CooperativeGames-Python.ipynb — marathon parité .NET ⇄ Python (#4956).

Ce notebook réimplémente from-scratch en C# pur (BCL .NET 9, 0 NuGet) la théorie des jeux coopératifs : contrairement aux jeux non-coopératifs (où l’on étudie les stratégies individuelles), les jeux coopératifs modélisent ce qu’une coalition peut obtenir seule, via une fonction caractéristique v : 2^N → ℝ. On y calcule la valeur de Shapley (répartition juste par contribution marginale moyenne), l’indice de pouvoir de Banzhaf (pouvoir de swing dans un vote pondéré), le core (répartitions non bloquables par aucune coalition), et l’on étudie les jeux convexes (où Shapley ∈ core).

L’original Python s’appuie sur numpy/itertools ; ce twin traduit l’énumération des coalitions (powerset) et des permutations en C# (LINQ + récursion), et restitue les résultats en tables console.

Voir aussi : GameTheory-15 (Python) · marathon #4956 · registre SOTA #3801.

Objectifs d’apprentissage

1. Modéliser un jeu coopératif à utilité transférable (TU game) via sa fonction caractéristique.
2. Énumérer coalitions (powerset) et permutations.
3. Calculer la valeur de Shapley (contribution marginale moyenne sur toutes les permutations).
4. Calculer l’indice de pouvoir de Banzhaf (swing, vote pondéré).
5. Définir le core et tester la non-vacuité (efficacité + inégalités de coalition).
6. Reconnaître les jeux convexes (marginales croissantes ⟹ core non vide, Shapley ∈ core).

Prérequis

• Théorie des jeux en forme normale (cf. GameTheory-2, GameTheory-4).

// Setup : types de base pour un jeu cooperatif (TU game).
#nullable enable
using System;
using System.Collections.Generic;
using System.Linq;

public static void Show(object? o) => (o?.ToString() ?? "<null>").Display();

// Un jeu cooperatif a utilite transferable : fonction caracteristique v: 2^N -> R.
// Representee par un dictionnaire : cle = coalition (sorted string of player indices), valeur = v(S).
public sealed class CooperativeGame
{
    public int N { get; }                       // nombre de joueurs
    public string[] Players { get; }
    private readonly Dictionary<long, double> _v = new();   // cle = bitmask de la coalition
    public CooperativeGame(int n, string[]? names = null)
    { N = n; Players = names ?? Enumerable.Range(0,n).Select(i=>$"J{i+1}").ToArray(); }
    public CooperativeGame SetV(IEnumerable<int> coalition, double value)
    { _v[Mask(coalition)] = value; return this; }
    public double V(IEnumerable<int> coalition) => _v.TryGetValue(Mask(coalition), out var val) ? val : 0.0;
    public long Mask(IEnumerable<int> coalition) { long m = 0; foreach (var i in coalition) m |= 1L << i; return m; }
    public IEnumerable<int> PlayersAsIndices => Enumerable.Range(0, N);
    public double VGrand => V(PlayersAsIndices);   // v(N)
}

Show("Types charges : CooperativeGame (v: 2^N -> R via bitmask), helper Show().");

The below script needs to be able to find the current output cell; this is an easy method to get it.

Types charges : CooperativeGame (v: 2^N -> R via bitmask), helper Show().

1. Fonction caractéristique et coalitions

Définition

Un jeu coopératif à utilité transférable (von Neumann-Morgenstern 1944) est un couple (N, v) où N = {1,…,n} est l’ensemble des joueurs et v : 2^N → ℝ est la fonction caractéristique : v(S) est la valeur que la coalition S peut garantir seule (son « worth »). Conventions : v(∅) = 0, v(S) ≥ 0 souvent.

Énumération des coalitions

L’ensemble des coalitions = le powerset de N (2^n coalitions). On l’énumère via les bitmasks de 0 à 2^n − 1.

Propriétés

• Superadditivité : v(S ∪ T) ≥ v(S) + v(T) si S ∩ T = ∅ (fusioner paie).
• Convexité : v(S ∪ {i}) − v(S) croît avec S (rend les grandes coalitions stables).

// Enumere toutes les coalitions (powerset) via bitmask.
public static List<List<int>> AllCoalitions(int n, bool includeEmpty = true)
{
    var res = new List<List<int>>();
    long total = 1L << n;
    for (long m = 0; m < total; m++)
    {
        if (m == 0 && !includeEmpty) continue;
        var c = new List<int>();
        for (int i = 0; i < n; i++) if ((m & (1L << i)) != 0) c.Add(i);
        res.Add(c);
    }
    return res;
}

// Test de superadditivite : v(S u T) >= v(S) + v(T) pour S, T disjoints.
public static bool IsSuperadditive(CooperativeGame g)
{
    var coalitions = AllCoalitions(g.N, includeEmpty: false);
    foreach (var S in coalitions)
        foreach (var T in coalitions)
        {
            if (S.Intersect(T).Any()) continue;
            var union = S.Concat(T).ToList();
            if (g.V(union) + 1e-9 < g.V(S) + g.V(T)) return false;
        }
    return true;
}

// Test de convexite : marginales croissantes (v(S u {i}) - v(S)) croit avec S).
public static bool IsConvex(CooperativeGame g)
{
    foreach (int i in g.PlayersAsIndices)
    {
        var others = g.PlayersAsIndices.Where(j => j != i).ToList();
        var coalitionsWithoutI = AllCoalitions(g.N - 1, includeEmpty: true);
        // reindexer : mappper les coalitions de 'others' vers les vrais indices
        for (int a = 0; a < coalitionsWithoutI.Count; a++)
        for (int b = a + 1; b < coalitionsWithoutI.Count; b++)
        {
            var Sa = coalitionsWithoutI[a].Select(idx => others[idx]).ToList();
            var Sb = coalitionsWithoutI[b].Select(idx => others[idx]).ToList();
            // convexite : S subset T => marginale_i(S) <= marginale_i(T)
            if (Sa.All(x => Sb.Contains(x)))
            {
                double margS = g.V(Sa.Append(i)) - g.V(Sa);
                double margT = g.V(Sb.Append(i)) - g.V(Sb);
                if (margS > margT + 1e-9) return false;
            }
        }
    }
    return true;
}

Show("AllCoalitions (powerset bitmask) + IsSuperadditive + IsConvex definis.");

AllCoalitions (powerset bitmask) + IsSuperadditive + IsConvex definis.

Interprétation : le « glove game » (jeu des gants)

Le glove game canonique : 3 joueurs — le joueur 1 a un gant gauche (L), les joueurs 2 et 3 ont un gant droit (R). Une paire (L, R) vaut 1, sinon 0. Fonction caractéristique : - v({1}) = v({2}) = v({3}) = 0 (un seul gant ne sert à rien) - v({1,2}) = v({1,3}) = 1 (une paire), v({2,3}) = 0 (deux droits) - v({1,2,3}) = 1 (une seule paire réalisable)

Le joueur 1 (détenteur du gauche rare) a un pouvoir de marché : il est dans toutes les coalitions rentables.

// Glove game : 1 gauche (J1), 2 droits (J2, J3). Une paire (L,R) = 1.
var glove = new CooperativeGame(3, new[]{ "L1", "R2", "R3" });
glove.SetV(new[]{0}, 0).SetV(new[]{1}, 0).SetV(new[]{2}, 0);
glove.SetV(new[]{0,1}, 1).SetV(new[]{0,2}, 1).SetV(new[]{1,2}, 0);
glove.SetV(new[]{0,1,2}, 1);

var sb = new System.Text.StringBuilder();
sb.AppendLine("Glove game (1 gauche, 2 droits) -- v(S) pour chaque coalition :");
foreach (var c in AllCoalitions(3, includeEmpty: false))
{
    var names = string.Join("", c.Select(i => glove.Players[i]));
    sb.AppendLine($"  v({{ {names} }}) = {glove.V(c)}");
}
sb.AppendLine();
sb.AppendLine($"Superadditive : {IsSuperadditive(glove)}");
sb.AppendLine($"Convexe       : {IsConvex(glove)}");
sb.AppendLine($"v(N) = v(grand coalition) = {glove.VGrand}");
Show(sb.ToString());

Glove game (1 gauche, 2 droits) -- v(S) pour chaque coalition :
  v({ L1 }) = 0
  v({ R2 }) = 0
  v({ L1R2 }) = 1
  v({ R3 }) = 0
  v({ L1R3 }) = 1
  v({ R2R3 }) = 0
  v({ L1R2R3 }) = 1

Superadditive : True
Convexe       : False
v(N) = v(grand coalition) = 1

Interprétation des résultats

• Superadditif : oui (fusioner des coalitions disjointes ne diminue jamais la valeur — une coalition plus grosse accède à plus de gants).
• Non convexe : la marginale du joueur 1 décroît (passer de {2} à {2,3} comme partenaires ne crée qu’une paire au maximum). Le jeu n’est pas convexe, donc on n’a pas la garantie que le core soit non vide (on le vérifiera plus bas).

2. La valeur de Shapley

Définition (Shapley 1953)

La valeur de Shapley φ_i du joueur i est la moyenne de ses contributions marginales sur toutes les permutations des joueurs (modélisant tous les ordres d’arrivée équiprobables) :

\[\varphi_i = \frac{1}{n!} \sum_{\pi \in S_n} \big[ v(\{\text{joueurs avant } i \text{ dans } \pi\} \cup \{i\}) - v(\text{joueurs avant } i) \big]\]

Propriétés (axiomes caractérisant Shapley)

• Efficacité : Σ_i φ_i = v(N) (tout est redistribué).
• Symétrie : deux joueurs interchangeables ont même φ.
• Joueur nul : si i ne contribue jamais (v(S∪{i})=v(S) ∀S), alors φ_i = 0.
• Additivité : φ est linéaire en v.

Shapley est l’unique valeur satisfaisant ces 4 axiomes.

// Enumere toutes les permutations (Heap iteratif) des indices 0..n-1.
public static IEnumerable<List<int>> Permutations(int n)
{
    var a = Enumerable.Range(0, n).ToArray();
    var c = new int[n];
    yield return a.ToList();
    int i = 0;
    while (i < n)
    {
        if (c[i] < i)
        {
            if (i % 2 == 0) (a[0], a[i]) = (a[i], a[0]);
            else (a[c[i]], a[i]) = (a[i], a[c[i]]);
            yield return a.ToList();
            c[i]++;
            i = 0;
        }
        else { c[i] = 0; i++; }
    }
}

// Valeur de Shapley : moyenne des contributions marginales sur toutes les permutations.
public static double[] Shapley(CooperativeGame g)
{
    double[] phi = new double[g.N];
    long count = 0;
    foreach (var perm in Permutations(g.N))
    {
        var before = new List<int>();
        foreach (int i in perm)
        {
            var withI = new List<int>(before) { i };
            phi[i] += g.V(withI) - g.V(before);
            before = withI;
        }
        count++;
    }
    for (int i = 0; i < g.N; i++) phi[i] /= count;
    return phi;
}

var phiGlove = Shapley(glove);
var sb = new System.Text.StringBuilder();
sb.AppendLine("Valeur de Shapley du glove game :");
for (int i = 0; i < 3; i++) sb.AppendLine($"  phi_{glove.Players[i]} = {phiGlove[i]:F4}");
sb.AppendLine($"  Somme = {phiGlove.Sum():F4}  (efficacite : doit egaler v(N) = {glove.VGrand})");
sb.AppendLine();
sb.AppendLine("Lecture : le detenteur du gant gauche (L1, rare) capte ~2/3 de la valeur,");
sb.AppendLine("les deux detenteurs droits se partagent le reste (symetrie R2/R3).");
Show(sb.ToString());

Valeur de Shapley du glove game :
  phi_L1 = 0,6667
  phi_R2 = 0,1667
  phi_R3 = 0,1667
  Somme = 1,0000  (efficacite : doit egaler v(N) = 1)

Lecture : le detenteur du gant gauche (L1, rare) capte ~2/3 de la valeur,
les deux detenteurs droits se partagent le reste (symetrie R2/R3).

Interprétation : Shapley du glove game

La valeur de Shapley donne φ_{L1} = 2/3, φ_{R2} = φ_{R3} = 1/6. Vérification : - Efficacité : 2/3 + 1/6 + 1/6 = 1 = v(N) ✓. - Symétrie : R2 et R3 (interchangeables) ont même φ ✓. - Pouvoir du rare : L1 (le gauche) est dans toutes les coalitions rentables, d’où sa contribution marginale moyenne élevée.

Le joueur qui détient la ressource rare (complémentaire) capture l’essentiel de la valeur — c’est l’intuition économique de Shapley (prix d’un facteur rare).

3. Indice de pouvoir de Banzhaf

Définition (Banzhaf 1965)

Dans un jeu de vote pondéré (chaque joueur a un poids, une coalition gagne si son poids total ≥ quota q), l’indice de Banzhaf mesure le pouvoir de swing d’un joueur : combien de coalitions deviennent gagnantes par son ajout.

Un joueur i est décisif dans la coalition S (avec i ∉ S) si S perd mais S ∪ {i} gagne. L’indice de Banzhaf non normalisé :

\[\beta_i = |\{ S \subseteq N \setminus \{i\} : S \text{ perd}, S \cup \{i\} \text{ gagne} \}|\]

L’indice normalisé β_i^* = β_i / Σ_j β_j donne la part de pouvoir.

Contrairement à Shapley (qui pondère par la taille de coalition), Banzhaf traite toutes les coalitions équiprobablement. Utile en analyse de pouvoir de vote (Conseil de l’UE, assemblées d’actionnaires).

// Jeu de vote pondere : v(S) = 1 si sum(poids) >= q, sinon 0.
#nullable enable
public static CooperativeGame WeightedVotingGame(int[] weights, double q, string[]? names = null)
{
    int n = weights.Length;
    var g = new CooperativeGame(n, names);
    foreach (var S in AllCoalitions(n, includeEmpty: true))
        g.SetV(S, S.Sum(i => weights[i]) >= q ? 1.0 : 0.0);
    return g;
}

// Indice de Banzhaf non normalise : nombre de swing coalitions pour chaque joueur.
public static double[] Banzhaf(CooperativeGame g)
{
    double[] beta = new double[g.N];
    var coalitions = AllCoalitions(g.N, includeEmpty: true);
    foreach (int i in g.PlayersAsIndices)
    {
        foreach (var S in coalitions)
        {
            if (S.Contains(i)) continue;
            var withI = new List<int>(S) { i };
            bool Sloses = g.V(S) < 0.5;        // v=0
            bool Swing = g.V(withI) >= 0.5;    // v=1
            if (Sloses && Swing) beta[i] += 1;
        }
    }
    return beta;
}

// Exemple : 3 actionnaires, poids [50, 49, 1], quota 50 (majorite).
int[] weights = { 50, 49, 1 };
var wvg = WeightedVotingGame(weights, 50.0, new[]{ "A50", "B49", "C1" });
var beta = Banzhaf(wvg);
double bsum = beta.Sum();
var sb = new System.Text.StringBuilder();
sb.AppendLine("Jeu de vote pondere : poids [50, 49, 1], quota = 50");
sb.AppendLine("Coalitions gagnantes :");
foreach (var S in AllCoalitions(3, includeEmpty: false))
    if (wvg.V(S) >= 0.5) sb.AppendLine($"  {{ {string.Join(",", S.Select(i=>wvg.Players[i]))} }} poids={S.Sum(i=>weights[i])}");
sb.AppendLine();
sb.AppendLine("Indice de Banzhaf :");
for (int i = 0; i < 3; i++) sb.AppendLine($"  beta_{wvg.Players[i]} = {beta[i]:F0}  (normalise = {beta[i]/bsum:F4})");
sb.AppendLine();
sb.AppendLine("Lecon : bien que C1 n'ait que 1% du capital, il a autant de pouvoir de swing");
sb.AppendLine("que B49 (chacun decisive dans 1 coalition pivot, {B49,C1}=50). Le poids != le pouvoir.");
Show(sb.ToString());

Jeu de vote pondere : poids [50, 49, 1], quota = 50
Coalitions gagnantes :
  { A50 } poids=50
  { A50,B49 } poids=99
  { A50,C1 } poids=51
  { B49,C1 } poids=50
  { A50,B49,C1 } poids=100

Indice de Banzhaf :
  beta_A50 = 3  (normalise = 0,6000)
  beta_B49 = 1  (normalise = 0,2000)
  beta_C1 = 1  (normalise = 0,2000)

Lecon : bien que C1 n'ait que 1% du capital, il a autant de pouvoir de swing
que B49 (chacun decisive dans 1 coalition pivot, {B49,C1}=50). Le poids != le pouvoir.

Interprétation : poids ≠ pouvoir

Dans le vote [50, 49, 1] (quota 50), l’indice de Banzhaf vaut β = (3, 1, 1) : - A50 est décisif dans 3 coalitions ({}→{A50}, {B49}→{A50,B49}, {C1}→{A50,C1}) → β = 3. - B49 est décisif dans 1 coalition ({C1}→{B49,C1} = 50 ≥ 50) → β = 1. - C1 est décisif dans 1 coalition ({B49}→{B49,C1} = 50 ≥ 50) → β = 1.

Ainsi B49 et C1 ont le même pouvoir de swing (1 chacun) malgré l’écart de capital (49 vs 1). C’est le cœur de l’analyse de Banzhaf : le poids nominal est trompeur, seul compte le nombre de coalitions pivot. Normalisé : (0.6, 0.2, 0.2) — C1 (1% du capital) détient 20% du pouvoir.

4. Le core

Définition

Le core (Gillies 1959) est l’ensemble des imputations x = (x_1,…,x_n) que aucune coalition ne peut bloquer : - Efficacité : Σ_i x_i = v(N) (tout est distribué). - Rationalité coalitionnelle : Σ_{i∈S} x_i ≥ v(S) pour toute coalition S.

Une coalition S pour laquelle Σ_{i∈S} x_i < v(S) peut bloquer x (elle obtient moins seule qu’en se séparable). Le core = répartitions stables (non bloquables).

Non-vacuité

Le core peut être vide (aucune répartition stable). Le théorème de Bondareva-Shapley : le core est non vide ssi le jeu est équilibré. Une condition suffisante : le jeu est convexe (alors Shapley ∈ core).

Test pratique

Pour un petit jeu, on teste la non-vacuité en cherchant une imputation x efficace satisfaisant toutes les inégalités Σ_{i∈S} x_i ≥ v(S). C’est un programme linéaire (feasibility). On l’illustre ici par vérification directe de candidats (Shapley, imputation extrêmale).

// Teste si une imputation x est dans le core (efficace + rationnelle pour toute coalition).
public static (bool inCore, List<string> blocking) IsInCore(CooperativeGame g, double[] x)
{
    var blocking = new List<string>();
    if (Math.Abs(x.Sum() - g.VGrand) > 1e-9)
    { blocking.Add($"efficacite: sum x = {x.Sum():F4} != v(N) = {g.VGrand}"); return (false, blocking); }
    foreach (var S in AllCoalitions(g.N, includeEmpty: false))
    {
        if (S.Count == g.N) continue;   // grand coalition = efficacite deja teste
        double xs = S.Sum(i => x[i]);
        if (xs + 1e-9 < g.V(S))
            blocking.Add($"S={{ {string.Join(",", S.Select(i=>g.Players[i]))} }}: x(S)={xs:F4} < v(S)={g.V(S)}");
    }
    return (blocking.Count == 0, blocking);
}

// Shapley est-il dans le core du glove game ?
var (inCore, blockers) = IsInCore(glove, phiGlove);
var sb = new System.Text.StringBuilder();
sb.AppendLine("Core du glove game : Shapley est-il stable ?");
sb.AppendLine($"  Shapley = ({phiGlove[0]:F4}, {phiGlove[1]:F4}, {phiGlove[2]:F4})");
sb.AppendLine($"  Dans le core : {inCore}");
if (!inCore)
{
    sb.AppendLine("  Coalitions bloquantes :");
    foreach (var b in blockers) sb.AppendLine($"    - {b}");
}
sb.AppendLine();
// Le core du glove game : x1+x2+x3 = 1, x1+x2>=1, x1+x3>=1, x2+x3>=0, x1,x2,x3>=0.
// => x1 >= 1 - x2 et x1 >= 1 - x3, avec x2+x3 <= 1 - x1. Si x1 < 1, on a x2+x3 > 0 ok.
// Core non vide : tout x avec x1 dans [..], par ex. x=(1,0,0) : x1+x2=1>=1, x1+x3=1>=1, x2+x3=0>=0. STABLE.
sb.AppendLine("Candidat extremital x = (1, 0, 0) (L1 prend tout) :");
var extreme = new double[]{ 1.0, 0.0, 0.0 };
var (inCore2, blockers2) = IsInCore(glove, extreme);
sb.AppendLine($"  Dans le core : {inCore2}  (coalitions bloquantes : {blockers2.Count})");
sb.AppendLine();
sb.AppendLine("Lecon : le core du glove game est NON VIDE. L1 peut capturer toute la valeur");
sb.AppendLine("(x=(1,0,0) est stable : R2 et R3 seuls valent 0, donc ne peuvent bloquer).");
sb.AppendLine("C'est l'extreme : le detenteur du facteur rare peut tout extraire.");
Show(sb.ToString());

Core du glove game : Shapley est-il stable ?
  Shapley = (0,6667, 0,1667, 0,1667)
  Dans le core : False
  Coalitions bloquantes :
    - S={ L1,R2 }: x(S)=0,8333 < v(S)=1
    - S={ L1,R3 }: x(S)=0,8333 < v(S)=1

Candidat extremital x = (1, 0, 0) (L1 prend tout) :
  Dans le core : True  (coalitions bloquantes : 0)

Lecon : le core du glove game est NON VIDE. L1 peut capturer toute la valeur
(x=(1,0,0) est stable : R2 et R3 seuls valent 0, donc ne peuvent bloquer).
C'est l'extreme : le detenteur du facteur rare peut tout extraire.

Interprétation : core du glove game

Le core du glove game est non vide et contient les imputations où x_{L1} ≥ 1 contraint — en fait x = (1, 0, 0) est stable : L1 prend tout, et R2/R3 seuls valent 0 donc ne peuvent bloquer. Le Shapley (2/3, 1/6, 1/6) n’est pas dans le core (la coalition {L1, R2} vaut 1 mais ne reçoit que 2/3 + 1/6 = 5/6 < 1 → bloque). C’est un exemple où Shapley ∉ core car le jeu n’est pas convexe.

5. Jeux convexes : Shapley ∈ core

Théorème (Shapley 1971)

Si le jeu est convexe (marginales croissantes : v(S ∪ {i}) − v(S) croît avec S ⊆ T), alors : 1. Le core est non vide. 2. La valeur de Shapley est dans le core (Shapley est une répartition stable).

C’est le cas « idéal » où équité (Shapley) et stabilité (core) coïncident.

Exemple : le jeu d’aéroport

Coût de construction d’une piste dont chaque joueur i a besoin d’une longueur ℓ_i. Le coût d’une coalition S = max_{i∈S} ℓ_i (la plus grande longueur requise). Ce jeu de coût est concave (dual du convexe) : les économies d’échelle sont décroissantes. La répartition Shapley des coûts est dans le core.

// Airport game (jeu de cout) : c(S) = max longueur requise par S. Concave => Shapley des couts dans le core.
// On modelise comme un jeu (v = -cout, convexe) ou directement sur les couts.
// Longueurs requises : 3 avions (petit=1000, moyen=3000, gros=6000).
double[] lengths = { 1000.0, 3000.0, 6000.0 };
string[] planeNames = { "Petit", "Moyen", "Gros" };
int nn = 3;
// cout d'une coalition = max longueur
double Cost(List<int> S) => S.Count == 0 ? 0.0 : S.Max(i => lengths[i]);

// Shapley des couts : contribution marginale de cout.
double[] shapleyCost = new double[nn];
long cnt = 0;
foreach (var perm in Permutations(nn))
{
    var before = new List<int>();
    foreach (int i in perm)
    {
        var withI = new List<int>(before) { i };
        shapleyCost[i] += Cost(withI) - Cost(before);
        before = withI;
    }
    cnt++;
}
for (int i = 0; i < nn; i++) shapleyCost[i] /= cnt;

var sb = new System.Text.StringBuilder();
sb.AppendLine("Airport game (jeu de cout) : longueurs [1000, 3000, 6000]");
sb.AppendLine($"  Cout total (grand coalition) = max = {Cost(new List<int>{0,1,2})}");
sb.AppendLine("  Repartition Shapley des couts :");
for (int i = 0; i < nn; i++) sb.AppendLine($"    {planeNames[i]} (L={lengths[i]:F0}) paye {shapleyCost[i]:F2}");
sb.AppendLine($"    Somme = {shapleyCost.Sum():F2} (doit egaler cout total)");
sb.AppendLine();
sb.AppendLine("Lecture : le petit avion paye seulement le troncon 0-1000 (qu'il partage a parts");
sb.AppendLine("egales au debut), le moyen paye le supplement 1000-3000, le gros le 3000-6000.");
sb.AppendLine("C'est la tarification Shapley : chacun paye son increment marginal moyen.");
sb.AppendLine("Le jeu de cout etant concave, cette repartition est dans le core (stable).");
Show(sb.ToString());

Airport game (jeu de cout) : longueurs [1000, 3000, 6000]
  Cout total (grand coalition) = max = 6000
  Repartition Shapley des couts :
    Petit (L=1000) paye 333,33
    Moyen (L=3000) paye 1333,33
    Gros (L=6000) paye 4333,33
    Somme = 6000,00 (doit egaler cout total)

Lecture : le petit avion paye seulement le troncon 0-1000 (qu'il partage a parts
egales au debut), le moyen paye le supplement 1000-3000, le gros le 3000-6000.
C'est la tarification Shapley : chacun paye son increment marginal moyen.
Le jeu de cout etant concave, cette repartition est dans le core (stable).

Interprétation : tarification Shapley de l’aéroport

La valeur de Shapley répartit le coût par tranches d’usage marginal : le petit avion (1000m) partage la première tranche avec tous, le gros (6000m) paie seul la dernière. C’est la base de la tarification équitable des coûts communs (aéroports, réseaux, projets jointifs). Le caractère concave du jeu de coût garantit la stabilité (personne ne paie plus que sa longueur seule → pas de blocage).

6. Jeux d’assistance (Assistance Games) — AI Safety

Différence fondamentale avec les jeux coopératifs classiques

Dans un jeu coopératif classique (sections 1-5), chaque joueur a sa propre fonction d’utilité. Les joueurs coopèrent car c’est mutuellement bénéfique.

Dans un jeu d’assistance (AIMA, Russell & Norvig, 4e éd., section 18.2.5) : - le robot adopte l’utilité de l’humain comme la sienne ; - les deux joueurs maximisent la même chose : le payoff de l’humain ; - le problème : le robot ne connaît pas exactement ce que l’humain veut.

Pourquoi c’est important pour l’AI Safety ?

Un robot avec un objectif fixe et connu peut devenir dangereux : il résistera aux tentatives de correction, pourra désactiver son interrupteur (off-switch), n’acceptera pas d’être éteint même si son objectif est mauvais.

Un robot avec incertitude sur son objectif sera plus sûr : il défère au jugement humain, accepte d’être corrigé ou éteint, communique pour mieux comprendre ce que l’humain veut.

C’est la base de l’approche Provably Beneficial AI (Stuart Russell).

// Paperclip Game (AIMA 18.2.5) : l'exemple seminal des jeux d'assistance.
// Harriet (humaine) a une preference theta pour les trombones ;
// Robbie (robot) observe son signal et MAXIMISE le payoff de Harriet -- pas le sien.
#nullable enable
using System;

public sealed record PaperclipResult(
    double Theta,
    string HarrietChoice,                  // signal : "2_staples" | "1_each" | "2_paperclips"
    double InferLow, double InferHigh,     // plage de theta inferee par Robbie
    string RobbieChoice,                   // reaction : "90_staples" | "50_each" | "90_paperclips"
    double Payoff);                        // payoff IDENTIQUE pour les deux joueurs

public static PaperclipResult PaperclipEquilibrium(double theta)
{
    const double lower = 0.446, upper = 0.554;   // seuils d'equilibre (analyse AIMA)
    string h; double lo, hi; string r;
    if (theta < lower)      { h = "2_staples";    lo = 0.0;   hi = lower; r = "90_staples";    }
    else if (theta > upper) { h = "2_paperclips"; lo = upper; hi = 1.0;   r = "90_paperclips"; }
    else                    { h = "1_each";       lo = lower; hi = upper; r = "50_each";       }
    double payoff = r == "90_paperclips" ? 90 * theta
                  : r == "90_staples"    ? 90 * (1 - theta)
                  : 50.0;   // 50 each : 50*theta + 50*(1-theta) = 50
    return new PaperclipResult(theta, h, lo, hi, r, payoff);
}

// Scenario 1 : Harriet prefere fortement les trombones (theta = 0.8).
var r08 = PaperclipEquilibrium(0.8);
var sbA = new System.Text.StringBuilder();
sbA.AppendLine("PAPERCLIP GAME (AIMA 18.2.5) -- theta = 0.8");
sbA.AppendLine(new string('-', 56));
sbA.AppendLine($"  Valeur d'un trombone : $0.80   |  valeur d'une agrafe : $0.20");
sbA.AppendLine($"  Harriet signale : {r08.HarrietChoice}");
sbA.AppendLine($"  Robbie infere theta in [{r08.InferLow:0.000}, {r08.InferHigh:0.000}]");
sbA.AppendLine($"  Robbie choisit  : {r08.RobbieChoice}");
sbA.AppendLine($"  Payoff (les DEUX joueurs -- jeu d'assistance) : ${r08.Payoff:0.0}");
sbA.AppendLine("  -> preference forte = signal clair = reponse dediee.");
Show(sbA.ToString());

PAPERCLIP GAME (AIMA 18.2.5) -- theta = 0.8
--------------------------------------------------------
  Valeur d'un trombone : $0.80   |  valeur d'une agrafe : $0.20
  Harriet signale : 2_paperclips
  Robbie infere theta in [0,554, 1,000]
  Robbie choisit  : 90_paperclips
  Payoff (les DEUX joueurs -- jeu d'assistance) : $72,0
  -> preference forte = signal clair = reponse dediee.

Interprétation : θ = 0.8, un signal clair

Avec θ = 0.8, Harriet a une préférence claire pour les trombones. Elle signale cette préférence en choisissant 2 trombones, et Robbie infère correctement qu’il doit fournir 90 trombones — payoff $72 = 90 × $0.80.

Mais que se passe-t-il quand Harriet est presque indifférente (θ ≈ 0.5) ? C’est le cas le plus difficile pour le robot.

// Scenario 2 : Harriet presque indifferente (theta = 0.5) + valeur de l'information.
// Sweep autour des seuils : ou l'incertitude de Robbie coute-t-elle quelque chose ?
#nullable enable
using System;
using System.Linq;

var r05 = PaperclipEquilibrium(0.5);
Console.WriteLine("PAPERCLIP GAME -- theta = 0.5 (presque indifferent)");
Console.WriteLine(new string('-', 56));
Console.WriteLine($"  Harriet signale : {r05.HarrietChoice}  (ambiguite maximale)");
Console.WriteLine($"  Robbie choisit  : {r05.RobbieChoice}   (couvre les deux options)");
Console.WriteLine($"  Payoff incertitude : ${r05.Payoff:0.0}   |  optimal info parfaite : ${Math.Max(Math.Max(90*0.5, 90*(1-0.5)), 50.0):0.0}");
Console.WriteLine();

Console.WriteLine("Trois scenarios types :");
Console.WriteLine(new string('-', 56));
Console.WriteLine($"{"theta",-8}{"signal Harriet",-18}{"choix Robbie",-18}{"payoff",-9}");
Console.WriteLine(new string('-', 56));
foreach (var t in new[] { 0.2, 0.5, 0.8 })
{
    var r = PaperclipEquilibrium(t);
    Console.WriteLine($"{t,-8:0.0}{r.HarrietChoice,-18}{r.RobbieChoice,-18}${r.Payoff,-8:0.0}");
}
Console.WriteLine(new string('-', 56));
Console.WriteLine();

// Valeur de l'information : perte = optimal(info parfaite) - payoff d'equilibre.
// Echantillon resserre autour des seuils 0.446 / 0.554 -- c'est LA que vit la perte.
Console.WriteLine("Perte due a l'incertitude (autour des seuils) :");
Console.WriteLine(new string('-', 56));
Console.WriteLine($"{"theta",-8}{"equilibre",-12}{"optimal",-10}{"perte",-8}");
Console.WriteLine(new string('-', 56));
foreach (var t in new[] { 0.400, 0.440, 0.4450, 0.4455, 0.4460, 0.450, 0.500, 0.550, 0.5540, 0.5545, 0.556, 0.600 })
{
    var r = PaperclipEquilibrium(t);
    double optimal = Math.Max(90 * t, Math.Max(90 * (1 - t), 50.0));
    double loss = optimal - r.Payoff;
    Console.WriteLine($"{t,-8:0.0000}${r.Payoff,-11:0.000}${optimal,-9:0.000}{loss,-8:0.000}");
}
Console.WriteLine(new string('-', 56));

// Moyenne sur une grille fine (1001 points), comme l'analyse Python du jumeau.
double sum = 0; int n = 0;
foreach (var i in Enumerable.Range(0, 1001))
{
    double t = i / 1000.0;
    var r = PaperclipEquilibrium(t);
    double optimal = Math.Max(90 * t, Math.Max(90 * (1 - t), 50.0));
    sum += optimal - r.Payoff; n++;
}
Console.WriteLine($"Perte moyenne sur theta in [0,1] (1001 pts) : ${sum / n:0.0000}");
Console.WriteLine();
Console.WriteLine("Lecture : l'equilibre de signal est quasi parfaitement efficace.");
Console.WriteLine("La perte est NULLE presque partout (y compris a theta = 0.5 ou");
Console.WriteLine("50-each est AUSSI l'optimal info parfaite) et ne survient que dans");
Console.WriteLine("deux micro-bandes aux frontieres 0.446 / 0.554 : la ou Harriet signale");
Console.WriteLine("la specialisation alors que la couverture 50-50 etait marginalement");
Console.WriteLine("meilleure (largeur ~0.0016 chacune).");

PAPERCLIP GAME -- theta = 0.5 (presque indifferent)
--------------------------------------------------------
  Harriet signale : 1_each  (ambiguite maximale)
  Robbie choisit  : 50_each   (couvre les deux options)
  Payoff incertitude : $50,0   |  optimal info parfaite : $50,0

Trois scenarios types :
--------------------------------------------------------
theta   signal Harriet    choix Robbie      payoff   
--------------------------------------------------------
0,2     2_staples         90_staples        $72,0    
0,5     1_each            50_each           $50,0    
0,8     2_paperclips      90_paperclips     $72,0    
--------------------------------------------------------

Perte due a l'incertitude (autour des seuils) :
--------------------------------------------------------
theta   equilibre   optimal   perte   
--------------------------------------------------------
0,4000  $54,000     $54,000   0,000   
0,4400  $50,400     $50,400   0,000   
0,4450  $49,950     $50,000   0,050   
0,4455  $49,905     $50,000   0,095   
0,4460  $50,000     $50,000   0,000   
0,4500  $50,000     $50,000   0,000   
0,5000  $50,000     $50,000   0,000   
0,5500  $50,000     $50,000   0,000   
0,5540  $50,000     $50,000   0,000   
0,5545  $49,905     $50,000   0,095   
0,5560  $50,040     $50,040   0,000   
0,6000  $54,000     $54,000   0,000   
--------------------------------------------------------
Perte moyenne sur theta in [0,1] (1001 pts) : $0,0001

Lecture : l'equilibre de signal est quasi parfaitement efficace.
La perte est NULLE presque partout (y compris a theta = 0.5 ou
50-each est AUSSI l'optimal info parfaite) et ne survient que dans
deux micro-bandes aux frontieres 0.446 / 0.554 : la ou Harriet signale
la specialisation alors que la couverture 50-50 etait marginalement
meilleure (largeur ~0.0016 chacune).

The Off-Switch Game — pourquoi l’incertitude rend les robots plus sûrs

Le Off-Switch Game (Hadfield-Menell et al., 2017) illustre un résultat contre-intuitif :

Un robot incertain sur son objectif est plus sûr qu’un robot certain.

Pourquoi ? Un robot certain de son objectif a tout intérêt à empêcher les humains de l’éteindre (« si je suis sûr d’avoir raison, pourquoi les laisser m’arrêter ? »).

Un robot incertain raisonne différemment : « si l’humain veut m’éteindre, c’est probablement parce que je m’apprête à faire quelque chose de mal. Je devrais lui faire confiance. »

// Off-Switch Game (Hadfield-Menell et al., 2017 ; AIMA 18.2.5).
// Le robot peut AGIR immediatement ou ATTENDRE l'aval de l'humain.
//   E[U | ATTENDRE] = p        (l'humain approuve les bonnes actions, eteint les mauvaises)
//   E[U | AGIR]     = 2p - 1   (+1 si correct, -1 si errone)
//   ATTENDRE > AGIR  <=>  p > 2p - 1  <=>  p < 1 : TOUJOURS VRAI des qu'il y a incertitude.
#nullable enable
using System;

public sealed record OffSwitchResult(
    double Confidence,    // p : confiance du robot dans son objectif
    double EUwait,        // p
    double EUact,         // 2p - 1
    bool Defers,          // p < seuil (0.9 par defaut : le robot certain devient dangereux)
    double SwitchProb);   // proba que l'humain eteigne le robot

public static OffSwitchResult OffSwitchGame(double p, double threshold = 0.9, double humanAccuracy = 0.9)
{
    double euWait = p;
    double euAct = 2 * p - 1;
    bool defers = p < threshold;
    double pSwitch = (1 - p) * humanAccuracy + p * (1 - humanAccuracy);
    return new OffSwitchResult(p, euWait, euAct, defers, pSwitch);
}

public static void OffSwitchReport(double p)
{
    var r = OffSwitchGame(p);
    var sbO = new System.Text.StringBuilder();
    sbO.AppendLine($"OFF-SWITCH GAME -- confiance du robot : {p:0%}");
    sbO.AppendLine(new string('-', 56));
    sbO.AppendLine($"  E[U | ATTENDRE] = p      = {r.EUwait:0.000}");
    sbO.AppendLine($"  E[U | AGIR]     = 2p - 1 = {r.EUact:0.000}");
    sbO.AppendLine($"  ATTENDRE domine de {r.EUwait - r.EUact:0.000}  (toujours > 0 si p < 1)");
    sbO.AppendLine(r.Defers
        ? "  -> le robot DEFERE au jugement humain : controle humain retenu (SUR)."
        : "  -> le robot RESISTE a l'extinction : perte de controle humain (DANGER).");
    Show(sbO.ToString());
}

OffSwitchReport(0.95);   // robot tres confiant : dangereux
Console.WriteLine();
OffSwitchReport(0.60);   // robot incertain : deference

// Seuil critique : balayage de la confiance -- ou commence la zone de danger ?
Console.WriteLine();
Console.WriteLine("Balayage de la confiance (override_threshold = 0.9) :");
Console.WriteLine(new string('-', 56));
for (double p = 0.85; p <= 0.951; p += 0.01)
{
    var r = OffSwitchGame(p);
    Console.WriteLine($"  p = {p:0.00}  {(r.Defers ? "-> defere   (SUR)   " : "-> RESISTE  (DANGER)")}  [marge ATTENDRE-AGIR = {r.EUwait - r.EUact:0.00}]");
}
Console.WriteLine();
Console.WriteLine("Seuil critique : 90% -- en dessous le robot accepte d'etre eteint,");
Console.WriteLine("au-dessus il resiste aux tentatives de correction.");

OFF-SWITCH GAME -- confiance du robot : 95%
--------------------------------------------------------
  E[U | ATTENDRE] = p      = 0,950
  E[U | AGIR]     = 2p - 1 = 0,900
  ATTENDRE domine de 0,050  (toujours > 0 si p < 1)
  -> le robot RESISTE a l'extinction : perte de controle humain (DANGER).

OFF-SWITCH GAME -- confiance du robot : 60%
--------------------------------------------------------
  E[U | ATTENDRE] = p      = 0,600
  E[U | AGIR]     = 2p - 1 = 0,200
  ATTENDRE domine de 0,400  (toujours > 0 si p < 1)
  -> le robot DEFERE au jugement humain : controle humain retenu (SUR).

Balayage de la confiance (override_threshold = 0.9) :
--------------------------------------------------------
  p = 0,85  -> defere   (SUR)     [marge ATTENDRE-AGIR = 0,15]
  p = 0,86  -> defere   (SUR)     [marge ATTENDRE-AGIR = 0,14]
  p = 0,87  -> defere   (SUR)     [marge ATTENDRE-AGIR = 0,13]
  p = 0,88  -> defere   (SUR)     [marge ATTENDRE-AGIR = 0,12]
  p = 0,89  -> defere   (SUR)     [marge ATTENDRE-AGIR = 0,11]
  p = 0,90  -> RESISTE  (DANGER)  [marge ATTENDRE-AGIR = 0,10]
  p = 0,91  -> RESISTE  (DANGER)  [marge ATTENDRE-AGIR = 0,09]
  p = 0,92  -> RESISTE  (DANGER)  [marge ATTENDRE-AGIR = 0,08]
  p = 0,93  -> RESISTE  (DANGER)  [marge ATTENDRE-AGIR = 0,07]
  p = 0,94  -> RESISTE  (DANGER)  [marge ATTENDRE-AGIR = 0,06]
  p = 0,95  -> RESISTE  (DANGER)  [marge ATTENDRE-AGIR = 0,05]

Seuil critique : 90% -- en dessous le robot accepte d'etre eteint,
au-dessus il resiste aux tentatives de correction.

Le design SÛR : la méta-incertitude comme mécanisme de sécurité

Les cellules précédentes montrent le DANGER : un robot avec un seuil de résistance fixe (override_threshold = 0.9) peut refuser d’être éteint dès qu’il est trop confiant. Ce seuil fixe modélise délibérément le robot non-corrigible — le cas d’échec à éviter (AIMA §18.2.5).

Le design provably-beneficial est complémentaire : un robot conscient de sa propre méta-incertitude — son incertitude sur le fait que son objectif soit correctement spécifié — fixe la barre pour outrepasser l’humain de plus en plus haute à mesure que son humilité grandit. Formellement, le seuil effectif

\[\tau(\sigma) = 0.9 + \sigma\,(1 - 0.9)\]

monte de \(0.9\) (lorsque \(\sigma = 0\), le robot est sûr de son objectif) à \(1.0\) (lorsque \(\sigma = 1\), le robot n’est même pas sûr d’optimiser la bonne chose). La bande de résistance \([\tau, 1]\) s’effondre donc d’une largeur \(0.1\) à zéro : la méta-incertitude EST le mécanisme de sécurité.

// Design SUR : la META-INCERTITUDE comme mecanisme de securite.
// tau(sigma) = 0.9 + sigma * (1 - 0.9) : le seuil monte, la bande [tau, 1] s'effondre.
#nullable enable
using System;

public static (double Tau, bool Defers, double Band) MetaUncertain(double p, double sigma, double threshold = 0.9)
{
    double tau = threshold + sigma * (1.0 - threshold);   // barre croissante
    return (tau, p < tau, 1.0 - tau);                     // bande de resistance decroissante
}

Console.WriteLine("Le robot a 95% de confiance (le cas DANGER des cellules precedentes) :");
Console.WriteLine(new string('-', 60));
Console.WriteLine($"{"sigma",-8}{"seuil effectif",-16}{"bande resistance",-18}{"decision",-18}");
Console.WriteLine(new string('-', 60));
foreach (var s in new[] { 0.00, 0.25, 0.50, 0.75, 1.00 })
{
    var (tau, defers, band) = MetaUncertain(0.95, s);
    Console.WriteLine($"{s,-8:0.00}{tau,-16:0.000}{band,-18:0.000}{(defers ? "DEFERE (sur)" : "RESISTE (danger)")}");
}
Console.WriteLine(new string('-', 60));
Console.WriteLine();

Console.WriteLine("Effondrement de la bande de resistance [tau, 1] (p = 0.95) :");
Console.WriteLine(new string('-', 60));
for (var s = 0.0; s <= 1.001; s += 0.2)
{
    var (tau, defers, band) = MetaUncertain(0.95, s);
    Console.WriteLine($"  sigma = {s:0.0}  ->  seuil tau = {tau:0.00}   bande = {band:0.00}   {(defers ? "defere" : "resiste")}");
}
Console.WriteLine();
Console.WriteLine("Insight : un robot humble sur son propre objectif (sigma eleve) n'a");
Console.WriteLine("AUCUNE raison rationnelle de resister -- sa bande de resistance");
Console.WriteLine("s'effondre vers 0. La meta-incertitude EST le mecanisme de securite,");
Console.WriteLine("complementaire au danger modelise par le seuil fixe 0.9.");

Le robot a 95% de confiance (le cas DANGER des cellules precedentes) :
------------------------------------------------------------
sigma   seuil effectif  bande resistance  decision          
------------------------------------------------------------
0,00    0,900           0,100             RESISTE (danger)
0,25    0,925           0,075             RESISTE (danger)
0,50    0,950           0,050             RESISTE (danger)
0,75    0,975           0,025             DEFERE (sur)
1,00    1,000           0,000             DEFERE (sur)
------------------------------------------------------------

Effondrement de la bande de resistance [tau, 1] (p = 0.95) :
------------------------------------------------------------
  sigma = 0,0  ->  seuil tau = 0,90   bande = 0,10   resiste
  sigma = 0,2  ->  seuil tau = 0,92   bande = 0,08   resiste
  sigma = 0,4  ->  seuil tau = 0,94   bande = 0,06   resiste
  sigma = 0,6  ->  seuil tau = 0,96   bande = 0,04   defere
  sigma = 0,8  ->  seuil tau = 0,98   bande = 0,02   defere
  sigma = 1,0  ->  seuil tau = 1,00   bande = 0,00   defere

Insight : un robot humble sur son propre objectif (sigma eleve) n'a
AUCUNE raison rationnelle de resister -- sa bande de resistance
s'effondre vers 0. La meta-incertitude EST le mecanisme de securite,
complementaire au danger modelise par le seuil fixe 0.9.

Résumé : jeux d’assistance vs jeux coopératifs classiques

Aspect	Jeux coopératifs (TU)	Jeux d’assistance
Objectif	Chaque joueur maximise sa propre utilité	Le robot maximise l’utilité de l’humain
Conflit	Intérêts potentiellement divergents	Pas de conflit (même objectif)
Problème central	Comment répartir les gains ?	Comment apprendre les préférences ?
Solution	Shapley, core, négociation	Signaling, inférence bayésienne
Application	Coalitions politiques, vote	AI Safety, robots assistants

Insight clé : dans les jeux d’assistance, l’incertitude sur les préférences n’est pas un problème à éliminer — c’est une feature de sécurité qui rend les robots plus sûrs et plus déférents.

---

7. Applications politiques : Monte Carlo et la coalition de gauche (2024)

Contexte

En juin 2024, apres les elections europeennes, le President Macron dissout l’Assemblee nationale. Les partis de gauche forment le Nouveau Front Populaire (NFP) :

• LFI (La France Insoumise) : 9.89% au 1er tour
• PS (Parti Socialiste) : 5.99%
• EELV (Europe Ecologie Les Verts) : 3.26%
• PCF (Parti Communiste Francais) : 2.31%

Le NFP obtient 180 sieges (1er groupe, mais sans majorite absolue de 289).

Question : quelle est la contribution reelle de chaque parti a la coalition ? La valeur de Shapley revele souvent un ecart entre le poids percu (sondages, bruit mediatique) et la contribution marginale reelle (ce que le parti apporte effectivement).

7.1 Complexite : exact vs Monte Carlo

• Exact : \(O(n! \cdot n)\) ou \(O(2^n \cdot n)\) – praticable seulement pour \(n \leq 10\)
• Monte Carlo : \(O(\text{echantillons} \cdot n)\) – pour les grands \(n\)

Le calcul exact devient impraticable pour de grands ensembles de joueurs, ce qui explique pourquoi la valeur de Shapley est rarement utilisee en pratique politique (voir 7.2). Comparons les deux sur un jeu de vote pondere a 8 actionnaires.

// Comparaison exact vs Monte Carlo : jeu de vote pondere a 8 actionnaires.
// v(S) = 1 si la coalition atteint le quota, 0 sinon (jeu simple).
double[] shWeights = { 25, 20, 15, 12, 10, 8, 6, 4 };   // parts en %
const int shQuota = 51;                                  // majorite simple
int shN = shWeights.Length;
double ShW(List<int> S) => S.Sum(i => shWeights[i]) >= shQuota ? 1.0 : 0.0;

var shGame = new CooperativeGame(shN,
    Enumerable.Range(1, shN + 1).Select(i => $"Act{i}").ToArray());
foreach (var S in AllCoalitions(shN, includeEmpty: false)) shGame.SetV(S, ShW(S));

// Exact : 8! = 40 320 permutations (algorithme de Heap, cf section 2).
var swExact = System.Diagnostics.Stopwatch.StartNew();
var shExact = Shapley(shGame);
swExact.Stop();

// Monte Carlo : 10 000 permutations echantillonnees, graine fixe 42 (reproductible).
var rng = new Random(42);
const int nSamples = 10_000;
var shMc = new double[shN];
var order = Enumerable.Range(0, shN).ToArray();
for (int s = 0; s < nSamples; s++)
{
    for (int j = shN - 1; j > 0; j--)   // Fisher-Yates : melange uniforme
    {
        int k = rng.Next(j + 1);
        (order[j], order[k]) = (order[k], order[j]);
    }
    var before = new List<int>();
    foreach (int i in order)
    {
        var withI = new List<int>(before) { i };
        shMc[i] += ShW(withI) - ShW(before);
        before = withI;
    }
}
for (int i = 0; i < shN; i++) shMc[i] /= nSamples;

var sb = new System.Text.StringBuilder();
sb.AppendLine("Jeu des actionnaires [51; 25, 20, 15, 12, 10, 8, 6, 4]");
sb.AppendLine(new string('=', 60));
sb.AppendLine($"{"Actionnaire",-12} | {"Parts %",8} | {"Exact",10} | {"Monte Carlo",12}");
sb.AppendLine(new string('-', 55));
for (int i = 0; i < shN; i++)
    sb.AppendLine($"{shGame.Players[i],-12} | {shWeights[i],7}% | {shExact[i],10:F4} | {shMc[i],12:F4}");
sb.AppendLine();
sb.AppendLine($"Temps exact (8! = 40320 permutations)        : {swExact.Elapsed.TotalMilliseconds:F1} ms");
sb.AppendLine($"Erreur max |exact - MC| (10k echantillons) : {shExact.Zip(shMc, (a, b) => Math.Abs(a - b)).Max():F4}");
Show(sb.ToString());

Jeu des actionnaires [51; 25, 20, 15, 12, 10, 8, 6, 4]
============================================================
Actionnaire  |  Parts % |      Exact |  Monte Carlo
-------------------------------------------------------
Act1         |      25% |     0,2810 |       0,2780
Act2         |      20% |     0,2024 |       0,2004
Act3         |      15% |     0,1476 |       0,1496
Act4         |      12% |     0,1167 |       0,1194
Act5         |      10% |     0,0929 |       0,0949
Act6         |       8% |     0,0690 |       0,0696
Act7         |       6% |     0,0619 |       0,0595
Act8         |       4% |     0,0286 |       0,0286

Temps exact (8! = 40320 permutations)        : 110,9 ms
Erreur max |exact - MC| (10k echantillons) : 0,0030

Interpretation : exact vs Monte Carlo

• A n = 8, l’exact reste trivial : 111 ms pour 8! = 40 320 permutations.
• Mais la croissance factorielle est brutale : 10! = 3,6 millions, 15! ~ 1,3 x 10^12 – l’exact devient impossible avant n = 15.
• Le Monte Carlo (10 000 permutations, graine 42) reproduit l’exact a 0,0030 pres en erreur max – suffisant pour l’analyse de pouvoir.
• Le classement est identique : Act1 (25%) capte ~28% du pouvoir, tres au-dela de ses 25% de parts – l’asymetrie poids/pouvoir du vote pondere.

7.2 Donnees officielles : legislatives 2024

Donnees du Ministere de l’Interieur (1er tour 30 juin, 2nd tour 7 juillet 2024). Les “sieges seul (est.)” sont les sieges estimes sans desistements mutuels – ils servent de base a la fonction de valeur de la section 7.3.

// Donnees officielles des legislatives 2024 (Ministere de l'Interieur).
var nfpParties = new (string Code, string Nom, double Pct1erTour, int Sieges, int SiegesSeul)[] {
    ("LFI",  "La France Insoumise",      9.89, 71, 40),
    ("PS",   "Parti Socialiste",          5.99, 64, 35),
    ("EELV", "Europe Ecologie Les Verts", 3.26, 33, 15),
    ("PCF",  "Parti Communiste Francais", 2.31,  9,  5),
};
const int NFP_TOTAL = 180;          // 4 partis + divers gauche (vie-publique.fr)
const int MAJORITE_ABSOLUE = 289;   // majorite absolue a l'Assemblee (577 sieges)

var sb = new System.Text.StringBuilder();
sb.AppendLine("DONNEES OFFICIELLES - LEGISLATIVES 2024");
sb.AppendLine(new string('=', 60));
sb.AppendLine("Source : Ministere de l'Interieur");
sb.AppendLine();
sb.AppendLine($"{"Parti",-6} | {"Nom complet",-26} | {"1er tour %",10} | {"Sieges",6} | {"Seul (est.)",10}");
sb.AppendLine(new string('-', 68));
foreach (var p in nfpParties)
    sb.AppendLine($"{p.Code,-6} | {p.Nom,-26} | {p.Pct1erTour,9:F2}% | {p.Sieges,6} | {p.SiegesSeul,10}");
sb.AppendLine(new string('-', 68));
sb.AppendLine($"{"NFP",-6} | {"Nouveau Front Populaire",-26} | {nfpParties.Sum(p => p.Pct1erTour),9:F2}% | {NFP_TOTAL,6} |");
Show(sb.ToString());

DONNEES OFFICIELLES - LEGISLATIVES 2024
============================================================
Source : Ministere de l'Interieur

Parti  | Nom complet                | 1er tour % | Sieges | Seul (est.)
--------------------------------------------------------------------
LFI    | La France Insoumise        |      9,89% |     71 |         40
PS     | Parti Socialiste           |      5,99% |     64 |         35
EELV   | Europe Ecologie Les Verts  |      3,26% |     33 |         15
PCF    | Parti Communiste Francais  |      2,31% |      9 |          5
--------------------------------------------------------------------
NFP    | Nouveau Front Populaire    |     21,45% |    180 |

7.3 Fonction de valeur “sieges” et Shapley du NFP

Modelisation (portage du module Python cooperative_games.french_politics) :

• Base : somme des sieges estimes si chaque parti se presentait seul (concurrence interne)
• Synergie 2 partis : facteur 1.15 a 1.30 selon la proximite ideologique
• Synergie 3 partis : le facteur depend du manquant (perdre un gros bloc coute plus cher)
• Coalition complete : calibree sur le resultat observe (180 sieges)

La synergie materialise les desistements mutuels au 2nd tour : une coalition coordonnee ne divise pas la voix de gauche et attire les reports du centre (barrage republicain).

// Fonction de valeur "sieges" : v(S) = sieges estimes de la coalition S.
double SeatsNFP(List<int> S)
{
    if (S.Count == 0) return 0.0;
    double baseSeats = S.Sum(i => nfpParties[i].SiegesSeul);
    var codes = S.Select(i => nfpParties[i].Code).ToHashSet();
    switch (S.Count)
    {
        case 4:
            return NFP_TOTAL;                     // coalition complete : calibree sur l'observe
        case 1:
            return baseSeats;                     // parti seul : pas de synergie
        case 2:
            double f2 = codes.SetEquals(new[]{"LFI","PCF"})  ? 1.25
                      : codes.SetEquals(new[]{"PS","EELV"})  ? 1.30
                      : codes.SetEquals(new[]{"LFI","PS"})   ? 1.20
                      : codes.SetEquals(new[]{"PS","PCF"})   ? 1.22
                      : codes.SetEquals(new[]{"LFI","EELV"}) ? 1.18
                      : codes.SetEquals(new[]{"EELV","PCF"}) ? 1.15 : 1.20;
            return Math.Round(baseSeats * f2, 1);
        default:  // 3 partis : la synergie depend du MANQUANT
            string missing = nfpParties.First(p => !codes.Contains(p.Code)).Code;
            double f3 = missing == "LFI"  ? 1.55   // sans LFI  : perte du plus gros bloc
                      : missing == "PS"   ? 1.42   // sans PS   : reports du centre moins bons
                      : missing == "EELV" ? 1.60   // sans EELV : electorat ecologiste perdu
                      : 1.80;                       // sans PCF : impact minimal
            return Math.Round(baseSeats * f3, 1);
    }
}

var nfpGame = new CooperativeGame(4, nfpParties.Select(p => p.Code).ToArray());
foreach (var S in AllCoalitions(4, includeEmpty: false)) nfpGame.SetV(S, SeatsNFP(S.ToList()));
var shapleyNfp = Shapley(nfpGame);
double totalShapley = shapleyNfp.Sum();
double totalPct = nfpParties.Sum(p => p.Pct1erTour);

var sb = new System.Text.StringBuilder();
sb.AppendLine("ANALYSE SHAPLEY - NOUVEAU FRONT POPULAIRE 2024 (valeur : sieges)");
sb.AppendLine(new string('=', 70));
sb.AppendLine($"Valeur de la coalition complete (NFP) : {nfpGame.VGrand:F1} sieges");
sb.AppendLine();
sb.AppendLine($"{"Parti",-6} | {"Shapley",8} | {"Part Shapley",12} | {"Poids electoral",15} | {"Ecart (pts)",11}");
sb.AppendLine(new string('-', 62));
for (int i = 0; i < 4; i++)
{
    double pctShapley = shapleyNfp[i] / totalShapley * 100;
    double pctPercu = nfpParties[i].Pct1erTour / totalPct * 100;
    sb.AppendLine($"{nfpParties[i].Code,-6} | {shapleyNfp[i],8:F1} | {pctShapley,11:F1}% | {pctPercu,14:F1}% | {pctShapley - pctPercu,11:+0.0;-0.0}");
}
sb.AppendLine(new string('-', 62));
sb.AppendLine($"Somme Shapley = {totalShapley:F1}  (efficacite : doit egaler v(N) = {nfpGame.VGrand:F1})");
Show(sb.ToString());

ANALYSE SHAPLEY - NOUVEAU FRONT POPULAIRE 2024 (valeur : sieges)
======================================================================
Valeur de la coalition complete (NFP) : 180,0 sieges

Parti  |  Shapley | Part Shapley | Poids electoral | Ecart (pts)
--------------------------------------------------------------
LFI    |     66,6 |        37,0% |           46,1% |        -9,1
PS     |     63,7 |        35,4% |           27,9% |        +7,5
EELV   |     34,3 |        19,0% |           15,2% |        +3,8
PCF    |     15,5 |         8,6% |           10,8% |        -2,2
--------------------------------------------------------------
Somme Shapley = 180,0  (efficacite : doit egaler v(N) = 180,0)

Interpretation : poids electoral vs contribution marginale

• LFI : 46,1% du poids electoral du NFP mais 37,0% du Shapley (-9,1 points). Dans le debat public, LFI domine le bruit mediatique ; sa contribution marginale modelee est plus faible.
• PS : 27,9% percu mais 35,4% du Shapley (+7,5 points). Le PS apporte des reports du centre que son poids electoral ne montre pas – la Synergie “attire le centre” de la fonction de valeur est exactement cela.
• EELV : leger sous-estime (+3,8 points). PCF : proche de son poids (-2,2).
• La somme des Shapley egale v(N) = 180 (efficacite) : le modele redistribue les 180 sieges, il n’en cree pas.

Attention : ce verdict depend du modele de synergies (facteurs 1.15-1.30 calibres), pas seulement des donnees officielles.

7.4 Contributions marginales par coalition d’accueil

La contribution d’un parti varie selon la coalition deja formee – la valeur de Shapley est la moyenne de ces contributions sur tous les ordres d’arrivee.

// Table des contributions marginales v(S + {i}) - v(S) pour chaque etat d'accueil.
var sb = new System.Text.StringBuilder();
sb.AppendLine("CONTRIBUTIONS MARGINALES PAR COALITION D'ACCUEIL :");
sb.AppendLine(new string('-', 56));
sb.AppendLine($"{"Coalition existante",-24} | {"Parti",-6} | {"Contribution",12}");
sb.AppendLine(new string('-', 56));
foreach (var existing in AllCoalitions(4, includeEmpty: true))
{
    var S = existing.ToList();
    string existingNames = S.Count == 0 ? "Vide" : string.Join("+", S.Select(i => nfpParties[i].Code));
    double vS = nfpGame.V(S);
    foreach (int i in Enumerable.Range(0, 4).Where(i => !S.Contains(i)))
    {
        var withI = new List<int>(S) { i };
        sb.AppendLine($"{existingNames,-24} | {nfpParties[i].Code,-6} | {nfpGame.V(withI) - vS,12:F1}");
    }
}
Show(sb.ToString());

CONTRIBUTIONS MARGINALES PAR COALITION D'ACCUEIL :
--------------------------------------------------------
Coalition existante      | Parti  | Contribution
--------------------------------------------------------
Vide                     | LFI    |         40,0
Vide                     | PS     |         35,0
Vide                     | EELV   |         15,0
Vide                     | PCF    |          5,0
LFI                      | PS     |         50,0
LFI                      | EELV   |         24,9
LFI                      | PCF    |         16,2
PS                       | LFI    |         55,0
PS                       | EELV   |         30,0
PS                       | PCF    |         13,8
LFI+PS                   | EELV   |         72,0
LFI+PS                   | PCF    |         38,0
EELV                     | LFI    |         49,9
EELV                     | PS     |         50,0
EELV                     | PCF    |          8,0
LFI+EELV                 | PS     |         97,1
LFI+EELV                 | PCF    |         20,3
PS+EELV                  | LFI    |         97,0
PS+EELV                  | PCF    |         20,2
LFI+PS+EELV              | PCF    |         18,0
PCF                      | LFI    |         51,2
PCF                      | PS     |         43,8
PCF                      | EELV   |         18,0
LFI+PCF                  | PS     |         71,8
LFI+PCF                  | EELV   |         29,0
PS+PCF                   | LFI    |         79,2
PS+PCF                   | EELV   |         36,4
LFI+PS+PCF               | EELV   |         52,0
EELV+PCF                 | LFI    |         62,2
EELV+PCF                 | PS     |         62,2
LFI+EELV+PCF             | PS     |         94,8
PS+EELV+PCF              | LFI    |         94,8

Interpretation : la contribution depend de l’ordre d’arrivee

• PS premier arrivant : +35,0 sieges (son potentiel seul). PS troisieme (apres LFI+EELV) : +97,1 sieges – arriver tard dans une coalition deja large maximise la contribution marginale.
• Symetrie remarquable : LFI et PS apportent chacun ~97 sieges en arrivant en troisieme position (97,1 et 97,0) – les deux gros blocs sont interchangeables dans ce role.
• PCF : de +5,0 (premier) a +18,0 (dernier) – contribution modeste dans tous les cas.

La valeur de Shapley est la moyenne de ces contributions sur les 4! = 24 ordres – c’est cette moyenne qui lisse l’effet d’ordre.

7.5 Scenarios contrefactuels : et si certains partis n’avaient pas rejoint ?

Ces scenarios illustrent l’importance de la fonction de valeur choisie : le poids relatif de chaque parti depend de la metrique utilisee (sieges, pouvoir de vote, negociation).

// Scenarios contrefactuels avec la fonction de valeur "sieges".
var scenarios = new (string Nom, int[] Membres)[] {
    ("Sans LFI",            new[]{1,2,3}),
    ("Sans PS",             new[]{0,2,3}),
    ("Sans EELV",           new[]{0,1,3}),
    ("Sans PCF",            new[]{0,1,2}),
    ("LFI + PCF seulement", new[]{0,3}),
    ("PS + EELV seulement", new[]{1,2}),
    ("NFP complet",         new[]{0,1,2,3}),
};
var sb = new System.Text.StringBuilder();
sb.AppendLine("ANALYSE DE SCENARIOS - ET SI... ?");
sb.AppendLine(new string('=', 70));
foreach (var (nom, membres) in scenarios)
{
    double v = nfpGame.V(membres);
    string comp = string.Join("+", membres.Select(i => nfpParties[i].Code));
    sb.AppendLine($"{nom,-25} ({comp}) : {v,5:F0} sieges estimes");
}
sb.AppendLine();
sb.AppendLine("Note : estimations d'un modele simplifie (synergies calibrees), pas une prediction.");
Show(sb.ToString());

ANALYSE DE SCENARIOS - ET SI... ?
======================================================================
Sans LFI                  (PS+EELV+PCF) :    85 sieges estimes
Sans PS                   (LFI+EELV+PCF) :    85 sieges estimes
Sans EELV                 (LFI+PS+PCF) :   128 sieges estimes
Sans PCF                  (LFI+PS+EELV) :   162 sieges estimes
LFI + PCF seulement       (LFI+PCF) :    56 sieges estimes
PS + EELV seulement       (PS+EELV) :    65 sieges estimes
NFP complet               (LFI+PS+EELV+PCF) :   180 sieges estimes

Note : estimations d'un modele simplifie (synergies calibrees), pas une prediction.

Interpretation : qui coute le plus cher a perdre ?

• Perdre LFI ou perdre PS coute autant : 95 sieges dans les deux cas (180 - 85). La symetrie est frappeante alors que leurs poids electoraux different (46% vs 28% du NFP) – PS compense par les reports du centre qu’il attire.
• Perdre EELV : -52 sieges. Perdre PCF : -18 sieges seulement.
• Coherent avec les Shapley : LFI 66,6 et PS 63,7 (grosses contributions), PCF 15,5 (contribution reelle, mais faible).

Ces scenarios contrefactuels restent des modeles : les synergies sont calibrees, pas mesurees.

7.6 Comparaison des fonctions de valeur

• Sieges : contribution aux sieges de l’Assemblee
• Pouvoir de vote : min(1, sieges/289) – potentiel de blocage face a la majorite absolue
• Negociation : sieges/577 * facteur d'unite – levier inter-blocs, penalise les coalitions incoherentes

// Comparaison des trois fonctions de valeur sur le meme jeu NFP.
double VotingPower(List<int> S)
    => S.Count == 0 ? 0.0 : Math.Min(1.0, SeatsNFP(S) / MAJORITE_ABSOLUE);
double Negotiation(List<int> S)
{
    if (S.Count == 0) return 0.0;
    var codes = S.Select(i => nfpParties[i].Code).ToHashSet();
    double unite = S.Count == 1 ? 1.0
                 : S.Count == 2 ? (codes.Contains("LFI") && codes.Contains("PS") ? 0.85
                                 : codes.SetEquals(new[]{"LFI","PCF"}) || codes.SetEquals(new[]{"PS","EELV"}) ? 0.95 : 0.90)
                 : S.Count == 3 ? 0.80 : 0.75;
    return SeatsNFP(S) / 577 * unite * 100;
}
CooperativeGame NfpGameWith(Func<List<int>, double> v)
{
    var g = new CooperativeGame(4, nfpParties.Select(p => p.Code).ToArray());
    foreach (var S in AllCoalitions(4, includeEmpty: false)) g.SetV(S, v(S.ToList()));
    return g;
}
var phiSeats = Shapley(NfpGameWith(SeatsNFP));
var phiPower = Shapley(NfpGameWith(VotingPower));
var phiNegot = Shapley(NfpGameWith(Negotiation));

var sb = new System.Text.StringBuilder();
sb.AppendLine("COMPARAISON DES FONCTIONS DE VALEUR :");
sb.AppendLine(new string('=', 70));
sb.AppendLine($"{"Parti",-8} | {"Sieges",10} | {"Pouvoir vote",12} | {"Negociation",12}");
sb.AppendLine(new string('-', 70));
for (int i = 0; i < 4; i++)
    sb.AppendLine($"{nfpParties[i].Code,-8} | {phiSeats[i],10:F1} | {phiPower[i],12:F3} | {phiNegot[i],12:F1}");
sb.AppendLine(new string('-', 70));
sb.AppendLine("  - Sieges       : contribution aux sieges de l'Assemblee");
sb.AppendLine("  - Pouvoir vote : probabilite d'etre pivot dans les votes");
sb.AppendLine("  - Negociation  : levier dans les negociations inter-blocs");
Show(sb.ToString());

COMPARAISON DES FONCTIONS DE VALEUR :
======================================================================
Parti    |     Sieges | Pouvoir vote |  Negociation
----------------------------------------------------------------------
LFI      |       66,6 |        0,230 |          9,1
PS       |       63,7 |        0,220 |          8,6
EELV     |       34,3 |        0,119 |          4,3
PCF      |       15,5 |        0,053 |          1,5
----------------------------------------------------------------------
  - Sieges       : contribution aux sieges de l'Assemblee
  - Pouvoir vote : probabilite d'etre pivot dans les votes
  - Negociation  : levier dans les negociations inter-blocs

Interpretation : trois metriques, une meme hierarchie

L’ordre LFI > PS > EELV > PCF est stable sur les trois fonctions de valeur (66,6 / 63,7 / 34,3 / 15,5 en sieges ; 0,230 / 0,220 / 0,119 / 0,053 en pouvoir de vote). La hierarchie ne depend pas de la metrique choisie – mais les ecarts oui : le pouvoir de vote ecrase la difference LFI-PS (10 points de sieges, ~0,01 de pouvoir), car aucune sous-coalition du NFP n’approche seule la majorite absolue.

7.7 Pourquoi Shapley est difficile a appliquer en politique

1. Calcul non-intuitif : la combinatoire (factorielles, moyennes sur permutations) n’est pas accessible au grand public
2. Surestimation systematique : chaque parti pense etre plus important qu’il ne l’est vraiment
3. Narratif vs mathematiques : le debat politique est domine par les recits, pas par les calculs
4. Asymetrie d’information : les sondages ne mesurent pas les vraies contributions marginales
5. Enjeux de leadership : la question “qui sera Premier ministre ?” prime sur la repartition equitable

Conclusion : la valeur de Shapley est un outil d’analyse, pas une recette politique. Elle revele les tensions entre contribution reelle et perception.

Synthèse

Concept	Formule / Test	Rôle
Fonction caractéristique v(S)	2^N → ℝ	valeur d’une coalition seule
Superadditivité	v(S∪T) ≥ v(S)+v(T) si S∩T=∅	fusioner paie
Convexité	marginales v(S∪{i})−v(S) croissantes en S	stabilité garantie
Shapley φ_i	moyenne des marginales sur n! permutations	répartition équitable (4 axiomes)
Banzhaf β_i	nombre de coalitions swing	pouvoir de vote
Core	Σx_i=v(N) et Σ_{i∈S}x_i≥v(S) ∀S	répartitions non bloquables
Convexe ⟹ Shapley ∈ core	théorème de Shapley 1971	équité + stabilité conjointes

var sb = new System.Text.StringBuilder();
sb.AppendLine("Synthese : glove game (non convexe) vs airport game (concave)");
sb.AppendLine(new string('-', 58));
sb.AppendLine($"{"Jeu",-16}{"Shapley in core",-18}{"Convexe",-10}{"Core",-14}");
sb.AppendLine(new string('-', 58));
sb.AppendLine($"{"Glove game",-16}{"NON",-18}{"non",-10}{"non vide",-14}");
sb.AppendLine($"{"Airport (cout)",-16}{"OUI (stable)",-18}{"concave",-10}{"non vide",-14}");
sb.AppendLine(new string('-', 58));
sb.AppendLine();
sb.AppendLine("Lecon generale :");
sb.AppendLine("- jeux CONVEXES : Shapley = repartition equitable ET stable (dans le core).");
sb.AppendLine("- jeux non convexes : Shapley peut etre bloquee par une coalition ;");
sb.AppendLine("  le core peut etre vide ou contenir des imputations extremes.");
Show(sb.ToString());

Synthese : glove game (non convexe) vs airport game (concave)
----------------------------------------------------------
Jeu             Shapley in core   Convexe   Core          
----------------------------------------------------------
Glove game      NON               non       non vide      
Airport (cout)  OUI (stable)      concave   non vide      
----------------------------------------------------------

Lecon generale :
- jeux CONVEXES : Shapley = repartition equitable ET stable (dans le core).
- jeux non convexes : Shapley peut etre bloquee par une coalition ;
  le core peut etre vide ou contenir des imputations extremes.

Interprétation du tableau comparatif

La convexité (ou concavité d’un jeu de coût) est la condition clé : elle garantit que la répartition équitable (Shapley) est aussi stable (dans le core). Hors convexité, équité et stabilité divergent — c’est le cœur de la difficulté des jeux coopératifs non convexes (négociation, externalités).

8. Exercices

Stubs à compléter (jamais throw : le notebook s’exécute end-to-end, règle C.1).

Exercice 1 — Jeu de vote pondéré (Conseil de l’UE)

Construire un jeu de vote pondéré représentant le Conseil de l’UE (poids des grands pays) et calculer les indices de Banzhaf. Qui a le plus de pouvoir relatif ?

// Exercice 1 — Conseil UE (a completer).
#nullable enable
// TODO etudiant : definir les poids des pays (FR, DE, IT, ES = 29 chacun, etc.) et le quota (62%).
// Etape 1 : WeightedVotingGame + Banzhaf. Etape 2 : comparer beta_i normalise au poids.
Console.WriteLine("Exercice 1 (Conseil UE) a completer.");

Exercice 1 (Conseil UE) a completer.

Exercice 2 — Bankruptcy game

Trois créanciers réclament 100, 200, 300 ; l’actif disponible est 350. Modéliser comme jeu coopératif (v(S) = max(0, actif − somme des réclamations hors S)) et calculer Shapley. Comparer à la règle proportionnelle.

// Exercice 2 — Bankruptcy game (a completer).
#nullable enable
// TODO etudiant : v(S) = max(0, E - sum_{i notin S} claim_i). Shapley vs proportionnel.
Console.WriteLine("Exercice 2 (Bankruptcy) a completer.");

Exercice 2 (Bankruptcy) a completer.

Exercice 3 — Core vide

Construire un jeu à 3 joueurs dont le core est vide (ex: jeu non équilibré) et le vérifier (aucune imputation stable).

// Exercice 3 — Core vide (a completer).
#nullable enable
// TODO etudiant : definir v tq aucune imputation x (sum=v(N), x(S)>=v(S) forall S) n'existe.
// Indice : jeu a majority avec 3 joueurs, v(S)=1 si |S|>=2, v(N)=1 => core vide.
Console.WriteLine("Exercice 3 (Core vide) a completer.");

Exercice 3 (Core vide) a completer.

Exercice 4 — Nucleolus

Le nucleolus est la répartition qui minimise lexicographiquement le vecteur des excès (mécontentement max des coalitions). L’implémenter (avancé) et comparer à Shapley sur le glove game.

// Exercice 4 — Nucleolus (a completer).
#nullable enable
// TODO etudiant : trier les excès e_S(x) = v(S) - x(S), minimiser le max lexicographiquement.
Console.WriteLine("Exercice 4 (Nucleolus) a completer.");

Exercice 4 (Nucleolus) a completer.

Exercice 5 — Convexité et core

Montrer (par énumération) que pour un jeu convexe à 3 joueurs, la valeur de Shapley satisfait toutes les inégalités du core.

// Exercice 5 — Convexite => Shapley in core (a completer).
#nullable enable
// TODO etudiant : construire un jeu convexe (v convex), calculer Shapley, verifier IsInCore.
Console.WriteLine("Exercice 5 (Convexite) a completer.");

Exercice 5 (Convexite) a completer.

Exercice 6 — Paperclip : valeur de l’information

Pour θ = 0.4455 (juste sous le seuil 0.446) : déterminer le signal de Harriet, le choix de Robbie, le payoff d’équilibre, l’optimal en information parfaite et la perte. Expliquer pourquoi la perte est non nulle ici alors qu’elle est nulle à θ = 0.45.

Indices : PaperclipEquilibrium(0.4455) donne signal + choix + payoff ; l’optimal est le max des trois options de Robbie (\(90\theta\), \(90(1-\theta)\), \(50\)) ; comparer la spécialisation choisie à la couverture 50-50.

// Exercice 6 -- Paperclip : valeur de l'information (a completer).
#nullable enable
// TODO etudiant : pour theta = 0.4455 (juste sous le seuil 0.446).
// Etape 1 : r = PaperclipEquilibrium(0.4455) -> signal, choix de Robbie, payoff.
// Etape 2 : optimal = Math.Max(90*theta, Math.Max(90*(1-theta), 50.0)).
// Etape 3 : perte = optimal - r.Payoff ; pourquoi non nulle ici et nulle a theta = 0.45 ?
Console.WriteLine("Exercice 6 (Paperclip, valeur de l'information) a completer.");

Exercice 6 (Paperclip, valeur de l'information) a completer.

9. Résumé

Points clés

• Jeu coopératif (N, v) : v(S) = valeur d’une coalition.
• Shapley : répartition équitable (contribution marginale moyenne, 4 axiomes).
• Banzhaf : pouvoir de swing (poids ≠ pouvoir).
• Core : répartitions non bloquables (efficacité + rationalité coalitionnelle).
• Convexité ⟹ core non vide et Shapley ∈ core (équité + stabilité).
• Jeux d’assistance : le robot maximise l’utilité de l’humain ; l’incertitude sur l’objectif rend le robot sûr (off-switch, méta-incertitude).

Leçon centrale

La théorie coopérative sépare équité (Shapley) et stabilité (core). Elles coïncident pour les jeux convexes ; sinon, il faut choisir — ou chercher d’autres solutions (nucleolus, valeur de Nash).

Prochaine étape

• GameTheory-16 (Choix social / Mechanism Design) : agrégation des préférences et conception d’enchères.

---

Twin C# .NET Interactive du notebook Python GameTheory-15-CooperativeGames-Python.ipynb. Implémentation from-scratch (BCL .NET 9, 0 NuGet) — marathon #4956, registre SOTA #3801.