GameTheory-16c : La dimension paiement que le designer n’a jamais cherchée — extraction de revenu sous DSIC+IR au premier meilleur

GT-16b a posé le triplet de l’automated mechanism design sur un domaine jouet : un générateur qui énumère et choisit, un vérificateur indépendant qui contrôle DSIC et IR, un témoin d’impossibilité. Mais son générateur a un aveugle : il n’énumère que les issues — les paiements sont codés en dur à zéro. Et son témoin d’impossibilité, qui condamne les paiements strictement positifs, prouve son énoncé via un agent de type 0… alors que le vérificateur du notebook checke l’IR sur les types vrais de l’instance — sur l’instance où les deux agents sont de type 1, l’argument du témoin ne tire jamais.

Cette variante -c remet la dimension paiement dans l’énumération et mesure les deux écarts. Premier écart, la table : sur l’instance (1,1), 47 mécanismes DSIC+IR existent, dont 29 à bien-être optimal avec revenu strictement positif — le designer committé en atteint zéro. La forme close du revenu maximal est lisible : Σθᵢ. Deuxième écart, la couture de lectures : sous l’IR ex-interim que la preuve du témoin présuppose (tout type pourrait se présenter), les paiements ≡ 0 ne sont pas un choix mais un théorème — sous l’IR point-prior que le vérificateur implémente, un mécanisme à paiement uniforme survit sur (1,1) et extrait tout le surplus. Les 29 mécanismes à revenu positif vivent uniquement d’un côté de la couture.

