Gestione di conflitti nei Sistemi Multi-Agente tramite la Teoria dei Giochi

UNIVERSITA' DI PISA

Scuola di Ingegneria

Tesi di Laurea Magistrale in Ingegneria

Robotica e dell'Automazione

Gestione dei Sistemi Multi-Agente tramite

la Teoria dei Giochi

Relatori:

Candidato:

Dott.ssa Lucia Pallottino

Tiziano Girletti

Centro di Ricerca in Bioingegneria e Robotica E. Piaggio

Dipartimento di Ingegneria dell'Informazione

Sessione di laurea del 03/10/2014

Anno accademico 2013/2014

Abstract

Nella presente tesi è introdotto un algoritmo per la gestione di risorse condivise tra più agenti autonomi facenti parte di una stessa squadra. Caratteristica dello scenario di applicazione è l'assenza di comuni-cazione attiva tra le entità coinvolte. La scelta del controllo da attuare da parte del singolo agente si basa sulla Teoria dei Giochi, branca della matematica usata tipicamente per la modellazione della realtà nei problemi decisionali. Ogni agente, a partire dal proprio stato, dalle informazioni osservate tramite i propri sensori e da ipotesi sulla natura degli avversari, crea un gioco per determinare la strategia da applicare, cercando un compromesso tra i propri obiettivi e quelli della squadra.

L'algoritmo è stato progettato per essere applicabile in scenari con caratteristiche diverse, per ognuno dei quali è necessario adattare le denizioni presentate. La valutazione dell'ecienza del metodo proposto si è basata su simulazioni relative a due veicoli in competizione per l'accesso esclusivo ad una risorsa. In base ai risultati ottenuti sono state analizzate le potenzialità e i limiti dell'algoritmo.

In this work an algorithm is introduced to manage shared resources in multi-agent systems. The application scenario is characterized by the absence of communication between the involved entities. The Game Theory, a branch of mathematics typically used in decision-making problems, is used to model the system, and agent control input is chosen accordingly. Each agent based on its own state, on sensors information and assumptions about the nature of the opponents, creates a game to determine the strategy to be applied, looking for a trade-o between its goals and those of the team.

The algorithm has been designed to be applicable in dierent scenarios, with dierent characteristics that require an ad-hoc adaption of the denitions presented. The evaluation of the proposed method eciency is based on simulations of two vehicles competing for exclusive access to a resource. Based on the results obtained, the algorithm prospective and limitations has been analyzed.

Indice

1 Introduzione 6

1.1 Comunicazione nei sistemi distribuiti . . . 6

1.2 Ambiti di utilizzo . . . 7

1.2.1 La Battaglia per l'Energia . . . 8

1.2.2 Leader Election . . . 8

1.2.3 Altri scenari multi agenti . . . 9

1.3 La Teoria dei Giochi . . . 9

1.3.1 Standard e Extensive Games . . . 11

1.3.2 Giochi a informazione incompleta . . . 15

1.3.3 Ricerca degli Equilibri . . . 19

1.4 Stato dell'arte . . . 21

2 Presentazione dell'algoritmo 23 2.1 Obiettivi e caratteristiche principali dell'algoritmo . . . 23

2.2 Denizioni dalla Teoria dei Giochi . . . 24

2.2.1 Caratteristiche del gioco creato . . . 24

2.2.2 Combinazione dei giochi . . . 25

2.2.3 Equilibrio per la scelta della strategia . . . 26

2.3 Metodo di learning . . . 27

2.4 Sviluppo dell'algoritmo . . . 28

2.4.1 Inizializzazione . . . 28

2.4.2 Modellazione del conitto . . . 28

2.4.3 Conclusione . . . 30

2.5 Applicazioni dell'algoritmo . . . 31

2.5.1 Scenari con veicoli . . . 32

2.5.2 Battaglia per l'Energia e Leader Election . . . 33

2.5.2.1 Algoritmo e dinamica degli agenti . . . 34

2.5.3 Altri scenari . . . 35

2.6 Sviluppo: identicazione dell'avversario . . . 36

3 Aspetti computazionali 39 3.1 La scelta della strategia . . . 39

3.1.1 Numero di Giocatori . . . 39

3.1.2 Algoritmo di Lemke-Howson . . . 40

3.1.3 Strategia Pianicata . . . 41 2

3.1.4 Strategia ipotizzata dell'avversario . . . 41

3.2 Progettazione del gioco . . . 42

3.2.1 Guadagni . . . 42

3.2.2 Probabilità . . . 50

3.2.3 Passo di previsione . . . 51

3.3 Conitto tra più di due agenti . . . 52

4 Simulazioni e risultati 54 4.1 Ecienza dell'algoritmo . . . 54

4.1.1 Caratteristiche delle prove eettuate . . . 54

4.1.1.1 Denizione del passo di previsione massimo testato . . . 54

4.1.1.2 Ambiente . . . 56

4.1.1.3 Agenti . . . 56

4.1.1.4 Misura dell'Ecienza: Priorità di accesso e criteri di successo . . . 57

4.1.2 Risultati della Battaglia per l'Energia . . . 57

4.1.2.1 Ecienza a parità di priorità di Tipo . . . 58

4.1.2.2 Ecienza Massima dell'algoritmo . . . 58

4.1.2.3 Analisi del Fallimento . . . 58

4.1.3 Risultati Leader Election . . . 63

4.1.3.1 Ecienza a parità di priorità di Tipo . . . 63

4.1.3.2 Ecienza Massima dell'algoritmo . . . 63

4.1.3.3 Analisi del Fallimento . . . 63

4.2 Identicazione dell'avversario . . . 63

4.2.1 Risultati . . . 67

4.2.2 Analisi dei fallimenti . . . 68 5 Conclusioni e sviluppi futuri 69

Summary

Il progetto di tesi consiste nello sviluppo di un algoritmo capace di risolvere i conitti che possono nascere in sistemi multi-agente dovuti alla richiesta di accesso ad una risorsa condivisa da più agenti in scenari caratterizzati dall'assenza di comunicazione attiva. Con il termine di agente si indica una entità (veicolo, processore, attuatore, robot) in grado di percepire l'ambiente che lo circonda attraverso dei sensori e di prendere decisioni in maniera autonoma per il raggiungimento dei propri obiettivi. Il conitto nasce nel momento in cui più agenti richiedono l'accesso ad una risorsa (punto di arrivo, canale di comunicazione, fonte di energia), escludendosi mutualmente, e si troveranno a coordinarsi per determinare chi potrà entrare in possesso della risorsa. L'assenza di comunicazione attiva, dovuta a fattori ambientali o a ragioni di sicurezza, comporta l'impossibilità di scambio di informazioni tra gli agenti che devono quindi eettuare delle scelte basandosi solamente su ciò che potrà essere percepito dai propri sensori. Tale problematica combina aspetti competitivi e cooperativi, in quanto ogni agente cerca di entrare in possesso della risorsa, ma, a seconda delle priorità dei propri avversari calcolate durante l'evoluzione dell'algoritmo, potrà dover cedere ad altri l'accesso.

L'algoritmo proposto nella presente tesi sfrutta i concetti derivanti dalla Teoria dei Giochi, branca della matematica che nasce per la modellazione di conitti tra entità di tipo competitivo e cooperativo in termini di giocatori, azioni e guadagni. Ogni agente crea un proprio modello in cui inserisce le informazioni a lui note riguardanti il mondo che lo circonda e, analizzandolo, deciderà le proprie azioni di controllo. Per sopperire alla mancanza di dati, sono introdotte delle ipotesi all'interno dei modelli, sfruttando i concetti presentati negli giochi estesi a informazione incompleta, parte della Teoria dei Giochi sfruttata per lo studio di conitti con queste caratteristiche. Il confronto con le azioni degli altri agenti consentirà di comprendere quanto queste ipotesi siano aderenti alla realtà o quanto debbano essere modicate tramite procedimenti di learning.

L'algoritmo è stato progettato per essere applicabile in scenari diversi, ognuno caratterizzato da una tipologia di agenti e da priorità calcolate diverse. Tra questi è stato analizzato in maniera più approfondita lo scenario riguardante veicoli in competizione per il raggiungimento di un punto nello spazio. Per questo ambito è stata progettata completamente la forma del gioco su cui basare la scelta, a partire dalla denizione delle azioni possibili no ai valori dei guadagni ottenibili. Attraverso le simulazioni basate su questo scenario è stato analizzato il comportamento dell'algoritmo all'interno di due conitti di natura diversa tra loro, riguardanti entrambi due veicoli in competizione per un target, ma che dieriscono per il calcolo delle priorità necessarie per il possesso della risorsa.

Parallelamente è stato ideato un algoritmo che sfrutta i risultati ottenuti in questo scenario per consentire l'identicazione di alcune caratteristiche da parte di un agente riguardanti i propri avversari. La presente tesi è strutturata in cinque parti. Nella prima sono indicati il ruolo della comunicazione all'interno dei sistemi multi agente, i metodi possibili per superarla e le basi di Teoria dei Giochi utili allo sviluppo del metodo proposto. Nel secondo capitolo è presentato l'algoritmo per la gestione dei

