Per i casi in cui non `e possibile dedurre la strategia ottima per il giocatore Difensore analizzando l’andamento delle matrici di utilit`a, vi sono svariate strumenti che `e possibile applicare per raggiungere una soluzione.
4.3.1
Analisi matematica
Un primo metodo di calcolo dell’equilibrio comporta un’analisi del grafico del- l’utilit`a attesa dei due giocatori. Dopo aver generato una scelta iniziale per il giocatore Difensore, chiamata h∗
0, randomizzando su tutte le sue possibili azio-
ni, viene calcolata la best response del giocatore Attaccante a quest’ultima, chiamata ∆µ∗0 . Quindi si calcolano iterativamente le best response successive
calcolando, al ciclo i − esimo, h∗
i come best response del giocatore Difensore
a ∆µ∗
i−1 e ∆µ∗i come best response del giocatore Attaccante ad h∗i. Il ciclo si
Figura 4.6: Comportamento del grafico dell’utilit`a attesa in caso di variazioni di ∆µ (a), γ (b) e P(Attaccante presente) (c).
per la coppia di azioni (∆µ∗i−1, h ∗ i)e quella per (∆µ ∗ i−2, h ∗
i−1)`e inferiore ad una
determinata soglia.
La procedura cos`ı delineata `e efficace per calcolare equilibri in strategie pure. L’equilibrio, se esiste, viene trovato in media in tre iterazioni.
Data: h∗0scelta randomicamente, soglia t
Result: Equilibrio per il gioco, composto dall’ultima coppia (h∗i, ∆µ∗i)
Calcola ∆µ∗
0 come Best Response a h∗0
Imposta UD,1= 0e UD,2= t ∗ 2
Imposta i = 1
while UD,2− UD,1> tdo
Imposta UD,1= UD,2
Calcola h∗i come Best Response a ∆µ ∗ i−1
Calcola ∆µ∗i come Best Response ad h ∗ i
Calcola UD,2come utilit`a attesa del Difensore per la coppia di azioni
(h∗i, ∆µ∗i−1)
end
Algorithm 1:Calcolo dell’Equilibrio per Bisezione.
4.3.2
Algoritmo di Lemke-Howson
L’algoritmo di Lemke-Howson [6] permette di trovare un equilibrio di un gio- co a due giocatori non degenere sfruttando i politopi P e Q delle best response dei due giocatori. Partendo dal vertice (0,0) del politopo P × Q, segue un cammino tra i vertici fino a trovarne uno completamente etichettato, visitando unicamente i vertici quasi completamente etichettati e spostandosi solo su uni dei due politopi P e Q e rimanendo fermo nell’altro.
Partendo da uno dei due politopi, l’algoritmo si sposta dal vertice (0,0) ver- so un altro vertice a lui adiacente e quasi completamente etichettato (scelto a caso). L’assenza di un’etichetta implica che un’altra etichetta h relativa ad una strategia di uno dei due giocatori (supponiamo al giocatore A) sia duplicata. L’algoritmo si sposta quindi di vertice sul politopo relativo all’altro giocatore (giocatore B), scegliendo in base ad un criterio di complementariet`a rispetto alla scelta eseguita nel passo precedente. Se la strategia individuata a questo punto `e tale per cui la strategia del primo giocatore (A) `e una best response, allora l’algoritmo termina con successo; se invece cos`ı non `e, si torna al primo politopo e si procede a cambiare nuovamente vertice. L’algoritmo di Lemke- Howson visita ad ogni passo una nuova coppia di vertici, senza mai tornare su una coppia gi`a visitata in precedenza. Questo implica che l’algoritmo termina sempre, trovando con successo un punto di equilibrio.
In questo lavoro si `e utilizzata una variante dell’algoritmo, chiamata ran- dom restart Lemke-Howson [10], che introduce un elemento di randomizza- zione nella procedura, migliorando di molto le prestazioni dell’algoritmo. L’al- goritmo `e stato applicato su diversi insiemi di dati, relativi a diverse discretiz-
zazioni dell’intervallo di valori possibili per le azioni dei due giocatori, per un totale di undici diversi livelli di discretizzazione che sono andati da un mini- mo di 10 punti di discretizzazione sull’intero insieme ad un massimo di 500. Per sua costruzione, l’algoritmo di Lemke-Howson `e in grado di calcolare ad ogni esecuzione uno dei possibili equilibri in strategie pure del gioco, differen- te a seconda del valore del parametro randomizzato.
Per questo motivo il calcolo tramite l’algoritmo rrLH `e stato ripetuto pi `u volte per ogni insieme di dati in ingresso possibile, impostando di volta in volta un valore diverso del parametro fino a ricoprire interamente l’intervallo di valori possibile per il parametro stesso, e sono stati analizzati i risultati cal- colando la frequenza con cui le varie azioni dei due giocatori si sono presentate in un equilibrio. Il calcolo ha mostrato che:
• quasi nella totalit`a dei casi gli equilibri in strategie pure implicano che il giocatore Attaccante giochi l’azione che gli permette di massimizzare l’alterazione rispetto alla distribuzione base;
• la frequenza di presenza delle azioni del giocatore Difensore negli equi- libri mostra un massimo relativo intorno al 40% dell’intervallo di valori possibili per h, ed un picco intorno al 60-70%.
In Figura 4.7 viene mostrata la tipica distribuzione della presenza delle azioni possibili per il giocatore Difensore negli equilibri calcolati con l’algo- ritmo rrLH, relativa nel caso specifico alla discretizzazione dell’intervallo di valori possibili in 150 punti.
Figura 4.7: Frequenza degli equilibri per il giocatore Difensore, caso con 150 punti di discretizzazione.
γ = 0, = 0 γ = 0, > 0 γ > 0, = 0 γ > 0, > 0 Caso 1 Esiste Esiste Esiste Non esiste Caso 2 Esiste Esiste Non esiste Non esiste Caso 3 Esiste Esiste Non esiste Non esiste Caso 4 Esiste Esiste Non esiste Non esiste
Tabella 4.2: Calcolo in forma chiusa.
4.3.3
Programmazione Lineare Intera
Per il calcolo degli equilibri sono stati formalizzati anche due problemi di programmazione lineare intera.
Il primo `e stato utilizzato per calcolare gli equilibri del gioco in strategie miste. `E stato applicato sia ad un gioco classico sia ad un gioco di tipo baye- siano, in cui il giocatore Attaccante pu `o assumere uno tra due tipi (presente e non presente), utilizzando nel secondo caso per il giocatore Difensore una tabella delle utilit`a popolata con le utilit`a attese, calcolata come somma delle due utilit`a relative rispettivamente al caso in cui il giocatore Attaccante `e pre- sente ed al caso in cui `e assente, pesate per la probabilit`a di presenza o meno del giocatore Attaccante stesso.
Il secondo, invece, `e stato utilizzato per risolvere un gioco Bayesiano di ti- po Leader-Follower [11], in cui il giocatore Difensore assume il ruolo di leader. Per la soluzione `e stato deciso di suddividere il problema in due sottoproble- mi: prima viene calcolato in programmazione lineare, per ogni possibile azio- ne del giocatore Difensore, l’equilibrio del gioco; quindi si seleziona tra tutti i risultati cos`ı ottenuti l’azione del giocatore Difensore che gli garantisce l’uti- lit`a attesa pi `u alta. Cos`ı facendo `e possibile semplificare il calcolo, riducendo il tutto da un problema di programmazione mista intera ad un problema di programmazione lineare intera.