💻 computer science

Strategies in Sabotage Games: Temporal and Epistemic Perspectives

Questo articolo propone un quadro teorico che utilizza la logica temporale alternata (ATL $^\ast$ ) e le sue estensioni epistemiche per analizzare le strategie vincenti nei giochi di sabotaggio, permettendo di ragionare sia sulle proprietà temporali dei grafi dinamici sia sull'incertezza dei giocatori.

Autori originali: Nina Gierasimczuk, Katrine B. P. Thoft

Pubblicato 2026-04-07

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Nina Gierasimczuk, Katrine B. P. Thoft

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immagina di essere in una città futuristica dove le strade (i collegamenti) possono scomparire magicamente o apparire dal nulla. Questo è il mondo dei Giochi di Sabotaggio.

1. La Storia di Base: Il Corridore e il Diavolo

In questo gioco ci sono due personaggi:

Il Corridore (Runner): Vuole arrivare a una destinazione specifica (ad esempio, la stazione di Copenhagen) il più velocemente possibile.
Il Diavolo (Demon/Blocker): È un sabotatore che vuole impedire al Corridore di arrivare. Ad ogni turno, il Diavolo può cancellare una strada dalla mappa.

L'obiettivo del Corridore è trovare un percorso sicuro. L'obiettivo del Diavolo è tagliare tutte le vie di fuga.

2. Il Vecchio Modo di Pensare (La Logica Statica)

Fino a poco tempo fa, gli studiosi guardavano questo gioco come una fotografia fissa. Si chiedevano: "Se il Diavolo taglia una strada a caso, il Corridore può ancora arrivare?".
Usavano una logica chiamata SML (Logica Modale di Sabotaggio). Era come guardare una mappa e chiedersi: "C'è ancora un percorso?".
Il problema: Questa logica era un po' rigida. Non teneva bene conto del tempo (quanto dura il gioco) e non considerava cosa i giocatori sanno o non sanno (ad esempio, se il Corridore sa dove si trova il Diavolo).

3. La Nuova Idea: Guardare il Gioco come un Film (ATL*)

Gli autori di questo articolo, Nina e Katrine, dicono: "Aspetta, questo non è una foto, è un film!".
Introducono una nuova lente chiamata ATL* (Logica Temporale Alternata). Invece di guardare solo la mappa, guardano la strategia nel tempo.

L'analogia del Chess vs. Scacchi: La vecchia logica era come guardare una singola mossa degli scacchi. La nuova logica (ATL*) è come guardare l'intera partita, chiedendosi: "Il Corridore ha una strategia per vincere, indipendentemente da cosa fa il Diavolo?".
Il concetto di "Vita" (Liveness): Oltre a chiedere "Arrivo a destinazione?", si chiede anche: "Posso rimanere in gioco abbastanza a lungo?". Immagina di essere in un labirinto che si restringe. Anche se non esci, se riesci a non essere intrappolato per 100 mosse, hai vinto una versione diversa del gioco.

4. Tre Modi per Giocare (Le Regole del Movimento)

Gli autori esplorano tre modi diversi in cui il gioco può svolgersi, come se fossero diversi generi di film:

Turno per Turno (Classico): Il Corridore si muove, poi il Diavolo taglia una strada. Poi il Corridore, poi il Diavolo. È come una partita a scacchi classica.
Contemporaneo (Concorrente): Entrambi agiscono allo stesso tempo.
- Metafora: Immagina di correre su un ponte mentre qualcuno cerca di tagliarlo. Se scegli lo stesso ponte che lui sta tagliando, la tua corsa si annulla e rimani fermo. È più rischioso!
Generale: Un mix dove a volte si agisce insieme, a volte si aspetta. È il modo più flessibile per simulare la realtà.

5. Il Concetto del "Taglio Minimo" (Il Problema del Ponte)

C'è un concetto matematico affascinante qui: il Taglio Minimo.
Immagina di voler isolare una città tagliando il minor numero possibile di ponti.

Il problema statico: "Quali sono i 2 ponti da tagliare per isolare la città?"
Il problema dinamico (la novità di questo paper): "Se il Corridore si muove mentre taglio i ponti, quanti ponti devo tagliare davvero per fermarlo?"
- Esempio: Se tagli un ponte, il Corridore potrebbe essere già passato dall'altro lato! Quindi il Diavolo deve essere più intelligente e tagliare i ponti in un ordine specifico, adattandosi ai movimenti del Corridore. È come cercare di fermare un'auto in fuga non solo tagliando le strade, ma prevedendo dove l'auto girerà.

6. La Magia dell'Angelo (Edificatori)

C'è anche una versione "Angelo" del gioco. Oltre al Diavolo che taglia strade, c'è un Angelo che può costruire nuove strade!