conitti, partendo dalla denizione dei concetti di base no all'esposizione dei passi che lo caratterizzano. All'interno dello stesso capitolo è indicato come poter applicare il metodo proposto negli scenari proposti ed è presentato un algoritmo usato per l'identicazione basato su quello di gestione. La terza parte espone gli aspetti più pratici dello sviluppo dell'algoritmo, indicando come verranno scelti i controlli da applicare e la progettazione dei guadagni che è stata scelta. Il quarto capitolo mostra i risultati delle simulazioni ottenute e valuta l'ecienza dei due algoritmi proposti. L'ultimo capitolo espone quindi le conclusioni della tesi e propone alcuni sviluppi futuri del lavoro svolto.

Capitolo 1

Introduzione

Scopo di questo capitolo è quello di presentare in maniera preliminare i concetti che saranno utilizzati all'interno della tesi. Nella prima parte è analizzata l'importanza della comunicazione all'interno dei sistemi distribuiti. Successivamente, sono denite le caratteristiche degli scenari di utilizzo per i quali l'algoritmo proposto è stato ipotizzato e indicati i conitti che possono caratterizzarli. Nella terza parte è presentata la Teoria dei Giochi, concentrandosi sugli elementi che saranno utili per lo sviluppo dell'algoritmo. Nell'ultimo punto è indicata una analisi su quanto è possibile trovare in letteratura nell'argomento trattato.

1.1 Comunicazione nei sistemi distribuiti

Con il termine di sistema distribuito si indica genericamente una tipologia di sistema costituito da un insieme di agenti, autonomi nelle scelte e con capacità di calcolo proprie, interconnessi tra loro per con-sentire il passaggio di informazioni, per l'espletamento di una certa funzionalità e in cui le comunicazioni interne avvengono tramite lo scambio di opportuni messaggi, seguendo determinati protocolli. Questa metodologia presenta alcune caratteristiche peculiari. I singoli elementi del sistema presentano una ele-vata capacità decisionale, il che garantisce l'adabilità ai guasti della struttura, in quanto l'avaria di un agente non impedisce agli altri di operare. Tramite lo scambio di dati, gli agenti possono aumentare le proprie conoscenze, raggiungere decisioni comuni e soddisfare gli obiettivi comuni, creando una forma di intelligenza distribuita. La presenza di più agenti può consentire di eettuare più sotto problemi in con-temporanea e di specializzare alcuni di essi per particolari processi, progettandoli in maniera dedicata. Per tali ragioni, in questo momento lo sviluppo preme su questa soluzione rispetto a quelle centralizzate, in una ottica di una società dei robot sempre più sviluppata. In letteratura, si parla sempre più spesso di Internet of Things, cioè di macchine in rete capaci di ottenere obiettivi comuni tramite lo scambio dati e le condivisione delle risorse ([1] [2]). La presenza di tanti agenti autonomi operanti in uno stesso ambiente, però, presenta nuovi problemi da gestire, quali la necessità di algoritmi distribuiti che consen-tano il coordinamento tra le varie azioni e il bisogno di informazioni. Ogni agente avrà una conoscenza parziale di ciò che accade nel mondo, ottenuta tramite sensori e, per poter eettuare i propri compiti, dovrà interfacciarsi con gli altri, per poter coordinarsi con le azioni altrui. Ciò comporta una elevato usso di scambio dei dati tra le varie parti del sistema. Problematiche come decidere un Leader, l'ac-cesso ad una risorsa o il raggiungimento di un consenso su un valore, possono essere risolte così tramite

algoritmi che, dopo il passaggio di informazioni, consentano agli agenti di trovare un bilanciamento tra le diverse visioni.

Esistono però alcune problemi che compromettono l'uso della comunicazione. Non è possibile avere scambi di dati perfetti e per questo i protocolli di trasmissione prevedono, di loro natura, meccanismi ridondanti per la spedizione di messaggi, in modo da minimizzare gli errori, ma aumentando il carico computazionale richiesto per il passaggio di informazioni. A questo, si devono aggiungere i problemi ambientali che possono intervenire nella trasmissione e rendere inservibile i messaggi inviati. Interferenze dovute a sorgenti di onde elettromagnetiche presenti nello scenario di lavoro possono corrompere i dati scambiati. Un caso esemplare è quello degli ambienti sottomarini, dove gli agenti percepiscono la presenza l'uni degli altri, ma lo scambio di informazioni è molto limitato, in quanto le onde radio non possono propagarsi nell'acqua e le onde sonore, le uniche sfruttabili per un passaggio di dati in questo ambiente, consentono scambi di breve entità e molto disturbati ([3] [4]). Un altra problematica è legata al mondo delle conversazioni cifrate, presenti in ambienti caratterizzati dal bisogno di un elevato livello di sicurezza. In questi casi, per rendere più sicura la cifratura si tende a diminuire il usso di dati scambiati tra gli agenti ([5]).

Per tutte queste ragioni, si può capire come una interessante via di indagine può essere quella gestire i conitti tra agenti, minimizzando, o annullando, lo scambio di dati In letteratura, come sarà mostrato all'interno nella sezione 1.4, sono presenti alcuni tipi di algoritmi nati per gestire i conitti con questo scopo. Tra questi, nella presente Tesi sarà analizzata la metodologia che prevede lo sfruttamento della Teoria dei Giochi.

1.2 Ambiti di utilizzo

L'algoritmo che verrà sviluppato all'interno della presente tesi nasce per poter essere applicato in ambiti con caratteristiche diverse tra loro. Alcuni esempi che verranno trattati sono:

• Gestione dii veicoli che competono per l'accesso ad un punto specico dello spazio (corridoi, carico/scarico materiale, stazioni di carica);

• Elezione di un leader all'interno di una squadra di veicoli operanti in un ambiente comune; • Gestione della rete di comunicazione all'interno dei sistemi Multi-Core;

• Razionalizzazione dell'energia utilizzabile nelle reti Smart-Grid.

Per tutti questi ambiti è possibile infatti denire una risorsa alla quale gli agenti hanno bisogno di ac-cedere e dei criteri in base ai quali denire l'ordine di accesso a questa. Questi esempi dieriscono per l'esclusività della risorsa, il tipo di azioni che gli agenti possono eettuare e i criteri di accesso. Tutti i problemi presentati, però, combinano caratteristiche di competizione e di cooperazione tra gli agenti e sono caratterizzati, o possono esserlo, dall'assenza di comunicazione all'interno della rete. La proget-tazione dell'algoritmo all'interno della presente tesi si concentrerà sugli scenari con veicoli, cercando di risolvere problemi quali la competizione per l'accesso ad una stazione di carica, in seguito indicato come Battaglia per l'Energia (o BpE) e l'elezione di un Leader all'interno della rete, in seguito indicato come Leader Election (o LE), ma saranno presentate anche le linee guida per l'applicazione negli altri casi.

1.2.1 La Battaglia per l'Energia

Si denisce ora il primo dei due scenari che saranno usati come esempio di problematica nel quale testare l'algoritmo proposto. L'area di lavoro prevederà la presenza di alcuni agenti che eettuano alcuni task in uno spazio piano comune, privo di ostacoli. E' presente nella zona indicata un unico caricabatterie, un punto di ricarica al quale tutti possono accedere in caso di bisogno. Quando un agente entra in riserva, cioè ha meno energia residua di un valore limite, si dirige verso il caricabatterie per poi ripartire con il suo percorso. Essendo presente, però, solo un unico punto di ricarica, nel momento in cui due o più agenti si presentano in un area vicina al target, nasce il problema di individuare quale veicolo deve raggiungere per primo il punto. E' un classico problema di accesso esclusivo ad una risorsa condivisa. Ogni agente avrà quindi interesse a raggiungere per primo l'obiettivo, quindi si ha competizione, ma viene anche richiesta un'ottica di cooperazione, in quanto gli agenti dovranno capire chi tra loro ha più bisogno di accedere alla risorsa e cedergli il diritto di arrivare per primo. Ma questo non sarà l'unico criterio in base al quale individuare chi merita questo privilegio, perchè ci dovrà essere una combinazione tra il bisogno di energia e la distanza che l'agente deve coprire per raggiungere il target, in modo da evitare che un veicolo sprechi quanto ha già percorso prima dell'inizio del conitto . Normalmente un problema di questa natura è facilmente risolvibile tramite la comunicazione attiva, in quanto gli agenti potrebbero scambiarsi i rispettivi stati e, dopo un algoritmo di consenso, si arriverebbe ad un punto di incontro, consentendo all'agente che lo necessità maggiormente ed è più vicino al target di accedere alla risorsa. L'obiettivo di questa tesi è cercare di capire se e come si può risolvere un conitto di questo tipo senza alcun scambio di dati.

Caratteristica fondamentale per l'algoritmo qui proposto sarà che ogni agente abbia conoscenza perfetta di se stesso. Ognuno di essi deve conoscere il proprio livello di Batteria, la propria distanza dall'obiettivo e la distanza dagli avversari. Quest'ultimi due dati indicano che è importante la presenza di un sensore capace di rilevare la posizione del target e degli altri agenti entro una certa area. Spesso gli agenti sono già equipaggiati con sensori di questo tipo, per evitare collisioni o per monitorare l'ambiente circostante, di conseguenza non viene richiesto alcun aumento di equipaggiamento. Note e comuni ai vari agenti saranno le funzioni di decisione, ma i valori da inserire potranno (e saranno) diversi.

1.2.2 Leader Election

