Progetto e realizzazione di un sistema per la negoziazione multiattributo con informazione incompleta

Si puo´ affermare che negoziare e´ il miglior modo per risolvere situazioni di
conflitto, anche di non fondamentale importanza.
Se si pensa alla negoziazione come ad una metodologia per il raggiungimento
di un obbiettivo comune altrimenti irraggiungibile, si coglie il suo vero signi-
ficato.
Etimologicamente infatti, il termine negoziazione deriva dal latino negotium,
parola composta da nec e otium e indica la contrattazione per il raggiungi-
mento di un accordo.
In questo senso, la negoziazione si configura anche come una competenza,
in quanto permette di raggiungere obbiettivi prefissati cooperando. Edmund
Burke, statista e oratore del XVIII secolo, osservo´ che ogni vantaggio ed ogni
beneficio dell’uomo, ogni virtu´ ed ogni atto prudente, sono fondati sul com-
promesso e sul baratto.
Il campo di azione della negoziazione e´ davvero sterminato: oltre al mondo
degli affari, a cui piu´ facilmente l’associamo, essa coinvolge anche le relazioni
personali e familiari.
Considerando questi aspetti, non sorprende il fatto che la negoziazione sia
stata e sia tutt’ora oggetto di studio dell’ Intelligenza Artificiale (IA).
In una negoziazione infatti, risulta fondamentale conoscere l’ambito su cui si
discute per poi fare delle proposte e prendere delle decisioni.
L’Intelligenza Artificiale, e piu´ nello specifico l’ Ingegneria della Conoscenza
(IC), si occupa di studiare la realizzazione ed il mantenimento di sistemi ba-
sati su conoscenze, in cui e´ possibile utilizzare le informazioni contenute in
una knowledge base mediante procedure automatiche di ragionamento.
L’obbiettivo e´ nello stesso tempo ambizioso ed affascinante: permettere a
macchine di negoziare mediante il ragionamento, in maniera similare ad un
essere umano.
II
Ovviamente e´ necessario definire in maniera assolutamente rigorosa la sin-
tassi, mediante cui e´ associata alla conoscenza una struttura, e la semantica,
che la renda non ambigua.
A tale scopo vengono utilizzate logiche descrittive e linguaggi standardizzati
basati su queste logiche.
Obbiettivo di questo lavoro di tesi e´ realizzare un prototipo con cui valutare
empiricamente un meccanismo di negoziazione bilaterale multi-attributo.
Nel primo capitolo si effettua una panoramica storica sul problema della
negoziazione e su alcune strategie proposte in letteratura, per poi successi-
vamente nel secondo capitolo introdurre le logiche descrittive.
Nel terzo capitolo si mostra come e´ possibile sfruttare le logiche descrittive
per implementare meccanismi di negoziazione, nel quarto capitolo invece si il-
lustra la progettazione del prototipo. Discussioni e sviluppi futuri concludono
questo lavoro di tesi.
III
Capitolo 1
Teoria dei giochi e tecniche di
negoziazione
La rapida crescita e diffusione di sistemi di comunicazione elettronici, co-
me la rete Internet, degli ultimi anni, ha determinato un crescente interesse
della ricerca sullo studio di transazioni elettroniche automatiche.
In questo capitolo si effettua una panoramica della letteratura corrente nei
campi della Teoria dei giochi 1 e dell’ applicazione dei modelli di negoziazione
elaborati per essa dall’ Intelligenza Artificiale.
Mentre la ricerca di equilibri, infatti, e´ compito della teoria dei giochi, l’ au-
tomatizzazione della procedura di contrattazione e´ compito dell’ intelligenza
artificiale
Il ruolo della contrattazione viene formalizzato mediante strumenti propri
della teoria dei giochi, quali il protocollo di negoziazione e la strategia di ne-
goziazione.
1La teoria dei giochi e´ la scienza matematica che analizza situazioni di conflitto e ne
ricerca soluzioni competitive e cooperative tramite modelli, ovvero tramite uno studio delle
decisioni individuali in situazioni in cui vi sono interazioni tra i diversi soggetti, tali per cui
le decisioni di un soggetto possono influire sui risultati conseguibili da parte di un rivale,
secondo un meccanismo di retroazione.
1
1.1 La negoziazione nella storia economica
Il protocollo definisce fondamentalmente le regole del gioco, esplicitando qua-
li azioni possono essere effettuate e quando, mentre la strategia definisce i
possibili comportamenti che gli agenti possono intraprendere.
1.1 La negoziazione nella storia economica
Il problema della negoziazione e´ stato trattato per decenni da numerosi
economisti, in particolare nella Teoria dei Giochi, ed e´ ancora oggi oggetto
di studio. Rubenstein [18] , nel 1982, definisce la negoziazione in maniera
semplice e precisa :
Due individui dispongono di diversi potenziali accordi contrattuali. Entram-
bi hanno interesse nel raggiungimento di un accordo,ma i loro interessi non
sono perfettamente identici. Quale sara´ l’accordo, assumendo che entrambi
si comportino in maniera razionale?
Per lungo tempo, il problema della negoziazione e´ stato considerato indeter-
minato.
Von Neumann e Morgenstern [21] hanno concordato che al massimo e´ pos-
sibile affermare che un possibile accordo si concretizzera´ nel cosiddetto Bar-
gaining Set.
Un ”Bargaining Set” consiste generalmente in un numero infinito di accordi
differenti possibili, pertanto non permette di definire con certezza una solu-
zione unica ad un problema di negoziazione, ma determina soltanto un set
di soluzioni potenziali .
Se sono soddisfatte ulteriori condizioni, quali gli assiomi proposti da Nash
[9] , allora e´ possibile ottenere un’unica soluzione.
Dipendentemente dal contesto applicativo, tali assiomi possono o meno risul-
2
1.1 La negoziazione nella storia economica
tare ragionevoli, pertanto Nash ha suggerito di considerare un gioco2 strate-
gico, oltre a questi assiomi, per superare la loro non validita´ universale.
Rubinstein [19] ad esempio ha provato che il protocollo delle ”offerte alter-
nate” permette di individuare una soluzione unica, mentre Binmore [2] ha
inoltre dimostrato che la soluzione del modello di contrattazione di Rubin-
stein coincide con la soluzione di Nash sotto particolari ipotesi.
Molto spesso, nell’ambito della teoria dei giochi, vengono effettuate delle as-
sunzioni esemplicative per permettere di rendere meno onerosa la procedura
matematica di inviduazione della soluzione del problema di negoziazione.
Per esempio, normalmente si assume che :
1. La conoscenza delle circostanze in cui si sviluppa il gioco sia completa
2. I giocatori3 si comportino in maniera completamente razionale
La prima assunzione implica che le regole del gioco e le preferenze ed i com-
portamenti degli agenti siano conoscenza comune.4 Normalmente l’infor-
mazione incompleta viene modellata mediante la definizione di un limitato
numero di ”tipologie” di giocatori, ognuno determinato unicamente da un
set di preferenze e comportamenti.
Ogni giocatore non e´ certo dell’ esatto tipo del proprio opponente ma conside-
ra certa la probabilita´ che un agente appartenga ad un certo tipo, e pertanto,
uno scenario con informazione incompleta puo´ essere considerato ad infor-
mazione imperfetta 5 .
La seconda assunzione invece e´ relativa al bisogno di conoscenza comune re-
lativamente al modo di ragionare di ogni giocatore: normalmente, si assume
2
In questo contesto, si fa riferimento ai termini gioco e protocollo come sinonimi.
3
In questo contesto si fa riferimento ai termini agente e giocatore come sinonimi
4Conoscenza comune significa che ogni giocatore conosce cio´ che conosce ogni altro
giocatore.
5Un gioco e´ detto a conoscenza imperfetta se non ci sono mosse simultanee ed ogni
decisione e´ presa conoscendo le decisioni precedenti.
3
1.2 Negoziazione e Teoria dei Giochi
che gli agenti cerchino di massimizzare la propria utilita´.
Nell’ambito dell’ Intelligenza artificiale, comunque, assunzioni quali la cono-
scenza completa e la completa razionalita´ a volte vengono rilassate, gli agenti
ed il loro comportamento sono modellati in maniera diretta, pertanto il pro-
blema della negoziazione e della ricerca di una soluzione sono modellati in
maniera diversa rispetto alla Teoria dei Giochi.
1.2 Negoziazione e Teoria dei Giochi
La Teoria dei giochi si occupa dello studio di modelli matematici di coo-
perazione e conflitto tra individui intelligenti e razionali.
La Teoria di giochi, prevede una classificazione fondamentale in :
• Teoria collaborativa
• Teoria competitiva
La teoria collaborativa si occupa fondamentalmente di cercare una solu-
zione dato un set di soluzioni potenziali, prescindendo dalle regole specifiche
del gioco e dalla sua tipologia.
Spesso, nella vita reale, imprese possono trarre profitto cooperando, per
esempio dividendosi opportunamente quote di un largo mercato o riducendo
la competizione diretta, mediante un’ attivita´ di cooperazione con altre im-
prese.
In questi giochi, viene creato un surplus di utilita´ nel momento in cui due o
piu´ agenti collaborano e formano una coalizione.
La teoria dei giochi collaborativa puo´ determinare come debba essere sud-
diviso tale surplus, data una coalizione di agenti ed un set di assunzioni
(assiomi).
4
1.2 Negoziazione e Teoria dei Giochi
La teoria dei giochi competitiva invece si occupa di studiare giochi nello spe-
cifico, con un particolare set di regole e strategie ben definito, conosciute
precedentemente dagli agenti.
La teoria dei giochi competitiva usa la nozione di strategia di equilibrio per
determinare i risultati razionali di un gioco.
Nella letteratura sono stati proposti numerosi concetti di equilibrio, tra cui
largamente usati sono le ”strategie dominanti”, gli ”equilibri di Nash” e gli
’equilibri perfetti nei sottogiochi”.
Una strategia dominante e´ ottimale in tutte le circostanze, per cui non ha
importanza quale sia la strategia degli altri agenti: risulta essere pertanto
molto forte, in questo caso, la nozione di strategia di equilibrio.
Un po’ meno marcata, ma comunque forte, e´ la nozione di ”Equilibrio di
Nash”6 [10].
Le strategie scelte da tutti gli agenti si dicono in Equilibrio di Nash se nessun
agente puo´ trarre vantaggio cambiando la propria strategia, se le strategie
degli altri giocatori restano invariate.
Nash ha inoltre dimostrato che ogni gioco con un numero finito di strategie
prevede almeno un punto di equilibrio.
Un raffinamento importante del concetto di Equilibrio di Nash e´ la definizio-
ne di Equilibrio perfetto nei sottogiochi, introdotto da Selten[20]
La nozione di sottogioco perfetto modella l’ idea di una situazione strate-
gica ben definita, ed applica una nozione di comportamento razionale (in
particolare la nozione di equilibrio di Nash) ogni volta che si fronteggia una
situazione strategica ben definita.
6
In teoria dei giochi si definisce equilibrio di Nash un profilo di strategie (una per ciascun
giocatore) rispetto al quale nessun giocatore ha interesse ad essere l’unico a cambiare.
5
1.2 Negoziazione e Teoria dei Giochi
1.2.1 Teoria cooperativa
La teoria cooperativa considera, fondamentalmente, i possibili risultati di
un gioco, senza entrare nel merito dei dettagli del gioco stesso. Normalmente
i risultati vengono quantificati in termini di utilita´.
Nel caso di giochi a due giocatori, i risultati sono rappresentati da coppie di
utilita´. La teoria dei giochi cooperativa studia in particolare quale risultato
eventualmente prevale, dato un set di possibili coppie di utilita´.
Ci si riferisce ad un set di possibili risultati anche con l’appellativo di bargai-
ning problem.
Una funzione che permette di ottenere da un bargaining problem un’unica
soluzione e´ chiamata concetto soluzione.
Normalmente, un concetto soluzione e´ valido solo per un certo sottoinsieme
di tutti i possibili bargaining problems, ad esempio, la soluzione di Nash [9]
si applica unicamente a spazi di negoziazione convessi e compatti.
Solo se questi requisiti sono soddisfatti, il problema di negoziazione puo´ essere
propriamente denominato problema di negoziazione di Nash. Una soluzione
alternativa al problema di negoziazione e´ stata successivamente proposta da
Kalai e Smorodinsky [6].
Nella teoria cooperativa esistono, quindi, soluzioni differenti ad un bargaining
problem, la cui scelta dipende fondamentalmente dal contesto in cui avviene
la negoziazione, ad esempio dalle leggi presenti in uno stato nel caso di una
particolare attivita´ economica.
Da questa considerazione si deriva che il contesto determina la scelta di quali
assiomi sembrino ragionevoli, e pertanto influenza direttamente il problema
di negoziazione ed il tentativo di trovarne la soluzione.
6
1.2 Negoziazione e Teoria dei Giochi
La soluzione di Nash Nash ha proposto quattro proprieta´, denominati
Assiomi di Nash, che devono essere soddisfatti da agenti razionali: [9]. I
quattro assiomi di Nash sono i seguenti:
1. Il risultato finale non deve dipendere da come gli agenti abbiano cali-
brato la propria scala di utilita´.
Questo significa che sebbene sia stata utilizzata una particolare funzio-
ne di utilita´ per specificare le preferenze di un agente, il risultato non
dovrebbe cambiare modificando la funzione di utilita´.
Nello specifico, ogni trasformazione della funzione di utilita´ che model-
la le preferenze espresse dalla funzione di utilita´ originaria, dovrebbe
fornire lo stesso risultato.
2. Il risultato del gioco (payoff) dovrebbe sempre essere efficiente secondo
Pareto 7, sotto l’ ipotesi che gli agenti siano razionali8
3. Il risultato deve essere indipendente da alternative irrilevanti.
Se gli agenti sono d’accordo sulla coppia di utilita´ s, e se t e´ un accordo
fattibile,non devono mai accordarsi su t se s e´ un accordo possibile.
4. Il gioco deve essere simmetrico, in quanto non deve dipendere dalla
posizione assunta dall’agente nel gioco stesso.
La soluzione che soddisfa queste quattro proprieta´ e´ caratterizzata dalla
coppia di payoff s = (x1, x2) , che massimizza il cosiddetto prodotto di Nash
(x1 − d1) (x2 − d2), dove d1 e d2 sono i risultati relativi al primo ed al secondo
agente in caso di disaccordo, e questa e´ l’unica soluzione che soddisfa i quattro
assiomi.
7Un accordo e´ efficiente secondo Pareto se nessun agente puo´ migliorare il suo payoff
senza che l’altro agente subisca una perdita.
8Un accordo e´ individualmente razionale se assegna ad ogni agente un’utilita´ che e´
almeno uguale a quella che un agente puo´ garantire a se´ stesso in assenza di accordo.
7
1.2 Negoziazione e Teoria dei Giochi
Figura 1.1: Costruzione della soluzione di Nash ad un bargaining problem.
La linea continua identifica la frontiera di efficienza di Pareto. Il bargaining
problem e´ definito dal set di possibili coppie di utilita´, rappresentate dall’area
grigia, e dal punto di disaccordo d , che specifica i payoff degli agenti in caso
di disaccordo. Per trovare la soluzione di Nash ( simmetrica ), e´ necessario
tracciare una linea tangente alla frontiera dell’efficienza di Pareto, in maniera
tale che la soluzione di Nash divida in due segmenti di uguale lunghezza la
distanza tra d ed r.
8
1.2 Negoziazione e Teoria dei Giochi
Nella figura 1.1 e´ mostrato come costruire la soluzione di Nash per un
dato bargaining problem.
Dato un bargaining problem di Nash, in cui il set di possibili accordi razionali
e´ non vuoto, la soluzione di Nash conduce ad un risultato unico.
A causa del quarto assioma, entrambi i giocatori sono descritti simmetrica-
mente.
Una soluzione piu´ generale prevede l’ attribuzione di un cosiddetto ”bargai-
ning power” ad ogni agente, α e β.
In tal caso, il problema non e´ piu´ simmetrico, e la sua soluzione dipende dai
valori di α e β.
Tali valori dipendono dal particolare tipo di gioco a cui si fa riferimento: ad
esempio, α e β potrebbero rappresentare il rispettivo potere contrattuale di
due imprese in un determinato mercato.
La soluzione di Nash corrispondente ad un bargaining problem generalizzato
in cui α e β sono i bargaining power associati ai due agenti, e´ data dalla
coppia s che massimizza il prodotto (x1 − d1)α (x2 − d2)β.
La soluzione di Kalai-Smorodinsky Kalai e Smorodinsky hanno pro-
posto un’ alternativa al terzo assioma di Nash ( indipendenza di alternative
irrilevanti ), oggetto di forte controversia, ed hanno proposto un assioma al-
ternativo : l’ Assioma di monotonicita´ [6].
La soluzione di Kalai e Smorodinsky rappresenta pertanto un raffinamento
della soluzione di Nash.
Dato un set S di punti individualmente razionali ed efficienti secondo Pa-
reto, siano mi (S) = max {si|sS} i punti di massima utilita´ possibile per l ’
i-esimo giocatore con i = 1, 2.
9