GameTheory-23 — L’algorithme de Kuhn-Munkres : affectation optimale et dualité

Hommage. James R. Munkres, professeur émérite au MIT, s’est éteint le 30 juillet 2026 à 95 ans. Si son nom est familier des générations d’étudiants par son manuel de topologie (Topology, 1975 — le « Munkres » des cours 18.901), il est pour nous le co-éponyme de l’algorithme de Kuhn-Munkres — la méthode hongroise pour le problème d’affectation, dont il a établi en 1957 la première analyse de complexité fortement polynomiale. Ce notebook travaille son théorème.

Écho dans le dépôt. La méthode tourne en production pédagogique dans Sudoku-15 — Solveurs probabilistes (C#) : le solveur v4 (max-product sur facteurs AllDiff d’arité 9) appelle Kuhn-Munkres (Hungarian) pour extraire son affectation à chaque message.

1. Le problème d’affectation

$n$ agents, $n$ tâches, une matrice de coûts $c_{ij}$ (le coût pour que l’agent $i$ fasse la tâche $j$). Une affectation (matching parfait) $\sigma$ est une permutation : chaque agent reçoit exactement une tâche, chaque tâche exactement un agent. Le problème :

\[\min_{\sigma \in S_n} \sum_{i=1}^{n} c_{i,\sigma(i)}\]

L’énumération est hors de question : $|S_n| = n!$ — à $n = 12$ cela dépasse déjà 479 millions de permutations. L’algorithme de Kuhn-Munkres résout le problème en $O(n^3)$.

Fil conducteur du notebook : nous implémentons l’algorithme from scratch (labels, graphe d’égalité, arbres hongrois), le confrontons à la référence SOTA scipy.optimize.linear_sum_assignment, puis nous lisons le résultat par la dualité linéaire — et cette lecture ouvre la porte à la théorie des jeux : le jeu d’affectation de Shapley-Shubik, dont le cœur coïncide exactement avec les solutions duales optimales.

import numpy as np
from math import factorial
from scipy.optimize import linear_sum_assignment

rng = np.random.default_rng(42)

# L'exemple fil rouge : 4 agents, 4 taches (couts positifs, exemple deterministe)
C = np.array([
    [9, 2, 7, 8],
    [6, 4, 3, 7],
    [5, 8, 1, 8],
    [7, 6, 9, 4],
], dtype=float)
n = len(C)
print("Matrice de couts C :")
print(C)
print(f"\nTaille de l'espace de recherche : {n}! = {factorial(n)} permutations")

Matrice de couts C :
[[9. 2. 7. 8.]
 [6. 4. 3. 7.]
 [5. 8. 1. 8.]
 [7. 6. 9. 4.]]

Taille de l'espace de recherche : 4! = 24 permutations

Lecture de l’exemple

La matrice $C$ dit par exemple que l’agent 0 fait la tâche 1 pour 2 (bon marché) mais la tâche 0 pour 9 (cher). Une heuristique gloutonne — prendre à chaque ligne son minimum — donnerait 2 + 3 + 1 + 4 = 10, mais les colonnes 1 et 2 seraient disputées : le glouton ne produit pas une permutation. Le vrai problème est de trouver l’équilibre entre les lignes. Vérifions d’abord par force brute (possible à $n=4$), pour avoir une vérité de référence.

from itertools import permutations
from math import factorial

def valeur_bruit(C, sigma):
    return sum(C[i, sigma[i]] for i in range(len(C)))

# Force brute : toutes les permutations (n=4 seulement !)
brute = min((valeur_bruit(C, list(p)), list(p)) for p in permutations(range(n)))
print(f"Optimum par force brute : {brute[0]:.0f}  (permutation {list(brute[1])})")
print(f"Permutations testees : {factorial(n)}")

Optimum par force brute : 13  (permutation [1, 0, 2, 3])
Permutations testees : 24

2. L’implémentation pédagogique de Kuhn-Munkres

L’algorithme maintient des potentiels duaux (les « labels ») $u_i$ pour les lignes et $v_j$ pour les colonnes, avec la contrainte de réalisabilité duale :

\[u_i + v_j \le c_{ij} \quad \text{pour tout } (i, j)\]

Le graphe d’égalité est le sous-graphe des arêtes saturées : $u_i + v_j = c_{ij}$. Un matching n’utilisant que des arêtes d’égalité et couvrant tout le monde est optimal — c’est le théorème de dualité (le matching est une solution primale réalisable, les potentiels une solution duale réalisable, et ils ont la même valeur : aucun gap).

Tant qu’un matching parfait n’existe pas dans le graphe d’égalité, l’algorithme construit un arbre hongrois (alternant depuis une ligne non appariée) et resserre les labels du montant minimal $\delta$ qui fait apparaître une nouvelle arête d’égalité. C’est ce $\delta$ qui garantit la terminaison et le temps polynomial.

def kuhn_munkres(C):
    """Algorithme de Kuhn-Munkres (methode hongroise), version pedagogique.

    Travaille en ARITHMETIQUE ENTIERS EXACTE (les couts doivent etre entiers) :
    les resserrements successifs de labels accumuleraient en flottants une erreur
    d'arrondi qui casse le test d'egalite u_i + v_j == c_ij -- et avec lui la
    terminaison. Sur entiers, l'egalite est exacte et l'algorithme termine.

    Chaque iteration construit UNE FOIS l'arbre hongrois (BFS depuis la ligne non
    appariee i0) : dec_j[j] memorise la ligne qui a decouvert la colonne j. Si le
    BFS atteint une colonne libre, le chemin augmentant se remonte par dec_j et
    match_row ; sinon, l'arbre fournit le delta de resserrement.

    Retourne (valeur, assignment, u, v) avec u_i + v_j <= c_ij pour tout (i, j).
    """
    C = np.asarray(C, dtype=np.int64)
    n = len(C)
    u = C.min(axis=1).astype(np.int64).copy()   # dual realisable : u_i + 0 <= c_ij
    v = np.zeros(n, dtype=np.int64)

    match_col = [-1] * n   # colonne j -> ligne appariee
    match_row = [-1] * n   # ligne i -> colonne appariee

    def arbre_hongrois(i0):
        """BFS alternant depuis i0 dans le graphe d'egalite.
        Retourne (dec_j, lignes, colonnes, j_libre) -- j_libre = colonne libre
        atteinte (None si l'arbre est bloque)."""
        dec_j = {}                       # colonne -> ligne qui l'a decouverte
        lignes, colonnes = {i0}, set()
        file = [i0]
        while file:
            i = file.pop(0)
            for j in range(n):
                if j in colonnes or u[i] + v[j] != C[i, j]:
                    continue
                dec_j[j] = i
                colonnes.add(j)
                if match_col[j] == -1:
                    return dec_j, lignes, colonnes, j
                lignes.add(match_col[j])
                file.append(match_col[j])
        return dec_j, lignes, colonnes, None

    for i0 in range(n):
        while match_row[i0] == -1:
            dec_j, lignes, colonnes, j_libre = arbre_hongrois(i0)
            if j_libre is not None:
                # Remonter le chemin augmentant : colonne libre <- dec_j -> ligne
                # appariee <- match_row -> colonne dec_j[...] -> ... jusqu'a i0.
                j = j_libre
                i = dec_j[j]
                while True:
                    j_suiv = match_row[i]          # ancienne colonne de la ligne i
                    match_col[j] = i
                    match_row[i] = j
                    if i == i0:
                        break
                    j = j_suiv
                    i = dec_j[j]
            else:
                # Arbre bloque : resserrement par delta, la plus petite marge sur
                # les aretes sortantes (ligne dans l'arbre, colonne hors arbre) --
                # strictement positive par construction de l'arbre.
                hors = [j for j in range(n) if j not in colonnes]
                delta = min(int(C[i, j] - u[i] - v[j]) for i in lignes for j in hors)
                for i in lignes:
                    u[i] += delta
                for j in colonnes:
                    v[j] -= delta
    assert sorted(match_row) == list(range(n)), "pas un matching parfait"
    valeur = int(sum(int(C[i, match_row[i]]) for i in range(n)))
    return valeur, match_row, u, v

val_km, assign_km, u, v = kuhn_munkres(C)
print(f"Kuhn-Munkres from scratch : valeur = {val_km}, affectation = {assign_km}")

Kuhn-Munkres from scratch : valeur = 13, affectation = [1, 0, 2, 3]

# Confrontation a la reference SOTA : scipy.optimize.linear_sum_assignment
rows, cols = linear_sum_assignment(C)
val_sota = C[rows, cols].sum()
print(f"scipy (SOTA)              : valeur = {val_sota:.0f}, affectation = {list(cols)}")
print(f"Coincidence from scratch == SOTA : {val_km == val_sota and assign_km == list(cols)}")

# Verification multi-instances (deterministe, graine fixee) : 50 matrices 6x6
ecarts = []
for k in range(50):
    M = rng.integers(0, 50, size=(6, 6)).astype(float)
    vk, ak, _, _ = kuhn_munkres(M)
    r, c2 = linear_sum_assignment(M)
    ecarts.append(vk - M[r, c2].sum())
print(f"50 instances aleatoires 6x6 : max |KM - scipy| = {max(abs(np.array(ecarts)))}")

scipy (SOTA)              : valeur = 13, affectation = [np.int64(1), np.int64(0), np.int64(2), np.int64(3)]
Coincidence from scratch == SOTA : True
50 instances aleatoires 6x6 : max |KM - scipy| = 0.0

Lecture du résultat

Sur le fil rouge, KM from scratch et SciPy retournent la même valeur (13) et la même affectation [1, 0, 2, 3] — coïncidence exacte. Sur 50 instances aléatoires 6×6 (graine 42, coûts entiers) : max |KM − scipy| = 0.0 — cinquante accords parfaits. L’accord porte sur la valeur ; plusieurs affectations peuvent atteindre 13 sur d’autres instances, ici même la permutation coïncide.

Ce que la confrontation établit

Sur l’exemple fil rouge comme sur 50 instances aléatoires, l’implémentation pédagogique et la référence SOTA de SciPy coïncident exactement — même valeur, même affectation. Ce n’est pas surprenant : linear_sum_assignment implémente une variante jonction-flots de la même idée algorithmique (l’algorithme de Jonker-Volgenant), optimisée en constantes. Le point pédagogique est ailleurs : notre version expose les potentiels duaux $(u, v)$, que la routine SciPy ne retourne pas — et ce sont eux qui portent toute la suite du notebook.

3. La lecture par dualité linéaire

Le problème d’affectation est un programme linéaire (en variables $x_{ij} \in \{0,1\}$, relaxé en $[0,1]$ — l’intégralité est automatique car la matrice est unimodulaire) :

\[\min \sum_{ij} c_{ij} x_{ij} \quad \text{s.c.} \quad \sum_j x_{ij} = 1 \ \forall i, \quad \sum_i x_{ij} = 1 \ \forall j\]

Son dual a exactement la forme de nos potentiels :

\[\max \sum_i u_i + \sum_j v_j \quad \text{s.c.} \quad u_i + v_j \le c_{ij} \ \forall (i,j)\]

La théorie LP promet : toute solution primale réalisable et toute solution duale réalisable avec valeurs égales sont toutes deux optimales (dualité faible + gap nul). Vérifions numériquement que notre run le réalise.

# Verifications de dualite sur le run precedent
# (1) realisabilite duale : u_i + v_j <= c_ij partout
marges = C - u[:, None] - v[None, :]
print(f"(1) Realisabilite duale  : max(u_i + v_j - c_ij) = {max(0.0, -marges.min()):.2e} (<= 0 attendu)")

# (2) egalite primale-duale : somme des potentiels == valeur du matching
val_dual = u.sum() + v.sum()
print(f"(2) Valeur primale (matching) = {val_km:.0f}")
print(f"    Valeur duale  (u.sum + v.sum) = {val_dual:.0f}")
print(f"    Gap de dualite = {abs(val_km - val_dual):.2e} (0 attendu)")

# (3) les aretes du matching sont toutes des aretes d'egalite
sur_eg = all(abs(u[i] + v[assign_km[i]] - C[i, assign_km[i]]) < 1e-9 for i in range(n))
print(f"(3) Toutes les aretes du matching sont d'egalite : {sur_eg}")

(1) Realisabilite duale  : max(u_i + v_j - c_ij) = 0.00e+00 (<= 0 attendu)
(2) Valeur primale (matching) = 13
    Valeur duale  (u.sum + v.sum) = 13
    Gap de dualite = 0.00e+00 (0 attendu)
(3) Toutes les aretes du matching sont d'egalite : True

Lecture du résultat

Le triple test LP est vert : (1) faisabilité duale exacte — la plus grande violation de $u_i + v_j \le c_{ij}$ est 0 ; (2) valeur primale = valeur duale = 13, gap de dualité 0 ; (3) les 4 arêtes du matching sont toutes des arêtes d’égalité. Par la dualité forte, ce couple (matching, potentiels) est certifié optimal : aucun solveur extérieur ne peut faire mieux que 13 — et nous le savons sans lui faire confiance, le certificat vit dans le notebook.

4. Le pont théorie des jeux : le jeu d’affectation de Shapley-Shubik

Le théorème de Shapley-Shubik (1971) vit sur un jeu de surplus. On convertit les coûts en valeurs : $\alpha_{ij} = M - c_{ij}$ avec $M = \max C$. Maximiser le surplus total revient à minimiser le coût total (la même permutation est optimale) — le surplus optimal vaut $nM - 13$.

Le jeu coopératif : chaque agent $i$ et chaque vendeur de tâche $j$ (le joueur $n + j$) sont des joueurs ; une paire $(i, j)$ laissée seule génère un surplus $\alpha_{ij}$. La valeur d’une coalition $S$ est le meilleur surplus que $S$ réalise en interne : l’affectation optimale dans le rectangle agents($S$) × vendeurs($S$). Une imputation répartit le surplus optimal entre les $2n$ joueurs ; elle est dans le cœur si elle est efficiente ($= $ valeur de la grande coalition) et si aucune coalition ne peut faire mieux seule : part($S$) $\ge$ valeur($S$) pour tout $S$.

Le théorème : le cœur du jeu d’affectation coïncide avec l’ensemble des solutions duales optimales du LP de surplus. Concrètement, nos potentiels KM $(u, v)$ — qui satisfont $u_i + v_j \le c_{ij}$ — donnent une imputation de cœur par translation : $\mathrm{alloc}_i = U - u_i$ et $\mathrm{alloc}_{n+j} = (M - U) - v_j$, pour n’importe quel $U \in [\max u,\ M - \max v]$ (l’intervalle garantit des parts non négatives). Chaque inégalité de paire du cœur se lit alors $\mathrm{alloc}_i + \mathrm{alloc}_{n+j} \ge \alpha_{ij}$ — la réalisabilité duale, mot pour mot.

C’est l’un des résultats les plus beaux de la théorie coopérative : une brique purement combinatoire (le cœur, défini par une exponentielle d’inégalités de coalition) se révèle être un objet LP (le polytope dual, fini et calculable). Le vérifier numériquement.

# Le jeu d'affectation de Shapley-Shubik sur notre exemple, en version surplus.
# alpha_ij = M - c_ij : maximiser le surplus = minimiser le cout (meme optimum).
# Joueurs : n agents + n vendeurs (proprietaires des taches).
# Valeur d'une coalition S = meilleur surplus interne : affectation optimale
# dans le rectangle agents(S) x vendeurs(S).
# Coeur : part(S) >= valeur(S) pour toute coalition S (aucune ne peut bloquer).

from itertools import combinations

M = int(C.max())
alpha = M - C
r_opt, c_opt = linear_sum_assignment(-alpha)
V_surplus = alpha[r_opt, c_opt].sum()
print(f"Surplus optimal : {V_surplus:.0f}  (= n*M - 13 = {n * M - 13})")

# Imputation de coeur derivee des potentiels KM (u, v) : translation par U.
U = int(u.max())
print(f"Parts non negatives pour tout U dans [{U}, {M - int(v.max())}] ; on prend U = {U}")
alloc = {i: U - int(u[i]) for i in range(n)}
alloc.update({n + j: (M - U) - int(v[j]) for j in range(n)})

def valeur_coalition(S):
    """Meilleur surplus interne de S : matching optimal dans le rectangle (alpha >= 0)."""
    A = sorted(p for p in S if p < n)          # agents de la coalition
    B = sorted(p - n for p in S if p >= n)     # vendeurs de la coalition
    if not A or not B:
        return 0.0
    sub = alpha[np.ix_(A, B)]                  # sous-matrice rectangle
    r, c = linear_sum_assignment(-sub)
    return float(sub[r, c].sum())

violations = []
joueurs = list(range(2 * n))
for taille in range(1, 2 * n):
    for S in combinations(joueurs, taille):
        part = sum(alloc[p] for p in S)
        vs = valeur_coalition(S)
        if part < vs - 1e-9:
            violations.append((S, part, vs))
print(f"Coalitions testees : {2**(2*n) - 2}")
print(f"Violations du coeur par l'imputation KM : {len(violations)}")
print(f"Efficacite : somme des parts = {sum(alloc.values()):.0f}"
      f" == surplus grand coalition = {V_surplus:.0f} ?"
      f" {abs(sum(alloc.values()) - V_surplus) < 1e-9}")

Surplus optimal : 23  (= n*M - 13 = 23)
Parts non negatives pour tout U dans [6, 9] ; on prend U = 6
Coalitions testees : 254
Violations du coeur par l'imputation KM : 0
Efficacite : somme des parts = 23 == surplus grand coalition = 23 ? True

Lecture du résultat

Surplus optimal 23 = 4·9 − 13 ; translation valide pour tout U ∈ [6, 9] (parts non négatives) ; sur les 254 coalitions ($2^{2n} - 2$), 0 violations ; efficacité exacte : la somme des parts (23) égale le surplus de la grande coalition. L’imputation dérivée des potentiels KM est un point du cœur — le théorème de Shapley-Shubik, vérifié exhaustivement sur cette instance.

Ce que la vérification dit — et ne dit pas

L’imputation dérivée des potentiels $(u, v)$ de Kuhn-Munkres viole aucune des $2^{2n} - 2$ inégalités de coalition : elle est dans le cœur, et l’efficacité est réalisée. Ce que le test numérique ne prouve pas, c’est la réciproque (tout le cœur est de cette forme) — c’est le théorème de Shapley-Shubik, dont la formalisation Lean est livrée dans le lake compagnon assignment_lean/ (Assignment/Optimality.lean). Le lien LP ↔︎ cœur n’est pas une coïncidence : c’est la complémentarité primale-duale qui, réinterprétée en langage de coalitions, dit exactement qu’aucune coalition ne peut bloquer.

5. Gale-Shapley contre Kuhn-Munkres : deux notions d’optimum

Le dépôt contient déjà game_theory_lean/StableMarriage/GaleShapley.lean — le mariage stable de Gale-Shapley. Les deux algorithmes répondent à des questions différentes sur le même type d’objet (un matching) :

	Gale-Shapley	Kuhn-Munkres
Données	préférences ordinales (rang)	coûts cardinaux
Objectif	stabilité (pas de paire bloquante)	optimalité pondérée (valeur min/max)
Garantie	stable, optimal pour le côté proposant	optimal en valeur, dualité certifiée
Complexité	$O(n^2)$	$O(n^3)$

Sur notre matrice de coûts, Gale-Shapley ne s’applique pas tel quel (il veut des rangs) — mais nous pouvons convertir les coûts en préférences et observer que le matching stable peut être plus cher que l’optimum : stabilité et optimalité pondérée sont des propriétés indépendantes.

# Stabilite vs optimalite : Gale-Shapley sur preferences derivees des couts
def gale_shapley(prefs_agents, prefs_taches):
    """prefs_agents[i] = ordre de preference des taches (meilleur en premier).
    Retourne le matching (agent -> tache), optimal pour les AGENTS (cote proposant)."""
    n = len(prefs_agents)
    libre = list(range(n))
    prop_de = [0] * n          # prochain indice de proposition de chaque agent
    tenue = [-1] * n           # tache j -> agent qui la tient actuellement
    rang_tache = [{t: r for r, t in enumerate(prefs_taches[j])} for j in range(n)]
    while libre:
        i = libre.pop(0)
        j = prefs_agents[i][prop_de[i]]
        prop_de[i] += 1
        if tenue[j] == -1:
            tenue[j] = i
        elif rang_tache[j][i] < rang_tache[j][tenue[j]]:
            evince = tenue[j]
            tenue[j] = i
            libre.append(evince)
        else:
            if prop_de[i] < n:
                libre.append(i)
    return {tenue[j]: j for j in range(n)}

# Preferences = couts croissants (agent prefere la tache la MOINS chere pour lui)
prefs_agents = [list(np.argsort(C[i])) for i in range(n)]
prefs_taches = [list(np.argsort(C[:, j])) for j in range(n)]  # tache prefere l'agent le moins cher
gs = gale_shapley(prefs_agents, prefs_taches)
assign_gs = [gs[i] for i in range(n)]
val_gs = valeur_bruit(C, assign_gs)
print(f"Gale-Shapley (stable)   : valeur = {val_gs:.0f}, affectation = {assign_gs}")
print(f"Kuhn-Munkres (optimal)  : valeur = {val_km:.0f}, affectation = {assign_km}")
print(f"Ecart sur l'exemple fil rouge : {val_gs - val_km:.0f}")

# Sur CETTE matrice, GS et KM coïncident -- c'est possible, pas garanti. Le scan
# suivant cherche (graine fixee) une instance ou le matching stable est PLUS CHER
# que l'optimum : la stabilite se paie parfois.
rng2 = np.random.default_rng(7)
for essai in range(500):
    M = rng2.integers(0, 9, size=(4, 4))
    prefs_a = [list(np.argsort(M[i])) for i in range(4)]
    prefs_t = [list(np.argsort(M[:, j])) for j in range(4)]
    gs = gale_shapley(prefs_a, prefs_t)
    v_gs = valeur_bruit(M, [gs[i] for i in range(4)])
    r, c2 = linear_sum_assignment(M)
    v_opt = M[r, c2].sum()
    if v_gs > v_opt:
        print(f"Instance divergente (essai {essai}) : GS stable = {v_gs}, KM optimal = {v_opt}")
        print("Matrice :")
        print(M)
        print(f"La stabilite se paie : +{v_gs - v_opt} par rapport a l'optimum")
        break
else:
    print("Aucune divergence trouvee en 500 essais -- rapporter honnetement")

Gale-Shapley (stable)   : valeur = 13, affectation = [1, 0, 2, 3]
Kuhn-Munkres (optimal)  : valeur = 13, affectation = [1, 0, 2, 3]
Ecart sur l'exemple fil rouge : 0
Instance divergente (essai 1) : GS stable = 12, KM optimal = 9
Matrice :
[[1 7 1 4]
 [7 2 3 2]
 [6 2 8 4]
 [4 4 5 4]]
La stabilite se paie : +3 par rapport a l'optimum

Lecture du résultat

Sur le fil rouge, GS et KM coïncident (écart 0) — c’est possible, jamais garanti. Le scan seedé (graine 7) le confirme immédiatement : dès l’essai 1, une matrice 4×4 où le matching stable GS coûte 12 contre un optimum KM de 9 — la stabilité se paie +3, soit 33 % au-dessus de l’optimum. Stabilité ordinale et optimalité cardinale sont des propriétés indépendantes : exiger l’une ne donne pas l’autre.

6. Exercices

Trois exercices pour s’approprier l’algorithme. Les stubs s’exécutent sans erreur (le notebook reste exécutable de bout en bout) — à vous de les compléter.

Exercice 1 — Détecter les affectations non optimales

Écrivez est_optimal(C, assignment) qui vérifie (par comparaison à la force brute, possible pour $n \le 6$) si une affectation donnée est optimale. Testez-la sur l’affectation identité de la matrice $C$ du notebook — elle n’est probablement pas optimale.

# Exercice 1 : detecteur d'optimalite par force brute
# TODO etudiant
# Indice : reutiliser valeur_bruit et permutations ; n = len(C) <= 6
# Etape 1 : calculer la valeur de l'affectation donnee
# Etape 2 : calculer l'optimum par force brute
# Etape 3 : comparer

def est_optimal(C, assignment):
    """Retourne True ssi assignment atteint l'optimum (force brute, n <= 6)."""
    # TODO etudiant
    return None  # a completer

# Test attendu (decommente apres completion) :
# print(est_optimal(C, list(range(n))))   # identite : optimale ?

print("Exercice a completer")

Exercice a completer

Exercice 2 — Le crédit partial du glouton

Le glouton ligne-par-ligne (chaque agent prend sa tâche la moins chère disponible) produit une affectation réalisable mais sous-optimale sur certaines matrices. Implémentez le glouton, trouvez (par recherche aléatoire seedée) une matrice 4×4 où il échoue, et mesurez l’écart à l’optimum. Combien vaut le pire rapport valeur_glouton / valeur_optimale que vous observez ?

# Exercice 2 : glouton ligne-par-ligne et son pire cas
# TODO etudiant
# Indice : pour chaque ligne dans l'ordre, prendre la colonne libre la moins chere
# Etape 1 : implémenter glouton(C) -> assignment
# Etape 2 : boucle sur rng.integers pour trouver une matrice ou glouton != optimum
# Etape 3 : mesurer le rapport

def glouton(C):
    """Glouton ligne par ligne : retourne une affectation realisable."""
    # TODO etudiant
    return None  # a completer

# Test attendu (decommente apres completion) :
# M = np.array([[1, 2], [2, 100]])
# print(glouton(M))  # -> [0, 1] : le glouton prend 1 puis 100, l'optimum est 2+2=4

print("Exercice a completer")

Exercice a completer

Exercice 3 — Un deuxième point du cœur

Le cœur du jeu d’affectation est un polytope, pas un point : l’imputation de la section 4 dépend du choix de $U$ dans l’intervalle $[\max u,\ M - \max v]$. Choisissez un autre $U$, vérifiez que la nouvelle imputation satisfait encore toutes les inégalités de coalition mais donne des parts différentes à certains joueurs. Deux points du cœur = deux partages équilibrés du même surplus optimal.

# Exercice 3 : un deuxieme point du coeur
# TODO etudiant
# Indice : reprendre la cellule de la section 4 avec un autre U, ex. U2 = M - int(v.max())
# Etape 1 : construire alloc2 par la translation alloc2_i = U2 - u_i, alloc2_{n+j} = (M - U2) - v_j
# Etape 2 : verifier part2(S) >= valeur_coalition(S) pour toutes les coalitions
# Etape 3 : comparer alloc et alloc2 joueur par joueur (certaines parts changent, la somme non)

# TODO etudiant
print("Exercice a completer")

Exercice a completer

7. Conclusion

Ce notebook a suivi le fil d’un seul théorème — la dualité du problème d’affectation — à travers trois lectures :

Algorithmique : Kuhn-Munkres from scratch, labels et arbres hongrois, confronté à la référence SOTA SciPy — coïncidence exacte sur l’exemple et 50 instances aléatoires.
Optimisation linéaire : les potentiels de l’algorithme sont une solution duale optimale, le gap de dualité est nul, toutes les arêtes du matching sont des arêtes d’égalité — c’est le certificat d’optimalité.
Théorie des jeux : le théorème de Shapley-Shubik — le cœur du jeu d’affectation est exactement le polytope dual optimal. Vérifié numériquement : aucune coalition ne bloque l’imputation, la valeur est épuisé. La formalisation Lean vit dans assignment_lean/.

Et la comparaison Gale-Shapley / Kuhn-Munkres rappelle que « bon matching » n’a pas un sens unique : stabilité et optimalité pondérée sont des propriétés logiquement indépendantes.

Références

Kuhn, H. W. (1955). « The Hungarian Method for the Assignment Problem ». Naval Research Logistics Quarterly 2:83–97.
Munkres, J. R. (1957). « Algorithms for the Assignment and Transportation Problems ». J. SIAM 5(1):32–38 — l’analyse de complexité fortement polynomiale.
Shapley, L. S. & Shubik, M. (1971). « The Assignment Game I: The Core ». International Journal of Game Theory 1:111–130.
scipy.optimize.linear_sum_assignment — la référence SOTA (Jonker-Volgenant).
Hommage MIT News (13 août 2026) : « James Munkres, mathematician, musician and gardener ».

Navigation série : GameTheory-20 · GameTheory-20d · GameTheory-6i · GT-23

Retour au sommet