Analisi degli equilibri notevoli nelle modellazioni in forma di gioco strategico del test di Shewhart

(1)

POLITECNICO DI MILANO

FACOLT `

A DI INGEGNERIA DELL’INFORMAZIONE

Corso di Laurea in Ingegneria Informatica

ANALISI DEGLI EQUILIBRI NOTEVOLI NELLE

MODELLAZIONI IN FORMA DI GIOCO STRATEGICO DEL

TEST DI SHEWHART

Relatore:

Prof. Nicola GATTI

Correlatore:Ing. Manuel ROVERI

Tesi di laurea di:

Marco SUBACCHI

Matr. 734559

(2)

(3)

Ringraziamenti

Doverosi ringraziamenti vanno, prima di tutto, al mio relatore Nicola Gatti ed al correlatore Manuel Roveri, per il tempo che mi hanno dedicato.

Un sentito grazie anche alla mia famiglia, ed in particolare ai miei genitori, per il supporto che mi hanno dimostrato in varie occasioni e ad Alex, tra le altre cose per il tempo che ha dedicato all’opera di correzione della bozza.

(4)

(5)

Indice

1 Introduzione 13

2 Stato dell’arte 15

2.1 Change Detection Test . . . 15

2.1.1 Shewhart Control Chart . . . 16

2.1.2 Geometric Moving Average Control Chart . . . 16

2.1.3 Cumulative Sum Algorithm . . . 17

2.2 Teoria dei Giochi . . . 17

2.2.1 Giochi in forma normale . . . 19

2.2.2 Giochi in forma estesa . . . 22

2.2.3 Giochi Bayesiani . . . 24

2.2.4 Ottimizzazione matematica . . . 25

2.2.5 Giochi per la sicurezza . . . 26

3 Struttura del problema e strumenti utilizzati 29 3.1 Fasi del lavoro . . . 29

3.2 Software utilizzati . . . 30

4 Test di Shewhart 33 4.1 Formalizzazione del test . . . 33

4.2 Formalizzazione delle strategie . . . 35

4.2.1 Caso 1 . . . 35

4.2.2 Caso 2 . . . 38

4.2.3 Casi 3 e 4 . . . 41

4.2.4 Utilit`a istante per istante . . . 42

4.3 Calcolo delle strategie . . . 42

4.3.1 Analisi matematica . . . 42

4.3.2 Algoritmo di Lemke-Howson . . . 44

4.3.3 Programmazione Lineare Intera . . . 46

4.4 Risultati sperimentali . . . 46

(6)

(7)

Elenco delle figure

2.1 Rappresentazione in forma normale della battaglia dei sessi . . 19

4.1 Tabella delle utilit`a con penalit`a nulle. . . 36

4.2 Tabella delle utilit`a con γ nulla ed positiva. . . 37

4.3 Tabella delle utilit`a con γ positiva ed nulla. . . 38

4.4 Tabella delle utilit`a con γ ed positive. . . 39

4.5 Forma assunta dall’utilit`a attesa del giocatore Difensore. . . 40

4.6 Comportamento del grafico dell’utilit`a attesa in caso di varia-zioni di ∆µ (a), γ (b) e P(Attaccante presente) (c). . . 43

4.7 Frequenza degli equilibri per il giocatore Difensore, caso con 150 punti di discretizzazione. . . 45

(8)

(9)

Elenco delle tabelle

2.1 Battaglia dei sessi. . . 18 4.1 Esiti del gioco. . . 34 4.2 Riepilogo calcolo in forma chiusa. . . 46

(10)

(11)

Abstract

Il controllo di qualità è un’area di particolare importanza nei processi di pro-duzione industriale, per il mantenimento dei corretti parametri di qualità dei beni prodotti. L’ultimo secolo ha visto la nascita di svariati metodi applicabili al controllo di qualità, di cui i Change Detection Test sono uno dei primi esempi. Sempre nell’ambito dei sistemi industriali, i metodi di controllo di qualità possono essere applicati anche ad un differente scopo: il rilevamento delle in-trusioni il cui obiettivo sia quello di modificare il sistema produttivo stesso. Questo scenario pu ò essere facilmente modellato sotto forma di gioco strate-gico, ed il comportamento pi ù adeguato da tenere nella sua esecuzione pu ò essere calcolato come equilibrio del gioco stesso.

Nel presente lavoro di tesi si sono effettuati dei test su una formalizza-zione di un metodo di controllo della qualit`a, atti allo studio dell’esistenza di soluzioni notevoli valide per tutte le possibili applicazioni del test, sotto determinate ipotesi.

(12)

(13)

Capitolo 1

Introduzione

L’analisi delle serie numeriche `e un’area della matematica ampiamente stu-diata, e che trova applicazione in svariati ambiti. Buona parte dei sistemi fisici esistenti, siano essi naturali o creati dall’uomo, sono modellabili come serie di osservazioni di variabili casuali generate da una distribuzione di probabilit`a, nota o incognita.

Analizzando l’insieme di misurazioni con opportuni strumenti matematici è possibile risalire ad una formulazione, pi ù o meno precisa, della distribuzio-ne di probabilità che descrive il sistema; oppure è possibile prevedere il futuro comportamento del sistema stesso; o ancora verificare l’ipotesi che la serie sia generata da una determinata distribuzione di probabilità.

Una delle applicazioni possibili è quella del controllo di qualità nei sistemi produttivi industriali: i beni generati dal sistema produttivo vengono descritti come misurazione di una data caratteristica che ne rappresenta la qualità, e che deve restare all’interno di determinati parametri di accettabilità. In questo caso il sistema produttivo viene descritto sotto forma di distribuzione di probabi-lità, che genera variabili casuali che rappresentano le misurazioni effettuate sui beni.

Generalmente la non conformità delle misurazioni indica l’usura del siste-ma stesso. È per ò possibile che si verifichino situazioni in cui esista un agente esterno il cui obiettivo sia quello di alterare il processo produttivo. In questo caso il concetto di controllo di qualità si pu ò applicare anche all’individuazio-ne di questo agente esterno, scegliendo accuratamente i parametri di qualità tenendo conto anche di questa possibilità.

In questo lavoro di tesi si è studiato un test applicabile ai due scenari sopra descritti utilizzando la teoria matematica dei giochi. Dopo aver dato al test una descrizione pi ù formale sotto forma di gioco strategico, si sono identifi-cati vari scenari possibili, differenziati a seconda del valore di alcuni parame-tri, e per ognuno di questi si è dapprima verificata l’esistenza di equilibri in forma chiusa, quindi in caso contrario si è proceduto alla ricerca di eventuali

(14)

equilibri applicando le metodologie classiche della Teoria dei giochi. La tesi `e strutturata come segue.

Nel Capitolo 2 si `e data una panoramica generale della Teoria dei Giochi e dei Change Detection Test, di cui fa parte il test menzionato poc’anzi.

Nel Capitolo 3 si è descritto pi ù nel dettaglio lo scenario studiato e si è data una breve descrizione degli strumenti informatici utilizzati.

Nel Capitolo 4 viene affrontata la formalizzazione del test sotto forma di gioco strategico e ne vengono discusse le soluzioni possibili.

Nel Capitolo 5, infine, vengono discussi i risultati ed i possibili sviluppi futuri.

(15)

Capitolo 2

Stato dell’arte

L’obiettivo di questo capitolo `e quello di dare una panoramica generale delle aree di studio collegate al problema del riconoscimento di un intrusione in un sistema dinamico. Verranno quindi presentati i Change Detection Test, tecniche statistiche utilizzate per tentare di identificare variazioni nella distrubuzione di processi stocastici, e verranno esposte le basi della Teoria dei Giochi, che `e stata utilizzata in questo lavoro come soluzione alternativa ai CDT.

2.1 Change Detection Test

Il change detection [7] `e una parte dell’analisi statistica che ha lo scopo di iden-tificare variazioni nella distribuzione di un processo stocastico. Data una se-quenza di variabili casuali i.i.d. (yk)k, generate a partire da una distribuzione

pθ(y)dipendente da un parametro noto θ = θ0, ad un istante incognito t0si ha

che il parametro cambia, assumendo valore ignoto θ1 6= θ0: lo scopo del change

detection `e generalmente quello di rilevare il presentarsi di questa variazione, ed eventualmente di identificare l’istante t0 in cui si `e presentata e la portata

del cambiamento. Il change detection ha svariate applicazioni, come ad esempio il cointrollo della qualit`a nei sistemi produttivi o l’analisi di dati da rilevamenti sismici.

