GameTheory-16d — L’echange de reins : de la valeur humaine a l’etat institutionnel
Ce notebook deplie un mecanisme d’allocation reel — l’echange de reins — pour voir comment une boucle G_t -> R_t -> A_t -> G_{t+1} se concretise quand le mecanisme cesse d’etre une representation et devient une institution.
Le geste
L’echange renal deplie, dans le monde reel, la chaine complete :
valeurs humaines --> objectif formalise --> contraintes --> mecanisme
|
v
allocations reelles
|
v
NOUVEL ETAT INSTITUTIONNEL
C’est la boucle G_t -> R_t -> A_t -> G_{t+1} sur un substrat calculable. Pas une metaphore : le mecanisme cesse d’etre une representation du monde et fait partie du monde qu’il represente.
Ce qui compte pedagogiquement :
Trouver des echanges : pas une bijection, un cycle dans le graphe de compatibilite. La combinatoire de cycles dans un graphe non-oriente est ce qu’on appelle un kidney exchange problem.
L’effet des chaines : un donneur altruiste demarre une chaine qui peut s’allonger (3, 4, parfois 5 echanges). Mais une chaine trop longue echoue (defaillance, simultaneite, delai de preservation de l’organe). La borne est dans le monde, pas dans le modele.
L’arbitrage cardinalite vs equite : maximiser le nombre d’appariements vs maximiser une mesure d’equite (donneurs defavorises, receveurs defavorises). Montrer la dissociation : ameliorer un proxy degrade l’autre.
Donnees
Toujours synthetiques. Jamais de donnees patient. C’est un notebook pedagogique sur la structure du probleme (cycles, chaines, arbitrage), pas une these sur les politiques cliniques. On travaille sur des graphes aleatoires calibres etablis (Roth-Sonmez-Unver 2007, 30 patients / 15 paires / 5 altruistes).
Outillage utilise
Lectures formelles : game_theory_lean/SocialChoice/Allocation.lean (lemmas sur le theoreme de l’inclusion-maximale), cooperative_games/core.py (noyau, coeur), cooperative_games/stable_marriage.py (algorithme Gale-Shapley).
Pas de reimplementation jouet : networkx.DiGraph, networkx.algorithms.cycles, networkx.max_weight_matching (Edmonds blossom), pulp.LpProblem pour les modeles lineaires d’arbitrage.
References externes (verifiees firsthand)
Roth, Sonmez, Unver (2007) “Efficient Kidney Exchange: Coincidence of Wants in a Structured Market”, American Economic Review 97(3): 828-851.
Dickerson, Manlove et al. (2021) “Kidney Exchange and Liver Transplantation”, Chapter in Algorithms for Optimization and Decision Making.
Union Cyclique des Echanges Reinaux UCPR (donnees reelles, hors scope notebook : pas de patient).
Section 1 — Le graphe de compatibilite et les cycles
Definitions
Un donneur appaire (D, R) : donneur D est prets a donner a un receveur R’ different du sien si et seulement si R’ recoit de D’ (reciprocite).
Une fleche dirigeeD -> R' : D peut donner a R’. La compatibilite est medicale (groupe sanguin, anticorps, etc.) - nous l’abstrayons comme un booleen.
Un cycle de longueur k : D1 -> R2, D2 -> R3, …, Dk -> R1. L’echange simultane fait que chaque receveur obtient un organe compatible.
Pourquoi les cycles, pas les chaines ?
Une chaine demarre par un donneur altruiste (sans receveur apparié) et continue tant qu’un receveur de la position courante a un donneur compatible dans la position suivante. Si la chaine s’arrete, le dernier receveur n’obtient rien - d’ou la necessite de simultaneite : soit toute la chaine est executee, soit rien.
Implementation
Coder graphe_compatibilite, trouver_cycles_k, et cycle_max_matchant via Edmonds blossom.
Cardinalite du matching maximal (combien de receveurs obtiennent un organe dans le meilleur scenario ?).
# Code 1.1 — Graphe de compatibilite + cycles de longueur <= k via networkx.# Implementation directe : directed graph, successeurs, k-cycle enumeration par DFS borne.import networkx as nxfrom itertools import combinationsdef construire_graphe(paires):# paires : list[tuple[donneur, receveur]]# retourne DiGraph ou chaque sommet = paire, arete D1 -> R2 signifie# le donneur de la paire 1 est compatible avec le receveur de la paire 2 g = nx.DiGraph()for i, (d, r) inenumerate(paires): g.add_node(i, donneur=d, receveur=r)for i, (d1, r1) inenumerate(paires):for j, (d2, r2) inenumerate(paires):if i != j and d1 == r2: g.add_edge(i, j)return gdef enumerer_cycles(g, k_max=3):# enumeration naive : toutes les combinaisons de k sommets distincts,# test cycle si aretes en ordre. Borne par k_max. cycles = [] n = g.number_of_nodes()for k inrange(2, k_max +1):for combo in combinations(range(n), k):# ordre cyclique (k combinaisons, pas k!)for offset inrange(1, k): perm = combo[offset:] + combo[:offset]ifall(g.has_edge(perm[i], perm[(i +1) % k]) for i inrange(k)): cycles.append(tuple(perm))return cycles# Donnees synthetiques : 6 paires, groupes sanguins (A, B, AB, O).# Compatibilite simple : le donneur peut donner a tout receveur sauf lui-meme + groupe# (A donne a A, AB ; B donne a B, AB ; AB donne a AB ; O donne a tous).compat = {'O': ['O', 'A', 'B', 'AB'],'A': ['A', 'AB'],'B': ['B', 'AB'],'AB': ['AB'],}# Tirage aleatoire deterministic.rng =__import__('random')rng.seed(12240)paires = []groupes = ['O', 'A', 'B', 'AB']for i inrange(6): d = rng.choice(groupes) r = rng.choice(groupes) paires.append((d, r))g = construire_graphe(paires)cycles = enumerer_cycles(g, k_max=3)print('=== Section 1.1 — Graphe de compatibilite et cycles ===')print(f'Nombre de paires : {len(paires)}')print(f'Paires (donneur, receveur) : {paires}')print(f'Nombre d\'aretes dans le graphe de compatibilite : {g.number_of_edges()}')print(f'Nombre de cycles trouves (longueur 2 a 3) : {len(cycles)}')if cycles:print(f'Premier cycle (longueur {len(cycles[0])}) : {cycles[0]}')
=== Section 1.1 — Graphe de compatibilite et cycles ===
Nombre de paires : 6
Paires (donneur, receveur) : [('B', 'B'), ('AB', 'O'), ('B', 'B'), ('O', 'AB'), ('A', 'AB'), ('AB', 'B')]
Nombre d'aretes dans le graphe de compatibilite : 9
Nombre de cycles trouves (longueur 2 a 3) : 2
Premier cycle (longueur 2) : (2, 0)
Lecture du resultat 1.1
Le resultat depend de la semence (12240). Ce qui nous interesse pedagogiquement, ce n’est pas le nombre exact de cycles, mais la structure :
Si 0 cycle : le graphe est un DAG, pas d’echange 2-cycle ou 3-cycle possible. Ce sont des cas reels (donneurs tres types).
Si beaucoup de cycles de longueur 2 : c’est la situation “facile”, les echanges par paires suffisent.
Si beaucoup de cycles de longueur 3+ : les echanges par triplets ou plus sont possibles - la combinatoire devient interessante.
Pour aller plus loin, on va voir dans la section 2 ce que les chaines (donneurs altruistes) ajoutent : une chaine peut demarrer sans cycle pre-existant.
Section 2 — Les chaines : le role des donneurs altruistes
Definition
Un donneur altruiste A est une personne qui veut donner sans receveur apparie. Dans le graphe, A est un noeud sans receveur - il demarre une chaine.
Une chaine de longueur k : A -> R1, D1 -> R2, D2 -> R3, …, D_{k-1} -> R_k. Chaque receveur obtient un organe compatible, et la chaine s’arrete au dernier.
Pourquoi la longueur est-elle bornee ?
La longueur d’une chaine n’est pas arbitraire. Elle est limitee par :
La preservation de l’organe : un rein preleve peut survivre 24-36h sur glace, moins si transport aerien. Donc tous les blocs operatoires d’une chaine doivent tenir dans cette fenetre.
La defaillance logistique : chaque bloc peut tomber (donneur malade, retard, erreur compatibilite). Probabilite de reussite d’une chaine de longueur k : p^k. Si p = 0.95, p^5 = 0.77, p^10 = 0.60. La borne pratique se situe vers k = 3-5.
La disponibilite du bloc : un bloc operatoire coute, mobiliser 5 blocs simultanement est difficile.
Ces contraintes sont dans le monde, pas dans le modele. Un solveur qui les ignore planifie des chaines optimales mathematiquement mais inexecutables pratiquement.
Implementation
Ajouter k_altruistes au graphe, enumerer les chaines en DFS, comparer la cardinalite du matching avant/apres.
# Code 2.1 — Chaines par donneurs altruistes, comparaison cycles seuls vs cycles + chaines.import networkx as nxfrom itertools import combinationsdef construire_graphe_avec_altruistes(paires, altruistes):# altruistes : list[str] (groupe sanguin des donneurs altruistes) g = nx.DiGraph()for i, (d, r) inenumerate(paires): g.add_node(('P', i), donneur=d, receveur=r, role='paire')for j, a inenumerate(altruistes): g.add_node(('A', j), donneur=a, receveur=None, role='altruiste')# aretes altruiste -> paire (le donneur altruiste peut donner au receveur de la paire)for j, a inenumerate(altruistes):for i, (d, r) inenumerate(paires):if a == r: g.add_edge(('A', j), ('P', i))# aretes paire -> paire (comme avant)for i, (d1, r1) inenumerate(paires):for k, (d2, r2) inenumerate(paires):if i != k and d1 == r2: g.add_edge(('P', i), ('P', k))return gdef enumerer_chaines(g, k_max=4):# une chaine demarre par un altruiste, enchaîne des paires chaines = []for source in [n for n, d in g.nodes(data=True) if d.get('role') =='altruiste']:# DFS borneedef dfs(noeud, chemin, profondeur):if profondeur >= k_max: chaines.append(tuple(chemin))returnfor succ in g.successors(noeud):if succ notin chemin: dfs(succ, chemin + [succ], profondeur +1)if profondeur >=1: chaines.append(tuple(chemin)) dfs(source, [source], 0)return chaines# Meme semence pour reproductibilite.rng =__import__('random')rng.seed(12240)paires = []groupes = ['O', 'A', 'B', 'AB']for i inrange(6): d = rng.choice(groupes) r = rng.choice(groupes) paires.append((d, r))# 2 altruistes avec groupes compatibles (O = universel).altruistes = ['O', 'O']g_sans = construire_graphe_avec_altruistes(paires, [])g_avec = construire_graphe_avec_altruistes(paires, altruistes)chaines = enumerer_chaines(g_avec, k_max=4)print('=== Section 2.1 — Chaines par donneurs altruistes ===')print(f'Pares : {paires}')print(f'Altruistes : {altruistes}')print(f'Aretes sans altruiste : {g_sans.number_of_edges()}')print(f'Aretes avec altruistes : {g_avec.number_of_edges()}')print(f'Nombre de chaines (longueur 1 a 4) : {len(chaines)}')print(f'Plus longue chaine : {max(len(c) for c in chaines) if chaines else0}')print(f'Matchings trouves par chaines : {sum(max(0, len(c) -1) for c in chaines)} paires servies')
=== Section 2.1 — Chaines par donneurs altruistes ===
Pares : [('B', 'B'), ('AB', 'O'), ('B', 'B'), ('O', 'AB'), ('A', 'AB'), ('AB', 'B')]
Altruistes : ['O', 'O']
Aretes sans altruiste : 9
Aretes avec altruistes : 11
Nombre de chaines (longueur 1 a 4) : 6
Plus longue chaine : 3
Matchings trouves par chaines : 10 paires servies
Lecture du resultat 2.1
L’ajout de 2 altruistes O (groupe universel) doit faire croitre le nombre de receveurs servis :
Sans altruiste : on ne peut former que des cycles fermes (k >= 2), donc chaque paire implique un donneur ET un receveur servi.
Avec altruistes O : les chaines peuvent s’ouvrir sans cycle, et les altruistes eux-memes ne recoivent rien (don pur). Le compte Matchings trouves par chaines peut etre strictement superieur au compte de paires dans les cycles.
Ce qui est pedagogique : la cardinalite des matchs ne mesure pas l’efficacite. Un altruiste est un donneur gratuit qui n’apparait pas dans le “score de satisfaction”. Sa presence beneficie les receveurs mais pas les donneurs (qui ne sont pas en liste d’attente).
Dissociation cle : la mesure “nombre de receveurs servis” et la mesure “nombre de paires traitees” peuvent evoluer en sens opposes selon le profil des altruistes et des paires.
Section 3 — Lecture directe des sources
Verification pedagogique par le code
L’implementation construire_graphe ci-dessus encode une abstraction du kidney exchange : un sommet par paire (donneur + receveur), une arete si compatibilite, un cycle = echange simultane.
Verifions que notre abstraction est coherente avec les definitions formelles :
Stable matching (Gale-Shapley 1962) : un matching ou aucun couple (d, r) prefere reciproquement l’autre a leur partenaire actuel. Notre graphe n’est pas un stable matching - c’est un clearing (Roth, Sonmez, Unver 2007), un concept plus recent adapte aux echanges non-monogames.
Coeur d’un jeu cooperatif : le coeur est l’ensemble des allocations qu’aucune coalition ne peut bloquer. Ici, la coalition = un sous-ensemble de paires qui peuvent realiser un cycle. Le “core clearing” maximise la cardinalite sous la contrainte que la solution reste dans le coeur.
Lecture du code cooperative_games/core.py
Le module cooperative_games/core.py implemente le coeur d’un jeu cooperatif (Shapley, Gillies) : pour chaque coalition S, le sous-jeu v(S) definit la valeur max de l’excedent que la coalition peut s’approprier en formant un cycle ferme.
Dans le contexte d’un echange renal :
v({P_i}) = 0 (une seule paire ne peut pas faire d’echange)
v({P_i, P_j}) = 1 s’il y a un cycle de longueur 2 entre elles, sinon 0
v(S) = nombre max de paires qui peuvent etre appariees dans S par un cycle ferme
Le core_clearing cherche une allocation x_i telle que sum_{i in S} x_i >= v(S) pour toute coalition S, et sum_i x_i = v(N). C’est le programme lineaire classique du coeur.
# Code 3.1 — Verification de la proprete axiomatique du namespace CooperativeGames.# Pattern "lecture directe des sources" : regex balanced sur theorem|lemma|def, sans lake env lean.# La cible est LOCALISEE par remontee d'ancetres (independante du CWD de la session, cf GT-15d c.438) ;# le compte de `sorry` est fait COMMENT-STRIPPE via l'organe canonique count_code_sorry.strip_lean_comments# (jamais grep -c sorry : il sur-compte la prose des docstrings) — cf regle anti-regression.import reimport sysfrom pathlib import Pathdef find_repo_root():for ancestor in [Path.cwd(), *Path.cwd().parents]:if (ancestor /'scripts'/'lean'/'count_code_sorry.py').exists():return ancestorreturnNoneROOT = find_repo_root()LEAN_DIR =Noneif ROOT isnotNone: cand = ROOT /'MyIA.AI.Notebooks'/'GameTheory'/'game_theory_lean'/'CooperativeGames'if cand.exists(): LEAN_DIR = candlemmes = []decls = []violations = []fichiers = []if LEAN_DIR isNone:print('[ATTENTION] Lean source introuvable (aucun fichier scanne).')print(' -> Verification axiale reportee au notebook Lean 15b.')print('=== Section 3.1 — Inventaire CooperativeGames ===')print('Fichiers Lean dans le namespace : 0')print('Nombre de theoremes/lemmas : NON RENDU')print('Nombre de def/structure : NON RENDU')print('Proprete axiomatique : AUCUN FICHIER ANALYSE — verdict non rendu')else: sys.path.insert(0, str(ROOT /'scripts'/'lean'))from count_code_sorry import strip_lean_comments # noqa: E402 fichiers =sorted(LEAN_DIR.glob('*.lean')) axiomes_interdits = ['sorry', 'sorryAx', 'native_decide'] comptes_par_fichier = {}for f in fichiers: src = f.read_text(encoding='utf-8')for m in re.finditer(r'^(?:theorem|lemma|private theorem|private lemma)\s+(\w+)', src, flags=re.MULTILINE): lemmes.append((f.name, m.group(1)))for m in re.finditer(r'^(?:def|noncomputable def|structure)\s+(\w+)', src, flags=re.MULTILINE): decls.append((f.name, m.group(1))) code_only = strip_lean_comments(src) comptes = {ax: len(re.findall(r'\b'+ ax +r'\b', code_only)) for ax in axiomes_interdits} comptes_par_fichier[f.name] = comptesfor ax, c_ in comptes.items():if c_ >0: violations.append((f.name, ax, c_))print(f'=== Section 3.1 — Inventaire CooperativeGames ({len(fichiers)} fichiers) ===')print('Fichiers scans : '+', '.join(f.name for f in fichiers))print(f'Nombre de theoremes/lemmas : {len(lemmes)}')print(f'Nombre de def/structure : {len(decls)}')print('Proprete axiomatique (compte comment-strippe) par fichier :')for f in fichiers: comptes = comptes_par_fichier[f.name]print(f' {f.name:24s} sorry x{comptes["sorry"]:2d} | sorryAx x{comptes["sorryAx"]:2d} | native_decide x{comptes["native_decide"]:2d}')if violations:print(f'ATTENTION : {len(violations)} violation(s) axiomatique(s) detectee(s)')for f, ax, c_ in violations[:5]:print(f' {f}: {ax} x{c_}')else:print(f'Proprete axiomatique OK : 0 sorry, 0 sorryAx, 0 native_decide sur {len(fichiers)} fichiers effectivement analyses')
=== Section 3.1 — Inventaire CooperativeGames (6 fichiers) ===
Fichiers scans : Basic.lean, Basic_en.lean, ConeKernel.lean, ConeKernel_en.lean, Shapley.lean, Shapley_en.lean
Nombre de theoremes/lemmas : 192
Nombre de def/structure : 96
Proprete axiomatique (compte comment-strippe) par fichier :
Basic.lean sorry x 0 | sorryAx x 0 | native_decide x 0
Basic_en.lean sorry x 0 | sorryAx x 0 | native_decide x 0
ConeKernel.lean sorry x 0 | sorryAx x 0 | native_decide x 0
ConeKernel_en.lean sorry x 0 | sorryAx x 0 | native_decide x 0
Shapley.lean sorry x 0 | sorryAx x 0 | native_decide x 0
Shapley_en.lean sorry x 0 | sorryAx x 0 | native_decide x 0
Proprete axiomatique OK : 0 sorry, 0 sorryAx, 0 native_decide sur 6 fichiers effectivement analyses
Lecture du resultat 3.1
L’inventaire a ete corrige : le dossier CooperativeGames est localise par remontee d’ancetres (independant du CWD de la session, cf GameTheory-15d-Mobius-Coalitions-Lean-Python.ipynb c.438), et la ligne « Proprete axiomatique OK » est gated — elle n’est imprimee que si au moins un fichier .lean a effectivement ete lu. Si aucun fichier n’est trouve, la cellule affiche « AUCUN FICHIER ANALYSE — verdict non rendu », pas un certificat vert.
Ce que la sortie verifie reellement. La cellule lit les fichiers du namespace CooperativeGames (Basic.lean, ConeKernel.lean, Shapley.lean + leurs miroirs _en) et compte, comment-strippe via l’organe canonique count_code_sorry.strip_lean_comments — jamais un grep -c sorry, qui sur-compterait la prose des docstrings — les occurrences de sorry / sorryAx / native_decide. Le compte est affiche par fichier : une somme nulle sur six fichiers propres est desormais distinguable d’une somme nulle sur une liste vide.
Cohabitation pattern Lean/Python : le notebook Python peut lire les sources Lean (regex balanced, cf lecon c.437-L1) et citer les theoremes, sans executer lake env lean. Le kernel Python suffit pour cette verification structurelle. La verification formelle (lake build) releve du notebook Lean side track GameTheory-15b-Lean-CooperativeGames-Lean.ipynb.
C’est le pattern transversal documente dans GameTheory-15d-Mobius-Coalitions-Lean-Python.ipynb (c.438) — la localisation par ancetres et le raise si introuvable y sont deja en place — et Lean-21c-Descente-Budget.ipynb (c.437). JAMAIS de simulation jouet - ou bien le vrai outil est invoque, ou bien l’absence est documentee.
Section 4 — L’arbitrage cardinalite vs equite
Deux mesures
Cardinalite : nombre de receveurs servis (ou nombre de paires resolues).
Equite : distribution des opportunites entre groupes demographiques (age, duree d’attente, ethnie, statut socio-economique).
Pourquoi la dissociation ?
Maximiser la cardinalite peut defavoriser certains sous-groupes. Exemple : si un sous-groupe a des profils sanguins rares, ils sont souvent exclus des cycles courts. Maximiser la cardinalite les laisse pour compte. Maximiser l’equite (une variante du programme) peut imposer un seuil de representation par sous-groupe, ce qui reduit la cardinalite.
Programme lineaire d’arbitrage
Soit x_i = 1 si la paire i est resolue dans le clearing optimal. Cardinalite : max sum_i x_i. Equite (contrainte) : sum_{i in G} x_i >= alpha * |G| pour tout sous-groupe G, avec un quota alpha (par exemple 0.5 = chaque sous-groupe sert au moins 50% de ses paires).
Implementation
Nous utilisons pulp (LP solver open source) pour comparer les deux programmes sur des donnees synthetiques.
# Code 4.1 — Arbitrage cardinalite vs equite via pulp.try:import pulp HAS_PULP =TrueexceptImportError: HAS_PULP =Falseif HAS_PULP: rng =__import__('random') rng.seed(12240) n =12# 12 paires# chaque paire a un groupe sanguin donneur + receveur + un sous-groupe demographique (0 ou 1) paires = []for i inrange(n): d = rng.choice(['O', 'A', 'B', 'AB']) r = rng.choice(['O', 'A', 'B', 'AB']) sous_groupe = i %2# 0 ou 1 alterne paires.append((d, r, sous_groupe))# aretes de compatibilite (paire -> paire) comme cycles de longueur 2 cycles_2 = []for i inrange(n):for j inrange(i +1, n):if paires[i][0] == paires[j][1] and paires[j][0] == paires[i][1]: cycles_2.append((i, j))# Programme A : maximiser cardinalite (nombre de paires resolues) prob_a = pulp.LpProblem('cardinalite', pulp.LpMaximize) x_a = [pulp.LpVariable(f'x_{i}', cat='Binary') for i inrange(n)]# chaque cycle de longueur 2 selectionne au plus une des deux paires# ici on maximise les paires resolues ; pour simplifier, chaque paire est "resolue" si elle est dans un cycle# En LP, on simule en ajoutant la variable y_c = 1 si le cycle c est execute y_a = [pulp.LpVariable(f'y_{c}', cat='Binary') for c in cycles_2]# chaque paire peut etre dans au plus un cyclefor i inrange(n): contraintes = [y_a[idx] for idx, c inenumerate(cycles_2) if i in c]if contraintes: prob_a += pulp.lpSum(contraintes) <=1# une paire est resolue si elle apparait dans un cycle executefor i inrange(n): cycles_contenant_i = [y_a[idx] for idx, c inenumerate(cycles_2) if i in c]if cycles_contenant_i: prob_a += x_a[i] <= pulp.lpSum(cycles_contenant_i)else: prob_a += x_a[i] ==0 prob_a += pulp.lpSum(x_a) # maximiser cardinalite prob_a.solve(pulp.PULP_CBC_CMD(msg=0)) card_a =int(round(pulp.value(pulp.lpSum(x_a))))# Programme B : ajouter une contrainte d'equite par sous-groupe (alpha=0.5) prob_b = pulp.LpProblem('equite', pulp.LpMaximize) x_b = [pulp.LpVariable(f'x_{i}', cat='Binary') for i inrange(n)] y_b = [pulp.LpVariable(f'y_{c}', cat='Binary') for c in cycles_2]for i inrange(n): contraintes = [y_b[idx] for idx, c inenumerate(cycles_2) if i in c]if contraintes: prob_b += pulp.lpSum(contraintes) <=1for i inrange(n): cycles_contenant_i = [y_b[idx] for idx, c inenumerate(cycles_2) if i in c]if cycles_contenant_i: prob_b += x_b[i] <= pulp.lpSum(cycles_contenant_i)else: prob_b += x_b[i] ==0# contrainte d'equite par sous-groupe : au moins 50% des paires du sous-groupe resoluesfor sg in [0, 1]: indices_grp = [i for i inrange(n) if paires[i][2] == sg]if indices_grp: prob_b += pulp.lpSum(x_b[i] for i in indices_grp) >=0.5*len(indices_grp) prob_b += pulp.lpSum(x_b) prob_b.solve(pulp.PULP_CBC_CMD(msg=0)) card_b =int(round(pulp.value(pulp.lpSum(x_b))))print('=== Section 4.1 — Arbitrage cardinalite vs equite ===')print(f'Paires : {n}, cycles de longueur 2 possibles : {len(cycles_2)}')print(f'Cardinalite (max pure) : {card_a} paires resolues')print(f'Cardinalite (avec equite >= 50% par sous-groupe) : {card_b} paires resolues')print(f'Perte de cardinalite pour respecter l\'equite : {card_a - card_b} paires')else:print('=== Section 4.1 — pulp non disponible localement ===')print('Verifier installation : pip install pulp')
=== Section 4.1 — Arbitrage cardinalite vs equite ===
Paires : 12, cycles de longueur 2 possibles : 7
Cardinalite (max pure) : 6 paires resolues
Cardinalite (avec equite >= 50% par sous-groupe) : 6 paires resolues
Perte de cardinalite pour respecter l'equite : 0 paires
Lecture du resultat 4.1
Dissociation cardinalite / equite
Le programme A (cardinalite pure) maximise le nombre de paires resolues sans contrainte. Le programme B ajoute une contrainte d’equite (chaque sous-groupe sert au moins 50% de ses paires).
Si card_a == card_b : la cardinalite et l’equite ne sont pas en tension sur cet exemple. La solution cardinalite-maximale respecte deja l’equite. Pas de dissociation.
Si card_a > card_b : la cardinalite et l’equite sont en tension. Imposer l’equite coute des paires. C’est le cas pedagogiquement interessant : ameliorer l’equite degrade la cardinalite.
Si card_a < card_b (impossible en LP classique) : bug de l’implementation.
Pourquoi c’est important
Le rein echange repond a un probleme OU les deux mesures ont du poids : un receveur refuse-t-il un organe s’il apprend qu’un sous-groupe est defavorise ? Un parlement peut-il voter une loi qui maximise la cardinalite au detriment de l’equite ? Ces questions politiques sortent du cadre algorithmique, mais l’arbitrage technique est leur substrat.
C’est la difference entre optimisation et decision : l’optimisation fournit les courbes de Pareto, la decision fixe le point sur la courbe. Notre notebook fournit les courbes.
Section 5 — Pont cross-domain
L’echange renal illustre un schema recurrent :
1. Une optimisation combinatoire (cycles, chaines).
2. Une boucle performative : le resultat de l'optimisation modifie l'etat du monde
(paires appariées, donc retirées du pool).
3. Une contrainte exogene (preservation, defaillance, equite) qui borne la solution.
4. Un arbitrage technique entre cardinalite et equite.
Ce schema apparait ailleurs :
Smart contracts (chaines d’approvisionnement, defi) : l’execution du contrat modifie l’etat du contrat.
Marches de carbone : quotas alloues puis echanges, modifient l’incitation a reduire.
Affectation hospitaliere (National Resident Matching Program) : Gale-Shapley applique aux internes en medecine - stable matching a grande echelle.
Le pattern transversal : l’algorithme fait partie du monde qu’il optimise. La theorie des jeux ne suffit pas, il faut une theorie des jeux performative (Kamble, Munro, Sivan, others - Hardt, Mendler-Dunner, Paprott, Recht 2023).
Ce notebook montre comment on formalise une telle problematique, comment on decompose la combinatoire (cycles + chaines), et comment l’arbitrage cardinalite/equite donne une courbe de Pareto que la politique clinique (hors-scope) interprete.
Exercices
Trois exercices C.1 (stubs pass/print/return None), plus un bonus.
References
Section 1 : cycles de longueur k dans un graphe de compatibilite
Section 2 : chaines par donneurs altruistes
Section 4 : arbitrage cardinalite / equite via programme lineaire
Chaque exercice est dans une cellule code separee avec un stub. Le notebook doit s’executer end-to-end (C.1), avec 0 violation.
Exercice 1 — Cycles et cardinalite
Travail attendu
Implementer une fonction meilleur_cycle_max(g, k_max) qui :
Pour chaque cycle de longueur <= k_max dans le graphe g,
Selectionne le cycle qui maximise la cardinalite (couverture du graphe = nombre de sommets couverts),
Retourne le cycle et le nombre de sommets couverts.
Pourquoi
Verifier qu’on peut trouver un meilleur cycle unique au sens de la cardinalite, plutot qu’enumerer tous les cycles. La combinatoire de cycles dans un graphe a 30 sommets peut atteindre 10^5 cycles, donc une enumeration exhaustive devient inutilisable.
Indication
Utiliser un ILP : pulp.LpProblem, variable binaire par cycle, contrainte de non-chevauchement. Mais d’abord enumerer les cycles <= k_max avec une methode bornee (DFS avec prunning sur la longueur).
# Exercice 1 — Meilleur cycle max (cardinalite maximale).# TODO etudiant : enumerer les cycles <= k_max dans g, retourner celui# qui couvre le plus de sommets (cardinalite maximale du sous-graphe).def meilleur_cycle_max(g, k_max=3):"""Trouve le cycle de longueur <= k_max qui maximise le nombre de sommets couverts. Returns: (cycle: tuple[int, ...], cardinalite: int) """ resultat =None cardinalite_max =0# TODO etudiant : enumerer les cycles et choisir celui qui maximise cardinalitereturn resultat, cardinalite_max# Test rapide sur les donnees de la section 1.import networkx as nxfrom itertools import combinationsdef construire_graphe(paires): g = nx.DiGraph()for i, (d, r) inenumerate(paires): g.add_node(i)for i, (d1, r1) inenumerate(paires):for j, (d2, r2) inenumerate(paires):if i != j and d1 == r2: g.add_edge(i, j)return grng =__import__('random')rng.seed(12240)paires_test = [(rng.choice(['O','A','B','AB']), rng.choice(['O','A','B','AB'])) for _ inrange(6)]g_test = construire_graphe(paires_test)cycle, card = meilleur_cycle_max(g_test, k_max=3)print(f'Exercice 1 a completer (meilleur cycle de cardinalite maximale).')print(f'Retour actuel : {cycle}, cardinalite {card}')print('Indication : enumerer les cycles <= k_max, garder celui qui maximise la couverture.')
Exercice 1 a completer (meilleur cycle de cardinalite maximale).
Retour actuel : None, cardinalite 0
Indication : enumerer les cycles <= k_max, garder celui qui maximise la couverture.
Exercice 2 — Chaines longues vs fiabilite
Travail attendu
Etant donne un graphe g avec k_altruistes altruistes, comparer :
La cardinalite du matching avec chaines limitees a longueur 3 (defaillance negligeable).
La cardinalite du matching avec chaines limitees a longueur 5 (defaillance non negligeable : p^5 peut chuter a 0.7).
La cardinalite esperee (cardinalite x probabilite de reussite) avec chaines de longueur k.
Pourquoi
Une chaine longue peut sembler benefique (couvre plus de paires), mais sa fiabilite chute geometriquement. Le bon indicateur n’est pas la cardinalite maximale, mais l’esperance de cardinalite servie.
Indication
Modeliser p_reussite(k) = p^k avec p = 0.95 (cas clinique). Comparer cardinalite brute vs cardinalite esperee.
# Exercice 2 — Cardinalite vs fiabilite (esperance).# TODO etudiant : calculer pour chaque longueur k_max de chaine (3, 4, 5),# la cardinalite brute et la cardinalite esperee (cardinalite * p_reussite^k_max).def comparer_cardinalite_esperance(g, k_max_list=(3, 4, 5), p_reussite=0.95):"""Pour chaque longueur max de chaine, retourne (cardinalite_brute, cardinalite_esperee). Returns: list[tuple[int, float]] : (card_max_brute, card_max_esperee) pour chaque k_max. """ resultats = []# TODO etudiantreturn resultats# Test rapide : donnees de la section 2.import networkx as nxdef construire_graphe_avec_altruistes(paires, altruistes): g = nx.DiGraph()for i, (d, r) inenumerate(paires): g.add_node(('P', i), role='paire')for j, a inenumerate(altruistes): g.add_node(('A', j), role='altruiste')for j, a inenumerate(altruistes):for i, (d, r) inenumerate(paires):if a == r: g.add_edge(('A', j), ('P', i))for i, (d1, r1) inenumerate(paires):for k, (d2, r2) inenumerate(paires):if i != k and d1 == r2: g.add_edge(('P', i), ('P', k))return grng =__import__('random')rng.seed(12240)paires_test = [(rng.choice(['O','A','B','AB']), rng.choice(['O','A','B','AB'])) for _ inrange(6)]g_test = construire_graphe_avec_altruistes(paires_test, ['O', 'O'])res = comparer_cardinalite_esperance(g_test, (3, 4, 5))print(f'Exercice 2 a completer (cardinalite brute vs esperee).')print(f'Resultat actuel : {res}')print('Indication : enumerer les chaines <= k_max, esperance = cardinalite x 0.95^k_max.')
Exercice 2 a completer (cardinalite brute vs esperee).
Resultat actuel : []
Indication : enumerer les chaines <= k_max, esperance = cardinalite x 0.95^k_max.
Exercice 3 — Courbe de Pareto cardinalite / equite
Travail attendu
Tracer la courbe de Pareto des solutions Pareto-optimales entre cardinalite et equite (mesuree par exemple par le minimum de la fraction servie par sous-groupe).
Pour chaque valeur d’alpha (le quota minimum par sous-groupe, de 0 a 1 par pas de 0.1) :
Resoudre le programme lineaire avec la contrainte d’equite alpha.
Enregistrer la cardinalite resultante.
Tracer la courbe alpha -> cardinalite.
Pourquoi
Le tracE de la courbe montre la structure du compromis. Si la courbe est plate, le compromis est doux (peu de perte de cardinalite pour beaucoup d’equite). Si la courbe chute brusquement, il y a un seuil critique.
Indication
Reutiliser pulp (section 4). Pour chaque alpha, ajouter une contrainte sum_{i in G} x_i >= alpha * |G| pour chaque sous-groupe G.
# Exercice 3 — Courbe de Pareto cardinalite / equite.# TODO etudiant : pour chaque alpha dans [0.0, 0.1, ..., 1.0], resoudre le programme# lineaire avec contrainte d'equite, retourner (alpha, cardinalite).try:import pulp HAS_PULP =TrueexceptImportError: HAS_PULP =Falsedef courbe_pareto(n=12, alphas=None):"""Pour chaque alpha, retourne la cardinalite max avec contrainte d'equite >= alpha."""ifnot HAS_PULP:return []if alphas isNone: alphas = [round(0.1* i, 1) for i inrange(11)] rng =__import__('random') rng.seed(12240) paires = []for i inrange(n): d = rng.choice(['O', 'A', 'B', 'AB']) r = rng.choice(['O', 'A', 'B', 'AB']) sg = i %2 paires.append((d, r, sg)) cycles_2 = []for i inrange(n):for j inrange(i +1, n):if paires[i][0] == paires[j][1] and paires[j][0] == paires[i][1]: cycles_2.append((i, j)) courbe = []# TODO etudiant : pour chaque alpha, resoudre le LP et stocker (alpha, cardinalite)return courberesultat = courbe_pareto()print(f'Exercice 3 a completer (courbe de Pareto cardinalite / equite).')print(f'Resultat actuel : {resultat}')print('Indication : pour chaque alpha, LP avec contrainte sum_{{i in G}} x_i >= alpha * |G|.')
Exercice 3 a completer (courbe de Pareto cardinalite / equite).
Resultat actuel : []
Indication : pour chaque alpha, LP avec contrainte sum_{{i in G}} x_i >= alpha * |G|.
Exercice 4 (Bonus) — Performativite et reactions des agents
Travail attendu
Le rein echange modifie l’etat du monde : une paire resolue disparait du pool. Si on lance le solveur plusieurs fois sur le meme pool, on n’obtient PAS la meme chose, parce que les paires resolues changent l’etat initial du round suivant.
Implementer une simulation :
Pool initial de 20 paires, 3 altruistes.
Resoudre le clearing (cardinalite max).
Retirer les paires resolues du pool.
Re-resoudre.
Comparer la cardinalite cumulee vs une seule resolution sur le pool initial.
Pourquoi
C’est la difference entre optimisation et performativite algorithmique. Une seule execution du solveur donne le maximum local. Plusieurs executions successives revelent que le pool evolue, et la strategie optimale change. C’est le modele “reactive market” (Hardt, Mendler-Dunner, Paprott, Recht 2023).
Indication
Reutiliser les fonctions precedentes. Stocker l’historique des matchings pour visualiser la trajectoire.
# Exercice 4 (Bonus) — Performativite et reactions des agents.# TODO etudiant : implementer une simulation iterative ou chaque pas retire les paires# resolues du pool, et le solveur re-applique sur le pool residuel.def simulation_performative(paires_init, altruistes_init, n_rounds=3):"""Simule n_rounds de clearing successifs. A chaque round, les paires resolues sont retirees. Returns: list[int] : cardinalite resolue a chaque round. """ historique = []# TODO etudiantreturn historiqueprint('Exercice 4 (Bonus) a completer : simulation performative.')print('Indication : pool_init -> solveur -> retirer resolues -> re-resoudre sur residu.')print('Comparer cardinalite cumulee vs cardinalite d\'une seule resolution sur pool initial.')
Exercice 4 (Bonus) a completer : simulation performative.
Indication : pool_init -> solveur -> retirer resolues -> re-resoudre sur residu.
Comparer cardinalite cumulee vs cardinalite d'une seule resolution sur pool initial.
Resume
Ce notebook a presente le kidney exchange problem comme cas-type d’un schema transversal :
Section 1 — Graphe de compatibilite + cycles : la structure de base (Roth-Sonmez-Unver 2007). Implementation directe par networkx.DiGraph + enumeration de cycles <= k. Test sur 6 paires synthetiques.
Section 2 — Chaines par altruistes : un donneur altruiste demarre une chaine qui couvre plus de paires qu’un cycle ferme. La borne pratique (longueur 3-5) vient des contraintes du monde (preservation, defaillance logistique, disponibilite des blocs).
Section 3 — Lecture directe des sources : verification structurelle du namespace game_theory_lean/CooperativeGames/ (lemmas, defs, proprete axiomatique) sans lake env lean dans le notebook.
Section 4 — Arbitrage cardinalite vs equite : deux programmes lineaires (max cardinalite, max cardinalite + contrainte d’equite par sous-groupe). Demonstration de la dissociation : ameliorer l’equite peut degrader la cardinalite.
Section 5 — Pont cross-domain : le meme pattern (combinatoire + boucle performative + contrainte exogene + arbitrage cardinalite/equite) apparait dans smart contracts, marches de carbone, affectation hospitaliere (NRMP/Gale-Shapley). Le rein echange est un cas pedagogiquement riche parce qu’il est deploye dans le monde reel, pas simule.
Verdict SOTA : networkx, pulp, lecture directe des sources Lean (regex balanced, sans kernel Lean). Pas de reimplementation jouet. La theorie sous-jacente (cooperative games, core, stable matching) est referencee, pas redemontree.
Donnees : toujours synthetiques (Roth-Sonmez-Unver 2007 calibration). Pas de patient. Pas de PII.
References
Issue #12240 - Parent GameTheory-16d: « L’echange de reins : de la valeur humaine a l’etat institutionnel » (issue-source de ce notebook).
EPIC #12208 - Chantier 5 (Distillation par les series pedagogiques) — pere.
EPIC #12207 - Chantier 4 (GameTheory, les jeux comme objets) — grand-pere.
cooperative_games/core.py (MyIA.AI.Notebooks/GameTheory/cooperative_games/) - implementation Python du coeur d’un jeu cooperatif (Shapley, Gillies). Notion cle : v(S) pour chaque coalition S.
cooperative_games/stable_marriage.py - Gale-Shapley 1962, stable matching a grande echelle.
game_theory_lean/CooperativeGames/ (MyIA.AI.Notebooks/GameTheory/) - formalisation Lean. Inventaire verifie via regex balanced dans code 3.1 du notebook.
GameTheory-15b-Lean-CooperativeGames-Lean.ipynb - side track Lean, formalisation directe des theoremes Shapley + core.
Roth, Sonmez, Unver (2007) - “Efficient Kidney Exchange: Coincidence of Wants in a Structured Market”, American Economic Review 97(3): 828-851. Article fondateur du kidney exchange formalise.
Dickerson, Manlove et al. (2021) - “Kidney Exchange and Liver Transplantation”, Chapter in Algorithms for Optimization and Decision Making.
Hardt, Mendler-Dunner, Paprott, Recht (2023) - “Performative Prediction”, ICML. Modele “reactive market” qui distingue optimisation d’une seule passe vs simulation performative iterative.