POLITECNICO DI MILANOFACOLTA DI INGEGNERIA DELL’INFORMAZIONE

Corso di Laurea in Ingegneria Informatica

ANALISI DEGLI EQUILIBRI NOTEVOLI NELLEMODELLAZIONI IN FORMA DI GIOCO STRATEGICO DEL

TEST DI SHEWHART

Relatore: Prof. Nicola GATTICorrelatore:Ing. Manuel ROVERI

Tesi di laurea di:Marco SUBACCHIMatr. 734559

Anno Accademico 2012 - 2013

2

Ringraziamenti

Doverosi ringraziamenti vanno, prima di tutto, al mio relatore Nicola Gatti edal 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 lealtre cose per il tempo che ha dedicato all’opera di correzione della bozza.

Infine un enorme grazie collettivo a tutti i miei amici.

3

4

Indice

1 Introduzione 13

2 Stato dell’arte 152.1 Change Detection Test . . . . . . . . . . . . . . . . . . . . . . . . 15

2.1.1 Shewhart Control Chart . . . . . . . . . . . . . . . . . . . 162.1.2 Geometric Moving Average Control Chart . . . . . . . . 162.1.3 Cumulative Sum Algorithm . . . . . . . . . . . . . . . . . 17

2.2 Teoria dei Giochi . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.2.1 Giochi in forma normale . . . . . . . . . . . . . . . . . . . 192.2.2 Giochi in forma estesa . . . . . . . . . . . . . . . . . . . . 222.2.3 Giochi Bayesiani . . . . . . . . . . . . . . . . . . . . . . . 242.2.4 Ottimizzazione matematica . . . . . . . . . . . . . . . . . 252.2.5 Giochi per la sicurezza . . . . . . . . . . . . . . . . . . . . 26

3 Struttura del problema e strumenti utilizzati 293.1 Fasi del lavoro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293.2 Software utilizzati . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

4 Test di Shewhart 334.1 Formalizzazione del test . . . . . . . . . . . . . . . . . . . . . . . 334.2 Formalizzazione delle strategie . . . . . . . . . . . . . . . . . . . 35

4.2.1 Caso 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354.2.2 Caso 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384.2.3 Casi 3 e 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414.2.4 Utilita istante per istante . . . . . . . . . . . . . . . . . . . 42

4.3 Calcolo delle strategie . . . . . . . . . . . . . . . . . . . . . . . . 424.3.1 Analisi matematica . . . . . . . . . . . . . . . . . . . . . . 424.3.2 Algoritmo di Lemke-Howson . . . . . . . . . . . . . . . . 444.3.3 Programmazione Lineare Intera . . . . . . . . . . . . . . 46

4.4 Risultati sperimentali . . . . . . . . . . . . . . . . . . . . . . . . . 46

5 Conclusioni 47

5

6

Elenco delle figure

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

4.1 Tabella delle utilita con penalita nulle. . . . . . . . . . . . . . . . 364.2 Tabella delle utilita con γ nulla ed ε positiva. . . . . . . . . . . . 374.3 Tabella delle utilita con γ positiva ed ε nulla. . . . . . . . . . . . 384.4 Tabella delle utilita con γ ed ε positive. . . . . . . . . . . . . . . . 394.5 Forma assunta dall’utilita attesa del giocatore Difensore. . . . . 404.6 Comportamento del grafico dell’utilita attesa in caso di varia-

zioni di ∆µ (a), γ (b) e P(Attaccante presente) (c). . . . . . . . . . 434.7 Frequenza degli equilibri per il giocatore Difensore, caso con

150 punti di discretizzazione. . . . . . . . . . . . . . . . . . . . . 45

7

8

Elenco delle tabelle

2.1 Battaglia dei sessi. . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

4.1 Esiti del gioco. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344.2 Riepilogo calcolo in forma chiusa. . . . . . . . . . . . . . . . . . 46

9

10

Abstract

Il controllo di qualita e un’area di particolare importanza nei processi di pro-duzione industriale, per il mantenimento dei corretti parametri di qualita deibeni prodotti. L’ultimo secolo ha visto la nascita di svariati metodi applicabilial controllo di qualita, di cui i Change Detection Test sono uno dei primi esempi.

Sempre nell’ambito dei sistemi industriali, i metodi di controllo di qualitapossono 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 puo essere facilmente modellato sotto forma di gioco strate-gico, ed il comportamento piu adeguato da tenere nella sua esecuzione puoessere 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 qualita, atti allo studio dell’esistenzadi soluzioni notevoli valide per tutte le possibili applicazioni del test, sottodeterminate ipotesi.

11

12

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 fisiciesistenti, siano essi naturali o creati dall’uomo, sono modellabili come serie diosservazioni di variabili casuali generate da una distribuzione di probabilita,nota o incognita.

Analizzando l’insieme di misurazioni con opportuni strumenti matematicie possibile risalire ad una formulazione, piu o meno precisa, della distribuzio-ne di probabilita che descrive il sistema; oppure e possibile prevedere il futurocomportamento del sistema stesso; o ancora verificare l’ipotesi che la serie siagenerata da una determinata distribuzione di probabilita.

Una delle applicazioni possibili e quella del controllo di qualita nei sistemiproduttivi industriali: i beni generati dal sistema produttivo vengono descritticome misurazione di una data caratteristica che ne rappresenta la qualita, e chedeve restare all’interno di determinati parametri di accettabilita. In questo casoil sistema produttivo viene descritto sotto forma di distribuzione di probabi-lita, che genera variabili casuali che rappresentano le misurazioni effettuatesui beni.

Generalmente la non conformita delle misurazioni indica l’usura del siste-ma stesso. E pero possibile che si verifichino situazioni in cui esista un agenteesterno il cui obiettivo sia quello di alterare il processo produttivo. In questocaso il concetto di controllo di qualita si puo applicare anche all’individuazio-ne di questo agente esterno, scegliendo accuratamente i parametri di qualitatenendo conto anche di questa possibilita.

In questo lavoro di tesi si e studiato un test applicabile ai due scenari sopradescritti utilizzando la teoria matematica dei giochi. Dopo aver dato al testuna descrizione piu 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 e dapprima verificata l’esistenza di equilibri informa chiusa, quindi in caso contrario si e proceduto alla ricerca di eventuali