Metafora: Immagina un gioco dove il Diavolo chiude i tunnel, ma un Angelo ne apre di nuovi. Il Corridore deve navigare in un mondo che cambia costantemente, dove le strade spariscono e riappaiono. Questo rende il gioco infinito e molto più complesso.

7. La Soglia della Conoscenza (Cosa sanno i giocatori?)

Infine, gli autori aggiungono un livello di mistero: l'ignoranza.

Informazione Perfetta: Tutti vedono tutto. Il Diavolo sa dove sei.
Informazione Imperfetta: Il Diavolo non sa dove sei esattamente.
- Esempio: Il Corridore è in una stanza con due uscite. Il Diavolo sa che è in una delle due, ma non sa quale. Se il Diavolo taglia la strada sbagliata, il Corridore scappa.
- La logica nuova permette di dire: "Il Corridore ha una strategia per vincere, ma non sa di averla perché non vede il Diavolo". È come avere una mano vincente a poker, ma non sapere che l'avversario sta bluffando.

In Sintesi

Questo articolo è come un manuale di istruzioni per un videogioco molto sofisticato.
Gli autori dicono: "Non guardiamo solo la mappa. Guardiamo il tempo, guardiamo le strategie, guardiamo cosa i giocatori sanno e non sanno, e guardiamo come le strade cambiano mentre corriamo".

Usando questa nuova lente (ATL*), possiamo risolvere problemi complessi su come proteggere le reti (come internet o le ferrovie) o come progettare sistemi che resistono agli attacchi, tenendo conto che il nemico è intelligente e il mondo cambia in tempo reale.

1. Problema e Contesto

Il lavoro affronta la modellazione e l'analisi dei giochi di sabotaggio, un modello astratto in cui un agente ("runner") tenta di raggiungere uno stato obiettivo in un grafo, mentre un avversario ("demon" o "blocker") rimuove dinamicamente gli archi del grafo ad ogni turno.
Sebbene questi giochi siano stati tradizionalmente analizzati tramite la Logica Modale di Sabotaggio (SML), l'approccio classico presenta limitazioni significative:

Non gestisce adeguatamente le proprietà temporali (come la liveness o la durata del gioco).
Non supporta nativamente scenari con informazioni imperfette (incertezza epistemica).
È limitato a giochi strettamente a turni e non gestisce bene le mosse simultanee o le dinamiche complesse di strategie vincenti in contesti temporali estesi.

L'obiettivo del paper è fornire un quadro logico unificato che integri il ragionamento strategico temporale (tipico della logica temporale alternata) con la dinamica strutturale del sabotaggio, permettendo di studiare strategie vincenti, proprietà temporali e incertezza.

2. Metodologia

Gli autori ricostruiscono i giochi di sabotaggio all'interno del framework della Logica Temporale Alternata (ATL e ATL)*.

Strutture di Gioco: Vengono definite tre varianti di strutture di gioco basate su un grafo $G=(V, E)$ $G = (V, E)$ :
1. Turn-based (tb): I giocatori agiscono in sequenza alternata (Runner muove, poi Demon rimuove un arco).
2. Concurrent (con): I giocatori agiscono simultaneamente. Se scelgono lo stesso arco, l'azione si annulla (cancellazione reciproca).
3. General (gen): Una struttura flessibile che permette combinazioni di turni, mosse simultanee e pause (skip).
Modelli di Gioco: Le strutture vengono trasformate in modelli di gioco etichettati ( $M_{tb}, M_{con}, M_{gen}$ ) dove gli stati rappresentano l'intera configurazione del gioco (insieme degli archi rimanenti + posizione del runner), non solo i vertici del grafo.
Logica: Viene utilizzata ATL* per esprimere le strategie. La logica permette di quantificare sulle traiettorie (plays) risultanti dalle strategie dei coalizioni di agenti.
Estensioni:
- Introduzione di un operatore until parametrizzato (preso dalla logica temporale metrica) per gestire la liveness.
- Estensione a giochi angelici, dove un terzo agente può aggiungere archi al grafo.
- Integrazione con la Logica Epistemica Temporale Alternata (ATEL) per modellare l'incertezza e la conoscenza degli agenti.

3. Contributi Chiave

A. Nuove Varianti di Giochi e Caratterizzazione Logica

Giochi di Raggiungimento (RSG): Vengono formalizzati i classici giochi di raggiungimento. Gli autori dimostrano come le condizioni di vittoria per il runner (raggiungere $v_g$ ) possano essere espresse in ATL come $\langle\langle \{r\} \rangle\rangle F g$ .
Giochi di Liveness (LSG): Viene introdotta una nuova variante in cui l'obiettivo non è raggiungere un vertice specifico, ma rimanere "vivi" (avere mosse disponibili) per almeno $b$ turni. La vittoria è espressa tramite operatori temporali parametrizzati: $\langle\langle \{r\} \rangle\rangle \top U_{2b} (X \top)$ .
Confronto SML vs ATL: Viene mostrato come ATL superi SML permettendo di esprimere strategie per diverse sequenze di mosse e per giochi concorrenti, che SML non gestisce nativamente.