L'altro ambiente di applicazione che verrà usato per l'analisi dell'algoritmo proposto vede una serie di veicoli eleggere un leader all'interno del sistema. Tale procedura prevede la scelta da parte di tutti gli agenti di un coordinatore tra di essi che possa guidare gli altri all'interno di un preciso task distribuito. Un esempio può essere la denizione di una traiettoria da seguire in formazione. Gli algoritmi che risolvono tale problematica sfruttano il passaggio di messaggi contenti il codice di identicazione di ogni agente, in modo da consentire ad ogni elemento del sistema di conoscere il massimo valore presente nella squadra. L'agente corrispondente a quel codice viene quindi indicato come leader .[6]

L'algoritmo proposto all'interno della tesi vuole consentire questa procedura senza lo scambio di mes-saggi tra i veicoli, modellandolo come un problema di raggiungimento di un punto nello spazio. Il codice di identicazione verrà sfruttato come discriminante per l'accesso al target. In questo modo, l'unico veicolo che raggiungerà il traguardo sarà quello caratterizzato dal valore massimo presente all'interno della squadra e indicato come leader .

Anche in questo si chiede che l'agente abbia perfetta conoscenza di se stesso e sia equipaggiato di sensori capaci di rilevare le posizioni dei vari elementi all'interno di un ambiente comune.

1.2.3 Altri scenari multi agenti

Esistono possibili campi di applicazione dell'algoritmo in situazioni che non prevedono agenti, ma per i quali si ritrovano problematiche simili per l'accesso ad una risorsa:

• Processori all'interno di un Multi-Core: inserendo la logica della risorsa a cui accedere all'interno del mondo informatico, si può considerare il caso di più processori inseriti all'interno dello stesso computer, ognuno legato ad un task specico, ma vincolati agli altri dalla presenza di comuni canali di comunicazione accessibili solo da un agente alla volta. All'interno di questo ambiente è possibile indicare come conitto l'accesso simultaneo proprio a questi canali di comunicazione. Possono essere indicati come elementi in discriminanti l'accesso l'importanza del Task e i tentativi fatti per accedere alla risorsa. Dopo una serie di tentativi ripetuti, i vari processori dovranno capire quale è il più importante tra loro e cedere a lui la risorsa.

• Smart-Grid: considerando come agenti le case presenti all'interno di una stessa area, la risorsa a cui accedere diventa la linea elettrica e il problema diventa del tipo load shedding. Ogni agente gestirà in autonomia gli elettrodomestici presenti al proprio interno, ma dovrà considerare anche la quantità energia che occorrerà alle altre abitazioni. Di conseguenza, in base a successivi tentativi di accesso, dovrà capire di quanta parte della risorsa, che in questo caso può soddisfare più agenti in contemporanea, può disporre e gestire al meglio la parte interna. Quindi, in questo ambiente di lavoro non c'è un accesso esclusivo alla risorsa, come invece mostrato nei casi precedenti. Il privilegio di accesso può essere denita in base a valori relativi agli elettrodomestici che si vogliono utilizzare, condivisi tra le varie abitazioni.

Esistono già alcuni algoritmi che consentono di risolvere il problema di accesso alla risorsa in questi due scenari e alcuni di questi saranno discussi nella sezione 1.4. All'interno del capitolo 2 saranno presentate le modiche da apportare all'algoritmo proposto per questi scenari di utilizzo

1.3 La Teoria dei Giochi

E' possibile presentare la Teoria dei Giochi (TdG in seguito) attraverso la denizione presente in [7]: Il termine teoria dei giochi identica una disciplina che ha come oggetto di analisi le situazioni in cui più decisori si trovano a fare delle scelte, dal complesso delle quali dipende il risultato nale. [. . . ] Assunzioni standard sono che i decisori siano razionali, ovverosia che abbiano preferenze coerenti sul complesso degli esiti nali potenziali, e che ciascuno cerchi di determinare, per quanto in suo potere, l'esito che maggiormente preferisce. Altra ipotesi standard è che i decisori siano intelligenti, il che signica che sono in grado di rappresentare le situazioni che hanno di fronte, le possono analizzare, possono formulare ipotesi ed eettuare deduzioni sul comportamento proprio ed altrui [...].

Un'altra denizione è possibile trovarla in [8]: Game theory is a bag of analytical tools designed to help us understand the phenomena that we observe when decision-makers interact. The basic assump-tions that underlie the theory are that decision-makers pursue well-dened exogenous objectives (they are rational) and take into account their knowledge or expectations of other decision-makers' behavior (they reason strategically).

E' quindi un metodo per modellare la realtà in caso di decisioni o scelte da parte di individui razionali. Nei casi più semplici, per denire un gioco, cioè un modello, bastano questi elementi:

Descrizione 1 (Standard Game) Si denisce come Standard (o Strategic) Game l'insieme dei se-guenti elementi:

Lei\Lui W L W 1,3 0,0

L 0,0 3,1 Tabella 1.1: La Battaglia dei Sessi

• Un insieme nito G di giocatori, con G = G1_{, G}2_{, ....G}K _{e G}k _{il singolo giocatore, appartenente}

a G;

• Per ogni giocatore Gk _{si denisce un insieme nito di azioni possibili A}

k = {a1...aj};

• Una funzione di guadagno U(A1, A2..AK)che collega l'insieme A con l'insieme R dei reali, indicante

il guadagno di tutti i giocatori in quella combinazione di azioni. Si indica con Uk la parte di U

relativa ad un singolo giocatore.

Questa denizione di base può trovare molti riscontri e infatti la TdG viene utilizzata quotidianamente in vari campi: economia, biologia, sport, ambienti strategico-militare, politica, informatica, sociologia, psicologia e molti altri ([7]). Si riporta qui un esempio classico in letteratura per chiarire quanto esposto, indicato come La Battaglia dei Sessi. In esso, sono presenti due danzati interessati a decidere che lm vedere insieme. Nel cinema sono presenti due lm: uno di guerra (indicato con W e preferito da lui) e l'altro d'Amore (indicato con L e preferito da lei). Quindi abbiamo:

• Due Giocatori G = {Lei, Lui};

• Due possibili scelte per entrambi ALei= ALui = {W, L}.

Il passo successivo è denire i guadagni per le 4 combinazioni possibili delle azioni dei due giocatori. Di seguito (e in tutta la tesi), verrà indicata prima l'azione (o la serie di azioni) del primo giocatore (in questo caso Lei), e di seguito quella del secondo giocatore (cioè Lui). Stesso comportamento sarà tenuto per le coppie di guadagni mostrati.

• Le combinazioni di azioni (L,W) e (W,L) prevedono che Lui e Lei facciano due scelte diverse, ma questo va contro l'idea di vedere il lm insieme, quindi il guadagno sarà basso per entrambi; • (W,W) è una opzione perfetta per Lui (guadagno massimo), ma non per Lei, anche se comunque

rimane la possibilità di vedere il lm insieme (guadagno medio);

• (L,L) è una opzione perfetta per Lei (guadagno massimo), ma non per Lui, anche se comunque rimane la possibilità di vedere il lm insieme (guadagno medio).

E' possibile indicare una situazione di questo tipo nella Tab 1.1. E' possibile vedere sono (W,W) e (L,L) quelle a guadagno maggiore. Ma, oltre la logica, esiste un principio per denire i guadagni che spettano ai vari giocatori? Spesso vengono utilizzate funzioni di costo, guadagni monetari ottenibili in base alle scelte fatte ([7], [8]). In questi casi è quindi semplice legare il guadagno modellato con quello reale. In altri si segue un procedimento logico simile a quello qui mostrato.

Con l'aumento delle applicazioni della TdG nei vari campi mostrati sopra, si è avuto uno sviluppo molto ampio, a tratti confusionario, dei concetti matematici della Teoria per adattare i principi di base ai vari utilizzi. E' possibile dividere i vari tipi di Giochi, sempre riferendosi a quanto indicato in [8], in base a due parametri: Decisioni nel Tempo e Quantità di Informazioni.