Esistono svariati test che vengono utilizzati per identificare i cambiamenti nella distribuzione, chiamati Change Detection Test. I CDT vengono general-mente suddivisi in due categorie principali: i test On-Line hanno lo scopo di identificare il cambiamento il pi `u velocemente possibile, generalmente senza valutare il valore di t0 o di θ1; i test Off-line utilizzano i test di ipotesi per

va-lutare il valore di t0e/o di θ1. Per valutare la bont`a di un CDT si usano cinque

criteri principali:

• l’intervallo di tempo medio che intercorre tra un falso positivo ed il se-guente;

(16)

• la probabilit`a di falso positivo; • il ritardo medio di identificazione; • la probabilit`a di falso negativo; • la precisione nella stima di t0 e θ1.

Di seguito sono presentati alcuni tra i principali CDT On-Line.

2.1.1 Shewhart Control Chart

Lo Shewhart Control Chart, o pi `u semplicemente Test di Shewhart, si basa sul concetto di ispezione continua. Vengono estratti campioni di n variabili ge-nerate dal processo stocastico, che vengono analizzati per decidere tra le due ipotesi

H0 : θ = θ0

H1 : θ 6= θ0

Finch´e i campioni confermano l’ipotesi H0, si procede con il

campionamen-to ed il test. Nell’istante in cui la decisione del test volge verso l’ipotesi H1 il

campionamento (e normalmente il processo) vengono fermati.

La decisione tra le due ipotesi viene effettuata tramite un test di soglia su una statistica s del processo. Viene definita una soglia di accettabilit`a entro la quale si `e ragionevolmente sicuri che le variabili casuali sono state generate da una distribuzione caratterizzata dal parametro θ0, e viene per ogni campione viene

paragonato il suo valore campionario della statistica alla soglia: se il valore campionario rientra all’interno della soglia si considera confermata l’ipotesi H0, altrimenti viene segnalata una variazione nella distribuzione.

È ovviamente necessario definire con accuratezza la soglia di accettabilità, evitando di scegliere una fascia troppo larga, accettando campioni generati da una distribuzione con θ 6= θ1 (e quindi aumentando la probabilità di falsi

negativi) oppure troppo stretta, identificando una variazione a seguito delle normali fluttuazioni del valore campionario della distribuzione originale (e quindi aumentando la probabilit`a di falsi positivi).

2.1.2 Geometric Moving Average Control Chart

I test Geometric Moving Average sono una variante del test di Shewhart. Come il test di Shewhart basano il loro funzionamento sul paragone tra una statistica del processo ed una fascia di accettabilit`a sul suo valore della statistica per le variabili. La statistica che viene usata come parametro di controllo si basa sulla verosimiglianza che il parametro θ per ogni campione sia quello originale

(17)

o meno. I vari valori vengono poi sommati e pesati in modo da considerare maggiormente il valore dell’ultimo campione.

si = ln p_θ1(yi)

p_θ0(yi)

g0 = 0

gk = (1 − α)gk−1+ αsk

Il test identifica una variazione nella distribuzione del processo qualora gk

risulti al di fuori della fascia di accettabilit`a. Una possibile variazione (chia-mata Finite Moving Average) consiste nel definire un insieme finito di fattori di sconto γi di cardinalit`a n, e quindi tener conto nel calcolo di gksolo le ultime n

variabili.

2.1.3 Cumulative Sum Algorithm

L’algoritmo a somme cumulative (detto anche CUSUM), ispirato dal lavoro di A. Wald [12], propone un test ripetuto sulle due ipotesi definite poc’anzi. Co-me per il test di Shewhart, l’algoritmo CUSUM raccoglie campioni di diCo-men- dimen-sione fissata n e ne calcola il valore campionario di una statistica, calcolandone poi la differenza rispetto al valore nominale della distribuzione di probabili`a. Il termine corrente viene calcolato a partire dal precedente, sommandone il valore a quello della differenza cos`ı calcolata, nel modo descritto di seguito: S0 = 0

Si = max[0, Si−1+ (xi− ¯x)]

dove xi `e il valore campionario della statistica utilizzata e ¯x `e il suo valore

nominale. `E poi il valore di Siad essere confrontato con la fascia di accettabilit`a

per decidere tra l’ipotesi H0 : θ = θ0e l’ipotesi H1 : θ = θ1.

2.2 Teoria dei Giochi

I primi studi di teoria dei giochi risalgono alla fine degli anni ’20, ad opera di John von Neumann [15]. Successivamente lo stesso von Neumann ed Oskar Morgenstern ampliarono questo lavoro, applicando le teorie di von Neumann alla descrizione dei comportamenti umani nell’ambito economico, creando quello che viene definito il lavoro sul quale si basa la moderna teoria dei giochi [4].

Al giorno d’oggi la teoria dei giochi [5] è un campo della matematica che si occupa di descrivere e studiare situazioni in cui due o pi ù agenti interagiscono, modellizzandole sotto forma di gioco strategico. In altri termini, è lo studio delle decisioni prese dai singoli agenti nella situazione descritta dal gioco al fine di

(18)

Insieme Elementi N n1 = Alice, n2= Bruno A a1,1 = partita, a1,2= cinema, a2,1 = partita, a2,2= cinema U1 u1(a1,1, a2,1) = 1, u1(a1,1, a2,2) = −1, u1(a1,2, a2,1) = 2, u1(a1,2, a2,2) = 4 U2 u2(a1,1, a2,1) = 4, u2(a1,1, a2,2) = −1, u2(a1,2, a2,1) = 2, u2(a1,2, a2,2) = 1

Tabella 2.1: Esempio di gioco: la battaglia dei sessi.

massimizzare il proprio guadagno personale, tenuto conto che le proprie de-cisioni influenzano lo stato del gioco percepito dagli altri agenti (e viceversa). Trova applicazione in molti campi, sia scientifici che umanistici.

Un gioco strategico è descritto da una tripla di elementi < N, A, U >, dove N rappresenta l’insieme degli agenti che prendono parte al gioco (chiamati giocatori), A è l’insieme gli stati del gioco possibili ed ui è la funzione di utilità

per il giocatore i − esimo.

L’insieme A `e composto dal prodotto cartesiano degli insiemi A1, A2...An,

dove l’insieme Ai rappresenta le azioni possibili per l’i − esimo giocatore.

La funzione di utilità riveste uno scopo di primaria importanza nell’ambito dello studio dei giochi strategici. La funzione di utilità infatti mappa gli stati del mondo su un insieme di numeri reali, esprimendo il grado di preferenza che l’agente ha per ciascuno stato. Questo permette di definire un ordine di preferenza tra gli stati. Quindi la funzione di utilità per l’agente i è definita come:

ui : A 7→ R

Nel caso in cui, per un qualsiasi motivo, il valore dell’utilit`a non dovesse essere calcolabile deterministicamente, si parla di utilit`a attesa.

L’insieme delle azioni scelte dai giocatori è detto strategia. Nel caso che i giocatori scelgano deterministicamente una strategia si parla di strategie pure, mentre se la strategia è una distribuzione di probabilità su tutte le azioni pos-sibili si parla di strategie miste.

Esempio (la battaglia dei sessi). Si prenda in considerazione una coppia di persone, Alice e Bruno. I due devono decidere come passare il Sabato sera, e si trovano di fronte due possibilit`a di scelta: andare a vedere la partita di cal-cio oppure andare al cinema. Bruno preferirebbe andare a vedere la partita, in quanto non apprezza il cinema, mentre per Alice vale il contrario. Inoltre, en-trambi preferirebbero ritrovarsi nello stesso luogo piuttosto che andare in due

(19)

posti separati. Lo scopo del gioco per i due agenti `e di scegliere dove andare, senza poter comunicare tra di loro.

Supponendo di assegnare un’utilit`a di +3 nel caso l’agente vada nel luogo che preferisce, -1 e +1 rispettivamente nel caso che entrambi vadano nello stes-so luogo o in due luoghi diversi e 0 nel castes-so che l’agente non vada nel luogo che preferisce, la tripla che rappresenta il gioco `e composta descritto in tabella 2.1.

2.2.1 Giochi in forma normale

La forma normale è una delle possibili rappresentazioni per le interazioni stra-tegiche tra gli agenti. Il gioco viene descritto sotto forma di matrice delle uti-lità, che riporta le utilità attese per tutti i giocatori in ogni possibile stato del gioco. Tipicamente vengono rappresentati in forma normale i giochi simul-tanei (in cui l’ordine in cui i giocatori scelgono l’azione da compiere non ha importanza), ma è possibile ridurre in forma normale anche giochi sequenziali.