Références : GT-16b (GameTheory-16b-Automated-Mechanism-Design-Python.ipynb, issues #12211/#12259) · Conitzer & Sandholm (2002), Automated Mechanism Design · Crémer & McLean (1988), parenté de l’extraction à prior corrélé. Epic de maturation #12208 (stage 2, issue #13188).

Objectifs d’apprentissage

  1. Lire un espace de recherche : repérer que le générateur de GT-16b n’énumère que les issues et que ses paiements ≡ 0 sont un choix de design — designer dans un sous-espace et le nommer.
  2. Énumérer l’espace complet : 2⁴ issues × tables de paiement {0,1} — 4096 candidats — filtrés par le même vérificateur indépendant (copie locale, zéro import), et mesurer la frontière revenu / bien-être sur les 4 instances point-prior.
  3. Exhiber le mécanisme extrateur et le faire vérifier cellule par cellule — DSIC, IR, bien-être, revenu — par l’organe hérité de GT-16b.
  4. Lire une preuve d’impossibilité dans sa sémantique : le témoin de GT-16b est vrai — et même renforcé — en lecture ex-interim, faux sur (1,1) en lecture point-prior ; localiser la couture entre les deux et la mesurer des deux côtés.
  5. Écrire les bornes honnêtes : forme close du revenu (Σθᵢ), lien Crémer-McLean (extraction complète = propriété du prior ponctuel), ce que le jouet ne dit pas hors prior ponctuel.

1. Ce que le designer committé designe vraiment

Le domaine de GT-16b : 2 agents, types θ ∈ {0,1}, issue o ∈ {0,1}, paiements ∈ {0,1}. Un mécanisme est un couple de tables : issue(r) ∈ {0,1} et paiement(r) ∈ {0,1}² pour chacun des 4 profils de reports r. L’espace COMPLET des mécanismes compte 2⁴ × 4⁴ = 4096 candidats. Le générateur de GT-16b n’en visite que 2⁴ = 16 : il énumère les issues, prend l’argmax de bien-être, puis fixe tous les paiements à zéro (« les paiements minimaux qui satisfont trivialement IR », dit son commentaire). Le choix est défendable — mais c’est un choix : l’utilité quasi-linéaire uᵢ = θᵢ·issue − paiementᵢ rend les transferts neutres pour le bien-être J = Σθᵢ·issue, donc ignorer les paiements ne coûte rien au critère optimisé… et coûte tout au seul autre critère naturel, le revenu.

Reproduisons d’abord le designer committé sur l’instance true = (1,1) — le point-prior où les deux agents sont de type 1.

import itertools

PROFILES = [(0, 0), (0, 1), (1, 0), (1, 1)]   # profils de reports (2 agents, 2 types)
N_AGENTS = 2
PAY_RANGE = (0, 1)

# === Reproduction du designer GT-16b : issues par argmax, paiements ~ 0 ===
def generate_gt16b(true_types):
    """Espace visite : les 16 tables d'issues. Paiements codes a zero."""
    best_J, best_issue = -1, None
    for issue_choice in itertools.product([0, 1], repeat=len(PROFILES)):
        issue_table = dict(zip(PROFILES, issue_choice))
        J = sum(true_types[i] * issue_table[tuple(true_types)] for i in range(N_AGENTS))
        if J > best_J:
            best_J, best_issue = J, issue_choice
    payment_table = {p: (0,) * N_AGENTS for p in PROFILES}
    return dict(zip(PROFILES, best_issue)), payment_table, best_J

TRUE_11 = (1, 1)
issue_16b, pay_16b, J_16b = generate_gt16b(TRUE_11)
revenue_16b = sum(pay_16b[tuple(TRUE_11)])
print(f"Instance point-prior : true = {TRUE_11}")
print(f"Designer GT-16b -> issue((1,1)) = {issue_16b[(1,1)]}, paiements ~ 0 partout")
print(f"Bien-etre J = {J_16b} (premier meilleur)   Revenu = {revenue_16b}")
print()
print(f"Espace visite par le generateur : {2**len(PROFILES)} tables d'issues")
print(f"Espace complet des mecanismes   : {2**len(PROFILES)} x {4**len(PROFILES)} = "
      f"{2**len(PROFILES) * 4**len(PROFILES)} candidats")
Instance point-prior : true = (1, 1)
Designer GT-16b -> issue((1,1)) = 1, paiements ~ 0 partout
Bien-etre J = 2 (premier meilleur)   Revenu = 0

Espace visite par le generateur : 16 tables d'issues
Espace complet des mecanismes   : 16 x 256 = 4096 candidats

Lecture de la sortie committée : le designer atteint le premier meilleur (J = 2 : l’issue vaut 1 au profil vrai, chaque agent de type 1 en tire 1) avec un revenu nul. Les deux nombres de la dernière ligne disent tout : le générateur visite 16 candidats sur 4096 — 0,4 % de l’espace des mécanismes. Rien dans le domaine n’impose ce choix : IR se satisfait aussi avec des paiements positifs, et DSIC se vérifie sur n’importe quelle table. La question de la section 2 est donc : que contiennent les 99,6 % restants ?

2. L’énumération conjointe — le vérificateur hérité tranche

On hérite l’organe de GT-16b : son vérificateur indépendant, en copie locale, zéro import du générateur — mêmes définitions de l’utilité quasi-linéaire, de DSIC (aucune déviation unilatérale strictement profitable, pour chaque agent et chaque profil reporté) et d’IR (utilité ≥ 0 pour chaque agent et chaque profil, aux types vrais — la sémantique exacte de verify_IR de GT-16b). Puis on énumère les 4096 candidats de l’espace complet, et on compte par instance point-prior : les admissibles (DSIC ∧ IR), parmi eux les à bien-être optimal, parmi ceux-ci les à revenu strictement positif, et le revenu maximal.

# === Verificateur herite de GT-16b (copie locale, zero import du generateur) ===
def verif_utility_i(theta_i, issue):
    """Utilite grossiere (hors paiement) — copie locale de verify_utility_i."""
    return theta_i * issue

def verif_dsic(M, true_types):
    """Aucune deviation unilaterale strictement profitable, chaque agent, chaque profil."""
    issue_table, payment_table = M
    for r in PROFILES:
        for i in range(N_AGENTS):
            u_sincere = verif_utility_i(true_types[i], issue_table[r]) - payment_table[r][i]
            for theta_dev in (0, 1):
                r_dev = list(r); r_dev[i] = theta_dev; r_dev = tuple(r_dev)
                u_dev = verif_utility_i(true_types[i], issue_table[r_dev]) - payment_table[r_dev][i]
                if u_dev > u_sincere + 1e-9:
                    return False, f"DSIC fail: agent {i} prefere {r_dev} a {r}"
    return True, "DSIC OK"

def verif_ir(M, true_types):
    """Utilite >= 0 pour chaque agent et chaque profil, AUX TYPES VRAIS (semantique GT-16b)."""
    issue_table, payment_table = M
    for r in PROFILES:
        for i, theta_i in enumerate(true_types):
            u = verif_utility_i(theta_i, issue_table[r]) - payment_table[r][i]
            if u < -1e-9:
                return False, f"IR fail: agent {i} u={u} en profil {r}"
    return True, "IR OK"

def verif_welfare(M, true_types):
    issue_table, _ = M
    return sum(verif_utility_i(theta_i, issue_table[tuple(true_types)])
               for i, theta_i in enumerate(true_types))

def verif_revenue(M, true_types):
    """Revenu collecte au profil vrai (DSIC => report sincere)."""
    _, payment_table = M
    return sum(payment_table[tuple(true_types)])

def enumerer_tous():
    """Espace COMPLET : 4096 candidats (issue, paiement)."""
    for issue_choice in itertools.product([0, 1], repeat=len(PROFILES)):
        it = dict(zip(PROFILES, issue_choice))
        for pay_choice in itertools.product(itertools.product(PAY_RANGE, repeat=N_AGENTS),
                                            repeat=len(PROFILES)):
            yield it, dict(zip(PROFILES, pay_choice))

print(f"{'instance':>10} {'admissibles':>12} {'welfare-opt':>12} {'dont revenu>0':>14} {'max rev@fb':>11}")
print("-" * 66)
FRONTIERE = {}
for true in PROFILES:
    fb = sum(true)
    n_adm = n_fb = n_pos = 0
    best_rev = -1
    for M in enumerer_tous():
        if verif_dsic(M, true)[0] and verif_ir(M, true)[0]:
            n_adm += 1
            if verif_welfare(M, true) == fb:
                n_fb += 1
                rev = verif_revenue(M, true)
                if rev > 0:
                    n_pos += 1
                if rev > best_rev:
                    best_rev = rev
    FRONTIERE[true] = (n_adm, n_fb, n_pos, best_rev)
    print(f"{str(true):>10} {n_adm:>12} {n_fb:>12} {n_pos:>14} {best_rev:>11}")
  instance  admissibles  welfare-opt  dont revenu>0  max rev@fb
------------------------------------------------------------------
    (0, 0)           16           16              0           0
    (0, 1)           25           15             10           1
    (1, 0)           25           15             10           1
    (1, 1)           47           34             29           2

Lecture de la sortie committée : la colonne qui condamne l’effondrement est la dernière. Sur (1,1) : 47 mécanismes DSIC+IR, dont 34 à bien-être optimal (issue((1,1)) = 1), parmi lesquels 29 à revenu strictement positif, pour un revenu maximal de 2. Le designer committé (paiements ≡ 0) était admissible et optimal en bien-être — mais il laisse 2/2 = 100 % du revenu atteignable sur la table. La ligne (0,0) est le contre-point structurel : tous les types nuls ⇒ 16 admissibles, tous à bien-être « optimal » (fb = 0), aucun à revenu positif — IR force paiementᵢ = 0 pour tout agent de type 0 (son utilité est −paiementᵢ, indépendante de l’issue). Et la forme close se lit dans la dernière colonne : max revenu @ premier meilleur = Σθᵢ — 2, 1, 1, 0.

3. Le mécanisme extrateur — exhibé et vérifié par l’organe hérité

L’argmax revenu au premier meilleur sur (1,1) est lisible à l’œil dans l’énumération : issue = 1 uniquement au profil (1,1) (le bien-être du point-prior ne regarde que le profil vrai), chaque agent paie 1 au profil (1,1) — sa pleine valeur — et tout le reste à zéro. La logique : IR est serré à l’indifférence pour les types vrais (uᵢ = 1·1 − 1 = 0), et DSIC tient par indifférence faible — toute déviation mène à un profil où l’issue est 0 et le paiement 0, d’utilité 0, jamais strictement mieux que 0. C’est la discrimination parfaite du point-prior : le designer connaît les types, il facture exactement la valeur.

# === Le mecanisme extracteur, construit puis VERIFIE par l'organe herite ===
M_extracteur = (
    {(0, 0): 0, (0, 1): 0, (1, 0): 0, (1, 1): 1},          # issue = 1 seulement au profil vrai
    {(0, 0): (0, 0), (0, 1): (0, 0), (1, 0): (0, 0), (1, 1): (1, 1)},  # pleine valeur au profil vrai
)

ok_dsic, msg_dsic = verif_dsic(M_extracteur, TRUE_11)
ok_ir, msg_ir = verif_ir(M_extracteur, TRUE_11)
print("Mechanisme extracteur sur true = (1,1), verifie par le meme organe que GT-16b :")
print(f"  DSIC : {ok_dsic}  ({msg_dsic})")
print(f"  IR   : {ok_ir}  ({msg_ir})")
print(f"  Bien-etre : {verif_welfare(M_extracteur, TRUE_11)}  (premier meilleur = {sum(TRUE_11)})")
print(f"  Revenu    : {verif_revenue(M_extracteur, TRUE_11)}  (max de la frontiere)")
print()
# Le detail DSIC : pourquoi aucune deviation n'est strictement profitable
issue_t, pay_t = M_extracteur
print("Pourquoi DSIC tient (agent 1, profil sincere (1,1)) :")
u_sincere = verif_utility_i(1, issue_t[(1, 1)]) - pay_t[(1, 1)][0]
u_dev = verif_utility_i(1, issue_t[(0, 1)]) - pay_t[(0, 1)][0]
print(f"  sincere        : u = 1*{issue_t[(1,1)]} - {pay_t[(1,1)][0]} = {u_sincere}")
print(f"  devier (->0)   : u = 1*{issue_t[(0,1)]} - {pay_t[(0,1)][0]} = {u_dev}  (jamais > sincere)")
print()
print(f"Contre-temoin au designer GT-16b : bien-etre identique ({verif_welfare(M_extracteur, TRUE_11)} = J du designer),")
print(f"revenu {verif_revenue(M_extracteur, TRUE_11)} vs 0 : l'effondrement paiements ~ 0 coutait 100% du revenu.")
Mechanisme extracteur sur true = (1,1), verifie par le meme organe que GT-16b :
  DSIC : True  (DSIC OK)
  IR   : True  (IR OK)
  Bien-etre : 2  (premier meilleur = 2)
  Revenu    : 2  (max de la frontiere)

Pourquoi DSIC tient (agent 1, profil sincere (1,1)) :
  sincere        : u = 1*1 - 1 = 0
  devier (->0)   : u = 1*0 - 0 = 0  (jamais > sincere)

Contre-temoin au designer GT-16b : bien-etre identique (2 = J du designer),
revenu 2 vs 0 : l'effondrement paiements ~ 0 coutait 100% du revenu.

Lecture de la sortie committée : le mécanisme extrateur passe les quatre contrôles de l’organe hérité — DSIC, IR, bien-être au premier meilleur, revenu maximal. Le détail de la déviation montre la structure : l’agent sincère est à utilité 0 (IR serré), la déviation lui donne 0 — l’indifférence faible suffit à DSIC, qui n’exige que l’absence de déviation strictement profitable. La lecture économique est honnête et bornée : c’est l’extraction complète à prior ponctuel — le designer connaît les types vrais et designe pour cette seule instance, la limite dégénérée de la famille Crémer-McLean (extraction de tout le surplus quand la corrélation du prior est totale — ici, un point). Hors prior ponctuel, avec des types distribués, le problème devient la vraie AMD de Conitzer-Sandholm et cette garantie disparaît : question ouverte, pas une claim du jouet.

4. La couture du témoin d’impossibilité — deux lectures d’IR qui ne se rencontrent pas

Le témoin de GT-16b démontre : DSIC ∧ IR ∧ (∀r, ∀i : paiementᵢ(r) ≥ 1) ⇒ ensemble vide. Sa preuve : pour un agent de type 0, uᵢ = −paiementᵢ ≤ −1 < 0, IR violée. Relisez le vérificateur de la section 2 : verif_ir évalue l’utilité aux types vrais de l’instance. L’argument du témoin ne tire que si un agent de type 0 existe dans l’instance. Sur (1,1) il n’existe pas — la preuve est vide, et la question devient empirique : existe-t-il un mécanisme à paiement uniforme ≥ 1 admissible sur (1,1) ?

Les deux lectures d’IR méritent d’être nommées, car le jouet les mélange sans le dire :

  • IR point-prior (ce que verify_IR de GT-16b implémente, et donc tout son notebook exécute) : uᵢ ≥ 0 pour les types vrais — le designer sait qui est là.
  • IR ex-interim (ce que la preuve du témoin présuppose : « tout type pourrait se présenter ») : uᵢ ≥ 0 pour chaque type possible de chaque agent — le designer ne sait pas qui va se présenter.

On mesure les trois côtés de la couture : le témoin reproduit là où son agent de type 0 existe, son contre-témoin sur (1,1), et la ligne d’arrivée ex-interim complète.

# === Cote 1 : le temoin, reproduit la ou son agent de type 0 existe ===
def enumerer_uniformes():
    """Candidats avec paiement >= 1 PARTOUT (la contrainte du temoin GT-16b)."""
    for issue_choice in itertools.product([0, 1], repeat=len(PROFILES)):
        it = dict(zip(PROFILES, issue_choice))
        for pay_choice in itertools.product(itertools.product((1, 2), repeat=N_AGENTS),
                                            repeat=len(PROFILES)):
            yield it, dict(zip(PROFILES, pay_choice))

print("Temoin GT-16b (paiement uniforme >= 1), IR point-prior, instance par instance :")
for true in PROFILES:
    n = sum(1 for M in enumerer_uniformes()
            if verif_dsic(M, true)[0] and verif_ir(M, true)[0])
    verdict = "VIDE - temoin VRAI (un agent de type 0 existe)" if n == 0 else f"NON VIDE : {n} survivant(s)"
    print(f"  true={true} : admissibles = {n}  -> {verdict}")

# === Cote 2 : le contre-temoin sur (1,1) ===
M_survivant = ({p: 1 for p in PROFILES}, {p: (1, 1) for p in PROFILES})   # issue ~ 1, pay ~ (1,1)
print()
print("Le survivant uniforme sur (1,1), exhibe et verifie :")
print(f"  DSIC : {verif_dsic(M_survivant, TRUE_11)[0]}   IR point-prior : {verif_ir(M_survivant, TRUE_11)[0]}")
print(f"  Bien-etre : {verif_welfare(M_survivant, TRUE_11)}   Revenu : {verif_revenue(M_survivant, TRUE_11)}"
      "  (extraction complete)")

# === Cote 3 : la ligne d'arrivee ex-interim ===
def verif_ir_exinterim(M):
    """Tout type possible pourrait se presenter : u >= 0 pour chaque theta de chaque agent."""
    issue_table, payment_table = M
    for r in PROFILES:
        for i in range(N_AGENTS):
            for theta in (0, 1):
                if verif_utility_i(theta, issue_table[r]) - payment_table[r][i] < -1e-9:
                    return False
    return True

n_ex = 0
rev_ex = set()
avec_paiement_non_nul = 0
for M in enumerer_tous():
    if verif_ir_exinterim(M) and verif_dsic(M, TRUE_11)[0]:
        n_ex += 1
        rev_ex.add(verif_revenue(M, TRUE_11))
        if any(v != (0, 0) for v in M[1].values()):
            avec_paiement_non_nul += 1
print()
print("Lecture ex-interim (celle de la preuve du temoin) sur (1,1) :")
print(f"  admissibles DSIC + IR ex-interim = {n_ex}, dont un paiement non nul = {avec_paiement_non_nul}")
print(f"  revenus possibles = {sorted(rev_ex)}")
print("  -> sous ex-interim, paiements ~ 0 est un THEOREME (theta=0 force p=0 partout)")
Temoin GT-16b (paiement uniforme >= 1), IR point-prior, instance par instance :
  true=(0, 0) : admissibles = 0  -> VIDE - temoin VRAI (un agent de type 0 existe)
  true=(0, 1) : admissibles = 0  -> VIDE - temoin VRAI (un agent de type 0 existe)
  true=(1, 0) : admissibles = 0  -> VIDE - temoin VRAI (un agent de type 0 existe)
  true=(1, 1) : admissibles = 1  -> NON VIDE : 1 survivant(s)

Le survivant uniforme sur (1,1), exhibe et verifie :
  DSIC : True   IR point-prior : True
  Bien-etre : 2   Revenu : 2  (extraction complete)

Lecture ex-interim (celle de la preuve du temoin) sur (1,1) :
  admissibles DSIC + IR ex-interim = 2, dont un paiement non nul = 0
  revenus possibles = [0]
  -> sous ex-interim, paiements ~ 0 est un THEOREME (theta=0 force p=0 partout)

Lecture de la sortie committée : les trois côtés coexistent sans contradiction — mais ils requalifient l’énoncé de GT-16b. (1) Le témoin est vrai sur les trois instances qui contiennent un agent de type 0 : la contrainte uniforme y produit un ensemble vide, sa preuve tire exactement là où elle le prétend. (2) Sur (1,1), le contre-témoin existe : issue ≡ 1, paiements ≡ (1,1) passe DSIC et IR point-prior et extrait le revenu maximal 2 — un mécanisme à paiement uniforme et à extraction complète. La conclusion imprimée par GT-16b (« l’ensemble des mécanismes admissibles est VIDE ») est, en sémantique point-prior, une sur-généralisation : vraie instance par instance, sauf sur celle qui intéresse le plus le vendeur. (3) En lecture ex-interim, tout s’inverse : θ = 0 force pᵢ(r) = 0 pour tout r — aucun paiement positif n’est possible, l’effondrement de paiements ≡ 0 n’était pas un choix de design mais un théorème, et le témoin est vrai et renforcé (il condamnait l’uniforme ; la lecture ex-interim condamne tout paiement). La couture est le résultat central de la -c : la preuve du témoin raisonne ex-interim, le vérificateur checke point-prior, et les 29 mécanismes à revenu positif vivent uniquement du côté où la preuve ne s’applique pas.

5. Verdict — ce que l’effondrement coûte, ce qui survit

Question Réponse mesurée Statut
Le designer GT-16b était-il admissible ? Oui — DSIC ✓, IR ✓, bien-être premier meilleur ✓ survit
Son bien-être était-il optimal ? Oui — les transferts sont neutres pour J = Σθᵢ·issue survit
Son revenu ? 0, contre un maximum de Σθᵢ — 100 % du revenu atteignable laissé sur la table sur chaque instance à types 1 cède (le critère ignoré)
Le témoin d’impossibilité ? Vrai là où un agent de type 0 existe (3 instances sur 4) ; contredit sur (1,1) en point-prior (1 survivant uniforme, extraction complète) ; vrai et renforcé en ex-interim (tout paiement positif impossible) survit borné — portée réécrite, couture localisée
Forme close du revenu maximal @ premier meilleur ? Σθᵢ — les 4 instances la vérifient (2, 1, 1, 0) acquis

Le bilan de maturation est le même que pour GT-18b : le jouet survit borné. Aucun énoncé vérifié de GT-16b n’était faux — mais le générateur designait dans 0,4 % de l’espace des mécanismes, et le témoin bornait une contrainte que sa propre sémantique d’exécution n’impose pas sur l’instance la plus favorable. La -c ajoute la dimension manquante : la frontière revenu/bien-être complète, le mécanisme extrateur vérifié par l’organe hérité, et la localisation exacte de la couture point-prior / ex-interim.

Questions ouvertes — ce que ce jouet ne dit pas

  • Hors prior ponctuel. L’extraction complète tient parce que le designer connaît les types vrais avec certitude. Avec un prior distribué (même indépendant, même à 2 types), la contrainte DSIC devient liante et le revenu maximal exige la vraie machinerie AMD (énumération sur les distributions, pas sur les instances). La forme close Σθᵢ est une propriété du point-prior, pas du problème.
  • Le budget. Le jouet n’a pas de coût d’issue (proviser l’issue 1 est gratuite). Avec un coût c, la question devient : le revenu extrayable finance-t-il la provision ? — la vraie structure du problème du bien public, et le théorème de Green-Laffont entre par cette porte.
  • L’indifférence faible. DSIC est satisfait par indifférence (u = 0 partout pour les types vrais de l’extrateur). En pratique, un agent exactement indifférent peut dévier pour un dixième de raison ; la variante stricte (DSIC strict) vide probablement une partie de la frontière — mesurable dans le même jouet, non mesurée ici (exercice 3).

Exercice 1 : l’instance (0,0) est une forteresse

La table de la section 2 montre 16 mécanismes admissibles sur (0,0) et aucun à revenu positif. Démontrez-le proprement : pour chaque agent de type 0, écrivez la contrainte IR point-prior et montrez qu’elle force paiementᵢ(r) = 0 pour tout profil r — indépendamment de l’issue. Concluez : le revenu maximal d’une instance est nul dès que tous les types sont nuls, et la forme close Σθᵢ est cohérente. Vérifiez enfin votre preuve par énumération sur les deux autres instances à agent de type 0 : leur revenu ne peut venir que de l’agent intéressé.

# Exercice 1 a completer
# 1. Pour true = (0,0) : ecrire la contrainte IR d'un agent de type 0 (u_i = 0*issue - p_i)
# 2. En deduire p_i(r) = 0 pour tout r, puis revenu = 0 pour TOUT mecanisme admissible
# 3. Verifier : FRONTIERE[(0,0)][2] == 0 et FRONTIERE[(0,0)][3] == 0 ; puis (0,1) : revenu <= 1
# Indice : u_i = -p_i(r) >= 0 et p_i(r) dans {0,1} => p_i(r) = 0
print("Exercice a completer")
resultat_ex1 = None  # TODO etudiant : preuve_et_verification = ...
Exercice a completer

Exercice 2 : élargir la gamme des paiements

Toute la -c utilise des paiements ∈ {0, 1}. Sur l’instance (1,1), élargissez à {0, 1, 2} et relancez l’énumération conjointe (l’espace croît à 2⁴ × 9⁴ — reste trivial). Écrivez d’abord la borne : IR point-prior pour un agent de type 1 exige paiementᵢ(r) ≤ issue(r) ≤ 1 — le revenu au profil vrai est donc plafonné à 2, quelle que soit la gamme. Confirmez par l’énumération, puis observez ce que la gamme étendue ne change PAS : le bien-être J ne compte pas les paiements — dites ce que ça révèle de la définition du bien-être du jouet (un transfert de l’agent au designer y est invisible : ni coût, ni benefice social).

# Exercice 2 a completer
# 1. Prediction ecrite AVANT : max revenu @ fb sur (1,1) avec paiements dans {0,1,2} = ?
# 2. Enumerer (issues 2^4) x (paiements {0,1,2}^(2*4)) avec le meme verificateur
# 3. Comparer au max = 2 : la borne vient de IR (p_i <= issue <= 1), pas de la gamme
# 4. Bonus : J change-t-il avec les paiements ? (J ne compte que les utilites grossieres)
# Indice : pour l'agent i de type 1, IR en r exige 1*issue(r) - p_i(r) >= 0, et issue(r) <= 1
print("Exercice a completer")
resultat_ex2 = None  # TODO etudiant : max_revenu_gamme_etendue = ...
Exercice a completer

Exercice 3 : DSIC strict

L’extrateur satisfait DSIC par indifférence faible (u sincère = u déviation = 0). Construisez la variante stricte : un mécanisme est DSIC-strict si toute déviation est strictement moins bien (u sincère > u déviation). Attention au domaine : utilités et paiements entiers ⇒ les écarts sont entiers — réfléchissez à ce qu’un « strict » peut discriminer ici. Parmi les 29 mécanismes à revenu positif de (1,1), combien survivent au DSIC strict ? Le revenu maximal change-t-il ? Et le survivant uniforme de la section 4 (issue ≡ 1, paiements ≡ (1,1)) — que devient-il ? Concluez sur la robustesse de l’extraction : faut-il l’indifférence pour extraire, ou peut-on extraire en interdisant même les déviations neutres ?

# Exercice 3 a completer
# 1. Definir verif_dsic_strict(M, true) : u_sincere > u_dev pour toute deviation
# 2. Re-enumerer l'espace complet sur (1,1) : compter les DSIC-strict + IR a welfare optimal
# 3. Max revenu sous DSIC strict vs 2 (faible) ; et le survivant uniforme de la section 4 ?
# Indice : sur ce domaine, les ecarts d'utilite sont entiers -- l'egalite exacte est le seul cas filtre
print("Exercice a completer")
resultat_ex3 = None  # TODO etudiant : max_revenu_dsic_strict = ...
Exercice a completer

Conclusion et perspectives

GT-16b avait construit l’organe juste — un vérificateur indépendant qui tranche sans importer le générateur — et l’avait arrêté à mi-chemin de son propre espace. Quatre acquis :

  1. La mesure de l’effondrement : le générateur visitait 16 candidats sur 4096 ; en réparant, 29 mécanismes à bien-être optimal ET à revenu positif existent sur (1,1) — l’ignorance des paiements coûtait 100 % du revenu, pas une marge.
  2. La forme close : revenu maximal au premier meilleur = Σθᵢ, atteint par le mécanisme extrateur — pleine valeur facturée aux agents intéressés au profil vrai, IR serré, DSIC par indifférence. Une instance, pas un théorème général : l’extraction complète est la propriété du prior ponctuel.
  3. La couture localisée : la preuve du témoin raisonne ex-interim, le vérificateur checke point-prior. Sur les instances à agent de type 0 les lectures s’accordent (témoin vrai) ; sur (1,1) elles divergent — 29 mécanismes à revenu positif d’un côté, paiements ≡ 0 en théorème de l’autre. Une impossibilité sans contre-témoin surnomme sa contrainte ; avec contre-témoin, elle en montre la bordure.
  4. La méthode : le même geste s’applique à chaque designer borné — énumérer l’espace qu’il visite, l’espace complet, mesurer l’écart sur tous les critères du problème (pas seulement celui qu’il optimise), et nommer la sémantique exacte dans laquelle chaque preuve raisonne.

Perspectives immédiates dans le même jouet : le coût d’issue nul (le bien public de Green-Laffont), le DSIC strict de l’exercice 3, et la sortie du prior ponctuel — la vraie AMD où ces 4096 candidats deviennent des familles indexées par les distributions.

Retour au sommet