• Decisioni nel Tempo

 Standard Games: Giochi in cui ogni Giocatore deve scegliere tra le varie azioni una e una sola e, non appena eettuata, il Gioco si conclude (l'esempio della Battaglia dei Sessi rientra in questo tipo di Giochi);

 Extensive o Dynamic Games: Giochi in cui ogni Giocatore può scegliere tra le varie azioni una e una sola strategia, cioè una combinazione di azioni, da eettuare una dopo l'altra in una successione di Giochi;

• Quantità di Informazioni

 Complete/Incomplete Information: indica la conoscenza o meno di caratteristiche dell'avver-sario che inuenzano il modello;

 Perfect/Imperfect Information: tipico degli Extensive Games, indica la conoscenza o meno della sequenza di decisioni prese dall'avversario o di parti dello sviluppo nel tempo del Gioco. Si aggiunge che fonti diverse possono utilizzare altri nomi o indicare cose diverse con quelle che sono state qui presentato. Nel resto di questa tesi, verranno seguiti i termini qui deniti. Di seguito saranno presentate le dierenze tra Standard e Extensive Games e alcuni esempi di quest'ultimo caso. Sarà poi analizzato il comportamento nei casi di Standard Games with Incomplete Information, utile per il problema esposto nella tesi.

1.3.1 Standard e Extensive Games

Come già indicato, la dierenza fondamentale tra i due tipi di Giochi è il Tempo. Negli Standard, categoria nella quale rientrano gli esempi visti no ad ora, è possibile fare solo una scelta di una azione in base ai guadagni, mentre negli Extensive si sceglie una strategia, cioè una serie di azioni nel tempo, per rispondere a più scelte successive. Si supponga il caso nel quale si estenda la battaglia dei sessi a due serate consecutive, nelle quali, quindi, entrambi i giocatori debbano ripetere la scelta due volte. Si considerano uguali i guadagni in entrambi i giochi. L'inserimento del tempo muta leggermente quanto detto no ad ora, in quanto si è sempre supposto che i due giocatori attuino le proprie azioni nello stesso istante, non essendo inuenzati dalla decisione dell'altro. La comparsa di un ordine, di un prima o dopo, implica chiedere quali scelte in precedenza sono state fatte e quali no. Si può quindi denire un Extensive Games come:

Descrizione 2 (Extensive Game) Si denisce come Extensive (o Dynamic) Game l'insieme dei se-guenti elementi:

• Un insieme nito G di giocatori, con G = G1_{, G}2_{, ....G}K

e k il singolo giocatore, appartenente a G;

• Una strategia compiuta da un giocatore, cioè un insieme nito di azioni Sk _=Ak 1...AkN

, dove con Ak

n si indica l'azione del singolo giocatore k nel posto n della sequenza. Per ogni elemento

della strategia è possibile denire un insieme di azioni possibili Ak

n= {a1...aj};

• Una funzione di guadagno U(S1_{, S}2_..SK_{)che collega l'insieme A con l'insieme R dei reali, indicante}

il guadagno di tutti i giocatori in quella combinazione di azioni. Si indica con Uk la parte di U

(a) Gioco di Tipo 1

(b) Gioco di Tipo 2

(c) Gioco di Tipo 3

Usando questa forma base è possibile modellare giochi diversi, ma è spesso necessario anche inserire altre informazioni. Può essere importante inserire alcune informazioni sull'ordine con il quale le singole azioni vengono eettuate. Per comprendere meglio quanto esposto, si riprende l'esempio già visto in precedenza, applicandolo a tre casi particolari. Nel primo, i giocatori non fanno la scelta contemporaneamente, ma uno dopo l'altro. Nel secondo caso, scelta del secondo lm viene conoscendo dopo già la scelta precedente ed è quindi dipendente da essa. Nell'ultimo, si considera che i giocatori si dimenticano della scelta precedente, quindi la seconda non dipende dalla prima, o, che è equivalente, tutte le scelte vengono fatte all'inizio. E' possibile tradurre questi casi come si vede in Fig 1.1, attraverso la forma indicata come albero decisionale, la più indicata per visualizzare questo tipo di giochi. Nei quadrati sono indicate le azioni possibili (in celeste per Lui, in rosa per Lei). Ogni nodo dell'albero corrisponde ad una decisione che deve prendere un giocatore, ad una scelta tra le azioni possibili. Alle estremità si possono indicare i guadagni ottenibili, frutto delle scelte precedenti. Si può notare che facilmente il graco diventa più grande all'aumentare del numero di ripetizioni delle scelte fatte e delle azioni possibili. Avendo solo due agenti, con ognuno due azioni possibili e modellando due scelte successive si ottengono 16 combinazioni possibili. Anche se i 3 alberi mostrati sono simili, esistono dierenze che rispecchiano i casi diversi modellati. Nella seconda e nella terza immagine sono presenti tratti che uniscono nodi diversi. Questi rappresentano gracamente l'ipotesi di conoscenza o meno dell'azione fatta da parte di un giocatore. Signica che per il giocatore in questione non c'è dierenza tra i livelli superiori. Nel caso 1.1.b, si vede che Lei è libera di fare la prima scelta, come Lui, per il quale è indierente sapere su quale ramo è. Dopo, Lei deciderà la nuova azione sapendo come è nita la prima decisione, come farà Lui, indipendentemente da quanto avrà scelto Lei. E' quindi, teoricamente, possibile spezzare l'Extensive Games in due giochi Standard, a patto che si conti il fatto che i due giochi sono legati all'interno dei guadagni. Nel terzo graco, invece, non ci sono punti in cui i giocatori possano distinguere quanto stia accadendo. Tutti sanno a che punto si è nella sequenza, ma non sa delle decisioni prese dall'altro. Di conseguenza non c'è inuenza nelle scelte, che possono essere considerate come simultanee tra loro.

E' possibile trasformare i graci nella forma più nota, in tabella, trasformando il tutto in un unico Standard Games, a patto di considerare che il giocatore indichi subito le azioni che farebbe in tutti i casi. Di conseguenza, quella che in un gioco Standard è indicata come una singola azione, in questo caso diventa una combinazione di possibili azioni, in quanto il giocatore dovrà indicare il comportamento che terrà in tutti i casi possibili. Questo concetto sarà specicato nella riproduzione dei tre graci sopra mostrati, i quali non possono essere tradotti nello stesso Gioco Standard, in quanto sono diverse le ipotesi fatte al loro interno.

Nelle prima delle tre tabelle presenti in Tab 1.2, pur mostrando la trasformazione di soltanto parte del graco (si considera solo un ramo del gioco, per la trattazione completa si deve raddoppiare il numero di colonne e di righe e complicare ulteriormente il graco; per approfondire si rimanda al già citato [7]), si vede come le opzioni possibili al giocatore sono molte, in quanto non solo dipendono da quello che si vuole, ma anche da ciò che è successo in precedenza. Si introducono quindi le seguenti notazioni:

• ak

n (A)se l'azione n del giocatore k dipende da A, dove A = A 1

n, ....Ak−1n , Ak+1n , ....AKn

, cioè le azioni allo stesso passo degli altri giocatori;

• ak j/akl/a

k

h....se il giocatore k sceglie di giocare una azione diversa a seconda della situazione in cui

si trova.

Quindi, ad esempio, WWWW/WWWL signica che Lui indica di giocare W nel caso in cui la prima

azione di Lei è W e poi giocherà W sia se Lei giocherà di nuovo W, sia se questi giocherà L. L'idea è quella che, per poter pianicare a priori tutto il gioco, per ogni giocatore si dovrà considerare il guadagno

Lui\Lei W WW/W WL W WW/W LL W LW/W WL W LW/W LL WWWW/WWWL WWWW/WWLL WWLW/WWLL WWW LW/WWWL LWWW/LWWL LWWW/LWLL LWLW/LWWL LWLW/LWLL

(a) Trasformazione parziale del Gioco di Tipo 1

Lei\Lui W Wa/W Wb W Wa/W Lb W La/W Wb W La/W Lb

W Wa/W Wb

W Wa/W Lb

W La/W Wb

W La/W Lb

(b) Trasformazione parziale del Gioco di Tipo 2

Lei\Lui W W W L LW LL W W

W L LW LL

(c) Trasformazione Totale del Gioco di Tipo 3

in ognuna delle possibili combinazioni delle azioni possibili. Di conseguenza, i guadagni da inserire in tabella in questo caso saranno 128. Si può indicare per il caso generico:

U (a1 j_{s (A)}/a1 j_{f (A)}/.../a1 j_{h (A)}, a2 j_{l (A)}/a_{p (A)}2 j ..../a2 j_{q (A)}, ..., aK j_{d (A)}/aK j_{r (A)}/.../aK j_{t (A)}) = = U (a1 j_{s (A)}, a2 j_{l (A)}....aK j_{d (A)}) + U (a1 j_{f (A)}, a_{p (A)}2 j ....aK j_{r (A)}) + ... + U (a1 j_{h (A)}, a2 j_{q (A)}....aK j_{t (A)}) e, applicandolo ad un caso particolare tra quelli proposti,

UA(WWWW/WWWL, W WW/W WL) =

= UA(WWWW, W WW) + UA(WWWW, W WL) + UA(WWWL, W WW) + UA(WWWL, W WL)

UB(WWWW/WWWL, W WW/W WL) =

= UB(WWWW, W WW) + UB(WWWW, W WL) + UB(WWWL, W WW) + UB(WWWL, W WL)

Nella seconda tabella, invece, diminuisce il numero di azioni possibili, al prezzo di avere meno infor-mazioni sul gioco. I due giocatori scelgono la prima azione in autonomia e non c'è più la sudditanza da parte di uno dei giocanti rispetto all'altro, mentre solo la seconda scelta sarà vincolata al risultato della decisione (anche qui, per ragioni di spazio, si mostra solo la tabella relativa ad un ramo e si indicano con le lettere minuscole le due situazioni possibili in quel ramo). In questo i guadagni possibili sono 64. Il terzo caso, invece, vede entrambi i giocatori all'oscuro di quanto fatto in precedenza dall'avversario e le combinazioni possibili sono ancora meno, in quanto non sono più presenti le dipendenze, scompare l'aspetto di risposta tra gli agenti e l'inuenza tra questi e diventano solo 16 i guadagni possibili, tanti quanti quelli che sono presenti nel graco e non c'è alcun calcolo richiesto per ottenere i guadagni. Se da una parte si è invogliati a usare questo modello per la sua semplicità, dall'altra si rischia di perdere aspetti importanti della realtà. Il Gioco del Poker, ad esempio, non è modellabile in questo modo, in quanto andrebbero perse tutte le informazioni dovute alle puntate tra i vari giocatori. Una serie di ripetizioni di Morra Cinese, ad esempio, è possibile vederlo sotto questo aspetto, però se ogni gioco è slegato dall'altro dal punto di vista della scelta delle azioni.

1.3.2 Giochi a informazione incompleta

Si introduce ora, dopo l'aspetto del tempo, un'ulteriore possibilità di modellazione della realtà. Fino ad ora, si sono considerati giocatori che hanno una perfetta conoscenza del mondo che gli circonda al momento di una decisione, ma questo può non rispondere ai casi trattati. La scelta, ad esempio, se portare con se o no l'ombrello prima di sapere se pioverà o meno è una decisione che deve essere fatta in base a stime o, usando il termine comune in letteratura ([7]) a credenze, che indicano quanto è probabile che una situazione accada (in questo caso la presenza di pioggia). Altri esempi sono la mancanza di informazioni su uno dei giocatori in presenti, come il tipo di preferenze che questi ha o la tendenza a fare certe scelte. Per quanto riguarda l'argomento esposto nella tesi, saranno particolarmente interessanti i casi in cui le informazioni mancanti riguardano le preferenze dell'avversario, quindi il guadagno relativo ad un particolare gioco. Una possibile denizione, tra le molte proposte, è:

Descrizione 3 (Standard Game with Incomplete Information) Si denisce come Standard (o Strategic) Game with Incomplete Information l'insieme dei seguenti elementi:

• Un insieme nito G di giocatori, con G = G1_{, G}2_{, ....G}K

e k il singolo giocatore, appartenente a G;

• Un insieme nito di Tipo per ogni giocatore Gk T =G

k 1...GkJ

, caratterizzato ognuno da un relativo set di azioni e di guadagni;

• Una distribuzione di probabilità P (Gk

T), indicante la probabilità che un certo giocatore sia di un

certo tipo;

• Un insieme nito di azioni relativo ad ogni tipo di giocatore Ak j₌n_ak j 1 ...a

k j N o;

• Una funzione di guadagno UT(A1 j, A2 j....AK j)che collega l'insieme A con l'insieme R dei reali,

indicante il guadagno di tutti i giocatori in quella combinazione di azioni in quella combinazione di Tipi di Giocatori.

Verranno quindi creati una serie di giochi paralleli, ai quali parteciperanno i vari tipi di giocatori possibili. Partendo dall'esempio già spiegato della Battaglia dei Sessi e rimanendo in un caso di gioco Standard, si suppone che i singoli giocatori non conoscano i gusti dell'altro, ma che essi conoscano i propri. Questo gioco non è completo, in quanto non sapendo i gusti dell'avversario, non si possono indicare le preferenze e quindi valutare i guadagni che i giocatori potrebbero ottenere nelle varie situazioni. Il primo passo per poter costruire un gioco in questi casi è quello di denire i possibili Tipi di avversario. Si consideri che ci siano due possibili Lei e non si sappia quale delle due partecipi al gioco. Una che ama i lm di guerra e l'altra quelli d'amore. Questi due tipi vengono modellati creando due giochi separati presenti in Tab 1.3, che deniremo come Matrici di Tipo. Seguendo quanto indicato da Harsanyi [9], è possibile da questi due creare un unico gioco, introducendo un livello ttizio, in cui si indica la credenza di avere davanti un Tipo di Lei o l'altro. La struttura diventa simile quindi a quella di un Extensive Games, in cui la prima scelta non è di un giocatore, ma della Natura, un terzo giocatore ttizio che viene inserito, il quale sceglierà quale tipo di gioco, tra quelli proposti, sarà applicato (esempio visibile in Fig 1.2). La credenza viene modellata tramite la probabilità, che sarà indicata come Probabilità di Tipo. Con una probabilità p si sarà in un caso e con (1-p) nell'altro. In base a quanto già indicato nel caso dell'Extensive Game per la composizione di un unico Standard Game, sarà importante capire quali saranno le conoscenze da parte del giocatore nel momento della scelta. Se a Lui verrà rivelato il Tipo di Lei che ha di fronte e potrà fare quindi la scelta in base a questo, allora questo aspetto dovrà essere inserito nel gioco nale. Modellando i casi presentati nella sezione precedente e facendo riferimento sempre a [7], si fanno qui due esempi. In entrambi i casi Lui non ha informazioni sulla scelta della Natura, ma nel primo la rivelazione inuenza le scelte, nel secondo non c'è dipendenza. Si considera per questo esempio, che per Lei invece non ci sia dierenza nelle sue scelte a seconda del suo Tipo. La composizione delle matrici di partenza avviene in maniera diversa. Nel primo caso, dato che ogni giocatore deve dare tutte le possibili di combinazioni:

1. Preso il guadagno del singolo gioco UT(A1 j, A2 j....AK j), si moltiplica per la probabilità che quel

Tipo di gioco avvenga ¯ UT(A1 j, A2 j....AK j) = UT(A1 j, A2 j....AK j) YK 2 k P (Gk_T) ad esempio, nel caso esposto

¯

U1(W, W ) = p U1(W, W )

¯

U2(W, W ) = (1 − p) U2(W, W )

2. Presi i guadagni così calcolati, si sommano quelli a uguale strategia provenienti dai tutti i Tipi di Gioco possibili, usando la stessa notazione vista in precedenza riguardante la dierente scelta di

azioni in situazioni diverse U (a1 j s /a1 js /.../a1 js , a 2 j h /a 2 j h ..../a 2 j h , ..., a K j f /a K j f /.../a K j f ) = P2(K−1) 1 T ¯ UT(a1 js , a 2 j h ....a K j f ) = =P2(K−1) 1 T (UT(a1 js , a 2 j h ....a K j f ) YK 2 k P (Sk_|Gk T) YK 2 k P (Gk T))

quindi, sempre nel caso esposto,

U (W(p)/W(1−p), W ) = U1(W, W ) + U2(W, W )

U (W(p)/W(1−p), L) = U1(W, L) + U2(W, L)

U (L(p)/L(1−p), W ) = U1(L, W ) + U2(L, W )

U (L(p)/L(1−p), L) = U1(L, L) + U2(L, L)

e questo corrisponderà al guadagno nel caso Lui non dierenzi la sua scelta sapendo il tipo di Lei; 3. Per calcolare i guadagni di un giocatore nella situazione in cui questi eettui una scelta diversa a

seconda del tipo di uno degli avversari, si potrà generalizzare l'equazione già vista indicando U (a1 j s /a 1 j f /.../a 1 j h , a 2 j l /a2 jp ..../a2 jq , ..., a K j d /aK jr /.../a K j t ) = = ¯U1(a1 js , a 2 j l ....a K j d ) + ¯U2(a1 jf , a 2 j p ....a K j r ) + ... + ¯U2(K−1)(a1 j_h , a2 j_q ....aK j_t )

quindi, sempre nel caso esposto,

U (W(p)/L(1−p), W ) = U1(W, W ) + U2(L, W )

U (W(p)/L(1−p), L) = U1(W, L) + U2(L, L)

U (L(p)/W(1−p), W ) = U1(W, W ) + U2(L, W )

U (W(p)/L(1−p), L) = U1(W, L) + U2(L, L)

Il secondo esempio mostrato non necessita del terzo punto, in quanto Lui non sarà a conoscenza del Tipo e, quindi non prevede di fare scelte diverse a seconda dei casi..

(a) Gioco nel Caso 1

(b) Gioco nel Caso 2

Figura 1.2: Giochi ad Informazione Incompleta

Lui\Lei W L W 3,1 0,0 L 0,0 1,3 Lui\Lei W L W 3,3 0,0 L 0,0 1,1 Tabella 1.3: Matrici di Tipo

Lui\Lei W L Wp/W(1−p) 3,2p+1 0,0

Wp/L(1−p) 3p,3p (1-p),3(1-p)

Lp/W(1−p) 3(1-p),(1-p) p,p

Lp/L(1−p) 0,0 1,3-2p

(a) Gioco nel Caso1

Lui\Lei W L W 3,2p+1 0,0

L 0,0 1,3-2p

(b) Gioco nel Caso 2

Tabella 1.4: Risultato della composizione di Matrici nei due esempi

Il metodo di risoluzione dello stesso problema nel caso di Extensive Games verrà proposto nel capitolo 2, in quanto sarà lo strumento utilizzato all'interno dell'algoritmo, basandosi, ovviamente, su quanto visto nel caso degli Standard.

1.3.3 Ricerca degli Equilibri

Fino a questo punto sono stati presentati i metodi di modellazione della realtà. Resta da capire come sfruttare queste conoscenze, come capire quali saranno le azioni o strategie che i giocatori sceglieranno posti davanti alle scelte. Lo sviluppo della TdG ha generato molti metodi di lettura della realtà e di ricerca di quelli che vengono indicati come Equilibri. In maniera analoga al caso sico, si indica come Equilibrio una situazione in cui le forze agenti sul sistema non sono sbilanciate tra loro, cioè, in questo caso, la scelta delle azioni da parte dei due giocatori porta ad un punto in cui una eventuale modica porta ad uno sbilanciamento dei guadagni ottenuti. E' la situazione nale a cui il sistema tenderà se lasciato in autonomia ([7]). Esistono più metodi di ricerca dell'equilibrio e allo stesso tempo più denizioni di esso perché è possibile modellare lo stesso sistema in modi diversi. E' da precisare subito che spesso e in generale tali metodi non portano allo stesso risultato.

Storicamente, esistono tre metodi utilizzati in letteratura per la ricerca degli equilibri, scritti di seguito nel caso di due giocatori, ma facilmente traducibili in presenza di più partecipanti:

• Metodo Minmax: come si può leggere in [10] Il teorema del minimax (o del maximin) stabilisce che ogni gioco nito a somma costante possiede almeno un punto di equilibrio di minimax in strategie pure o miste e tale equilibrio è il punto di incontro tra la volontà dei giocatori di massimizzare il minimo payo ottenibile data la strategia dell'altro. Indicando con A il primo giocatore, con B il secondo e con U il guadagno, è possibile tradurre l'equilibrio Minmax con

minA(maxB(UA(aA, aB))) = maxB(minA(UB(aA, aB)))

come già indicato, è valido per quei giochi a somma costante o somma zero, cioè tali per cui UA(aA, aB) + UB(aA, aB) = 0, e per questo, ad esempio, non è applicabile alla Battaglia dei Sessi

sopra esposta;

• Ottimo Paretiano: sempre riferendosi a [7], si può indicare un equilibrio paretiano quando l'allo-cazione delle risorse è tale che non è possibile apportare miglioramenti paretiani al sistema, cioè non si può migliorare la condizione di un soggetto senza peggiorare la condizione di un altro, cioè non esistono combinazioni tali per cui, indicate con (aA∗, aB∗)le azioni che portano all'equilibrio,

si possa avere che

UA(aA, aB) > UA(aA∗, aB∗)

UB(aA, aB) > UB(aA∗, aB∗)

tale metodo è usato molto in economia o nella descrizione di sistemi sociali, considerando scenari, quindi, in cui si ha concorrenza pura a parità di condizioni tra i giocatori; nel caso della Battaglia dei Sessi, non esistono Ottimi Paretiani, in quanto le combinazioni (W,L) e (L,W) sono tali per cui, scelta una delle due come equilibrio, si ottiene in entrambi i casi 3 > 1 e 1 < 3 e, quindi, non è possibile scegliere un equilibrio.

• Equilibrio di Nash: è il concetto più sfruttato all'interno della TdG negli ultimi 50. E' possibile dare una rigorosa denizione [7]: Sia dato il gioco G(A, B, UA, UB). Diremo che (aA∗, aB∗) è

un equilibrio di Nash per G se: UA(aA∗, aB∗) > UA(aA, aB∗)per ogni aA di A e UB(aA∗, aB∗) >

UB(aA∗, aB)per ogni aBdi B. Nel caso della Battaglia dei Sessi, sia (W,L) e (L,W) sono equilibri

di Nash, in quanto soddisfano entrambi la denizione (si ha 3 > 0 e 1 > 0 per (W,L) e 1 > 0 e 3 > 0 per (L,W)). Rispetto agli equilibri precedentemente detti, si può dimostrare che esiste sempre almeno un Equilibrio di Nash all'interno di un Gioco. Può accadere che questo sia un equilibrio

W L W 3p,1(1-q) 0,0

L 0,0 1(1-p),3q

(a) caso per q e p generici

W L W 3/4, 3/4 0,0

L 0,0 3/4, 3/4

(b) Caso per p e q ssati

Tabella 1.5: La Battaglia dei Sessi (strategie miste)

puro, come nel caso della Battaglia dei Sessi nel caso in cui entrambi i giocatori vogliono andare a vedere un lm di guerra (in questo caso avrei un unico equilibrio in (W,W) arriva comunque ad un equilibrio), o misto. Si parla di equilibri misti quando un giocatore non indica una azione da eettuare, ma una distribuzione di probabilità sulle azioni, cioè indica per ognuna di esse una probabilità di scelta. Parallelamente, tali distribuzioni diventano pesi per i guadagni che si otterrebbero giocando una data distribuzione. Si riporta l'esempio della Battaglia dei Sessi in tale caso (Tabella 1.5a) .Supponendo p = q = 1/4 ottengo una situazione come quella presente in Tab. 1.5b. La teoria prevede che i due giocatori sceglieranno, entrambi, l'azione da giocare estraendola da questa distribuzione. E' chiaro che un equilibrio puro è un caso particolare di quello misto, con una distribuzione di probabilità in cui una azione ha la probabilità 1 di essere giocata. A seconda del tipo di gioco (Standard o Extensive, Complete o Incomplete) esistono diverse forme applicative degli Equilibri di Nash. Tra queste si sottolineano:

 Equilibri Bayesiani: Un equilibrio di Nash Bayesiano è denito come una combinazione di strategie e credenze specicate per ogni tipo di ogni giocatore circa i tipi degli altri giocatori. Questo prolo è tale per cui ogni giocatore massimizza il suo payo atteso, date le sue con-vinzioni circa i tipi degli altri giocatori e le strategie dagli altri giocatori. Il singolo guadagno ottenuto da una combinazione di azioni da parte dei vari agenti viene pesato della probabilità che quella data combinazione accada e, in base a questo, confrontato con gli altri guadagni come visto in precedenza. Tale equilibrio è quello più utilizzato nel caso di Standard Games ad Informazione Incompleta ([8]).

 Perfect Baysian Equlibrium: Sfruttabile nel caso di Extensive Games a Informazione In-completa o Imperfetta, richiede la dinamica all'interno della strategia, cioè che possa essere denita una sequenza di azioni tra i giocatori. E' un equilibrio di tipo parziale, in quanto si possono confrontare soltanto i guadagni che appartengono allo stesso ramo informativo del gioco, cioè tra casi simili.

I tre metodi presentati non sono gli unici utilizzati, in quanto, come detto per le tipologie di giochi, le denizioni nate nel corso del tempo si accavallano e si mischiano a seconda del campo di utilizzo.

Nel proseguo di questa tesi sarà mostrato come i vari concetti di TdG presentati saranno sfruttati per consentire la creazione dell'algoritmo. Nel Capitolo 2 si identicherà il tipo di gioco utile e si indicherà come tradurre i concetti presentati in base agli scenari di utilizzo proposti, mentre nel capitolo 3 si concluderà il modello attraverso la scelta dei guadagni e presentando il metodo di ricerca degli equilibri nel Gioco utilizzato.

1.4 Stato dell'arte

Come già anticipato, per risolvere il problema della mancanza di comunicazione tra agenti sono stati proposti più metodi. I principali rientrano in due tipologie: la Simbologia e la Stigmergy. Nel primo caso si parla di protocolli di comunicazione diversi da quelli standard che, invece di inviare pacchetti di informazioni tra i messaggi, prevede il passaggio di dati attraverso colori e suoni. Casi di questo tipo sono possibili da vedere in [11], ma in particolare in [12], articolo che raccoglie molti modi possibili di scambio di dati indiretto. Il secondo caso, invece, prevede come protocollo la modica dell'ambiente circostante, in maniera simile a quello delle formiche. E' possibile vedere alcuni esempi in [13] e [14]. In entrambi i casi, è facile capire come questi metodi male si avvicinano al problema proposto in 1.2, in quanto richiedono o altri sensori o un ambiente da modicare.

Per quanto riguarda l'utilizzo delle TdG nei sistemi Multi Agente, in letteratura è possibile trovare tra vie principali di utilizzo: esplorazione, formazione e inseguimento. Quest'ultima è una dei campi di studio storici per l'utilizzo della TdG, considerando l'inseguitore e l'inseguito come partecipanti ad un gioco nel quale il primo cerca di prevedere le azioni del secondo. E' possibile vedere alcuni esempi in [15] e [16]. In alcuni di questi casi è possibile vedere l'utilizzo di Giochi a Informazione Incompleta, ma prevedono giochi puramente competitivi, senza cooperazione.

I primi utilizzi della TdG nei casi di formazione e esplorazione, che quindi prevedono una collabo-razione tra gli agenti, sono più recenti. Nella maggior parte dei casi, inizialmente l'approccio ha visto l'inserimento nei problemi di funzioni di costo da minimizzare tramite metodi ricavabili dalla denizione di Equilibrio di Nash. Un interessante punto di partenza è presente in [17]. In esso, sono presentati molti possibili utilizzi della TdG, ma nessuno di questi viene approfondito nel particolare. Entrando più nello specico nel caso della formazione, sono presenti due campi di studio. In [18], il problema riguarda un gruppo di agenti mobili aventi caratteristiche diverse che operano in uno spazio comune con ostacoli e eettuano un inseguimento di un target in movimento. In questo articolo, la TdG non è usata per risolvere il problema dell'inseguimento, ma quello della coordinazione del movimento tra i vari agenti, ma sempre attraverso una funzione di costo comune a tutti i veicoli. Ognuno di loro conosce una parte del mondo che lo circonda tramite i sensori. Essi conoscono la posizione degli altri agenti e dove sono gli ostacoli nelle loro vicinanze. Tutte queste informazioni vengono passate al leader della formazione, che calcola, attraverso la funzione costo e il metodo ottenuto dall'equilibrio di Nash, le azioni per ognuno di loro. La funzione costo dipende da tre valori: la distanza dell'agente dagli ostacoli, dagli atri veicoli e dal centro de target. E' importante conoscere tutte le informazioni per poter decidere le azioni, in quanto ognuno è limitato da quelle degli altri. Se ci sono più soluzioni, il leader decide autonomamente in base ad un indice di performance. Una variazione è presente in [19], dove c'è sempre una funzione di costo, ma è legata solo al singolo agente ed è inuenzata solo dalla posizione all'interno della formazione dei vari veicoli. Al leader spetterà il compito di guidare tutti verso il target.

Nel campo dell'esplorazione la TdG viene spesso indicata come metodo per la scelta di una direzione in modo da massimizzare la velocità di ricerca di un oggetto. Normalmente viene divisa l'area di lavoro in regioni, con ogni veicolo che parte da un punto diverso e deve decidere quale zona esplorare. La scelta dipende dalle informazioni pre-caricate, dalla posizione e dalle comunicazioni con gli altri agenti. In [20] è presente una analisi completa e viene studiata la funzione costo che ogni veicolo usa, combinante la propria energia e il possibile premio che si otterrebbe con quella azione. Attraverso lo scambio di informazioni con gli altri agenti è poi possibile modicare quest'ultima parte, andando a direzionare la ricerca verso zone inesplorate. Problemi di questo tipo si possono leggere in [21] e [22], dove si arriva che alla conclusione che è un buon metodo, ma più gravoso dal punto di vista computazionale rispetto ad altri. Anche qui però è la TdG viene applicata in maniera particolare e non al pieno.

Più recentemente, lo sviluppo della TdG in questo ambito ha subito un interessante sviluppo. Si possono citare in questo senso [23], che presenta questi metodi come utili per la gestione di più agenti, ma senza entrare molto in profondità, e [24], il quale risulta un vero e proprio compendio per quanto riguarda una base dell'applicazione della logica degli Standard Games nei sistemi Multi Agente in molti casi, ampliando anche la parte di TdG che viene sfruttata all'interno dei vari algoritmi. Tra i nuovi lavori, si può citare [25], che osserva una situazione di competizioni tra agenti in presenza di asimmetria di informazioni. Un aspetto comune a tutti i lavori, anche i più recenti, è quella di non indicare i criteri di denizione dei guadagni dei giocatori o, se presenti, sono dicilmente esportabili in altri campi, il che ha reso dicoltosa la progettazione dei giochi nella presente tesi. Si aggiunge che comunque i testi proposti non presentano applicazioni simili alle problematiche che l'algoritmo proposto si pone di risolvere, di conseguenza non sarà possibile un confronto con essi.

Per gli esempi di applicazione dell'algoritmo proposti nella sezione 1.2.3 esistono molte proposte di utilizzo della TdG. Per il problema dei Multi-core si può citare [26] e [27], nei quali, non solo l'accesso ai canali di comunicazione viene deciso in base alla TdG, ma anche quello alla memoria e può essere regolata l'energia occorrente ad ogni processore. L'applicazione nell'ambito delle Smart Grid è invece trattata in [28] [29] e in [30], nei quali viene applicato un metodo simile in dierenti situazioni, ma si concentrano maggiormente sulla vendita e l'acquisto di energia all'interno di una rete rispetto al problema del Load Shedding. Anche in questi casi si può notare come spesso la Teoria dei Giochi venga sfruttata parzialmente, con il solo concetto di Equilibrio di Nash usato per risolvere funzioni di costo, perdendo parte delle potenzialità di questa branca matematica. Un articolo più vicino alle problematiche indicate nella Tesi è [31], dove la TdG è usata per controllare la potenza all'interno di un piccola rete.

Capitolo 2

Presentazione dell'algoritmo

Scopo di questo capitolo è quello di descrivere l'algoritmo proposto in questa tesi per la risoluzione dei conitti. Inizialmente Nella prima parte sono discussi e formalizzati gli obiettivi che devono essere raggiunti con esso e le sue caratteristiche principali. Successivamente è spiegato come verrà applicata la Teoria dei Giochi denita nel capitolo precedente. Nella terza parte è introdotto il concetto di Learning, cioè come il singolo agente può migliorare le proprie conoscenze sugli avversari. La quarta parte si occupa di denire i passi dell'algoritmo, dalle fasi iniziali no alla conclusione. Nella quinta sezione sono discussi i metodi di applicazione dell'algoritmo nei vari scenari. Nell'ultimo punto saranno discussi gli eventuali sviluppi del metodo proposto.

2.1 Obiettivi e caratteristiche principali dell'algoritmo

L'algoritmo nasce per gestire una situazione di conitto riguardante l'accesso a una risorsa condivisa tra 2 o più agenti in base alla priorità di accesso di ciascuno di essi, valore che ne denisce l'importanza rispetto agli altri. Si denisce Priorità di accesso come:

Denizione 4 (Priorità di accesso privata) Sia Qi lo stato di un agente facente parte di una rete

e si indichi con Qc

i la parte dello stato contenente valori coinvolti nel conitto. Si indica con Xpi

la parte di Qc

i nota al solo agente. Si denisce quindi la priorità di accesso privata la funzione

P ap: Xpi→ N

Denizione 5 (Priorità di accesso pubblica) Sia Qilo stato di un agente facente parte di una rete

e si indichi con Qc

i la parte dello stato contenente valori coinvolti nel conitto. Si indica con Xni

la parte di Qc

i nota a tutti gli agenti coinvolti. Si denisce quindi la priorità di accesso pubblica la

funzione

P an: Xni → N

Denizione 6 (Priorità di accesso) Denite le funzioni priorità di accesso pubblica P an_{e di priorità}

di accesso privata P ap _{si denisce quindi la priorità di accesso alla risorsa dell'agente}

P ai = P api + P a n i

Il valore legato alla priorità di accesso è strettamente legato all'applicazione dell'algoritmo. Alcuni esempi: il codice identicativo dell'agente, la distanza dall'arrivo, il ruolo all'interno di una coda.

L'applicazione dell'algoritmo all'interno di una squadra di agenti in conitto per l'acquisizione di una risorsa dovrà dare come risultato l'accesso a questa da parte dell'agente con valore di priorità maggiore, mentre gli avversari con priorità minore dovranno decidere autonomamente di uscire dal conitto e vedere la propria situazione subordinata rispetto a quella del vincitore.

L'algoritmo è di tipo distribuito, in quanto ogni agente dovrà decidere il proprio comportamento in maniera autonoma dagli altri, conoscendo però solo una parte del mondo che lo circonda. Come detto nella denizione precedente, una parte della priorità di accesso non è conoscenza comune e compito del metodo proposto sarà anche quello di sopperire a questa mancanza. L'algoritmo dovrà gestire sia gli obbiettivi personali, in quanto ogni agente cercherà di accedere alla risorsa, sia quelli comuni fra tutti gli elementi partecipanti alla rete, portando ad un consenso sull'agente vincitore del conitto. La funzione di priorità varierà in base al caso di applicazione. La dimensione della rete non è denita a priori e può variare all'interno dell'esecuzione stessa dell'algoritmo. Caratteristica fondamentale sarà l'assenza di comunicazione attiva tra gli agenti, di conseguenza l'acquisizione delle informazioni mancanti potrà avvenire solo tramite l'osservazione delle azioni altrui all'interno del conitto.

L'algoritmo è stato sviluppato nel tempo discreto. Questa scelta ha motivazioni legate alla attuazione pratica dell'algoritmo. Infatti, alcuni degli scenari di applicazione sono caratterizzate da dinamiche discrete, sia per quanto riguarda l'acquisizione delle informazioni tramite sensori, sia per le transizione degli stati degli agenti coinvolti.

2.2 Denizioni dalla Teoria dei Giochi

L'algoritmo prevede l'utilizzo della TdG per la scelta delle azioni da parte degli agenti, tramite la creazione di più Standard Games nel corso del tempo. Nel capitolo 1 sono state introdotte le denizioni di azione, strategia e di Tipo di Giocatore. Prima di denire i passi che l'algoritmo deve seguire, risulta importante capire come questi concetti verranno applicati in seguito. Tutta l'analisi dell'algoritmo verrà presentata dal punto di vista del singolo agente.

2.2.1 Caratteristiche del gioco creato

Ogni agente dovrà creare un gioco caratterizzato da:

• Un insieme nito di giocatori G = G1_{, G}2_{, ....G}K _{, dove con G}1_{si indica l'agente stesso, mentre}

con Gk _{si modelleranno gli avversari presenti nel conitto;}

• Ogni giocatore avversario potrà essere di due tipi Gk

T =Gkp, Gkv

_{, cioè un avversario con priorità} minore o uno con priorità maggiore rispetto all'agente stesso;

• Per ognuno dei Tipi di giocatore possibili verrà indicata una probabilità che valuta la possibilità di un avversario con quella priorità; tali probabilità verranno indicate come probabilità di tipo (in seguito PdT) e si richiede che P (Gk

p) + P (Gkv) = 1;

• Un set di strategie possibili, ognuna di forma S = {A1, A2, A3....AN}, di lunghezza N, con l'azione

al passo n Ana1n, a2n

, insieme comune a tutti i giocatori; ogni giocatore avrà una propria strategia Sk_{ S all'interno del gioco;}

• Per ognuna delle strategie avversarie possibili sarà indicata una probabilità di azione (in seguito PdA) di forma P (Sk_|Gk

T) = P (Ak1, Ak2, A3k....AkN|GkT); tali probabilità condizionate indicano la

tendenza di un Tipo di giocatore ad eettuare una certa scelta di azioni; considerando gli elementi facenti parte della strategia come eventi indipendenti tra loro, è possibile scrivere P (Sk_|Gk

T) =

P (Ak

1|GkT)P (Ak2|GkT)P (Ak3|GkT)....P (ANk|GkT), dove si richiede che P (a1 kn |GkT) + P (a2 kn |GkT) = 1;

• Un set di guadagni possibili U(S1_{, S}2_....SK_{)relativo a tutti i giocatori in quella combinazione di}

strategie, calcolate in base alle priorità (sia delle parti note, sia di quelle non note) degli agenti coinvolti; si indica con UT(S1, S2....SK)il guadagno dei giocatori data quella combinazione di

stra-tegia in quel Tipo di gioco; la forma dei guadagni è strettamente legata allo scenario di applicazione dell'algoritmo.

L'insieme delle PdT e PdA verrà in seguito indicato anche con il termine credenze usato in letteratura, come visibile in [7]. I giochi creati rientreranno nel gruppo degli Extensive Games With Incomplete Information, visto l'utilizzo di strategie e di probabilità sui tipi di giocatori presenti. Altre caratteristiche del conitto che dovranno essere inserite all'interno del gioco prevedono:

• L'agente che crea il gioco non è a conoscenza del Tipo di avversari che ha davanti, sia nel momento in cui sceglie una strategia, sia nel momento in cui la applica;

• Tutti i giocatori eettuano le proprie azioni in contemporanea, di conseguenza non c'è alcuna inuenza o sudditanza rispetto le scelte altrui.

Queste caratteristiche servono per evitare che l'agente abbia bisogno di attendere che gli avversari compiano le loro scelte per fare le proprie. Ciò, infatti, creerebbe una asimmetria tra i giocatori e la necessità di stabilire un ordine in base al quale eettuare le scelte. Traducendo queste caratteristiche nei giochi creati, si ottengono per ogni avversario guadagni legati a strategie pure, non frutto di combinazioni tra diversi set di azioni, come già indicato nel paragrafo 1.3.3. Nella sezione 2.2.3 sarà indicato perché questo aspetto è importante per l'algoritmo.

2.2.2 Combinazione dei giochi

In base a quanto visto nella sezione precedente, ogni agente si troverà davanti a 2(K−1) _{giochi diversi,}

tanti quanti sono le combinazioni possibili di avversari, ciascuno a K dimensioni, tante quante sono i giocatori. La Probabilità di essere in un gioco specico tra i tanti possibili sarà

YK

2 k

P (Gk_T)

Ogni gioco sarà frutto di situazioni diverse tra loro, quindi conterrà valori diversi, ma strutture simili. In ossequio a quanto visto in 1.3, per comodità di studio tutti questi giochi verranno tradotti prima in Standard Games di uguale dimensione, per poi costruite un unico Standard Game da analizzare per poter scegliere la strategia più conveniente per l'agente. La combinazione dei giochi presenta due aspetti da arontare: la possibile presenza di giochi a dimensione diversa e il calcolo dei guadagni da inserire nel gioco nale.

Per quanto riguarda il primo di questi due punti, a seconda dell'applicazione dell'algoritmo, è possibile che in qualcuno dei giochi si abbiano strategie per i giocatori di lunghezza J<N. Di conseguenza, la composizione con gli altri giochi non è possibile direttamente. Si impone, quindi, di aggiungere al set di strategie dei giocatori S = {A1, A2, A3....AJ} delle azioni ttizie Sf = {AJ +1, AJ +2, ....AN}, tali

per cui si abbia S ∪ Sf = {A1, A2, A3....AJ...AN}, che non verranno però fatte realmente dagli agenti.

Questo consente di avere giochi a uguale dimensione. In questi casi, visto che le azioni aggiunte non sono previste nel modello iniziale e non saranno eettuate, si impone che U(S1_{∪ S}1

f, S2∪ Sf2....SK∪ SfK) =

U (S1_{, S}2_....SK_{). Quindi tale aumento di strategie non varia i guadagni ottenibili in quel gioco.}

Il calcolo dei guadagni nali si basa su quanto già visto in 1.3.2 e in 1.3.3, dove si è mostrato il passaggio da un Extensive Game ad uno Standard Game e quello da più Standard dovuti a Tipi diversi di giocatori a un unico comune. Essendo in presenza di un Extensive Game with Incomplete Information, secondo quanto visibile in [8], il procedimento da seguire è:

• Preso il guadagno del singolo gioco UT(S1, S2....SK), questo viene pesato per le probabilità di

azione corrispondente a quella combinazione di strategie. Di conseguenza ˜ UT(S1, S2....SK) = UT(S1, S2....SK) YK 2 k P (Sk|Gk T)

• Nel caso in cui ci si trovi in presenza di giochi con azioni ttizie al loro interno, si avrà, in quanto quelle azioni non avvengono realmente

˜ UT(S1∪ Sf1, S 2_{∪ S}2 f....S K_{∪ S}K f ) = UT(S1∪ Sf1, S 2_{∪ S}2 f....S K_{∪ S}K f ) YK 2 k P (Sk|Gk T)

• Presi i singoli guadagni pesati ottenibili in un dato tipo di gioco, si moltiplicano per le probabilità di tipo corrispondenti ¯ UT(S1, S2....SK) = ˜UT(S1, S2....SK) YK 2 k P (Gk_T)

• Presi i guadagni così calcolati, si sommano quelli a uguale strategia provenienti dai tutti i Tipi di Gioco possibili U (S1_{, S}2_....SK_{) =}P2(K−1) 1 T ¯ UT(S1, S2....SK) = =P2(K−1) 1 T (UT(S1, S2....SK) YK 2 k P (Sk_|Gk T) YK 2 k P (Gk T)) (2.1)

In questo modo si ottiene un unico Standard Game in forma matriciale, contenente tutte le informazioni di tutti i possibili giochi. Attraverso lo studio di questo Gioco Finale, sarà possibile per l'agente che lo crea analizzare la realtà attorno a lui e scegliere la migliore strategia da applicare. La creazione di questo Gioco dovrà essere ripetuta tutte le volte che all'agente servirà decidere il set di azioni da compiere.

.

2.2.3 Equilibrio per la scelta della strategia

La scelta della strategia è il fulcro dell'intero algoritmo. Per poter eettuare questa decisione a partire dalle informazioni note e le ipotesi dei singoli agenti, si partirà dal contenitore creato in base a questi dati, cioè il Gioco Finale creato nel paragrafo precedente. Si impone che l'equilibrio del gioco corrisponda alla combinazione migliore possibile tra le strategie dei giocatori, in quanto equilibrio tra tutti gli interessi

dei giocatori. Tali strategie saranno poi quelle applicate nella realtà. Per capire quale tipo di equilibrio risulta più attinente alla problematica, sono stati analizzati i tre metodi già presentati in per la sua ricerca in 1.3.4 :

• Metodo Minmax: essendo nato per giochi a somma zero, tipicamente giochi di tipo non cooperativo, in cui il guadagno di un giocatore corrisponde alla perdita dell'avversario, non risulta applicabile nel nostro algoritmo, percjhè prevede anche aspetti cooperativi;

• Ottimo Paretiano: il metodo prevede il regime di concorrenza pura e l'assenza di asimmetrie informative, rendendolo non adatto al caso proposto;

• Equilibrio di Nash: con l'elevato numero di accezioni e modiche presenti in letteratura risulta applicabile in casi di problemi con giocatori cooperanti e allo stesso tempo in competizione tra loro;

 Equilibri Bayesiani (BE) e Perfect Bayesian Equilibrium (PBE): come già indicato, sono le accezioni al Nash Equilibrium da applicare nei casi di informazioni incomplete, rispettivamen-te se si inrispettivamen-terpreta il conitto come una serie di Standard Games o come un unico Exrispettivamen-tensive Game.

Si aggiunge che il NE è sempre presente all'interno di un gioco, nella forma pura o in quella mista, cosa che non è garantita per altri tipi di equilibrio. La teoria pura prevederebbe l'utilizzo dei PBE, ma la trasformazione dei giochi nella forma matriciale, Standard, ci consente l'utilizzo del BE, presente maggiormente in letteratura e, quindi, strumento più rodato nell'ambiente.

E' ora possibile indicare perché sono importanti le imposizioni fatte in precedenza per quanto riguarda la composizione delle matrici. Avendo giochi composti da sole strategie pure, per ogni giocatore sarà ben denito il set di azioni che questo dovrà fare per arrivare a quell'equilibrio. Ciò consentirà all'agente di denire quali sono le strategie che gli avversari dovrebbero fare per arrivare alla condizione migliore supposta in base alle proprie credenze. Tali combinazioni di azioni saranno in seguito indicate come le strategie ipotizzate degli avversari. Il confronto di queste con le azioni realmente fatte sarà necessario per anare proprio le ipotesi dell'agente e ciò sarebbe impossibile avendo giochi con strategie miste, che prevedono giocatori che possono attuare una strategia o l'altra.

2.3 Metodo di learning

Individuato un equilibrio, cioè la situazione migliore per il gruppo in base alle proprie conoscenze e alle proprie credenze, un agente identica quali strategie dovranno eettuare tutti i giocatori per arrivare a quei guadagni. Il singolo agente eettua quindi la serie di azioni di controllo trovate e confronta quelle relative agli avversari con le strategie realmente applicate da questi. Se le due sequenze di azioni, l'ipotizzata e la realizzata, non collimano, l'agente deve concludere che gli avversari stanno puntando ad un diverso equilibrio e che deve aggiornare le sue credenze per adattarle alla realtà, consentendo una successiva pianicazione migliore. Fin da subito, l'indagine si è concentrata sull'anare i valori delle PdT sugli altri agenti, in quanto tale valore inuenza i giochi che servono per la scelta delle strategie, e consente di individuare quale tra i tipi di gioco creati è più vicino alla realtà. Il learning dovrà consentire una modica dei valori di probabilità in caso di confronto negativo con la realtà. Il metodo più usato in letteratura ([32] e [33]) segue il Teorema di Bayes (TB) . Come è possibile vedere in ([33]), la TB si