Figura 2.1: Rappresentazione in forma normale della battaglia dei sessi Esistono vari concetti di soluzione per i giochi in forma normale. Di seguito sono riportati i principali.

Minmax

La strategia minmax è puntata a danneggiare l’avversario, indipendente-mente dal proprio guadagno personale. Il giocatore cercherà quindi di sele-zionare l’azione che minimizza la massima utilità attesa dell’avversario. Chia-mando i e j i due giocatori, la strategia minmax del giocatore i è definita come segue:

minmaxi = minsimaxsjuj(si, sj)

La strategia minmax `e comunque difficilmente applicata.

Maxmin

La strategia maxmin è il duale della strategia minmax. Il giocatore che sceglie di giocare secondo la strategia maxmin partirà dall’assunzione che il suo avversario sta giocando una strategia minmax: il suo scopo è quindi quello

(20)

di massimizzare il minimo guadagno atteso per se stesso. La strategia maxmin per il giocatore i `e dunque definita come segue:

maxmini = maxsiminsjui(si, sj)

Minmax regret

Sia r(si, sj) il rimpianto del giocatore per l’aver giocato la strategia si

in-vece che la strategia sj, ovvero r(si, sj) = u(si) − u(sj) con si 6= sj. Si

defini-sce come minmax regret la strategia che minimizza il massimo rimpianto. Pi `u formalmente la strategia minmax regret `e definita come;

minmaxr = minsimaxsj(u(sj) − u(si))

Pareto ottimalit`a

Il concetto di Pareto ottimalit`a di una strategia `e strettamente legato a quel-lo di Pareto dominanza. Si dice che una strategia s domina una strategia s0

se giocare s al posto di s0 non è sconveniente per nessun giocatore ed apporta beneficio ad almeno un giocatore. In altri termini, per nessun giocatore la stra-tegia s0 _{è una scelta migliore della strategia s ma per almeno un giocatore s è}

una scelta migliore di s0. Formalmente si ha che s0 `e Pareto dominata da s se ∀i ∈ N (ui(s) ≥ ui(s0)) ∧ ∃j ∈ N (uj(s) > uj(s0))

Definito il concetto di Pareto dominanza, si dice che una strategia s `e Pareto ottimale se non esiste alcuna soluzione s0 _{che `e Pareto dominante rispetto ad s.}

Le strategie Pareto ottimali sono, appunto, ottimali, e quindi rappresentano una possibile soluzione del gioco. Ogni gioco possiede almeno una soluzione Pareto ottimale, ma pu `o esisterne pi `u d’una.

Questo tipo di soluzione, per ò, è affetto da instabilità: difatti ha come ipo-tesi implicita il fatto che un agente non miri a danneggiare gli altri giocatori (scegliendo di conseguenza di compiere un’azione che non comporti un calo nell’utilità rispetto alle altre), mentre in generale non è cos`ı.

Equilibri di Nash

Il problema dell’instabilit`a delle soluzioni Pareto ottimali viene risolta da John Nash. Un equilibrio di Nash `e una strategia che si basa sul concetto di best response. Sia s una strategia ed s1, s2...sn le sue componenti, e si chiamino

si l’azione scelta dal giocatore i-esimo ed s−i l’insieme delle azioni scelte da

tutti gli altri giocatori: si si dice risposta ottima (best response) del giocatorei

i-esimo ad s−i se nessun’altra azione s0i del giocatore gli garantisce una utilit`a

maggiore. Formalmente si definisce risposta ottima l’azione si che soddisfa la

seguente condizione: ∀s0

(21)

Si definisce equilibrio di Nash una strategia s∗tale che ogni sua componen-te s∗

i sia una risposta ottima per il giocatore i-esimo alle azioni compiute dagli

altri giocatori.

∀i ∈ N (∀s0

i 6= si(ui(si, s−i) ≥ ui(s0i, s−i)))

In ogni gioco in forma normale esiste almeno un equilibrio di Nash.

Dominanza iterata

Un metodo per poter semplificare il calcolo degli equilibri di Nash `e quello di eliminare (virtualmente) le strategie dominate. Una strategia si si dice

do-minata da una strategia s0

i garantisce sempre una utilit`a inferiore ad s0i, quale

che siano le azioni che compongono s−i. Una soluzione dominata non pu `o,

per ovvi motivi, far parte di un equilibrio di Nash.

Il metodo della dominanza iterata consiste nel restringere la tabella delle utilit`a cancellando le azioni relative alle strategie dominate, e quindi calcolan-do gli equilibri di Nash sulla tabella risultante.

Equilibri Leader-Follower

L’idea che sta dietro al concetto di Leader-Follower è che uno dei gioca-tori (detto, appunto, Leader), comunichi in anticipo ai suoi avversari l’azione che è intenzionato a giocare. Sebbene questa linea d’azione potrebbe sembra-re sconveniente per il Leader, poiché da un vantaggio agli avversari, in sembra-realtà gli garantisce di massimizzare la propria utilità. Comunicando in anticipo l’a-zione che intende giocare, infatti, il giocatore Leader pu ò far affidamento sul fatto che gli altri giocatori risponderanno con la strategia che massimizza la loro utilità. Basandosi su questo, il Leader pu ò calcolare per ognuna delle sue azioni quale sarà la risposta dei suoi avversari. Di conseguenza pu ò calcolare l’utilità che ricaverà da ogni azione, e quindi scegliere quale azione giocare (e comunicare agli avversari).

Esempi di soluzione (la battaglia dei sessi). Si prenda nuovamente in con-siderazione il gioco della battaglia dei sessi.

Maxmin - Se Alice scegliesse di andare alla partita, riceverebbe come utilit`a minima possibile -1, associata alla decisione di Bruno di andare al cinema; se scegliesse invece di andare al cinema, riceverebbe nel caso peggiore una uti-lit`a pari a 2. Bruno, invece, riceverebbe nel caso peggiore -1 se decidesse di andare al cinema, e 2 se decidesse di andare alla partita. Se Alice e Bruno gio-cassero una strategia minmax andrebbero l’uno alla partita e l’altra al cinema, assicurandosi entrambi un guadagno di 2.

Minmax regret - Se Alice scegliesse di andare alla partita e Bruno fosse anda-to al cinema, Alice riceverebbe una utilit`a di -1 invece che una di 4, quindi con un rimpianto pari a 5; viceversa se Alice decidesse di andare al cinema e Bruno

(22)

alla partita, Alice avrebbe un rimpianto pari ad 1 (ricevendo una utilità di 1 in-vece che di 2). Analogamente, Bruno avrebbe un rimpianto di 5 se andasse al cinema mentre Alice è alla partita e di 1 nel caso contrario. Di nuovo, quindi, Bruno sceglierà di andare alla partita mentre Alice opterà per il cinema.

Soluzioni Pareto ottimali - Si osservi la Figura 2.1, che riporta la rappresen-tazione in forma normale del gioco (dove le righe rappresentano la scelta di Alice e le colonne la scelta di Bruno), ed etichettiamo le quattro possibili strate-gie come s1 = (partita, partita), s2 = (partita, cinema), s3 = (cinema, partita),

s4 = (cinema, cinema). Dalla figura si pu `o intuire facilmente come s1 non sia

Pareto dominata da nessuna delle altre strategie, poich´e Bruno riceve una uti-lit`a maggiore giocando s1 rispetto a qualsiasi altra strategia (ed Alice rispetto

ad s2). Analogamente s4non `e dominata da nessuna delle altre strategie (Alice

riceve di pi ù rispetto ad ogni altra strategia e Bruno rispetto ad s2), né lo è s3