13

equilibri applicando le metodologie classiche della Teoria dei giochi. La tesi estrutturata come segue.

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

Nel Capitolo 3 si e descritto piu nel dettaglio lo scenario studiato e si e datauna breve descrizione degli strumenti informatici utilizzati.

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

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

14

Capitolo 2

Stato dell’arte

L’obiettivo di questo capitolo e quello di dare una panoramica generale dellearee di studio collegate al problema del riconoscimento di un intrusione in unsistema dinamico. Verranno quindi presentati i Change Detection Test, tecnichestatistiche utilizzate per tentare di identificare variazioni nella distrubuzionedi processi stocastici, e verranno esposte le basi della Teoria dei Giochi, che estata 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 distribuzionepθ(y) dipendente da un parametro noto θ = θ0, ad un istante incognito t0 si hache il parametro cambia, assumendo valore ignoto θ1 6= θ0: lo scopo del changedetection e generalmente quello di rilevare il presentarsi di questa variazione,ed eventualmente di identificare l’istante t0 in cui si e presentata e la portatadel cambiamento. Il change detection ha svariate applicazioni, come ad esempioil cointrollo della qualita nei sistemi produttivi o l’analisi di dati da rilevamentisismici.

Esistono svariati test che vengono utilizzati per identificare i cambiamentinella distribuzione, chiamati Change Detection Test. I CDT vengono general-mente suddivisi in due categorie principali: i test On-Line hanno lo scopo diidentificare il cambiamento il piu velocemente possibile, generalmente senzavalutare il valore di t0 o di θ1; i test Off-line utilizzano i test di ipotesi per va-lutare il valore di t0 e/o di θ1. Per valutare la bonta di un CDT si usano cinquecriteri principali:

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

15

• la probabilita di falso positivo;

• il ritardo medio di identificazione;

• la probabilita 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 piu semplicemente Test di Shewhart, si basa sulconcetto di ispezione continua. Vengono estratti campioni di n variabili ge-nerate dal processo stocastico, che vengono analizzati per decidere tra le dueipotesi

H0 : θ = θ0

H1 : θ 6= θ0

Finche i campioni confermano l’ipotesiH0, si procede con il campionamen-to ed il test. Nell’istante in cui la decisione del test volge verso l’ipotesi H1 ilcampionamento (e normalmente il processo) vengono fermati.La decisione tra le due ipotesi viene effettuata tramite un test di soglia su unastatistica s del processo. Viene definita una soglia di accettabilita entro la qualesi e ragionevolmente sicuri che le variabili casuali sono state generate da unadistribuzione caratterizzata dal parametro θ0, e viene per ogni campione vieneparagonato il suo valore campionario della statistica alla soglia: se il valorecampionario rientra all’interno della soglia si considera confermata l’ipotesiH0, altrimenti viene segnalata una variazione nella distribuzione.

E ovviamente necessario definire con accuratezza la soglia di accettabilita,evitando di scegliere una fascia troppo larga, accettando campioni generatida una distribuzione con θ 6= θ1 (e quindi aumentando la probabilita di falsinegativi) oppure troppo stretta, identificando una variazione a seguito dellenormali fluttuazioni del valore campionario della distribuzione originale (equindi aumentando la probabilita di falsi positivi).

2.1.2 Geometric Moving Average Control Chart

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

16

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

si = lnpθ1 (yi)

pθ0 (yi)

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

Il test identifica una variazione nella distribuzione del processo qualora gkrisulti al di fuori della fascia di accettabilita. Una possibile variazione (chia-mata Finite Moving Average) consiste nel definire un insieme finito di fattori disconto γi di cardinalita n, e quindi tener conto nel calcolo di gk solo le ultime nvariabili.

2.1.3 Cumulative Sum Algorithm

L’algoritmo a somme cumulative (detto anche CUSUM), ispirato dal lavoro diA. 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 dimen-sione fissata n e ne calcola il valore campionario di una statistica, calcolandonepoi la differenza rispetto al valore nominale della distribuzione di probabilia.Il termine corrente viene calcolato a partire dal precedente, sommandone ilvalore a quello della differenza cosı calcolata, nel modo descritto di seguito:

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

dove xi e il valore campionario della statistica utilizzata e x e il suo valorenominale. E poi il valore di Si ad essere confrontato con la fascia di accettabilitaper decidere tra l’ipotesi H0 : θ = θ0 e l’ipotesi H1 : θ = θ1.

2.2 Teoria dei Giochi

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

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

17

Insieme ElementiN n1 = Alice, n2 = BrunoA a1,1 = partita, a1,2 = cinema,

a2,1 = partita, a2,2 = cinemaU1 u1(a1,1, a2,1) = 1, u1(a1,1, a2,2) = −1,

u1(a1,2, a2,1) = 2, u1(a1,2, a2,2) = 4U2 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 e descritto da una tripla di elementi < N,A,U >, doveN rappresenta l’insieme degli agenti che prendono parte al gioco (chiamatigiocatori), A e l’insieme gli stati del gioco possibili ed ui e la funzione di utilitaper 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 utilita riveste uno scopo di primaria importanza nell’ambitodello studio dei giochi strategici. La funzione di utilita infatti mappa gli statidel mondo su un insieme di numeri reali, esprimendo il grado di preferenzache l’agente ha per ciascuno stato. Questo permette di definire un ordine dipreferenza tra gli stati. Quindi la funzione di utilita per l’agente i e definitacome:

ui : A 7→ R

Nel caso in cui, per un qualsiasi motivo, il valore dell’utilita non dovesseessere calcolabile deterministicamente, si parla di utilita attesa.

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

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

18

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’utilita di +3 nel caso l’agente vada nel luogoche preferisce, -1 e +1 rispettivamente nel caso che entrambi vadano nello stes-so luogo o in due luoghi diversi e 0 nel caso che l’agente non vada nel luogoche preferisce, la tripla che rappresenta il gioco e composta descritto in tabella2.1.

2.2.1 Giochi in forma normale

