Navigation : GameTheory-09b-Commitment-Stackelberg-Python — engagement crédible · Sommaire GameTheory
GT-9b a montré qu’engager une action sous-optimale peut être l’optimum du leader dans un Stackelberg. Mais GT-9b se limite à une cible unique : l’incumbent choisit une action et l’entrant une réponse.
En sécurité (aéroports, parcs, réseaux), le défenseur alloue des ressources limitées sur plusieurs cibles, et l’attaquant choisit la cible à frapper après avoir observé le déploiement. Le bon modèle est le Stackelberg security game (Tambe 2011, Bondi et al. 2019). Deux complications ajoutées par Bondi et al. :
p_fn qu’une attaque réelle passe inaperçue).Ces deux ingrédients font que la stratégie ignorant l’incertitude peut être strictement moins bonne que de ne rien déployer du tout (Bondi et al., §4.3) — résultat spécifique à leur instance, à reproduire comme comparaison et non comme théorème universel.
Une instance Stackelberg security game avec : - un graphe de cibles T (3 cibles, valeurs hétérogènes) ; - R ressources défenseur à allouer (patrouilles) ; - un capteur imparfait (probabilité de détection p_d ; faux négatifs p_fn) ; - une réaction optionnelle du défenseur à l’alerte (coût + bénéfice) ; - paiements défenseur/attaquant pour chaque cible (succès/échec attaque, succès/échec défense).
Solveur exact : pour la petite instance (3 cibles), énumération des allocations (C(3,0) + C(3,1) + C(3,2) = 7 cas) + meilleure réponse du follower (tie-breaking SSE = Strong-Stackelberg Equilibrium).
Comparaisons (4 stratégies) : 1. NO-RES : pas de déploiement (baseline). 2. DET-SDP : SDP classique (Tambe 2011), ignorant l’incertitude du capteur. 3. UNC-PESS : variante pessimiste (utilise react=False partout). 4. UNC-OPT : intègre l’incertitude (réaction optimale espérée).
Sweep p_fn (taux de faux négatifs) : montre quand le capteur aide ou nuit.
Raccord pédagogique GT-9b : on prolonge le leader engage, follower observe en leader alloue sur un graphe, follower choisit la cible après observation, et on garde le vocabulaire de l’engagement crédible — la stratégie du défenseur est annoncée (commit), pas révocable (le follower la voit, contrairement à GT-9b §10 où l’annonce était révocable).
# Imports et utilitaires
import itertools
import random
from typing import Dict, List, Tuple
import numpy as np
random.seed(42)
np.random.seed(42)
try:
import pulp
HAS_PULP = True
print("pulp disponible -- MILP possible si >|T|")
except ImportError:
HAS_PULP = False
print("WARN: pulp absent, enumeration pure (suffit pour 3 cibles)")pulp disponible -- MILP possible si >|T|Trois cibles T0, T1, T2 de valeurs défense v_d et attaque v_a hétérogènes. La cible T1 est plus précieuse pour l’attaquant que T0 (paradoxe classique des SSG). Le défenseur dispose de R=2 unités de patrouille, chaque cible nécessitant 0 ou 1 patrouille pour être couverte.
Capteur : un signal s ∈ {0, 1} est observé par le défenseur après l’attaque. - Avec probabilité p_d (vrai positif) le capteur détecte correctement une attaque qui touche une cible couverte. - Avec probabilité p_fn = 1 - p_d (faux négatif) le capteur rate une attaque même couverte. - Pas de faux positifs ici (hypothèse de Bondi et al. §4.1 — p_fp = 0). Cette hypothèse aura une conséquence structurelle sur le verdict §3 : elle éteint le seul canal par lequel un capteur peut nuire.
Réaction : si le capteur sonne (s=1), le défenseur peut réagir — mobiliser une 3ᵉ unité qui intercepte l’attaque. La sémantique exacte : - l’attaquant est pris : son paiement chute de b_react en plus de sa pénalité de couverture ; - le défenseur sauve la cible : il ne subit plus V_D(t), il ne paie que le coût de mobilisation c_react.
Réagir n’est pas toujours rationnel : sur une cible de faible valeur, c_react dépasse la perte évitée — la décision appartient au défenseur, cible par cible, après le signal (elle est calculée en §1, pas supposée). Sans signal (faux négatif ou cible non couverte), pas de réaction possible.
Paiements (réalisés, hors aléa du capteur — l’espérance est prise au §2) : - Attaquant choisit t ∈ T → U_A = V_A(t), défenseur subit U_D = V_D(t). - Couverture de t (patrouille physiquement présente, que le capteur sonne ou non) : U_D = V_D(t) + cover_bonus ; U_A = V_A(t) − cover_penalty. - Réaction (interception) : U_A = V_A(t) − cover_penalty − b_react ; U_D = −c_react.
# Definition de l'instance (parametrable)
TARGETS = ["T0", "T1", "T2"]
V_D = {"T0": -1.0, "T1": -2.5, "T2": -4.0}
V_A = {"T0": 3.0, "T1": 4.0, "T2": 2.0}
R = 2
COVER_BONUS = 1.5
COVER_PENALTY_A = 1.0
P_D = 0.7
P_FN = 1 - P_D
C_REACT = 0.5
B_REACT = 2.0
print("=== Instance ===")
print(f"Cibles: {TARGETS}")
print(f"Ressources defenseur: R={R}")
print(f"V_D: {V_D}")
print(f"V_A: {V_A}")
print(f"Capteur: p_d={P_D}, p_fn={P_FN}")
print(f"Reaction: c={C_REACT}, b={B_REACT}")=== Instance ===
Cibles: ['T0', 'T1', 'T2']
Ressources defenseur: R=2
V_D: {'T0': -1.0, 'T1': -2.5, 'T2': -4.0}
V_A: {'T0': 3.0, 'T1': 4.0, 'T2': 2.0}
Capteur: p_d=0.7, p_fn=0.30000000000000004
Reaction: c=0.5, b=2.0Notez V_A[T1] = 4 > V_A[T0] = 3 > V_A[T2] = 2. Mais |V_D[T1]| = 2.5 < |V_D[T0]| = 1.0 — attention à la confusion : en fait V_D[T0] = -1 (peu coûteux à perdre), V_D[T1] = -2.5, V_D[T2] = -4 (très coûteux à perdre). Donc T2 est précieux pour le défenseur mais pas pour l’attaquant — couverture prioritaire du défenseur sur T2, et l’attaquant se rabat sur T1, où il est plus rentable qu’il ne serait sur T2 mais moins que sur T0. C’est précisément le paradoxe SSG (Tambe 2011 §2.2).
Avec couverture : V_D[T2] + COVER_BONUS = -4 + 1.5 = -2.5 (perte réduite si couvert). Pour l’attaquant : V_A[T1] - COVER_PENALTY_A = 3 (toujours rentable).
def payoff_attacker(t, covered, react):
"""Paiement ATTAQUANT realise sur t (deterministe -- l'alea du capteur
est pris en esperance par le solveur, pas ici).
covered : patrouille physiquement presente -> penalite COVER_PENALTY_A,
que le capteur sonne ou non. react : interception apres signal ->
l'attaquant est pris, il subit B_REACT en plus.
"""
u = V_A[t] - (COVER_PENALTY_A if covered else 0.0)
if react:
u -= B_REACT
return u
def payoff_defender(t, covered, react):
"""Paiement DEFENSEUR realise sur t.
react : interception -- la cible est sauvee (V_D[t] non subi), seule la
mobilisation C_REACT est payee. Sinon : perte attenuee par la couverture.
"""
if react:
return -C_REACT
return V_D[t] + (COVER_BONUS if covered else 0.0)
def reaction_rationnelle(t):
"""Decision du defenseur, prise APRES un signal realisé sur t couvert :
mobiliser ssi l'interception rapporte plus que de laisser passer,
-C_REACT > V_D[t] + COVER_BONUS
La reaction appartient au DEFENSEUR (pas a l'attaquant) : c'est lui qui
compare SES paiements, cible par cible.
"""
return payoff_defender(t, True, True) > payoff_defender(t, True, False)
POLITIQUE_REACTION = {t: reaction_rationnelle(t) for t in TARGETS}
print("=== Politique de reaction rationnelle (signal recu, cible couverte) ===")
for t in TARGETS:
intercepte = payoff_defender(t, True, True)
laisse = payoff_defender(t, True, False)
print(f" {t}: react = {POLITIQUE_REACTION[t]} "
f"(interception {intercepte:+.2f} vs laisser passer {laisse:+.2f})")
print()
print("=== Paiements REALISES par scenario ===")
print(f"{'cible':>4} | {'scenario':<22} | {'U_A':>6} | {'U_D':>6}")
print("-" * 48)
for t in TARGETS:
scenarios = [
("non couvert, attaque passe", payoff_attacker(t, False, False), payoff_defender(t, False, False)),
("couvert, pas de reaction", payoff_attacker(t, True, False), payoff_defender(t, True, False)),
("couvert, intercepte", payoff_attacker(t, True, True), payoff_defender(t, True, True)),
]
for nom, ua, ud in scenarios:
print(f"{t:>4} | {nom:<22} | {ua:>+6.2f} | {ud:>+6.2f}")=== Politique de reaction rationnelle (signal recu, cible couverte) ===
T0: react = False (interception -0.50 vs laisser passer +0.50)
T1: react = True (interception -0.50 vs laisser passer -1.00)
T2: react = True (interception -0.50 vs laisser passer -2.50)
=== Paiements REALISES par scenario ===
cible | scenario | U_A | U_D
------------------------------------------------
T0 | non couvert, attaque passe | +3.00 | -1.00
T0 | couvert, pas de reaction | +2.00 | +0.50
T0 | couvert, intercepte | +0.00 | -0.50
T1 | non couvert, attaque passe | +4.00 | -2.50
T1 | couvert, pas de reaction | +3.00 | -1.00
T1 | couvert, intercepte | +1.00 | -0.50
T2 | non couvert, attaque passe | +2.00 | -4.00
T2 | couvert, pas de reaction | +1.00 | -2.50
T2 | couvert, intercepte | -1.00 | -0.50Séquence du jeu (l’ordre détermine qui décide quoi) : 1. le défenseur s’engage sur une allocation x ⊆ T, |x| ≤ R (observable — commit, comme GT-9b) ; 2. l’attaquant observe x et choisit t ; 3. si t est couverte : le capteur sonne avec probabilité p_d (sinon, faux négatif, rien) ; 4. sur signal, le défenseur choisit de réagir ou non — c’est sa décision, cible par cible (politique calculée en §1).
Espérances : l’attaquant anticipe la politique de réaction du défenseur et évalue E[U(t | x)] = p_d · U(t | signal, politique de réaction) + p_fn · U(t | pas de signal). Sur cible non couverte, pas de capteur ni de réaction : paiements bruts.
Départage Strong Stackelberg — codé, pas déclaré. L’attaquant choisit t* = argmax_t U_A(t | x) ; à ex æquo, il prend la cible qui maximise U_D (le leader peut induire ce choix — c’est précisément ce qui distingue le Strong du Weak Stackelberg). Dans le solveur : max(ex_aequos, key=U_D). Ce départage n’est pas décoratif : les tables ci-dessous contiennent des ex æquos réels, dont un triple à p_fn = 0,5 — sans lui, le choix reviendrait à l’ordre de déclaration des cibles.
Les 4 stratégies = (croyance sur le capteur, politique de réaction), chacune jouée puis évaluée en espérance réelle (p_d = 0,7) pour être comparable :
| Stratégie | Croyance | Politique de réaction |
|---|---|---|
| NO-RES | pas de capteur | n/a (rien déployé) |
| DET-SDP (Tambe 2011) | capteur parfait (p_d = 1) |
optimale sous cette croyance |
| UNC-PESS | p_d réel |
réaction désactivée (supposée ineffective) |
| UNC-OPT | p_d réel |
optimale (celle du §1) |
Pour la petite instance (3 cibles), on énumère les allocations x (C(3,0) + C(3,1) + C(3,2) = 7 cas) et le défenseur maximise U_D selon sa croyance ; chaque ligne de la table finale rapporte l’espérance réelle obtenue en jouant la stratégie choisie.
def esperances(t, allocation, p_d, react_policy=None):
"""E[U_A], E[U_D] d'une attaque sur t sous allocation x, capteur p_d.
react_policy=None -> politique rationnelle du defenseur (§1) ;
react_policy=False -> reaction desactivee (UNC-PESS). Sur cible non
couverte : pas de capteur, paiements bruts, pas d'alea.
"""
covered = t in allocation
if not covered:
return V_A[t], V_D[t]
react = POLITIQUE_REACTION[t] if react_policy is None else react_policy
u_a = p_d * payoff_attacker(t, True, react) + (1.0 - p_d) * payoff_attacker(t, True, False)
u_d = p_d * payoff_defender(t, True, react) + (1.0 - p_d) * payoff_defender(t, True, False)
return u_a, u_d
def best_response_attacker(allocation, p_d, react_policy=None):
"""Meilleure reponse SSE de l'attaquant.
argmax de U_A ; A EX AEQUO, la cible qui maximise U_D -- le departage
Strong Stackelberg est CODE ici (pas declare dans une cellule de prose).
Retourne (t*, U_A, U_D, nb d'ex aequos) -- le decompte des ex aequos
rend visible quand le departage est actif.
"""
cands = [(t, *esperances(t, allocation, p_d, react_policy)) for t in TARGETS]
best_u_a = max(c[1] for c in cands)
ex_aequos = [c for c in cands if abs(c[1] - best_u_a) < 1e-12]
t_star, u_a, u_d = max(ex_aequos, key=lambda c: c[2])
return t_star, u_a, u_d, len(ex_aequos)
def enumerate_allocations():
out = []
for k in range(0, R + 1):
for combo in itertools.combinations(TARGETS, k):
out.append(list(combo))
return sorted(out, key=lambda x: (len(x), x))
def resoudre_strategie(name, belief_p_d, react_policy=None, no_deploy=False):
"""Choisit l'allocation qui maximise U_D SELON LA CROYANCE du defenseur,
puis rapporte l'esperance REELLE (p_d vrai) de la strategie jouee."""
allocations = [[]] if no_deploy else enumerate_allocations()
best = None
for alloc in allocations:
t_star, u_a_belief, u_d_belief, n_ties = best_response_attacker(alloc, belief_p_d, react_policy)
_, u_a_real, u_d_real, _ = best_response_attacker(alloc, P_D, react_policy)
if best is None or u_d_belief > best["U_D_belief"]:
best = {
"strategy": name, "alloc": alloc, "t_star": t_star,
"U_A": u_a_real, "U_D": u_d_real,
"U_D_belief": u_d_belief, "ties": n_ties,
}
return best
results = {
"NO-RES": resoudre_strategie("NO-RES", P_D, no_deploy=True),
"DET-SDP": resoudre_strategie("DET-SDP", 1.0),
"UNC-PESS": resoudre_strategie("UNC-PESS", P_D, react_policy=False),
"UNC-OPT": resoudre_strategie("UNC-OPT", P_D),
}
print(f"=== Resultats des 4 strategies (p_d={P_D}, esperances REELLES) ===")
print(f"{'Strategie':10s} | {'Allocation':16s} | {'t*':4s} | {'ex aequo':8s} | {'U_A':>7s} | {'U_D':>7s}")
print("-" * 66)
for name, r in results.items():
print(f"{name:10s} | {str(r['alloc']):16s} | {r['t_star']:4s} | {r['ties']:<8d} | {r['U_A']:+7.2f} | {r['U_D']:+7.2f}")
print()
print("U_A : a minimiser du point de vue du defenseur ; U_D : a maximiser.")
print("La colonne 'ex aequo' compte les cibles au meilleur U_A pour l'attaquant")
print("-- quand elle vaut > 1, le departage SSE (max U_D) a tranche.")=== Resultats des 4 strategies (p_d=0.7, esperances REELLES) ===
Strategie | Allocation | t* | ex aequo | U_A | U_D
------------------------------------------------------------------
NO-RES | [] | T1 | 1 | +4.00 | -2.50
DET-SDP | ['T0', 'T1'] | T0 | 2 | +2.00 | +0.50
UNC-PESS | ['T1'] | T0 | 2 | +3.00 | -1.00
UNC-OPT | ['T0', 'T1'] | T0 | 2 | +2.00 | +0.50
U_A : a minimiser du point de vue du defenseur ; U_D : a maximiser.
La colonne 'ex aequo' compte les cibles au meilleur U_A pour l'attaquant
-- quand elle vaut > 1, le departage SSE (max U_D) a tranche.Comparer les U_A (utilité de l’attaquant, à minimiser du point de vue du défenseur) et les U_D (utilité du défenseur, à maximiser) — les deux sont rapportées en espérance réelle sur p_d = 0,7, chaque stratégie étant choisie sous sa croyance puis évaluée au vrai capteur.
## 3. Sweep du taux de faux negatifs — QUAND le capteur aide ou nuit
# Chaque point du sweep : le p_d REEL vaut 1-p_fn (le capteur de ce point).
# Les strategies sont choisies ET evaluees sous ce p_d -- on mesure l'effet
# du capteur lui-meme, pas un ecart croyance/realite. DET-SDP garde sa
# croyance p_d=1 et est evaluee au p_d reel du point.
p_fn_grid = np.linspace(0.0, 0.9, 10)
sweep_results = []
P_D_SAVE = P_D
for p_fn in p_fn_grid:
P_D = 1.0 - p_fn
P_FN = p_fn
r_opt = resoudre_strategie("UNC-OPT", P_D)
r_det = resoudre_strategie("DET-SDP", 1.0)
r_pess = resoudre_strategie("UNC-PESS", P_D, react_policy=False)
r_nores = resoudre_strategie("NO-RES", P_D, no_deploy=True)
bondi = r_opt["U_D"] < r_nores["U_D"] - 1e-12
sweep_results.append({
"p_fn": p_fn, "OPT": r_opt, "DET": r_det, "PESS": r_pess, "NO-RES": r_nores,
"bondi": bondi,
})
P_D = P_D_SAVE
P_FN = 1.0 - P_D
print(f"{'p_fn':5s} | {'alloc OPT':16s} | {'t*':4s} | {'ex eq':5s} | {'U_A OPT':7s} | {'U_D OPT':7s} | {'U_A N-R':7s} | {'U_D N-R':7s} | BONDI")
print("-" * 92)
for s in sweep_results:
r, n = s["OPT"], s["NO-RES"]
flag = " <- CAPTEUR NUIT (U_D)" if s["bondi"] else ""
print(f"{s['p_fn']:.2f} | {str(r['alloc']):16s} | {r['t_star']:4s} | {r['ties']:<5d} | "
f"{r['U_A']:+7.2f} | {r['U_D']:+7.2f} | {n['U_A']:+7.2f} | {n['U_D']:+7.2f} |{flag}")
bondi_count = sum(1 for s in sweep_results if s["bondi"])
print()
print(f"Critere Bondi (U_D avec capteur < U_D sans capteur) declenche : {bondi_count}/{len(sweep_results)} points")p_fn | alloc OPT | t* | ex eq | U_A OPT | U_D OPT | U_A N-R | U_D N-R | BONDI
--------------------------------------------------------------------------------------------
0.00 | ['T0', 'T1'] | T0 | 2 | +2.00 | +0.50 | +4.00 | -2.50 |
0.10 | ['T0', 'T1'] | T0 | 2 | +2.00 | +0.50 | +4.00 | -2.50 |
0.20 | ['T0', 'T1'] | T0 | 2 | +2.00 | +0.50 | +4.00 | -2.50 |
0.30 | ['T0', 'T1'] | T0 | 2 | +2.00 | +0.50 | +4.00 | -2.50 |
0.40 | ['T0', 'T1'] | T0 | 2 | +2.00 | +0.50 | +4.00 | -2.50 |
0.50 | ['T0', 'T1'] | T0 | 3 | +2.00 | +0.50 | +4.00 | -2.50 |
0.60 | ['T0', 'T1'] | T1 | 1 | +2.20 | -0.80 | +4.00 | -2.50 |
0.70 | ['T0', 'T1'] | T1 | 1 | +2.40 | -0.85 | +4.00 | -2.50 |
0.80 | ['T0', 'T1'] | T1 | 1 | +2.60 | -0.90 | +4.00 | -2.50 |
0.90 | ['T0', 'T1'] | T1 | 1 | +2.80 | -0.95 | +4.00 | -2.50 |
Critere Bondi (U_D avec capteur < U_D sans capteur) declenche : 0/10 pointsDeux phénomènes lisibles dans la table :
Transition de phase à p_fn = 0,5. Tant que le capteur détecte plus d’une fois sur deux, l’attaquant est ex æquo entre T0 couverte et T2 non couverte (U_A = +2,00) — et à p_fn = 0,5 exactement, les trois cibles sont ex æquo : le départage SSE (max U_D) est alors le seul mécanisme qui décide où frappe l’attaquant, et il choisit T0 (U_D = +0,50). Dès p_fn > 0,5, T1 couverte redevient le meilleur coup de l’attaquant — la protection d’espérance de la patrouille fond avec p_d, elle ne dissuade plus — et U_D glisse de +0,50 à −0,95. Le capteur dégradé fait ré-entrer l’attaquant sur la cible chère : la table ne peut plus être constante, la structure du jeu traverse une frontière.
Le critère Bondi ne se déclenche jamais (0/10) — cause structurelle, pas un hasard de chiffres. Le résultat « capteur strictement moins bon que rien » (Bondi et al. 2019, §4.3) exige un canal de faux positifs : une alarme sans intrusion qui force le défenseur à brûler c_react sur une cible saine ou à dévier sa patrouille. Notre instance pose p_fp = 0 (hypothèse annoncée en §1) : le capteur ne peut jamais déclencher de réaction inutile, il n’apporte que de l’information. Reproduire le phénomène exigerait d’ajouter p_fp > 0 au modèle — c’est une frontière de modélisation assumée, documentée ici plutôt que contournée en ajustant les paiements jusqu’à obtenir la courbe du papier.
## 4. Analyse de sensibilite -- variation des paiements attaquant
# La valeur de T1 pour l'attaquant varie : le capteur reste-t-il utile ?
# Critere DU DEFENSEUR (le bon) : U_D(UNC-OPT) > U_D(NO-RES) ; on rapporte
# aussi U_A. A V_A[T1]=2 l'alloc optimale se REDUIT a une seule patrouille
# ([T0]) : le departage SSE y fait le travail de la 2e unite (triple ex aequo).
v_a_t1_grid = [2.0, 4.0, 6.0]
sens_results = []
for v_a_t1 in v_a_t1_grid:
V_A_SAVE = dict(V_A)
V_A_NEW = dict(V_A)
V_A_NEW["T1"] = v_a_t1
globals()['V_A'] = V_A_NEW
r_opt = resoudre_strategie("UNC-OPT", P_D)
r_nores = resoudre_strategie("NO-RES", P_D, no_deploy=True)
sens_results.append({
"V_A_T1": v_a_t1,
"alloc": r_opt["alloc"], "t_star": r_opt["t_star"], "ties": r_opt["ties"],
"U_A": r_opt["U_A"], "U_D": r_opt["U_D"],
"NO-RES_U_A": r_nores["U_A"], "NO-RES_U_D": r_nores["U_D"],
"sensor_helps_D": r_opt["U_D"] > r_nores["U_D"],
"sensor_helps_A": r_opt["U_A"] < r_nores["U_A"],
})
globals()['V_A'] = V_A_SAVE
print(f"{'V_A[T1]':8s} | {'alloc':16s} | {'t*':4s} | {'ex eq':5s} | {'U_A':>7s} | {'U_D':>7s} | {'N-R U_A':>8s} | {'N-R U_D':>8s} | capteur aide (U_D) ?")
print("-" * 92)
for r in sens_results:
helps = "OUI" if r["sensor_helps_D"] else "NON"
print(f"{r['V_A_T1']:+.1f} | {str(r['alloc']):16s} | {r['t_star']:4s} | {r['ties']:<5d} | "
f"{r['U_A']:+7.2f} | {r['U_D']:+7.2f} | {r['NO-RES_U_A']:+8.2f} | {r['NO-RES_U_D']:+8.2f} | {helps}")V_A[T1] | alloc | t* | ex eq | U_A | U_D | N-R U_A | N-R U_D | capteur aide (U_D) ?
--------------------------------------------------------------------------------------------
+2.0 | ['T0'] | T0 | 3 | +2.00 | +0.50 | +3.00 | -1.00 | OUI
+4.0 | ['T0', 'T1'] | T0 | 2 | +2.00 | +0.50 | +4.00 | -2.50 | OUI
+6.0 | ['T1'] | T1 | 1 | +3.60 | -0.65 | +6.00 | -2.50 | OUITableau de synthèse (espérances réelles, p_d = 0,7) :
| Stratégie | Croyance capteur | Allocation | t* | U_A | U_D |
|---|---|---|---|---|---|
| NO-RES | — | ∅ | T1 | +4,00 | −2,50 |
| DET-SDP (Tambe 2011) | parfait (p_d = 1) |
[T0, T1] | T0 (départage) | +2,00 | +0,50 |
| UNC-PESS | réel, réaction off | [T1] | T0 (départage) | +3,00 | −1,00 |
| UNC-OPT | réel (p_d = 0,7) |
[T0, T1] | T0 (départage) | +2,00 | +0,50 |
Trois lectures :
p_fn (§3). Fait mesuré de l’instance, pas une loi — sur d’autres paiements, DET-SDP sur-investit dans la réaction que le vrai capteur ne permet pas.p_fp = 0), il ne peut donc jamais déclencher de réaction coûteuse inutile. Reproduire le phénomène demanderait d’étendre le modèle à p_fp > 0 — frontière assumée, pas un échec de calcul. L’extension à R > 2 ou |T| > 3 demande un solveur MILP complet (pulp) ; ici l’énumération suffit.Raccord GT-9b : on a prolongé l’engagement crédible en déploiement sur un graphe sous incertitude. Le défenseur s’engage sur toute son allocation (commit), le follower observe avant d’attaquer, et la valeur du leader vient maintenant de deux sources : la couverture physique et la discipline de l’attaquant sur les ex æquo (départage SSE).
## 6. Synthese finale
print("=" * 70)
print("RESUME FINAL")
print("=" * 70)
print(f"Instance : 3 cibles, R={R} ressources, capteur p_d={P_D:.2f}, p_fn={P_FN:.2f}, p_fp=0")
print()
print("1) Departage SSE CODE (max U_D a ex aequo), actif sur l'instance de base :")
r_base = results["UNC-OPT"]
print(f" UNC-OPT : alloc={r_base['alloc']}, t*={r_base['t_star']} ({r_base['ties']} ex aequo)")
print(f" U_A={r_base['U_A']:+.2f}, U_D={r_base['U_D']:+.2f} contre NO-RES U_D={results['NO-RES']['U_D']:+.2f}")
print()
print("2) Sweep p_fn : transition de phase a p_fn=0.5 (3 ex aequo),")
print(" puis t* bascule vers T1 et U_D glisse de +0.50 a -0.95 :")
bondi_count = sum(1 for s in sweep_results if s["bondi"])
for s in sweep_results:
r = s["OPT"]
marker = " <- triple ex aequo" if r["ties"] == 3 else ""
print(f" p_fn={s['p_fn']:.2f} : t*={r['t_star']}, U_D(OPT)={r['U_D']:+.2f}{marker}")
print(f" Critere Bondi (U_D capteur < U_D sans capteur) : {bondi_count}/{len(sweep_results)}")
print(" Cause structurelle : p_fp=0 -> aucune reaction inutile possible.")
print()
helps_count = sum(1 for r in sens_results if r["sensor_helps_D"])
print(f"3) Sensibilite V_A[T1] : le capteur aide sur U_D dans {helps_count}/{len(sens_results)} cas.")
r2 = sens_results[0]
print(f" A V_A[T1]={r2['V_A_T1']:+.0f}, une SEULE patrouille suffit (alloc={r2['alloc']},")
print(f" {r2['ties']} ex aequo) : le departage SSE fait le travail de la 2e unite.")
print(" U_D passe de " + f"{r2['NO-RES_U_D']:+.2f} (sans capteur) a {r2['U_D']:+.2f}.")======================================================================
RESUME FINAL
======================================================================
Instance : 3 cibles, R=2 ressources, capteur p_d=0.70, p_fn=0.30, p_fp=0
1) Departage SSE CODE (max U_D a ex aequo), actif sur l'instance de base :
UNC-OPT : alloc=['T0', 'T1'], t*=T0 (2 ex aequo)
U_A=+2.00, U_D=+0.50 contre NO-RES U_D=-2.50
2) Sweep p_fn : transition de phase a p_fn=0.5 (3 ex aequo),
puis t* bascule vers T1 et U_D glisse de +0.50 a -0.95 :
p_fn=0.00 : t*=T0, U_D(OPT)=+0.50
p_fn=0.10 : t*=T0, U_D(OPT)=+0.50
p_fn=0.20 : t*=T0, U_D(OPT)=+0.50
p_fn=0.30 : t*=T0, U_D(OPT)=+0.50
p_fn=0.40 : t*=T0, U_D(OPT)=+0.50
p_fn=0.50 : t*=T0, U_D(OPT)=+0.50 <- triple ex aequo
p_fn=0.60 : t*=T1, U_D(OPT)=-0.80
p_fn=0.70 : t*=T1, U_D(OPT)=-0.85
p_fn=0.80 : t*=T1, U_D(OPT)=-0.90
p_fn=0.90 : t*=T1, U_D(OPT)=-0.95
Critere Bondi (U_D capteur < U_D sans capteur) : 0/10
Cause structurelle : p_fp=0 -> aucune reaction inutile possible.
3) Sensibilite V_A[T1] : le capteur aide sur U_D dans 3/3 cas.
A V_A[T1]=+2, une SEULE patrouille suffit (alloc=['T0'],
3 ex aequo) : le departage SSE fait le travail de la 2e unite.
U_D passe de -1.00 (sans capteur) a +0.50.