(Bruno riceve di pi `u rispetto ad s4, Alice rispetto ad s1 ed entrambi rispetto

ad s2). Al contrario, s2 risulta essere Pareto dominata da ciascuna delle altre

strategie. Ne risulta che s1, s3 ed s4 sono tre strategie Pareto ottimali per il

gioco.

Equilibri di Nash - Dalla tabella delle utilità riportata in Figura 2.1 si pu ò ricavae facilmente l’equilibrio di Nash del gioco utilizzando il metodo della dominanza iterata. L’azione cinema domina l’azione partita per Alice, men-tre viceversa l’azione partita domina l’azione cinema per Bruno. Il gioco ha dunque un unico equilibrio di Nash, che è la strategia s∗ = (cinema, partita).

Leader-Follower - Ipotizziamo che Alice sia il giocatore Leader: comunican-do l’azione partita come sua scelta di gioco, anche Bruno giocherebbe partita, garantendo ad Alice una utilità pari ad 1; se invece Alice comunicasse cinema, Bruno continuerebbe a scegliere partita ma l’utilità di Alice sarebbe pari a 2. Come leader, quindi, Alice giocherebbe cinema, garantendosi una utilità di 2. Analogamente, se Bruno scegliesse di giocare - e comunicare - l’azione partita si garantirebbe una utilità di 2, poiché Alice giocherebbe cinema, mentre se giocasse cinema si garantirebbe una utilità di 1. Anche in questo caso, quindi, la soluzione di equilibrio sarebbe la strategia s = (cinema, partita).

2.2.2 Giochi in forma estesa

Come la forma normale viene utilizzata per rappresentare i giochi simultanei, la forma estesa viene normalmente utilizzata per i giochi sequenziali. Il gio-co viene rappresentato graficamente sotto forma di albero, e formalmente `e descritto da una tupla di otto elementi < N, A, H, Z, χ, ρ, σ, u >, dove:

• N `e l’insieme degli n giocatori; • A `e l’insieme delle azioni possibili

(23)

• Z `e l’insieme dei nodi foglia dell’albero;

• χ : H 7→ A `e una funzione che assegna ad ogni nodo intermedio l’insieme Ahdi azioni che in esso ammissibili;

• ρ : H 7→ N `e una funzione che collega ogni nodo intermedio con il giocatore a cui spetta il turno di gioco;

• σ : H × χ(h ∈ H) 7→ H ∪ Z `e una funzione che per ogni coppia nodo intermedio - azione assegna al nodo intermedio il suo successore;

• u : Z 7→ Rn _{`e una funzione che assegna ad ogni nodo foglia le utilit`a che}

esso garantisce ai giocatori.

Nel caso di giochi ad informazione imperfetta - in cui i giocatori non hanno certezza del nodo in cui si trovano - alla tupla si aggiunge un nono elemento, I = I1, I2, ..., In i cui elementi Ii sono insiemi di classi di equivalenza per il

giocatore i, con la propriet`a che ∀h, h0 ∈ Ii(χ(h) = χ(h0) ∧ ρ(h) = ρ(h0)).

È possibile trasformare ogni gioco in forma estesa in un gioco in forma nor-male, che per ò risulterà essere estremamente esteso. Per fare ci ò si ridefinisce l’insieme delle azioni di ogni giocatore come insieme di ogni possibile sequen-za di azioni che questi pu ò giocare nel gioco in forma estesa. Chiamando Hi

l’insieme dei nodi intermedi hij tali che ρ(hij) = i, il nuovo insieme di azioni

del giocatore i-esimo sar`a:

Ai = hi1× hi2× ...

In questo modo `e possibile calcolare le soluzioni di equilibrio per i giochi in forma estesa calcolando quelli del gioco in forma normale.

Equilibrio perfetto per sottogiochi

Trasformare un gioco in forma estesa in uno in forma normale, per ò, fa perdere di vista la sequenzialità delle azioni nel gioco originale. Ne consegue che un equilibrio calcolato in un gioco in forma normale non sempre è un equilibrio per l’equivalente in forma estesa.

Un altro concetto di soluzione per i giochi in forma estesa `e quello di subga-me perfect equilibrium. Definendo cosubga-me sottogioco di un gioco ad informazione perfetta G un gioco G0 che sia una restrizione di G a partire da un nodo h, si chiama subgame perfect equilibrium una strategia s tale per cui per ogni sot-togioco G0di G la restrizione di s ai nodi di G0sia un equilibrio di Nash per G0. Inoltre essendo G un sottogioco di se stesso definito a partire dal nodo radice, ogni subgame perfect equiibria `e un equilibrio di Nash per G.

Un subgame perfect equilibrium si pu `o calcolare piuttosto facilmente per backward induction, tramite un algoritmo che implementa una singola ricerca

(24)

depth first dell’albero del gioco, usando le utilit`a dei giocatori come discrimi-nante per scegliere un nodo piuttosto che un altro. Il calcolo di tutti i subga-me perfect equilibria in un gioco ad informazione perfetta a due giocatori `e effettuabile in tempi cubici rispetto alla dimensione dell’insieme Z del gioco.

2.2.3 Giochi Bayesiani

I giochi Bayesiani, o giochi a informazione incompleta [2], rappresentano gio-chi in cui i giocatori hanno delle incertezze sulla situazione di gioco. L’incer-tezza viene rappresentata sotto forma di n distrubuzioni di probabilità su un insieme di giochi diversi ma con gli stessi insiemi N ed A, ognuna delle quali rappresenta la probabilità con cui ciascun giocatore ritiene di trovarsi in ognu-no dei giochi. Noognu-nostante la condizione che gli insiemi N ed A siaognu-no uguali pu ò sembrare troppo restrittiva in quanto l’incertezza potrebbe essere, appun-to, sul numero di giocatori o sulle azioni a loro possibili, queste ultime due incertezze possono essere rappresentate tramite variazioni nelle utilità.

I giochi Bayesiani possono essere rappresentati in tre modi principali: tra-mite information set, come giochi in forma estesa o tratra-mite tipi epistemici.

Definizione 2.2.1 (Gioco Bayesiano - Information Set). Un gioco Bayesiano `e una tupla di quattro elementi < N, G, P, I > dove:

• N `e l’insieme degli n giocatori;

• G `e un insieme di giochi con identico insieme N dei giocatori, tali che se g, g0 ∈ G allora ogni giocatore i ∈ N avr`a lo stesso spazio delle azioni in g come in g0;

• P `e l’insieme delle distribuzioni di probabilit`a assegnate a priori dai giocatori ai giochi appartenenti all’insieme G;

• I = (I1, I2, ..., In)`e un insieme di partizioni di G, ognuna associata ad un

agente.

Definizione 2.2.2(Gioco Bayesiano - Forma Estesa). Un gioco Bayesiano `e una tupla di nove elementi < N, A, H, Z, χ, ρ, σ, n∗, u >, dove:

• N `e l’insieme degli n+1 giocatori (1, 2, ..., n, n∗₎

;

• A, H, Z, χ, ρ, σ, u sono gli elementi descritti per i giochi in forma estesa; • n∗

`e il giocatore detto Natura.

Il giocatore Natura gioca solo nel nodo radice, scegliendo (tipicamente stoca-sticamente) il sottoalbero che descrive il gioco.

(25)

Definizione 2.2.3(Gioco Bayesiano - Tipi Epistemici). Un gioco Bayesiano `e una tupla di cinque elementi < N, A, Θ, p, u > dove:

• N `e l’insieme degli n giocatori;

• A `e l’insieme delle azioni, composto dagli n insiemi A1, A2, ..., An;

• Θ = Θ1× Θ2× ... × Θn`e l’insieme dei tipi, dove Θirappresenta i possibili

tipi che il giocatore i-esimo pu ò assumere; • p è la distribuzione di probabilità a priori su Θ; • u è la funzione di utilità attesa.

Dato un gioco Bayesiano descritto nella sua rappresentazione tramite tipi epistemici, gli equilibri di Nash si calcolano esattamente come nei giochi in forma normale: a partire dalle risposte ottime dei giocatori.

Le risposte ottime vengono per ò calcolate, in questo caso, basandosi sul concetto di utilità attesa ex ante. Data una strategia mista s in un gioco Bayesia-no, la sua utilità attesa ex ante per il giocatore i-esimo si calcola come

EUi(s) = P θ∈Θp(θ) P a∈A( Q j∈N sj(aj|θj))ui(a, θ)

definendo come sj(aj|θj)la probabilit`a che l’agente j-esimo appartenente al

tipo θj giochi l’azione aj, come definita in sj.

2.2.4 Ottimizzazione matematica

Per tutte le classi di gioco descritte in precedenza `e possibile risalire ad una soluzione formalizzando il gioco stesso sotto forma di problema di ottimizza-zione matematica.

Il calcolo della strategia maxmin `e effettuabile formalizzando il gioco come problema di programmazione lineare intera. Supponendo di voler calcolare la strategia maxmin per il giocatore 1:

max v1

s.t. U1x1 ≥ 1v1

1Tx1 = 1

x1 ≥ 0

dove U1 è la matrice delle utilità per il giocatore 1, x1 è un vettore i cui

elementi x1,j rappresentano la probabilit`a di giocare la j-esima azione e v1 `e

l’utilit`a massima attesa dal giocatore 1. Per il calcolo degli equilibri di Nash invece `e necessario l’utilizzo di programmazione mista intera. Per ogni gioca-tore si ipotizza nota la strategia dell’avversario, e si calcolano il problema di ottimizzazione relativo alla risposta ottima alla strategia (nell’esempio per il giocatore 1, con ¯x2che rappresenta la strategia del giocatore 2):

(26)

max xT 1U1x¯2

s.t. 1Tx1 = 1

x1 ≥ 0

ed il suo problema duale

min v1

s.t. 1v1 ≥ U1x¯2

Quindi si descrivono entrambe le formulazioni (primale e duale) tramite sistema di vincoli, sfruttando il teorema degli scarti complementari, e si uni-scono i due risultati facendo cadere l’assunzione che le azioni degli avversari siano note e fissate.

x1 ≥ 0 x2 ≥ 0 1T_x 1 = 1 1Tx2 = 1 1v1− U1x2 ≤ M (1 − s1) 1v2− U2Tx1 ≤ M (1 − s2) x1 ≤ s1 x2 ≤ s2 (s1)j ∈ 0, 1 (s2)j ∈ 0, 1

Nel caso di un gioco di Stackelberg, e quindi di un equilibrio Leader-Follower [14], si pu `o utilizzare un problema di programmazione lineare. Per ogni stra-tegia pura t del giocatore Follower si calcola la strastra-tegia mista del Leader tale che t sia una risposta ottima per il giocatore Follower alla strategia del Leader e che la strategia del Leader massimizzi la sua utilit`a a seguito della strategia t

max P s∈Spsul(s, t) s.t. ∀t0 _{∈ T,}P s∈Spsuf(s, t) ≥ P s∈Spsuf(s, t0) P s∈Sps = 1 ∀s ∈ S, ps ≥ 0

Tra queste, si seleziona quindi quella che massimizza l’utilità del Leader. Ovviamente nel caso si voglia che il Leader giochi una strategia pura biso-gnerà inserire un vincolo che imponga che la probabilità di giocare una singola strategia sia pari a 0 oppure 1.

2.2.5 Giochi per la sicurezza

La sicurezza è un campo di importanza primaria, che ha a che fare con una moltitudine di realtà e scenari. La Teoria dei Giochi pu ò venire efficacemente utilizzata in quest’ambito [1] [8] [9], per ottimizzare l’allocazione delle risorse e la pianificazione della risoluzione dei problemi.

I giochi per la sicurezza rientrano nella categoria dei giochi di Stackelberg caratterizzati dalla presenza di due tipi di giocatori: attaccanti e difensori. Lo

(27)

scenario tipicamente include il fatto che il difensore non ha una conoscenza completa sugli attaccanti, ed inoltre i giocatori si trovano in una situazione di tipo Leader-Follower, con il difensore che fa la parte del giocatore Leader. La prima formulazione di un gioco per la sicurezza è da attribuire molto pro-babilmente a John Von Neumann [16]. Il gioco è di tipo zero-sum (la somma delle utilità dei due giocatori fa sempre zero) a due giocatori, e si svolge in un ambiente a griglia. Uno dei giocatori chiamato hider decide una casella della griglia dove nascondersi mentre il secondo giocatore, detto seeker, seleziona un insieme di caselle dove cercare. A partire dal lavoro di von Neumann sono state definite diverse varianti, definite a seconda della mobilità dei giocatori: se entrambi i giocatori possono cambiare posizione si parla di giochi di infiltra-zione [3]; se l’agente seeker è mobile e l’agente hider non pu ò spostarsi si parla di giochi di ricerca; se la situazione è inversa rispetto ai giochi di ricerca, infine, si parla di giochi di agguato.

C’`e infine un importante caso particolare dei giochi di infiltrazione, chiama-to gioco di interdizione in cui il giocachiama-tore hider deve spostarsi da una posizione di origine ad una posizione obiettivo.

(28)

(29)

Capitolo 3

Struttura del problema e strumenti

utilizzati

Nel presente lavoro di tesi è stato deciso di modellare il controllo di qualità di una linea di produzione sotto forma di gioco strategico a due giocatori. Il pri-mo dei due giocatori va a simulare un CDT, nello specifico un test di Shewhart, mentre il secondo modella un agente esterno al processo che introduca varia-zioni nella produzione. Nello specifico l’azione del secondo giocatore si arti-cola nella modulazione dei parametri che descrivono la distribuzione di pro-babilità degli esiti dell’esperimento aleatorio “produzione”. Il problema che è stato affrontato consiste nel verificare l’ipotesi che esistano condizioni tali per cui il gioco strategico, simulato come descritto, presenti delle soluzioni note-voli. Per soluzione notevole si intende una strategia che sia di equilibrio per tutti i giochi costruiti come sopra descritto, al variare di selezionati parametri. L’obiettivo è stato dunque quello, dopo aver distinto vari casi possibili per il gioco, di ricercare una soluzione notevole intesa come descritto poc’anzi, oppure di verificare l’esistenza di un equilibrio in strategie pure per i casi in cui non è stato possibile trovare tale soluzione notevole.

3.1 Fasi del lavoro

Al fine di verificare l’esistenza delle strategie notevoli si è deciso di adotta-re un approccio na¨ıve al problema, simulando una gran quantità di partite e verificando le ipotesi esposte in precedenza. La ricerca si è svolta in due fasi:

• si `e verificata la possibilit`a di individuare una soluzione notevole in for-ma chiusa;

• dove non si `e trovata alcuna soluzione notevole, si sono effettuati vari test volti alla conferma dell’effettiva esistenza di un equilibrio in strategie pure.

(30)

Nella prima fase si è effettuato uno studio qualitativo del problema senza analizzare specifici dati numerici. Dopo aver suddiviso in macro-categorie le possibili occorrenze del gioco, a seconda del valore di alcuni parametri, si è passati ad studiare il comportamento generale delle utilità dei giocatori caso per caso, basandosi su questo studio per individuare i casi in cui è possibile rintracciare una soluzione di equilibrio in forma chiusa dai casi in cui invece è necessaria l’analisi degli effettivi valori numerici del problema.

Nella seconda fase è stata quindi effettuata la seconda analisi su diversi giochi, variando i parametri del test e generando quindi le matrici di utilità dei due giocatori. Le matrici di utilità sono poi state utilizzate come input per diversi test volti alla ricerca dell’esistenza di un equilibrio in strategie pure.

Il primo dei test effettuati ha previsto la descrizione in forma matemati-ca delle due utilità attese dei due giomatemati-catori, il cui valore dipende ovviamente dalle due azioni scelte dai giocatori. Si è quindi proceduto con il selezionare una scelta iniziale di azione per uno dei due giocatori e quindi con il calco-lare, tramite l’utilizzo dell’ambiente di calcolo Matlab, il punto di massimo della funzione relativa all’utilità dell’altro giocatore in corrispondenza di que-sta scelta iniziale, corrispondente alla rispoque-sta ottima per il giocatore. Si è poi calcolato iterativamente il punto di massimo di una o dell’altra funzione in corrispondenza del valore calcolato in precedenza per l’altro giocatore, fino al raggiungimento di un criterio di arresto.

Il secondo test `e stato effettuato utilizzando una versione modificata del-l’algoritmo di Lemke-Howson per il ritrovamento degli equilibri del gioco.

Infine si `e utilizzata la modellazione del test in forma di vari problemi di ottimizzazione matematica, risolti utilizzando il linguaggio di modellazione algebrica AMPL ed il risolutore CPlex.

3.2 Software utilizzati

Per l’esecuzione dei test descritti nella precedente sezione sono stati utilizzati svariati software.

Matlab

Matlab (Matrix laboratory) `e un ambiente di calcolo numerico multipiatta-forma che mette a disposizione dell’utente una vasta gamma di strumenti matematici, oltre a consentire l’implementazione di algoritmi ed altre utilit`a. Sviluppato utilizzando i linguaggi di programmazione C e Java, nonostante sia nato come strumento di puro calcolo numerico la successiva implemen-tazione di svariati pacchetti software ne ha consentito l’utilizzo anche per il calcolo simbolico, la simulazione grafica e la progettazione basata su

(31)

model-li. `E possibile richiamare da Matlab algoritmi scritti in differenti linguaggi di programmazione (come ad esempio i linguaggi C e C++).

In questo lavoro di tesi Matlab è stato utilizzato nella sua funzione pri-maria, ovvero il calcolo numerico. Sono stati implementati svariati algoritmi al fine di semplificare e velocizzare l’esecuzione dei test, sfruttando la capa-cità del software di manipolare le matrici numeriche. Gli algoritmi sono stati implementati sia per popolare automaticamente le matrici di utilità dei due giocatori al variare dei parametri del gioco sia per effettuare uno dei test atti al ritrovamento degli equilibri del gioco, sfruttando una ricerca dicotomica sui grafici che rappresentano le utilità stesse.

AMPL

AMPL (A Mathematical Programming Language) `e un linguaggio di program-mazione per la descrizione e la risoluzione di problemi matematici complessi, sviluppato in modo tale da avere una sintassi estremamente simile alla nota-zione matematica per la defininota-zione dei problemi di ottimizzanota-zione (e quindi da facilitare la scrittura e la lettura della descrizione dei problemi). La soluzio-ne di un problema richiede la preparaziosoluzio-ne di due file, uno con la descriziosoluzio-ne del problema stesso e l’altro contenente i dati numerici da utilizzare nel cal-colo, che vengono utilizzati come input per un risolutore, un software che ha il compito per l’appunto di risolvere il problema. AMPL supporta svariati risolutori, come ad esempio CPLEX e MINOS.

AMPL `e stato utilizzato per la risoluzione del gioco rappresentante il test di Shewhart, rappresentato in tre diversi problemi di ottimizzazione (relati-vi alla formulazione del gioco in forma normale, come gioco bayesiano e per la ricerca di un equilibrio leader-follower). I file contenenti i dati numerici sono stati generati tramite l’implementazione di un algoritmo in Matlab, che ha poi richiamato lo stesso AMPL per la risoluzione del problema associato, utilizzando il risolutore CPLEX.

Algoritmo di Lemke-Howson

Infine `e stata utilizzata una implementazione in linguaggio C dell’algoritmo di Lemke-Howson, funzionante sulle piattaforme Unix e derivate. L’imple-mentazione utilizzata modifica leggermente l’algoritmo originale, introducen-do un elemento di casualit`a e ripetizione che migliora le prestazioni generali dell’algoritmo. Di nuovo, come nel caso dell’utilizzo di AMPL, questa imple-mentazione richiede un file di input contenente i dati numerici che descrivono il gioco, anche in questo caso generati dal medesimo codice Matlab.

Durante le prime esecuzioni dei test `e stato riscontrato un errore di in-stabilit`a numerica dovuta alla scelta della precisione nella rappresentazione

(32)

dei numeri manipolati dall’algoritmo. Un’ulteriore versione dell’algoritmo, implementata con una maggiore precisione, ha risolto questo problema.

(33)

Capitolo 4

Test di Shewhart

Il test di Shewhart [13] è un CDT (Change Detection Test) sviluppato nei primi anni ’10. Nella sua concezione originale, è un test di controllo di qualità in un processo produttivo.

4.1 Formalizzazione del test

Gli articoli prodotti vengono modellati con una serie di variabili casuali i.i.d. X generate da una distrubuzione di probabilità nota. Vengono quindi selezio-nate una o pi ù caratteristiche della distribuzione di probabilità (ad esempio la media e la varianza) e viene impostata una fascia di controllo centrata nel valore nominale di tale caratteristica.

Ad intervalli prefissati vengono calcolati i valori campionari relativi agli articoli prodotti. Questi vengono poi confrontati con la fascia di controllo im-postata: se i valori rilevati non sono contenuti nella fascia di controllo viene segnalata un’anomalia comportando un blocco del sistema produttivo.

Se l’anomalia fosse il risultato dell’intervento di un agente esterno, il cui scopo `e quello di modificare il normale andamento del sistema, il test di Shewhart pu `o essere formalizzato sotto forma di gioco strategico.

In questo caso il giocatore relativo all’anomalia, chiamato giocatore Attac-cante, ha l’obiettivo di modificare i parametri della distrubuzione che gene-ra le variabili Xi, e le sue azioni nel gioco indicheranno di quanto intende

modificare i parametri di detta distribuzione.

Il giocatore relativo al test invece, chiamato giocatore Difensore, tenta di in-dividuare l’intervento del giocatore Attaccante impostando la soglia di accetta-bilit`a per i parametri campionari; le sue azioni esprimono la distanza dei bordi della fascia dal valore nominale del parametro. Ovviamente, poich`e la segna-lazione di un’anomalia implica il blocco del sistema produttivo, il giocatore Difensore deve prestare attenzione ad impostare la fascia di controllo in modo

(34)

Segnalazione NoSegnalazione ∆µ >0 AttaccanteCatturato VittoriaAttaccante ∆µ= 0 FalsoPositivo StatusQuo

Tabella 4.1: Esiti del gioco.

tale da non segnalare come anomalie eventuali articoli prodotti normalmente ma con valori particolarmente alti (o bassi).

Supponendo che il test si limiti a controllare la media campionaria, quindi, il giocatore Attaccante imposta un valore ∆µ con cui andrà a modificare la media del processo produttivo, mentre il giocatore difensore imposta la soglia di accettabilità h. Se il valore della media campionaria sarà esterno ai limiti della fascia di accettabilità, verrà segnalata la presenza dell’agente esterno. Il gioco sopra descritto ha, quindi, quattro possibili esiti a seconda dei valori scelti dai due giocatori. I suddetti esiti sono riportati in Tabella 1.1.

A seconda dell’esito del gioco, i due giocatori ricevono un diverso valore di ritorno. Pi ù precisamente, il giocatore Difensore riceverà un ritorno positi-vo qualora indichi correttamente la presenza di un’anomalia (o non ne indichi in assenza di anomalia) e nullo altrimenti, mentre il giocatore Attaccante ri-ceverà un ritorno positivo qualora riesca ad agire sul processo senza essere individuato.

Indicando con UD l’utilit`a del difensore e con UA quella dell’attaccante, e

con R il responso del giocatore difensore (A per indicare che il giocatore Di-fensore ha indicato la presenza del giocatore Attaccante, N A per indicarne il caso contrario) quindi, si avr`a:

UD = n 1 ∆µ > 0, R = A 1 ∆µ = 0, R = N A 0 altrimenti UA = n 1 ∆µ > 0, R = N A − altrimenti

Quanto descritto finora prende ovviamente come certa la presenza di un giocatore Attaccante (che pu ò comunque decidere se giocare o meno). Non è per ò detto che un giocatore Attaccante sia effettivamente presente nel gioco. La formalizzazione del Test di Shewhart assume quindi la forma di un gio-co Bayesiano, non a somma zero, in cui i giocatori possono appartenere ad uno specifico tipo. Nel caso del test di Shewhart, per il giocatore Attaccante possono essere definiti due tipi θ1 e θ2 che descrivono la presenza o meno

del-l’Attaccante all’interno del gioco. In questo caso, i valori sopra descritti per le utilit`a dei due giocatori saranno validi unicamente per il caso in cui il tipo θA del giocatore Attaccante sia θ1, ovvero per il caso in cui sia presente. Con

(35)

UD =

n 1 R = N A −γ R = A UA= 0

I valori indicati con e γ indicano due fattori di penalità che vengono as-segnati ai giocatori: il giocatore Attaccante riceverà una penalità pari a − nel caso in cui venga individuato dal giocatore Difensore; il giocatore Difensore, invece, riceverà una penalità pari a −γ a seguito di un falso positivo.

Quanto appena descritto rappresenta un singolo turno del gioco, e viene ri-petuto ad intervalli regolari lungo una finestra temporale di durata prefissata (indicata con il numero di intervalli, T). Ad ogni turno il giocatore Difenso-re esegue un controllo sui valori campionari da consideraDifenso-re, per decideDifenso-re se segnalare o meno la presenza di un’anomalia.

4.2 Formalizzazione delle strategie

Il comportamento migliore, ricercato sotto forma di equilibrio di Nash, che i due attori del gioco possono assumere dipende strettamente da quattro fat-tori: le due penalit`a, l’istante in cui il giocatore Attaccante entra in gioco e l’istante in cui i giocatori ricevono il ritorno indicato dall’utilit`a. Supponiamo per il momento che i due giocatori ricevano il ritorno al termine dell’orizzonte temporale.

4.2.1 Caso 1

Nel primo caso, il giocatore Attaccante ha le seguenti caratteristiche: • `e presente fin dal primo istante di gioco;

• `e sempre costretto a giocare.

In questo caso entrambi i giocatori hanno una unica tabella delle utilità. Per il giocatore Difensore l’utilità sarà crescente con l’aumentare di h nel caso che il giocatore Attaccante decida di giocare ∆µ = 0, con una utilità pari a −γ in h = 0, decrescente all’aumentare di h, e pari ad 1 in h = 0, altrimenti. Il giocatore Attaccante, invece, riceverà un ritorno pari a 0 nel caso decida ∆µ = 0, mentre negli altri casi sarà pari a − se il Difensore opta per h = 0 ed avrà un massimo in un luogo differente a seconda del valore di ∆µ per gli altri valori di h.

Con l’analisi dell’andamento delle matrici di utilit`a si pu `o intuire la strate-gia che i due giocatori sceglieranno di attuare durante il gioco.

Teorema 4.2.1(γ = 0, = 0 ).

(36)

le penalit`a γ per il giocatore Difensore in caso di falso positivo ed per il giocatore Attaccante nel caso venga individuato poste a zero, vi saranno multipli equilibri in strategie pure situati in corrispondenza dell’azione h = 0, per ogni ∆µ.

Dimostrazione. Con γ = 0 ed = 0, il giocatore Difensore riceverà un ritorno pari a 0 qualsiasi azione egli scelga, purchè l’Attaccante abbia selezionato ∆µ = 0. Analogamente, il giocatore Attaccante riceverà sempre un ritorno pari a 0 se h = 0 (Figura 4.1).

Supponiamo di partire da una strategia iniziale corrispondente a ∆µ = 0 ed h = h1 > 0. Il giocatore Attaccante tender`a ad aumentare il valore di ∆µ,

fino a giungere alla massima utilit`a ottenibile per h = h1. A seguito di questa

azione, per ò, il giocatore Difensore cercherà di massimizzare il proprio ritorno, diminuendo il valore di h fino a 0. In questo caso il giocatore Attaccante non avrà motivo di modificare il proprio valore di ∆µ, e quindi ci si troverà in una situazione di equilibrio.

Figura 4.1: Tabella delle utilit`a con penalit`a nulle.

Teorema 4.2.2(γ = 0, > 0).

In un Change Detection Test Game rappresentante un Test di Shewhart, con la penalità γper il giocatore Difensore in caso di falso positivo nulla e la penalità per il giocatore Attaccante nel caso venga individuato positiva, vi sarà un unico equilibrio in strategie pure situato in corrispondenza delle azioni h = 0 e ∆µ = 0.

Dimostrazione. Con γ = 0 ed positiva, il giocatore Difensore riceverà un ritor-no pari a 0 qualsiasi azione egli scelga, purchè l’Attaccante abbia selezionato ∆µ = 0. Il giocatore Attaccante, invece, avrà un ritorno negativo e pari a − con ∆µ positivo ed h = 0 (Figura 4.2).

Supponiamo di partire da una strategia iniziale corrispondente a ∆µ = 0 ed h = h1 > 0. Il giocatore Attaccante tender`a ad aumentare il valore di ∆µ,

(37)

fino a giungere alla massima utilit`a ottenibile per h = h1. A seguito di questa

azione, per ò, il giocatore Difensore cercherà di massimizzare il proprio ritorno, diminuendo il valore di h fino a 0. In risposta, il giocatore Attaccante diminuirà il valore di ∆µ fino a renderlo pari a 0, poichè il ritorno atteso per qualsiasi altro valore di ∆µ sarà negativo. Il giocatore Attaccante non avrà vantaggi nel modificare il valre di h, e quindi ci si troverà in una situazione di equilibrio.

Figura 4.2: Tabella delle utilit`a con γ nulla ed positiva.

Teorema 4.2.3(γ > 0, = 0).

In un Change Detection Test Game rappresentante un Test di Shewhart, con la penalità γper il giocatore Difensore in caso di falso positivo maggiore di zero e la penalità per il giocatore Attaccante nel caso venga indivituato nulla, vi sarà un unico equilibrio in strategie pure situato in corrispondenza delle azioni h = 0 e ∆µ = ∆µ1 > 0.

Dimostrazione. Con γ positiva ed = 0, il giocatore Difensore avrà una utilità decrescente al crescere di h, in corrispondenza di ∆µ = 0, e pari a −γ in h = 0. Il giocatore Attaccante, invece, avrà una utilità nulla per ogni valore di ∆µ, se h = 0(Figura 4.3).

Supponiamo di partire da una strategia iniziale corrispondente a ∆µ = 0 ed h = 0. Il giocatore Difensore cercherà di massimizare la propria utilità, e di conseguenza aumenterà il valore di h fino al massimo consentito. A questo punto anche il giocatore Attaccante aumenterà il valore di ∆µ, per ricevere il ritorno atteso massimo corrispondente ad h = hmax. Il giocatore Difensore

diminuirà quindi il valore di h fino al valore minimo h = 0, aumentando di conseguenza il proprio ritorno. Il giocatore Attaccante, a quel punto, non avrà vantaggio nel modificare il valore di ∆µ, e quindi ci si troverà in una situazione di equilibrio.

(38)

Figura 4.3: Tabella delle utilit`a con γ positiva ed nulla.

Teorema 4.2.4(γ > 0, > 0).

In un Change Detection Test Game rappresentante un Test di Shewhart, con la penalit`a γ per il giocatore Difensore in caso di falso positivo maggiore di zero e la penalit`a per il giocatore Attaccante nel caso venga indivituato anch’essa, il gioco non presenta strategie pure.

Dimostrazione. Con γ ed positive, il giocatore Difensore avrà una utilità de-crescente al crescere di h, in corrispondenza di ∆µ = 0, e pari a −γ in h = 0. Il giocatore Attaccante, invece, avrà un ritorno negativo e pari a − con ∆µ positivo ed h = 0 (Figura 4.4).

Supponiamo di partire da una strategia iniziale corrispondente a ∆µ = 0 ed h = 0. Il giocatore Difensore cercherà di massimizare la propria utilità, e di conseguenza aumenterà il valore di h fino al massimo consentito. A questo punto anche il giocatore Attaccante aumenterà il valore di ∆µ, per ricevere il ritorno atteso massimo corrispondente ad h = hmax. Il giocatore Difensore

diminuirà quindi il valore di h fino al valore minimo h = 0, aumentando di conseguenza il proprio ritorno. Il giocatore Attaccante, a quel punto, riporterà il valore di ∆µ a zero, in modo da massimizzare il proprio ritorno per h = 0. Quindi si ritornerà alla situazione di partenza.

4.2.2 Caso 2

Il secondo scenario possibile `e identificato dalle seguenti caratteristiche per il giocatore Attaccante:

• la sua presenza viene decisa da un terzo giocatore, detto Natura, che rappresenta la probabilit`a di presenza del giocatore Attaccante;

(39)

Figura 4.4: Tabella delle utilit`a con γ ed positive. • se presente, `e presente fin dall’inizio del gioco;

• se presente `e sempre costretto a giocare.

In questo scenario il giocatore Attaccante ha un’unica tabella delle utilità, mentre il giocatore Difensore ne ha due: una relativa al caso in cui l’Attac-cante sia presente (ed identica a quella descritta nel primo scenario) ed una relativa al caso in cui questi sia assente (in cui ogni colonna ha i medesimi valori espressi nella colonna relativa a ∆µ = 0 come indicata nel primo scena-rio). Per il giocatore Difensore si parlerà quindi di utilità attesa, ovvero somma delle utilità nei due casi pesata per la probabilità di ciascun caso.

In questo caso si pu ò distinguere tra due possibili scenari: quello in cui γ è nulla e quello in cui è invece positiva.

Nel caso in cui γ è nullo, il comportamento dei due giocatori sarà il medesimo che questi terrebbero nel primo caso. Difatti la tabella delle utilità per il gio-catore Difensore nel caso in cui l’Attaccante sia assente sarebbe una tabella di soli zeri. Quindi l’utilità attesa per il giocatore sarà identica a quella del primo scenario, ma riscalata in base alla probabilità della presenza dell’Attaccante. Con γ positivo, invece, l’utilità del giocatore Difensore viene calcolata come somma pesata delle sue due componenti, l’utilità del caso in cui il giocatore Attaccante è presente e quella del caso in cui il giocatore Attaccante è assente. La forma assunta da questa somma, se tracciata rispetto ad h, dipende stret-tamente da tre variabili: ∆µ, γ e la probabilità che il giocatore Attaccante sia presente. Fissate queste tre variabili si pu ò tracciare un grafico che delinea l’evoluzione dell’utilità al crescere del valore di h; tipicamente il grafico assu-me una forma prima ascendente e poi discendente (Figura 4.5), e nel punto di massimo si pu ò identificare l’azione migliore che pu ò scegliere il giocatore Difensore fissata una terna di valori per le variabili.

(40)

(41)

Ovviamente al variare dei valori assunti dalle tre variabili cambia anche il comportamento della funzione di utili`a attesa.

All’aumentare di ∆µ cambia il comportamento della componente relativa al caso in cui il giocatore Attaccante è presente, che avrà un punto di massimo associato ad un valore di h che cresce al crescere di ∆µ. In maniera simile anche il valore di h associato al massimo della funzione di utilità attesa cresce (Figura 4.6 a). Difatti aumentando il valore di ∆µ il giocatore difensore pu ò permettersi di impostare una fascia di controllo pi ù ampia per diminuire la probabilità di falso positivo nel caso il giocatore Attaccante sia assente, ma mantenendo una pari probabilità di individuarlo nel caso sia presente.

All’aumentare di γ cambia il comportamento della componente relativa al caso in cui il giocatore Attaccante è assente: il grafico associato avrà un valo-re di partenza (per h = 0) pi ù basso ed un coefficiente di cvalo-rescita maggiovalo-re. Questo influenza il punto di massimo del grafico dell’utilità attesa non solo abbassandone il valore ma anche associandolo ad un valore di h pi ù grande (Figura 4.6 b).

All’aumentare della probabilità di presenza del giocatore Attaccante, infi-ne, il comportamento del punto di massimo del grafico dell’utilità attesa ha un comportamento inverso rispetto a quello che tiene all’aumentare di γ: il suo valore cresce, e decresce invece il valore di h ad esso associato (Figura 4.6 c). All’aumentare della probabilità che il giocatore Attaccante sia presente, infatti, il giocatore Difensore potrà arrischiarsi ad impostare una fascia di controllo pi ù piccola, puntando sulla scarsa probabilità di assenza del giocatore Attac-cante e di conseguenza sulla minore possibilità di identificare un’intrusione in assenza di essa. Il fatto che il grafico dell’utilità attesa presenti sempre un pun-to di massimo indica che è possibile risalire ad un equilibrio in strategie pure per il gioco. Conoscendo i valori di γ e della probabilità di presenza del gioca-tore Attaccante si pu ò infatti risalire per ogni ∆µ al valore di h che garantisce la massima utilità al giocatore Difensore. Note queste coppie ∆µ - hmax è quindi

possibile risalire a quale (o quali) di queste garantisce la massima utilit`a per il giocatore Attaccante, identificando quindi l’equilibrio.

Non `e per `o possibile calcolare in forma chiusa gli equilibri in questi ultimi due casi.

4.2.3 Casi 3 e 4

Vi sono infine due ulteriori scenari possibili. Nel terzo scenario il giocatore Attaccante:

• `e presente o assente a seconda della decisione del giocatore Natura; • entra in gioco nel turno deciso dal giocatore Natura;

(42)

La probabilit`a di ingresso del giocatore Attaccante `e la medesima ad ogni turno di gioco.

Il quarto ed ultimo scenario possibile prevede invece che il giocatore Attac-cante:

• `e o meno presente nel gioco secondo una scelta effettuata dal giocatore stesso;

• sceglie il turno in cui entrare in gioco;

• da quando entra in gioco `e costretto a giocare.

Dal punto di vista del giocatore Difensore, tuttavia, questi ultimi due sce-nari sono analoghi al secondo scesce-nario: cambia unicamente la probabilit`a che il giocatore Attaccante sia presente o meno. Valgono dunque le stesse conside-razioni fatte per il secondo scenario.

4.2.4 Utilit`a istante per istante

Come negli ultimi due scenari descritti, anche per il caso in cui i giocatori rice-vano le rispettive utilit`a al termine di ogni turno valgono i medesimi ragiona-menti applicati per il caso precedente (in cui le utilit`a venivano guadagnate al termine del gioco).