La forma normale e una delle possibili rappresentazioni per le interazioni stra-tegiche tra gli agenti. Il gioco viene descritto sotto forma di matrice delle uti-lita, che riporta le utilita attese per tutti i giocatori in ogni possibile stato delgioco. Tipicamente vengono rappresentati in forma normale i giochi simul-tanei (in cui l’ordine in cui i giocatori scelgono l’azione da compiere non haimportanza), ma e 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 seguitosono riportati i principali.Minmax

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

minmaxi = minsi maxsj uj(si, sj)

La strategia minmax e comunque difficilmente applicata.

MaxminLa strategia maxmin e il duale della strategia minmax. Il giocatore che

sceglie di giocare secondo la strategia maxmin partira dall’assunzione che ilsuo avversario sta giocando una strategia minmax: il suo scopo e quindi quello

19

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

maxmini = maxsi minsj ui(si, sj)

Minmax regretSia 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. Piuformalmente la strategia minmax regret e definita come;

minmaxr = minsi maxsj(u(sj)− u(si))

Pareto ottimalitaIl concetto di Pareto ottimalita di una strategia e strettamente legato a quel-

lo di Pareto dominanza. Si dice che una strategia s domina una strategia s′

se giocare s al posto di s′ non e sconveniente per nessun giocatore ed apportabeneficio ad almeno un giocatore. In altri termini, per nessun giocatore la stra-tegia s′ e una scelta migliore della strategia s ma per almeno un giocatore s euna scelta migliore di s′. Formalmente si ha che s′ e Pareto dominata da s se

∀i ∈ N(ui(s) ≥ ui(s′)) ∧ ∃j ∈ N(uj(s) > uj(s

′))

Definito il concetto di Pareto dominanza, si dice che una strategia s e Paretoottimale se non esiste alcuna soluzione s′ che e Pareto dominante rispetto ad s.

Le strategie Pareto ottimali sono, appunto, ottimali, e quindi rappresentanouna possibile soluzione del gioco. Ogni gioco possiede almeno una soluzionePareto ottimale, ma puo esisterne piu d’una.

Questo tipo di soluzione, pero, e affetto da instabilita: 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 calonell’utilita rispetto alle altre), mentre in generale non e cosı.

Equilibri di NashIl problema dell’instabilita delle soluzioni Pareto ottimali viene risolta da

John Nash. Un equilibrio di Nash e una strategia che si basa sul concetto dibest response. Sia s una strategia ed s1, s2...sn le sue componenti, e si chiaminosi l’azione scelta dal giocatore i-esimo ed s−i l’insieme delle azioni scelte datutti gli altri giocatori: si si dice risposta ottima (best response) del giocatoreii-esimo ad s−i se nessun’altra azione s′i del giocatore gli garantisce una utilitamaggiore. Formalmente si definisce risposta ottima l’azione si che soddisfa laseguente condizione:

∀s′i 6= si(ui(si, s−i) ≥ ui(s′i, s−i))

20

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 daglialtri giocatori.

∀i ∈ N(∀s′i 6= si(ui(si, s−i) ≥ ui(s′i, s−i)))

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

Dominanza iterataUn 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 s′i garantisce sempre una utilita inferiore ad s′i, qualeche siano le azioni che compongono s−i. Una soluzione dominata non puo,per ovvi motivi, far parte di un equilibrio di Nash.

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

Equilibri Leader-FollowerL’idea che sta dietro al concetto di Leader-Follower e che uno dei gioca-