B. Connessione con la Teoria dei Grafi (Tagli Minimi)

Un contributo teorico fondamentale è la connessione tra le strategie di sabotaggio e il problema del taglio minimo s-t (s-t cut):

Viene definita una nozione di taglio minimo dinamico s-t: il numero minimo di round necessari al demon per impedire al runner di raggiungere l'obiettivo, tenendo conto che il runner si muove tra le rimozioni degli archi.
Viene dimostrato che il taglio minimo statico (teorema di Menger) non è sufficiente per prevedere l'esito del gioco dinamico, poiché il runner può "sfuggire" al taglio statico muovendosi prima che il demon completi la rimozione.
La logica ATL* permette di esprimere formalmente la strategia del demon per trovare questo taglio dinamico minimo: $\langle\langle \{d\} \rangle\rangle (\top U_k \langle\langle \emptyset \rangle\rangle G \neg g)$ .

C. Giochi Angelici

Viene proposta un'estensione in cui un agente "angelo" può aggiungere archi al grafo. Questo permette di modellare scenari di recupero della connettività e proprietà temporali più complesse (es. visitare l'obiettivo infinite volte, $\langle\langle C \rangle\rangle G F g$ ), che richiedono la potenza espressiva di ATL* rispetto ad ATL semplice.

D. Aspetti Epistemici (ATEL)

Il paper integra la conoscenza degli agenti:

Informazione Perfetta: Tutti gli agenti vedono lo stato completo.
Informazione Imperfetta: Gli agenti hanno accesso limitato (es. vedono solo il numero di archi uscenti dal nodo corrente o non vedono la posizione esatta del runner dopo la prima mossa).
Viene evidenziato il paradosso per cui un agente potrebbe avere una strategia vincente ma non saperlo (non avere la conoscenza della propria capacità strategica), portando alla distinzione tra capacità strategica e conoscenza della capacità strategica ( $\langle\langle \{r\} \rangle\rangle F g \land \neg K_r \langle\langle \{r\} \rangle\rangle F g$ ).

4. Risultati Principali

Impossibilità di vittoria nel RSG Turn-based: Per grafi semplici (non multi-grafi), se il runner non inizia sul vertice obiettivo e non c'è un arco diretto, il demon ha sempre una strategia vincente per impedire il raggiungimento dell'obiettivo (Proposizione 3.14). Questo spiega perché i giochi di sabotaggio sono spesso studiati su multi-grafi.
Differenza tra Giochi Turn-based e Concurrenti: Nei giochi concorrenti, la capacità del runner è ulteriormente limitata perché il demon può annullare la sua mossa scegliendo lo stesso arco. Tuttavia, nei giochi di liveness, questa stessa cancellazione diventa un vantaggio per il runner (se il demon cancella la sua mossa, il runner rimane nello stato corrente e "vive" un turno in più).
Espressività di ATL:* La logica permette di catturare proprietà che SML non può esprimere, come la dipendenza temporale delle strategie e la conoscenza strategica in condizioni di informazione imperfetta.
Nuova definizione di Taglio Dinamico: Viene formalizzato il concetto di taglio minimo dinamico, collegando la teoria dei giochi logici alla teoria algoritmica dei grafi dinamici.

5. Significato e Implicazioni

Questo lavoro è significativo perché:

Unifica domini: Colma il divario tra la logica modale di sabotaggio (dominio della teoria dei giochi e apprendimento formale) e la logica temporale strategica (dominio dei sistemi multi-agente e verifica formale).
Aumenta l'applicabilità: L'uso di ATL* e ATEL rende il modello applicabile a scenari reali più complessi, come reti di trasporto con cancellazioni dinamiche, sistemi di sicurezza con attaccanti e difensori, e scenari di apprendimento con informazioni parziali.
Ponte interdisciplinare: Crea un ponte tra la logica computazionale e la teoria dei grafi algoritmica, suggerendo nuove direzioni di ricerca per problemi di flusso massimo e taglio minimo in grafi dinamici.
Fondamento per l'incertezza: Fornisce una base solida per analizzare la "capacità strategica" in presenza di informazione imperfetta, un tema cruciale nell'intelligenza artificiale e nell'economia comportamentale.

In sintesi, il paper propone un framework logico robusto e flessibile per analizzare giochi dinamici su grafi, estendendo le capacità di ragionamento oltre la semplice raggiungibilità per includere la temporalità, la cooperazione, la competizione simultanea e l'incertezza epistemica.