I rapporti tra i valori nelle matrici di utilit`a infatti rimangono i medesimi, e quindi si possono applicare le regole descritte per il caso precedente.

4.3 Calcolo delle strategie

Per i casi in cui non è possibile dedurre la strategia ottima per il giocatore Difensore analizzando l’andamento delle matrici di utilità, vi sono svariate strumenti che è 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

(43)

Figura 4.6: Comportamento del grafico dell’utilit`a attesa in caso di variazioni di ∆µ (a), γ (b) e P(Attaccante presente) (c).

(44)

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à rispetto alla scelta eseguita nel passo precedente. Se la strategia individuata a questo punto è tale per cui la strategia del primo giocatore (A) è una best response, allora l’algoritmo termina con successo; se invece cos`ı non è, 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à 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 ranran-domizza- 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

(45)

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 massimini-mo 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.

(46)

γ = 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 è stato utilizzato per calcolare gli equilibri del gioco in strategie miste. È stato applicato sia ad un gioco classico sia ad un gioco di tipo baye-siano, in cui il giocatore Attaccante pu ò assumere uno tra due tipi (presente e non presente), utilizzando nel secondo caso per il giocatore Difensore una tabella delle utilità popolata con le utilità attese, calcolata come somma delle due utilità relative rispettivamente al caso in cui il giocatore Attaccante è pre-sente ed al caso in cui è aspre-sente, pesate per la probabilità di presenza o meno del giocatore Attaccante stesso.

Il secondo, invece, è 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 è 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à attesa pi ù alta. Cos`ı facendo è possibile semplificare il calcolo, riducendo il tutto da un problema di programmazione mista intera ad un problema di programmazione lineare intera.