tori (detto, appunto, Leader), comunichi in anticipo ai suoi avversari l’azioneche e intenzionato a giocare. Sebbene questa linea d’azione potrebbe sembra-re sconveniente per il Leader, poiche da un vantaggio agli avversari, in realtagli garantisce di massimizzare la propria utilita. Comunicando in anticipo l’a-zione che intende giocare, infatti, il giocatore Leader puo far affidamento sulfatto che gli altri giocatori risponderanno con la strategia che massimizza laloro utilita. Basandosi su questo, il Leader puo calcolare per ognuna delle sueazioni quale sara la risposta dei suoi avversari. Di conseguenza puo calcolarel’utilita che ricavera da ogni azione, e quindi scegliere quale azione giocare (ecomunicare 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 utilitaminima possibile -1, associata alla decisione di Bruno di andare al cinema; sescegliesse invece di andare al cinema, riceverebbe nel caso peggiore una uti-lita pari a 2. Bruno, invece, riceverebbe nel caso peggiore -1 se decidesse diandare 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 utilita di -1 invece che una di 4, quindi conun rimpianto pari a 5; viceversa se Alice decidesse di andare al cinema e Bruno

21

alla partita, Alice avrebbe un rimpianto pari ad 1 (ricevendo una utilita di 1 in-vece che di 2). Analogamente, Bruno avrebbe un rimpianto di 5 se andasse alcinema mentre Alice e alla partita e di 1 nel caso contrario. Di nuovo, quindi,Bruno scegliera di andare alla partita mentre Alice optera 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 diAlice 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 puo intuire facilmente come s1 non siaPareto dominata da nessuna delle altre strategie, poiche Bruno riceve una uti-lita maggiore giocando s1 rispetto a qualsiasi altra strategia (ed Alice rispettoad s2). Analogamente s4 non e dominata da nessuna delle altre strategie (Alicericeve di piu rispetto ad ogni altra strategia e Bruno rispetto ad s2), ne lo e s3

(Bruno riceve di piu rispetto ad s4, Alice rispetto ad s1 ed entrambi rispettoad s2). Al contrario, s2 risulta essere Pareto dominata da ciascuna delle altrestrategie. Ne risulta che s1, s3 ed s4 sono tre strategie Pareto ottimali per ilgioco.

Equilibri di Nash - Dalla tabella delle utilita riportata in Figura 2.1 si puoricavae facilmente l’equilibrio di Nash del gioco utilizzando il metodo delladominanza iterata. L’azione cinema domina l’azione partita per Alice, men-tre viceversa l’azione partita domina l’azione cinema per Bruno. Il gioco hadunque un unico equilibrio di Nash, che e 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 utilita pari ad 1; se invece Alice comunicasse cinema,Bruno continuerebbe a scegliere partita ma l’utilita di Alice sarebbe pari a 2.Come leader, quindi, Alice giocherebbe cinema, garantendosi una utilita di 2.Analogamente, se Bruno scegliesse di giocare - e comunicare - l’azione partitasi garantirebbe una utilita di 2, poiche Alice giocherebbe cinema, mentre segiocasse cinema si garantirebbe una utilita 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 edescritto 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

• H e l’insieme dei nodi intermedi dell’albero;

22

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

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

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

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

• u : Z 7→ Rn e una funzione che assegna ad ogni nodo foglia le utilita cheesso garantisce ai giocatori.

Nel caso di giochi ad informazione imperfetta - in cui i giocatori non hannocertezza 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 ilgiocatore i, con la proprieta che ∀h, h′ ∈ Ii(χ(h) = χ(h′) ∧ ρ(h) = ρ(h′)).

E possibile trasformare ogni gioco in forma estesa in un gioco in forma nor-male, che pero risultera essere estremamente esteso. Per fare cio si ridefiniscel’insieme delle azioni di ogni giocatore come insieme di ogni possibile sequen-za di azioni che questi puo giocare nel gioco in forma estesa. Chiamando Hi

l’insieme dei nodi intermedi hij tali che ρ(hij) = i, il nuovo insieme di azionidel giocatore i-esimo sara:

Ai = hi1 × hi2 × ...

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

Equilibrio perfetto per sottogiochiTrasformare un gioco in forma estesa in uno in forma normale, pero, fa

perdere di vista la sequenzialita delle azioni nel gioco originale. Ne consegueche un equilibrio calcolato in un gioco in forma normale non sempre e unequilibrio 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 come sottogioco di un gioco ad informazioneperfetta G un gioco G′ che sia una restrizione di G a partire da un nodo h, sichiama subgame perfect equilibrium una strategia s tale per cui per ogni sot-togioco G′ di G la restrizione di s ai nodi di G′ sia un equilibrio di Nash per G′.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 puo calcolare piuttosto facilmente perbackward induction, tramite un algoritmo che implementa una singola ricerca

23

depth first dell’albero del gioco, usando le utilita 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 eeffettuabile 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 probabilita su uninsieme di giochi diversi ma con gli stessi insiemi N ed A, ognuna delle qualirappresenta la probabilita con cui ciascun giocatore ritiene di trovarsi in ognu-no dei giochi. Nonostante la condizione che gli insiemi N ed A siano ugualipuo sembrare troppo restrittiva in quanto l’incertezza potrebbe essere, appun-to, sul numero di giocatori o sulle azioni a loro possibili, queste ultime dueincertezze possono essere rappresentate tramite variazioni nelle utilita.

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

Definizione 2.2.1 (Gioco Bayesiano - Information Set). Un gioco Bayesiano euna 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 seg, g′ ∈ G allora ogni giocatore i ∈ N avra lo stesso spazio delle azioni ing come in g′;

• P e l’insieme delle distribuzioni di probabilita assegnate a priori daigiocatori ai giochi appartenenti all’insieme G;

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

Definizione 2.2.2 (Gioco Bayesiano - Forma Estesa). Un gioco Bayesiano e unatupla 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.

24

Definizione 2.2.3 (Gioco Bayesiano - Tipi Epistemici). Un gioco Bayesiano euna 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 Θi rappresenta i possibilitipi che il giocatore i-esimo puo assumere;

• p e la distribuzione di probabilita a priori su Θ;

• u e la funzione di utilita attesa.

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

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

EUi(s) =∑

θ∈Θ p(θ)∑

a∈A(∏

j∈N sj(aj|θj))ui(a, θ)

definendo come sj(aj|θj) la probabilita che l’agente j-esimo appartenente altipo θ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 unasoluzione formalizzando il gioco stesso sotto forma di problema di ottimizza-zione matematica.

Il calcolo della strategia maxmin e effettuabile formalizzando il gioco comeproblema di programmazione lineare intera. Supponendo di voler calcolare lastrategia maxmin per il giocatore 1:

max v1

s.t. U1x1 ≥ 1v1

1Tx1 = 1x1 ≥ 0

dove U1 e la matrice delle utilita per il giocatore 1, x1 e un vettore i cuielementi x1,j rappresentano la probabilita di giocare la j-esima azione e v1 el’utilita massima attesa dal giocatore 1. Per il calcolo degli equilibri di Nashinvece e necessario l’utilizzo di programmazione mista intera. Per ogni gioca-tore si ipotizza nota la strategia dell’avversario, e si calcolano il problema diottimizzazione relativo alla risposta ottima alla strategia (nell’esempio per ilgiocatore 1, con x2 che rappresenta la strategia del giocatore 2):

25

max xT1U1x2

s.t. 1Tx1 = 1x1 ≥ 0

ed il suo problema duale

min v1

s.t. 1v1 ≥ U1x2

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

x1 ≥ 0 x2 ≥ 01Tx1 = 1 1Tx2 = 11v1 − U1x2 ≤M(1− s1) 1v2 − UT

2 x1 ≤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 puo utilizzare un problema di programmazione lineare. Per ogni stra-tegia pura t del giocatore Follower si calcola la strategia mista del Leader taleche t sia una risposta ottima per il giocatore Follower alla strategia del Leadere che la strategia del Leader massimizzi la sua utilita a seguito della strategia t

max∑

s∈S psul(s, t)s.t. ∀t′ ∈ T,

∑s∈S psuf (s, t) ≥

∑s∈S psuf (s, t

′)∑s∈S ps = 1

∀s ∈ S, ps ≥ 0

Tra queste, si seleziona quindi quella che massimizza l’utilita del Leader.Ovviamente nel caso si voglia che il Leader giochi una strategia pura biso-

gnera inserire un vincolo che imponga che la probabilita di giocare una singolastrategia sia pari a 0 oppure 1.

2.2.5 Giochi per la sicurezza

La sicurezza e un campo di importanza primaria, che ha a che fare con unamoltitudine di realta e scenari. La Teoria dei Giochi puo venire efficacementeutilizzata in quest’ambito [1] [8] [9], per ottimizzare l’allocazione delle risorsee la pianificazione della risoluzione dei problemi.

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

26

scenario tipicamente include il fatto che il difensore non ha una conoscenzacompleta sugli attaccanti, ed inoltre i giocatori si trovano in una situazione ditipo Leader-Follower, con il difensore che fa la parte del giocatore Leader.La prima formulazione di un gioco per la sicurezza e da attribuire molto pro-babilmente a John Von Neumann [16]. Il gioco e di tipo zero-sum (la sommadelle utilita dei due giocatori fa sempre zero) a due giocatori, e si svolge in unambiente a griglia. Uno dei giocatori chiamato hider decide una casella dellagriglia dove nascondersi mentre il secondo giocatore, detto seeker, selezionaun insieme di caselle dove cercare. A partire dal lavoro di von Neumann sonostate definite diverse varianti, definite a seconda della mobilita dei giocatori:se entrambi i giocatori possono cambiare posizione si parla di giochi di infiltra-zione [3]; se l’agente seeker e mobile e l’agente hider non puo spostarsi si parladi giochi di ricerca; se la situazione e 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 giocatore hider deve spostarsi da una posizionedi origine ad una posizione obiettivo.

27

28

Capitolo 3

Struttura del problema e strumentiutilizzati

Nel presente lavoro di tesi e stato deciso di modellare il controllo di qualita diuna 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-babilita degli esiti dell’esperimento aleatorio “produzione”. Il problema che estato affrontato consiste nel verificare l’ipotesi che esistano condizioni tali percui il gioco strategico, simulato come descritto, presenti delle soluzioni note-voli. Per soluzione notevole si intende una strategia che sia di equilibrio pertutti i giochi costruiti come sopra descritto, al variare di selezionati parametri.

L’obiettivo e stato dunque quello, dopo aver distinto vari casi possibili peril 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 incui non e stato possibile trovare tale soluzione notevole.

3.1 Fasi del lavoro

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

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

• dove non si e trovata alcuna soluzione notevole, si sono effettuati varitest volti alla conferma dell’effettiva esistenza di un equilibrio in strategiepure.

29

Nella prima fase si e effettuato uno studio qualitativo del problema senzaanalizzare specifici dati numerici. Dopo aver suddiviso in macro-categorie lepossibili occorrenze del gioco, a seconda del valore di alcuni parametri, si epassati ad studiare il comportamento generale delle utilita dei giocatori casoper caso, basandosi su questo studio per individuare i casi in cui e possibilerintracciare una soluzione di equilibrio in forma chiusa dai casi in cui invece enecessaria l’analisi degli effettivi valori numerici del problema.

Nella seconda fase e stata quindi effettuata la seconda analisi su diversigiochi, variando i parametri del test e generando quindi le matrici di utilitadei due giocatori. Le matrici di utilita sono poi state utilizzate come input perdiversi 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 utilita attese dei due giocatori, il cui valore dipende ovviamentedalle due azioni scelte dai giocatori. Si e quindi proceduto con il selezionareuna 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 massimodella funzione relativa all’utilita dell’altro giocatore in corrispondenza di que-sta scelta iniziale, corrispondente alla risposta ottima per il giocatore. Si e poicalcolato iterativamente il punto di massimo di una o dell’altra funzione incorrispondenza del valore calcolato in precedenza per l’altro giocatore, fino alraggiungimento 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 diottimizzazione matematica, risolti utilizzando il linguaggio di modellazionealgebrica AMPL ed il risolutore CPlex.

3.2 Software utilizzati

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

Matlab

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

30

li. E possibile richiamare da Matlab algoritmi scritti in differenti linguaggi diprogrammazione (come ad esempio i linguaggi C e C++).

In questo lavoro di tesi Matlab e stato utilizzato nella sua funzione pri-maria, ovvero il calcolo numerico. Sono stati implementati svariati algoritmial fine di semplificare e velocizzare l’esecuzione dei test, sfruttando la capa-cita del software di manipolare le matrici numeriche. Gli algoritmi sono statiimplementati sia per popolare automaticamente le matrici di utilita dei duegiocatori al variare dei parametri del gioco sia per effettuare uno dei test attial ritrovamento degli equilibri del gioco, sfruttando una ricerca dicotomica suigrafici che rappresentano le utilita 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 definizione dei problemi di ottimizzazione (e quindida facilitare la scrittura e la lettura della descrizione dei problemi). La soluzio-ne di un problema richiede la preparazione di due file, uno con la descrizionedel 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 hail compito per l’appunto di risolvere il problema. AMPL supporta svariatirisolutori, come ad esempio CPLEX e MINOS.

AMPL e stato utilizzato per la risoluzione del gioco rappresentante il testdi Shewhart, rappresentato in tre diversi problemi di ottimizzazione (relati-vi alla formulazione del gioco in forma normale, come gioco bayesiano e perla ricerca di un equilibrio leader-follower). I file contenenti i dati numericisono stati generati tramite l’implementazione di un algoritmo in Matlab, cheha 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’algoritmodi Lemke-Howson, funzionante sulle piattaforme Unix e derivate. L’imple-mentazione utilizzata modifica leggermente l’algoritmo originale, introducen-do un elemento di casualita e ripetizione che migliora le prestazioni generalidell’algoritmo. Di nuovo, come nel caso dell’utilizzo di AMPL, questa imple-mentazione richiede un file di input contenente i dati numerici che descrivonoil gioco, anche in questo caso generati dal medesimo codice Matlab.

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

31

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

32

Capitolo 4

Test di Shewhart

Il test di Shewhart [13] e un CDT (Change Detection Test) sviluppato nei primianni ’10. Nella sua concezione originale, e un test di controllo di qualita in unprocesso 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 probabilita nota. Vengono quindi selezio-nate una o piu caratteristiche della distribuzione di probabilita (ad esempiola media e la varianza) e viene impostata una fascia di controllo centrata nelvalore nominale di tale caratteristica.

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

Se l’anomalia fosse il risultato dell’intervento di un agente esterno, il cuiscopo e quello di modificare il normale andamento del sistema, il test di Shewhartpuo 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 intendemodificare 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-bilita per i parametri campionari; le sue azioni esprimono la distanza dei bordidella fascia dal valore nominale del parametro. Ovviamente, poiche la segna-lazione di un’anomalia implica il blocco del sistema produttivo, il giocatoreDifensore deve prestare attenzione ad impostare la fascia di controllo in modo

33

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

Tabella 4.1: Esiti del gioco.

tale da non segnalare come anomalie eventuali articoli prodotti normalmentema 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 andra a modificare lamedia del processo produttivo, mentre il giocatore difensore imposta la sogliadi accettabilita h. Se il valore della media campionaria sara esterno ai limitidella fascia di accettabilita, verra segnalata la presenza dell’agente esterno. Ilgioco sopra descritto ha, quindi, quattro possibili esiti a seconda dei valoriscelti dai due giocatori. I suddetti esiti sono riportati in Tabella 1.1.

A seconda dell’esito del gioco, i due giocatori ricevono un diverso valoredi ritorno. Piu precisamente, il giocatore Difensore ricevera un ritorno positi-vo qualora indichi correttamente la presenza di un’anomalia (o non ne indichiin assenza di anomalia) e nullo altrimenti, mentre il giocatore Attaccante ri-cevera un ritorno positivo qualora riesca ad agire sul processo senza essereindividuato.

Indicando con UD l’utilita del difensore e con UA quella dell’attaccante, econ R il responso del giocatore difensore (A per indicare che il giocatore Di-fensore ha indicato la presenza del giocatore Attaccante, NA per indicarne ilcaso contrario) quindi, si avra:

UD ={ 1 ∆µ > 0, R = A

1 ∆µ = 0, R = NA0 altrimenti

UA ={ 1 ∆µ > 0, R = NA−ε altrimenti

Quanto descritto finora prende ovviamente come certa la presenza di ungiocatore Attaccante (che puo comunque decidere se giocare o meno). Non epero 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 aduno specifico tipo. Nel caso del test di Shewhart, per il giocatore Attaccantepossono 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 perle utilita 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θA = θ2 si avranno i seguenti valori:

34

UD ={ 1 R = NA−γ R = A

UA = 0I valori indicati con ε e γ indicano due fattori di penalita che vengono as-

segnati ai giocatori: il giocatore Attaccante ricevera una penalita pari a −ε nelcaso in cui venga individuato dal giocatore Difensore; il giocatore Difensore,invece, ricevera una penalita 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 considerare, per decidere sesegnalare o meno la presenza di un’anomalia.

4.2 Formalizzazione delle strategie

Il comportamento migliore, ricercato sotto forma di equilibrio di Nash, che idue attori del gioco possono assumere dipende strettamente da quattro fat-tori: le due penalita, l’istante in cui il giocatore Attaccante entra in gioco el’istante in cui i giocatori ricevono il ritorno indicato dall’utilita. Supponiamoper il momento che i due giocatori ricevano il ritorno al termine dell’orizzontetemporale.

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 utilita.Per il giocatore Difensore l’utilita sara crescente con l’aumentare di h nel casoche il giocatore Attaccante decida di giocare ∆µ = 0, con una utilita pari a−γ in h = 0, decrescente all’aumentare di h, e pari ad 1 in h = 0, altrimenti.Il giocatore Attaccante, invece, ricevera un ritorno pari a 0 nel caso decida∆µ = 0, mentre negli altri casi sara pari a −ε se il Difensore opta per h = 0 edavra un massimo in un luogo differente a seconda del valore di ∆µ per gli altrivalori di h.

Con l’analisi dell’andamento delle matrici di utilita si puo intuire la strate-gia che i due giocatori sceglieranno di attuare durante il gioco.

Teorema 4.2.1 (γ = 0, ε = 0 ).In un Change Detection Test Game rappresentante un Test di Shewhart, con entrambe

35

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

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

Supponiamo di partire da una strategia iniziale corrispondente a ∆µ = 0ed h = h1 > 0. Il giocatore Attaccante tendera ad aumentare il valore di ∆µ,fino a giungere alla massima utilita ottenibile per h = h1. A seguito di questaazione, pero, il giocatore Difensore cerchera di massimizzare il proprio ritorno,diminuendo il valore di h fino a 0. In questo caso il giocatore Attaccante nonavra motivo di modificare il proprio valore di ∆µ, e quindi ci si trovera in unasituazione di equilibrio.

Figura 4.1: Tabella delle utilita con penalita nulle.

Teorema 4.2.2 (γ = 0, ε > 0).In un Change Detection Test Game rappresentante un Test di Shewhart, con la penalitaγ per il giocatore Difensore in caso di falso positivo nulla e la penalita ε per il giocatoreAttaccante nel caso venga individuato positiva, vi sara un unico equilibrio in strategiepure situato in corrispondenza delle azioni h = 0 e ∆µ = 0.

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

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

36

fino a giungere alla massima utilita ottenibile per h = h1. A seguito di questaazione, pero, il giocatore Difensore cerchera di massimizzare il proprio ritorno,diminuendo il valore di h fino a 0. In risposta, il giocatore Attaccante diminuirail valore di ∆µ fino a renderlo pari a 0, poiche il ritorno atteso per qualsiasialtro valore di ∆µ sara negativo. Il giocatore Attaccante non avra vantaggi nelmodificare il valre di h, e quindi ci si trovera in una situazione di equilibrio.

Figura 4.2: Tabella delle utilita con γ nulla ed ε positiva.

Teorema 4.2.3 (γ > 0, ε = 0).In un Change Detection Test Game rappresentante un Test di Shewhart, con la penalitaγ per il giocatore Difensore in caso di falso positivo maggiore di zero e la penalita ε peril giocatore Attaccante nel caso venga indivituato nulla, vi sara un unico equilibrio instrategie pure situato in corrispondenza delle azioni h = 0 e ∆µ = ∆µ1 > 0.

Dimostrazione. Con γ positiva ed ε = 0, il giocatore Difensore avra una utilitadecrescente al crescere di h, in corrispondenza di ∆µ = 0, e pari a −γ in h = 0.Il giocatore Attaccante, invece, avra una utilita nulla per ogni valore di ∆µ, seh = 0 (Figura 4.3).

Supponiamo di partire da una strategia iniziale corrispondente a ∆µ = 0ed h = 0. Il giocatore Difensore cerchera di massimizare la propria utilita, edi conseguenza aumentera il valore di h fino al massimo consentito. A questopunto anche il giocatore Attaccante aumentera il valore di ∆µ, per ricevereil ritorno atteso massimo corrispondente ad h = hmax. Il giocatore Difensorediminuira quindi il valore di h fino al valore minimo h = 0, aumentando diconseguenza il proprio ritorno. Il giocatore Attaccante, a quel punto, non avravantaggio nel modificare il valore di ∆µ, e quindi ci si trovera in una situazionedi equilibrio.

37

Figura 4.3: Tabella delle utilita con γ positiva ed ε nulla.

Teorema 4.2.4 (γ > 0, ε > 0).In un Change Detection Test Game rappresentante un Test di Shewhart, con la penalitaγ per il giocatore Difensore in caso di falso positivo maggiore di zero e la penalita ε peril giocatore Attaccante nel caso venga indivituato anch’essa, il gioco non presentastrategie pure.

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

Supponiamo di partire da una strategia iniziale corrispondente a ∆µ = 0ed h = 0. Il giocatore Difensore cerchera di massimizare la propria utilita, edi conseguenza aumentera il valore di h fino al massimo consentito. A questopunto anche il giocatore Attaccante aumentera il valore di ∆µ, per ricevereil ritorno atteso massimo corrispondente ad h = hmax. Il giocatore Difensorediminuira quindi il valore di h fino al valore minimo h = 0, aumentando diconseguenza il proprio ritorno. Il giocatore Attaccante, a quel punto, riporterail valore di ∆µ a zero, in modo da massimizzare il proprio ritorno per h = 0.Quindi si ritornera alla situazione di partenza.

4.2.2 Caso 2

Il secondo scenario possibile e identificato dalle seguenti caratteristiche per ilgiocatore Attaccante:

• la sua presenza viene decisa da un terzo giocatore, detto Natura, cherappresenta la probabilita di presenza del giocatore Attaccante;

38

Figura 4.4: Tabella delle utilita 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 utilita,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 unarelativa al caso in cui questi sia assente (in cui ogni colonna ha i medesimivalori espressi nella colonna relativa a ∆µ = 0 come indicata nel primo scena-rio). Per il giocatore Difensore si parlera quindi di utilita attesa, ovvero sommadelle utilita nei due casi pesata per la probabilita di ciascun caso.

In questo caso si puo distinguere tra due possibili scenari: quello in cui γ enulla e quello in cui e invece positiva.Nel caso in cui γ e nullo, il comportamento dei due giocatori sara il medesimoche questi terrebbero nel primo caso. Difatti la tabella delle utilita per il gio-catore Difensore nel caso in cui l’Attaccante sia assente sarebbe una tabella disoli zeri. Quindi l’utilita attesa per il giocatore sara identica a quella del primoscenario, ma riscalata in base alla probabilita della presenza dell’Attaccante.Con γ positivo, invece, l’utilita del giocatore Difensore viene calcolata comesomma pesata delle sue due componenti, l’utilita del caso in cui il giocatoreAttaccante e presente e quella del caso in cui il giocatore Attaccante e assente.La forma assunta da questa somma, se tracciata rispetto ad h, dipende stret-tamente da tre variabili: ∆µ, γ e la probabilita che il giocatore Attaccante siapresente. Fissate queste tre variabili si puo tracciare un grafico che delineal’evoluzione dell’utilita al crescere del valore di h; tipicamente il grafico assu-me una forma prima ascendente e poi discendente (Figura 4.5), e nel puntodi massimo si puo identificare l’azione migliore che puo scegliere il giocatoreDifensore fissata una terna di valori per le variabili.

39

Figura 4.5: Forma assunta dall’utilita attesa del giocatore Difensore.

40

Ovviamente al variare dei valori assunti dalle tre variabili cambia anche ilcomportamento della funzione di utilia attesa.

All’aumentare di ∆µ cambia il comportamento della componente relativaal caso in cui il giocatore Attaccante e presente, che avra un punto di massimoassociato ad un valore di h che cresce al crescere di ∆µ. In maniera simileanche il valore di h associato al massimo della funzione di utilita attesa cresce(Figura 4.6 a). Difatti aumentando il valore di ∆µ il giocatore difensore puopermettersi di impostare una fascia di controllo piu ampia per diminuire laprobabilita di falso positivo nel caso il giocatore Attaccante sia assente, mamantenendo una pari probabilita di individuarlo nel caso sia presente.

All’aumentare di γ cambia il comportamento della componente relativa alcaso in cui il giocatore Attaccante e assente: il grafico associato avra un valo-re di partenza (per h = 0) piu basso ed un coefficiente di crescita maggiore.Questo influenza il punto di massimo del grafico dell’utilita attesa non soloabbassandone il valore ma anche associandolo ad un valore di h piu grande(Figura 4.6 b).

All’aumentare della probabilita di presenza del giocatore Attaccante, infi-ne, il comportamento del punto di massimo del grafico dell’utilita attesa ha uncomportamento inverso rispetto a quello che tiene all’aumentare di γ: il suovalore cresce, e decresce invece il valore di h ad esso associato (Figura 4.6 c).All’aumentare della probabilita che il giocatore Attaccante sia presente, infatti,il giocatore Difensore potra arrischiarsi ad impostare una fascia di controllopiu piccola, puntando sulla scarsa probabilita di assenza del giocatore Attac-cante e di conseguenza sulla minore possibilita di identificare un’intrusione inassenza di essa. Il fatto che il grafico dell’utilita attesa presenti sempre un pun-to di massimo indica che e possibile risalire ad un equilibrio in strategie pureper il gioco. Conoscendo i valori di γ e della probabilita di presenza del gioca-tore Attaccante si puo infatti risalire per ogni ∆µ al valore di h che garantisce lamassima utilita al giocatore Difensore. Note queste coppie ∆µ - hmax e quindipossibile risalire a quale (o quali) di queste garantisce la massima utilita per ilgiocatore Attaccante, identificando quindi l’equilibrio.

Non e pero possibile calcolare in forma chiusa gli equilibri in questi ultimidue 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;

• da quando e in gioco e costretto a giocare.

41

La probabilita di ingresso del giocatore Attaccante e la medesima ad ogniturno 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 giocatorestesso;

• 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 scenario: cambia unicamente la probabilita cheil giocatore Attaccante sia presente o meno. Valgono dunque le stesse conside-razioni fatte per il secondo scenario.

4.2.4 Utilita istante per istante

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

I rapporti tra i valori nelle matrici di utilita infatti rimangono i medesimi, equindi si possono applicare le regole descritte per il caso precedente.

4.3 Calcolo delle strategie

Per i casi in cui non e possibile dedurre la strategia ottima per il giocatoreDifensore analizzando l’andamento delle matrici di utilita, vi sono svariatestrumenti 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’utilita attesa dei due giocatori. Dopo aver generato una scelta iniziale per ilgiocatore 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 successivecalcolando, al ciclo i − esimo, h∗i come best response del giocatore Difensorea ∆µ∗i−1 e ∆µ∗i come best response del giocatore Attaccante ad h∗i . Il ciclo siinterrompe quando la differenza tra l’utilita garantita al giocatore Difensore

42

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

43

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∗0 scelta randomicamente, soglia tResult: Equilibrio per il gioco, composto dall’ultima coppia (h∗i ,∆µ

∗i )

Calcola ∆µ∗0 come Best Response a h∗0Imposta UD,1 = 0 e UD,2 = t ∗ 2Imposta i = 1while UD,2 − UD,1 > t do

Imposta UD,1 = UD,2Calcola h∗i come Best Response a ∆µ∗i−1

Calcola ∆µ∗i come Best Response ad h∗iCalcola UD,2 come utilita attesa del Difensore per la coppia di azioni(h∗i ,∆µ

∗i−1)

endAlgorithm 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 responsedei due giocatori. Partendo dal vertice (0,0) del politopo P × Q, segue uncammino tra i vertici fino a trovarne uno completamente etichettato, visitandounicamente i vertici quasi completamente etichettati e spostandosi solo su unidei 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 acaso). L’assenza di un’etichetta implica che un’altra etichetta h relativa ad unastrategia 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 complementarieta rispettoalla scelta eseguita nel passo precedente. Se la strategia individuata a questopunto 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 primopolitopo e si procede a cambiare nuovamente vertice. L’algoritmo di Lemke-Howson visita ad ogni passo una nuova coppia di vertici, senza mai tornare suuna coppia gia visitata in precedenza. Questo implica che l’algoritmo terminasempre, 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-

44

zazioni dell’intervallo di valori possibili per le azioni dei due giocatori, per untotale 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 adogni 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 piuvolte per ogni insieme di dati in ingresso possibile, impostando di volta involta un valore diverso del parametro fino a ricoprire interamente l’intervallodi 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 presentatein un equilibrio. Il calcolo ha mostrato che:

• quasi nella totalita dei casi gli equilibri in strategie pure implicano cheil giocatore Attaccante giochi l’azione che gli permette di massimizzarel’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 valoripossibili per h, ed un picco intorno al 60-70%.

In Figura 4.7 viene mostrata la tipica distribuzione della presenza delleazioni possibili per il giocatore Difensore negli equilibri calcolati con l’algo-ritmo rrLH, relativa nel caso specifico alla discretizzazione dell’intervallo divalori possibili in 150 punti.

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

45

γ = 0, ε = 0 γ = 0, ε > 0 γ > 0, ε = 0 γ > 0, ε > 0Caso 1 Esiste Esiste Esiste Non esisteCaso 2 Esiste Esiste Non esiste Non esisteCaso 3 Esiste Esiste Non esiste Non esisteCaso 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 diprogrammazione lineare intera.

Il primo e stato utilizzato per calcolare gli equilibri del gioco in strategiemiste. E stato applicato sia ad un gioco classico sia ad un gioco di tipo baye-siano, in cui il giocatore Attaccante puo assumere uno tra due tipi (presentee non presente), utilizzando nel secondo caso per il giocatore Difensore unatabella delle utilita popolata con le utilita attese, calcolata come somma delledue utilita relative rispettivamente al caso in cui il giocatore Attaccante e pre-sente ed al caso in cui e assente, pesate per la probabilita di presenza o menodel 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 tuttii risultati cosı ottenuti l’azione del giocatore Difensore che gli garantisce l’uti-lita attesa piu alta. Cosı facendo e possibile semplificare il calcolo, riducendoil tutto da un problema di programmazione mista intera ad un problema diprogrammazione lineare intera.

4.4 Risultati sperimentali

In Tabella 4.2 vengono mostrati i risultati dello studio, esplicitando per qualecaso esiste o meno la possibilita di calcolare in forma chiusa un equilibrio peril gioco.

E stato verificato che in nove scenari su sedici e possibile calcolare in formachiusa le strategie di equilibrio per i due giocatori del test di Shewhart. Per icasi in cui il calcolo non e possibile in forma chiusa, sono sate testate differentimetodologie 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 usipersonali (cinque secondi nel caso peggiore, con la ricerca per bisezione).

46

Capitolo 5

Conclusioni

Le tecniche applicate per il controllo della qualita nell’ambito della produzioneindustriale possono essere applicate anche alla ricerca di eventuali intrusioninel sistema di produzione stesso. Formalizzando lo scenario sotto forma digioco strategico, e possibile calcolare i parametri migliori da impostare per iltest di controllo, in modo da avere sufficiente certezza di poter individuare pertempo le intrusioni da parte di agenti esterni.

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

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

47

48

Bibliografia

[1] M. Tambe B. An. Game theory for security: an important challenge formultiagent 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: Definitionand algorithms for solving large instances with single patroller and singleintruder. 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. Leyton-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 andApplication. 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 theAdvancement of Artificial Intelligence, pages 1124 – 1229, 2010.

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

49

[11] S. Kraus P. Paruchuri, J. P. Pearce. Playing games for security: an efficientexact algorithm for solving bayesian stackelberg games. In Agent Theories,Architectures, and Languages, volume 5, pages 895–902, 2008.

[12] E. S. Page. Continuous inspection scheme. Biometrika, 41:100–115, 1954.

[13] W. A. Shewhart. Economic control of quality of manufactured product. N.A.,1931.

[14] T. Sandholm V. Conitzer. Computing the optimal strategy to commit to.In ACM conference on Electronic Commerce, volume 7, pages 82–90, 2006.

[15] J. von Neumann. On the theory of parlor games. Mathematische Annalen,100:295–300, 1928.

[16] J. von Neumann. A certain zero-sum two person game equivalent to theoptimal assignment problem. Contribuition to the Theory of Games, pages5–12, 1953.

50