4.4 Risultati sperimentali

In Tabella 4.2 vengono mostrati i risultati dello studio, esplicitando per quale caso esiste o meno la possibilit`a di calcolare in forma chiusa un equilibrio per il gioco.

È stato verificato che in nove scenari su sedici è possibile calcolare in forma chiusa le strategie di equilibrio per i due giocatori del test di Shewhart. Per i casi in cui il calcolo non è possibile in forma chiusa, sono sate testate differenti metodologie di soluzione.

Il calcolo dell’equilibrio, quando non `e effettuabile in forma chiusa, `e pos-sibile in un tempo nell’ordine dei secondi su un comune calcolatore per usi personali (cinque secondi nel caso peggiore, con la ricerca per bisezione).

(47)

Capitolo 5

Conclusioni

Le tecniche applicate per il controllo della qualit`a nell’ambito della produzione industriale possono essere applicate anche alla ricerca di eventuali intrusioni nel sistema di produzione stesso. Formalizzando lo scenario sotto forma di gioco strategico, `e possibile calcolare i parametri migliori da impostare per il test di controllo, in modo da avere sufficiente certezza di poter individuare per tempo le intrusioni da parte di agenti esterni.

È stato dimostrato che sotto determinate assunzioni sulla natura del test il gioco che lo formalizza presenta soluzioni notevoli, e che quindi non è neces-sario un calcolo approfondito per la scelta dei parametri del test. È stato altres`ı dimostrato che nelle altre situazioni è possibile calcolare in tempo ragionevoli le impostazioni migliori per il test, tramite l’utilizzo di appropriati strumenti.

Gli sviluppi futuri in quest’area dovranno principalmente concentarsi nello studio dei casi in cui il sistema in studio possa variare il suo comportamento, introducendo quindi una situazione di incertezza nello scenario.

(48)

(49)

Bibliografia

[1] M. Tambe B. An. Game theory for security: an important challenge for multiagent systems. Lecture notes in Computer Science, 7541:17–30, 2012. [2] D. K. Levine E. Dekel, D. Fudenberg. Learning to play bayesian games.

Games and Economic Behavior, 46:282–303, 2004.

[3] N. Basilico F. Amigoni, N. Gatti. Patrolling security games: Definition and algorithms for solving large instances with single patroller and single intruder. Artificial Intelligence, 184-185:78–123, 2012.

[4] O. Morgenstern J. von Neumann. Theory of Games and Economic Behavior. Princeton University Press, 1944.

[5] Y. Shoham K. Brown. Multi-Agent System. Shoham and Leyton-Brown, 2009.

[6] C. E. Lemke and J. T. Howson. Equilbrium points of bimatrix games. Journal of the Society for Industrial and Applied Mathematics, 12:412–423, 2011.

[7] I. V. Nikiforov M. Basseville. Detection of Abrupt Changes: Theory and Application. Prentice-Hall, 1993.

[8] N. Gatti N. Basilico. Automated abstractions for patrolling security ga-mes. In Association for the Advancement of Artificial Intelligence, volume 25, pages 1096–1101, 2011.

[9] N. Gatti N. Basilico and F. Villa. Asynchronous multi-robot patrol-ling against intrusions in arbitrary topologies. In Association for the Advancement of Artificial Intelligence, pages 1124 – 1229, 2010.

[10] M. Rocco N. Gatti, G. Patrini and T. Sandholm. Combining local search techniques and path following for bimatrix games. In Conference on Uncertainty in Artificial Intelligence, volume 28, pages 412–423, 2012.