Università degli studi di L’Aquila
Facoltà di Scienze Matematiche, Fisiche e Naturali
Corso di Laurea in Informatica
Tesi di Laurea
Equilibri di Nash
in reti ottiche
non cooperative
Laureando
Relatori
Luca Moscardelli
Prof. Michele Flammini
Dott. Vittorio Bilò
Anno Accademico 2003-2004
A Sara
che è stata sempre al mio fianco
durante gli studi universitari
donandomi amore, forza,
sostegno e speranza.
Indice
Introduzione
VI
1 Teoria dei giochi
1.1
1.2
1
Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.1.1
Classificazione dei giochi . . . . . . . . . . . . . . . . .
2
1.1.2
Caratterizzazione dei giochi . . . . . . . . . . . . . . .
2
1.1.3
Una possibile soluzione di gioco:
equilibrio in strategie dominanti . . . . . . . . . . . . .
4
Equilibrio di Nash . . . . . . . . . . . . . . . . . . . . . . . . .
6
1.2.1
Esistenza . . . . . . . . . . . . . . . . . . . . . . . . .
8
1.2.2
Problematiche algoritmiche . . . . . . . . . . . . . . .
9
1.3
Load Balancing . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.4
Selfish Routing . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2 Reti ottiche
18
2.1
Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2
Modello . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.1
Reti ottiche non dirette . . . . . . . . . . . . . . . . . . 20
2.2.2
Reti ottiche dirette . . . . . . . . . . . . . . . . . . . . 22
2.2.3
Un parametro correlato ed alcuni risultati . . . . . . . 23
2.2.4
Istanze speciali . . . . . . . . . . . . . . . . . . . . . . 24
2.3
Routing statico . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.4
Routing on-line . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.4.1
Un algoritmo on-line per anelli
. . . . . . . . . . . . . 27
INDICE
IV
2.4.2
2.5
Un algoritmo on-line per alberi . . . . . . . . . . . . . 32
Routing dinamico . . . . . . . . . . . . . . . . . . . . . . . . . 33
3 Prezzo dell’anarchia in reti ottiche
36
3.1
Modello . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2
Una classe di funzioni di pagamento convergenti . . . . . . . . 42
3.3
Una classe di funzioni di pagamento inducenti
un gioco con alto prezzo dell’anarchia . . . . . . . . . . . . . . 43
3.4
Informazione completa . . . . . . . . . . . . . . . . . . . . . . 46
3.5
Informazione minimale . . . . . . . . . . . . . . . . . . . . . . 48
3.6
Informazione intermedia . . . . . . . . . . . . . . . . . . . . . 51
3.6.1
Funzioni di pagamento non convergenti . . . . . . . . . 52
4 Riduzione del prezzo dell’anarchia
in reti ottiche con topologie particolari
4.1
4.2
4.3
68
Anelli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.1.1
Il problema del routing puro . . . . . . . . . . . . . . . 69
4.1.2
Informazione minimale . . . . . . . . . . . . . . . . . . 70
4.1.3
Informazione intermedia . . . . . . . . . . . . . . . . . 73
Catene . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.2.1
Informazione minimale . . . . . . . . . . . . . . . . . . 78
4.2.2
Informazione intermedia . . . . . . . . . . . . . . . . . 79
Alberi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
5 Reti ottiche dirette e conclusioni
81
5.1
Risultati ottenuti . . . . . . . . . . . . . . . . . . . . . . . . . 81
5.2
Estensione dei risultati a reti ottiche dirette . . . . . . . . . . 83
5.3
5.2.1
Reti con topologia generica
. . . . . . . . . . . . . . . 84
5.2.2
Reti con topologie particolari . . . . . . . . . . . . . . 84
Problemi aperti . . . . . . . . . . . . . . . . . . . . . . . . . . 85
Ringraziamenti
Il primo ringraziamento va ai relatori che mi hanno guidato ed aiutato con
competenza e professionalità nella stesura della tesi, ed in modo particolare
al Prof. Michele Flammini per la fiducia che mi ha accordato e la particolare
disponibilità con cui mi ha seguito.
Un sentito ringraziamento va a tutti i professori che ho incontrato nel
corso degli studi universitari, tra i quali mi è gradito menzionare il Prof.
Flavio Corradini ed il Prof. Riccardo Silvestri, per aver contribuito con i
corsi da loro tenuti alla mia formazione universitaria e professionale.
Un grazie sincero ad Alessandro, Angelo, Lucio e Riccardo, colleghi di
corso ma soprattutto amici, con i quali ho condiviso molte soddisfazioni,
ma anche interminabili notti di lavoro; in loro ho sempre trovato lealtà e
generosità, ed insieme abbiamo trascorso momenti indimenticabili.
Infine, non posso dimenticare i miei genitori che hanno sempre saputo
fornirmi i mezzi e gli stimoli giusti per affrontare adeguatamente gli studi nel
mio itinerario scolastico ed universitario.
Introduzione
Le reti ottiche sono candidate a rappresentare il futuro delle reti di comunicazione, in quanto offrono una larghezza di banda nell’ordine delle decine
di terahertz, ossia mille volte superiore rispetto a quelle tradizionali. Tale
larghezza di banda può essere impiegata tramite la tecnica del multiplexing in
modo da permettere la comunicazione di più coppie di utenti sullo stesso link
fisico. L’informazione viaggia sottoforma di luce e con la stessa lunghezza
d’onda da un capo all’altro della comunicazione, senza mai essere trasformata in segnale elettrico; ciò permette una velocità di propagazione del segnale
e di comunicazione non paragonabile a quella delle tradizionali reti elettriche.
In questa tesi viene investigato il problema del routing su reti ottiche
in ambito non cooperativo, in cui le modalità di comunicazione tra le varie
coppie di utenti (agenti ) non vengono stabilite da un algoritmo centralizzato,
ma sono il risultato della libera evoluzione delle coppie stesse che agiscono
egoisticamente nel tentativo di minimizzare il proprio costo di comunicazione.
Utilizzando quindi nozioni e concetti classici della teoria dei giochi, tali
coppie di utenti sono impegnate in un gioco, alla ricerca della strategia che
minimizzi il proprio pagamento; il gioco ha termine laddove gli agenti raggiungono una situazione di equilibrio. L’equilibrio cui si fa riferimento nella
tesi è l’equilibrio di Nash, ovvero una situazione in cui, ferme restando le
scelte strategiche altrui, nessun agente trae vantaggio dal mutare la propria
strategia.
VII
Obiettivo
L’obiettivo della tesi è quello di incentivare gli agenti a comunicare in
modo tale da utilizzare un basso numero di lunghezze d’onda, essendo questo
un parametro critico per le reti ottiche attuali (tipicamente qualche centinaio
è il numero massimo di lunghezze d’onda utilizzabili).
A tale scopo, abbiamo elaborato delle funzioni di pagamento che inducono
gli agenti egoistici a raggiungere situazioni di equilibrio che utilizzino appunto
un basso numero di lunghezze d’onda.
Il problema è stato affrontato sia nel caso di reti con topologie generiche, sia in quello di reti con topologie particolari, ma comunque molto diffuse nelle reti ottiche. I risultati ottenuti sono dettagliatamente descritti nel
Paragrafo 5.1.
Struttura
La tesi è strutturata nel modo seguente.
Nel Capitolo 1 viene presentata una breve panoramica relativa alla teoria
dei giochi, con particolare attenzione alle problematiche connesse alla nozione
di equilibrio di Nash e alle principali tematiche algoritmiche coinvolte.
Nel Capitolo 2 viene descritto in dettaglio il modello delle reti ottiche e
vengono illustrati i relativi risultati presenti in letteratura. Il routing su reti
ottiche è stato infatti largamente studiato dal punto di vista centralizzato, sia
in uno scenario statico, in cui le coppie che richiedono la comunicazione sono
tutte inizialmente note all’algoritmo, sia in uno scenario on-line e dinamico
in cui le richieste arrivano nel tempo e devono essere servite senza alcuna
conoscenza di quelle future.
Nei capitoli successivi sono presenti i contributi originali del lavoro di
tesi. In particolare viene affrontato il problema del routing in ambito non
cooperativo e vengono presentate diverse funzioni di pagamento sia per reti
con topologia generica (Capitolo 3) che con topologia particolare (Capitolo
4). Per ogni funzione di pagamento è stato analizzato il gioco indotto corri-
VIII
spondente dal punto di vista della convergenza, dell’esistenza dell’equilibrio
e del prezzo dell’anarchia, ossia della spesa in termini di lunghezze d’onda impiegate da una soluzione in equilibrio, rispetto alla soluzione migliore
possibile.
Infine, nel Capitolo 5 è presente l’estensione dei risultati ottenuti per il
modello delle reti ottiche non dirette considerato nei capitoli 3 e 4 a quello
delle reti dirette. Inoltre, vengono presentate le conclusioni del lavoro di tesi
ed enunciati alcuni problemi rimasti aperti.
Pubblicazioni
I contributi originali di questa tesi hanno dato luogo a due articoli ([6],[5]);
uno di questi, contenente alcuni risultati preliminari, è stato già accettato alla
conferenza internazionale SIROCCO 2004 ([6]), che si è svolta dal 21 al 23
Giugno a Smolenice, in Slovacchia.
Capitolo 1
Teoria dei giochi
In questo capitolo vengono introdotti i principali concetti, relativi alla
teoria dei giochi, utilizzati nella tesi, che verranno meglio formalizzati ed
istanziati al routing in reti ottiche nel Capitolo 3.
Inoltre, alla fine del capitolo sono presentati un paio di problemi tipici
della letteratura algoritmica, che negli ultimi anni sono stati affrontati in
ambito non cooperativo grazie all’utilizzo di nozioni e concetti derivanti dalla
teoria dei giochi.
1.1
Introduzione
La teoria dei giochi ([38]) studia le situazioni in cui più agenti (giocatori ),
ognuno dei quali prende in modo strategico decisioni che potenzialmente si
ripercuotono sia su se stesso che sugli altri, interagiscono. In altri termini
vengono trattati i processi decisionali in cui l’utilità (o profitto) di ciascun
giocatore dipende non solo dalle proprie azioni, ma anche da quelle degli altri.
Iniziamo ora ad introdurre alcune nozioni della teoria dei giochi.
Consideriamo inizialmente la classificazione dei diversi tipi di gioco.
1.1 Introduzione
1.1.1
2
Classificazione dei giochi
In generale, i giochi possono essere di tipo cooperativo o non cooperativo. Un gioco è detto non cooperativo quando ai giocatori non è consentito
definire accordi relativamente alla condotta del gioco. Al contrario, in un
gioco cooperativo gli accordi sono consentiti. In questa tesi ci occuperemo
unicamente dei giochi non cooperativi.
In base alle informazioni a disposizione dei giocatori nel corso del gioco,
laddove la variabile tempo sia significativa per esso, possiamo distinguere tra
giochi ad informazione perfetta e giochi ad informazione imperfetta. Un gioco
è ad informazione imperfetta quando un giocatore si trova a dover decidere
cosa fare senza conoscere quali siano state tutte le scelte effettuate da chi lo ha
preceduto nella sequenza di decisioni. Viceversa, un gioco è ad informazione
perfetta se ogni giocatore, quando è chiamato a giocare, conosce in pieno
tutte le scelte fatte in precedenza, ossia conosce perfettamente la storia del
gioco.
Possiamo distinguere, inoltre, tra giochi ad informazione completa e giochi
ad informazione incompleta. In un gioco ad informazione completa, ogni
giocatore dispone di tutte le informazioni che determinano le scelte degli
avversari. Non tutti i giochi sono di questo tipo: in un gioco ad informazione
incompleta un giocatore potrebbe ad esempio non essere a conoscenza delle
possibili strategie degli altri giocatori, o dell’utilità che essi conseguono a
seguito di una data combinazione di strategie.
1.1.2
Caratterizzazione dei giochi
Un gioco è descritto dai seguenti elementi:
• un insieme di giocatori N = {1, 2, . . . , n};
• uno spazio di azioni Ai , i = 1, 2, . . . , n, per ogni giocatore, ovvero
l’insieme delle azioni che il giocatore i-esimo può intraprendere nel
gioco;
1.1 Introduzione
3
• un insieme di profili di strategie S, che è il prodotto cartesiano di tutti
gli insiemi di strategie dei singoli giocatori:
S = S1 × S2 × · · · × Sn ;
• le utilità (o profitti ) che ciascun giocatore consegue in tutte le possibili
configurazioni del gioco, ovvero un vettore
U(s) = (u1 (s), u2 (s), . . . , un (s))
di n funzioni aventi come dominio l’insieme dei profili di strategie S =
S1 × S2 × · · · × Sn e come codominio R;
Connesso al concetto di azione è quello di strategia. Per chiarirlo meglio
differenziamo due possibili forme rappresentative dei giochi. In un gioco in
forma strategica (o forma normale) per ogni giocatore è presente un insieme
di possibili strategie, e per ogni possibile profilo di strategie di tutti i giocatori
è data per ognuno di essi una corrispondente utilità.
La forma estesa (o albero di gioco) è una rappresentazione più dettagliata
della forma normale: è una descrizione completa di come il gioco può evolvere nel tempo, che include l’ordine in cui i giocatori effettuano le azioni e
le informazioni che possiedono nel momento in cui le effettuano. Tale rappresentazione si serve di un albero di gioco, in cui ogni nodo rappresenta un
punto in cui un giocatore può effettuare una scelta.
Come mostrato da von Neumann nel 1928, un gioco in forma estesa può
essere sempre convertito in uno equivalente in forma normale, modificando
opportunamente lo spazio delle azioni a disposizione dei giocatori.
Nel caso di gioco in forma strategica, una strategia per un giocatore è
semplicemente una delle sue possibili azioni; nel gioco in forma estesa, una
strategia per un giocatore è l’insieme di tutte le azioni che lui sceglierebbe
durante il gioco. Più precisamente, considerando l’albero di gioco, una strategia per un giocatore indica l’azione compiuta per ogni nodo dell’albero in
cui lo stesso giocatore deve effettuare una scelta.
1.1 Introduzione
4
Infine, si parla di strategie pure quando una singola strategia è scelta dal
giocatore, e di strategie miste quando una distribuzione di probabilità sulle
varie strategie è decisa dal giocatore. Naturalmente, una strategia pura è un
caso particolare di strategia mista, ovvero corrisponde alla strategia mista
che assegna probabilità 1 ad un’unica strategia e probabilità 0 a tutte le
altre.
1.1.3
Una possibile soluzione di gioco:
equilibrio in strategie dominanti
L’idea più accreditata di soluzione di un gioco è quella di equilibrio. Poiché
l’obiettivo di ogni partecipante al gioco è ottenere il massimo profitto, il
problema principale che ciascun giocatore deve risolvere nell’analizzare un
gioco è come fare ad individuare la strategia con cui giocare.
In alcuni casi un giocatore ha a disposizione una strategia che gli assicura
un profitto mai minore di quello che gli assicurano le altre, rispetto a tutte
le possibili scelte dei propri avversari. Tale strategia è definita dominante;
laddove queste strategie esistano per tutti i giocatori, la loro combinazione
dà luogo ad un equilibrio in strategie dominanti.
Definizione 1.1 (Equilibrio in strategie dominanti). Un profilio di strategie s∗ = (s∗1 , s∗2 , . . . , s∗n ) è in equilibrio in strategie dominanti se e solo se
∀i ∈ N e ∀(s1 , s1 , . . . , sn ) ∈ S1 × S1 × · · · × Sn
ui (s1 , . . . , si−1 , s∗i , si+1 , . . . , sn ) ≥ ui (s1 , . . . , si−1 , si , si+1 , . . . , sn ).
Per comprendere meglio tale definizione, ci serviamo del Dilemma del
Prigioniero, gioco strategico molto famoso in letteratura.
Il dilemma del prigioniero
La polizia ferma due pregiudicati che devono scontare un anno di prigione
ciascuno per un crimine minore. Il procuratore sospetta, ma non può provare, che i due siano complici in un crimine maggiore, punibile con ulteriori
1.1 Introduzione
5
cinque anni di galera. Nel tentativo di renderli condannabili per il crimine
maggiore, il giudice propone separatamente, a ciascuno di loro, il condono
dell’anno di prigione per il crimine minore, chiedendo in cambio l’accusa del
socio per quello maggiore. In tal modo, ciascun pregiudicato, accusando il
complice, sarebbe condannato a cinque anni per il crimine maggiore, se accusato dall’altro; rimesso subito in libertà, altrimenti. La situazione può
essere descritta come un gioco tra i due prigionieri, che hanno come possibili
strategie l’opzione di accusare o meno il socio e come funzione di utilità l’opposto del numero di anni di prigione che rischiano. L’interazione strategica
tra i due pregiudicati può essere rappresentata mediante una matrice dove il
primo prigioniero sceglie la riga ed il secondo la colonna (Tabella 1.1). Ad
esempio, se il primo prigioniero accusa il suo complice, ma il secondo non lo
accusa, si ottiene un’utilità pari a 0 per il primo ed un’utilità pari a −6 per
il secondo.
accusa
non accusa
accusa
(−5, −5)
(0, −6)
non accusa
(−6, −0)
(−1, −1)
Tabella 1.1: Il dilemma del prigioniero
Una strategia è dominante, per cui il gioco in cui tutti i giocatori la adottano è in equilibrio in strategie dominanti, se è una scelta strategica ottima
qualunque sia la scelta dell’altro giocatore. In altri termini, indipendentemente dalle scelte dell’altro giocatore, il giocatore che gioca la sua strategia
dominante ottiene un’utilità maggiore rispetto a quella che potrebbe ottenere
giocando qualsiasi altra strategia.
In questo caso si può vedere facilmente come l’unica strategia dominante sia quella di accusare, in quanto indipendentemente dalla scelta
dell’avversario si ottiene un anno di sconto sulla pena.
Si noti tuttavia come l’unico profilo di strategie in equilibrio (accusa, accusa) non costituisce la soluzione migliore per i prigionieri, che se potessero
1.2 Equilibrio di Nash
6
accordarsi come in un gioco cooperativo certamente opterebbero per il profilo
di strategie (non accusa, non accusa); risulta quindi evidente come in un gioco non cooperativo la soluzione (sia essa in equilibrio in strategie dominanti
o in equilibrio di Nash 1 ) non coincide con il profilo di strategie che realizza
un ottimo sociale 2 .
Nel caso in cui una soluzione in strategie dominanti non sia individuabile
ci si deve accontentare di un obiettivo più modesto: è necessario introdurre
un ulteriore criterio di soluzione che sia applicabile ad una classe più ampia
di giochi.
1.2
Equilibrio di Nash
In modo intuitivo, un equilibrio di Nash [36] si ha laddove in un profilo
di strategie nessun giocatore ha convenienza nel mutare la propria strategia,
ferme restando quelle degli altri giocatori.
Definizione 1.2 (Equilibrio di Nash). Un profilio di strategie s∗ =
(s∗1 , s∗2 , . . . , s∗n ) è in equilibrio di Nash se e solo se ∀i ∈ N e ∀si ∈ Si
ui (s∗1 , . . . , s∗i−1 , s∗i , s∗i+1 , . . . , s∗n ) ≥ ui (s∗1 , . . . , s∗i−1 , si , s∗i+1 , . . . , s∗n ).
Per comprendere il significato dell’equilibrio di Nash può essere utile confrontarlo con quello in strategie dominanti. Dato un gioco, se un profilo di
strategie s = (s1 , s2 , . . . , sn ) costituisce la soluzione in strategie dominanti
del gioco, ciò implica che per ogni giocatore i la strategia si è la migliore sia
rispetto alle strategie degli avversari contenute in s, che rispetto a tutte le
altre strategie a disposizione degli avversari.
Di contro, se un insieme di strategie s = (s1 , s2 , . . . , sn ) costituisce un
equilibrio di Nash, ogni singola strategia si rappresenta una strategia ottima,
tra le strategie a disposizione del giocatore i, rispetto alle strategie degli
1
2
L’equilibrio di Nash verrà introdotto nel Paragrafo 1.2
Il concetto di ottimo sociale verrà chiarito nel Paragrafo 1.2.2
1.2 Equilibrio di Nash
7
avversari contenute in s, cioè dato che gli altri giocatori giochino proprio le
strategie contenute nell’insieme in esame.
Tornando al dilemma del prigioniero, possiamo osservare come il profilo
di strategie in cui ogni prigioniero accusa l’altro è anche un equilibrio di Nash
(in realtà è l’unico), oltre ad essere un equilibrio in strategie dominanti. Ciò
non deve destare stupore, in quanto è facile dimostrare che un equilibrio in
strategie dominanti è anche un equilibrio di Nash. Il viceversa però non è
vero, e dunque quest’ultimo individua una soluzione per una classe più ampia
di giochi, come si può evincere da un altro gioco molto famoso in letteratura:
la battaglia dei sessi.
La battaglia dei sessi
Due fidanzati devono decidere come trascorrere il pomeriggio; le due alternative possibili sono andare allo stadio o fare shopping. Ognuno dei due
ha una propria preferenza; in particolare, il fidanzato preferisce andare allo
stadio mentre la fidanzata fare shopping. Se i due andranno insieme allo
stadio, il fidanzato riceverà un guadagno in termini di utilità maggiore della
fidanzata; viceversa, se i due andranno a fare shopping sarà la fidanzata ad
ottenere un beneficio maggiore. Inoltre, poiché entrambi preferiscono trascorrere insieme il pomeriggio piuttosto che uscire da soli, se si dovesse verificare
quest’ultima circostanza otterrebbero un beneficio pari a 0. Nella rappresentazione in forma strategica del gioco presente in Tabella 1.2, il fidanzato
sceglie la riga mentre la fidanzata la colonna.
stadio shopping
stadio
(2, 1)
(0, 0)
shopping
(0, 0)
(1, 2)
Tabella 1.2: La battaglia dei sessi
L’analisi della matrice mostra che esistono due profili di strategie in equilibrio di Nash, ovvero i due profili in cui i due fidanzati trascorrono insieme
1.2 Equilibrio di Nash
8
il pomeriggio. Tuttavia può essere facilmente verificato che in questo gioco
non esiste nessun equilibrio in strategie dominanti.
L’equilibrio di Nash è, quindi, un criterio di soluzione di gioco che richiede
vincoli meno stringenti di quello in strategie dominanti. In questa tesi siamo
interessati esclusivamente all’equilibrio di Nash come criterio di soluzione di
gioco.
1.2.1
Esistenza
Nash in [37] ha dimostrato l’esistenza dell’equilibrio per ogni gioco
considerando però strategie miste.
Per quanto riguarda strategie pure, in [37, 42] è dimostrata l’esistenza
dell’equilibrio per una particolare classe di giochi, che non comprende però
quelli con insieme di strategie finito o comunque numerabile, che tipicamente
sono di interesse per le applicazioni informatiche della teoria dei giochi.3
Mostriamo ora un esempio di gioco in cui non esiste un equilibrio di Nash
in strategie pure.
Accoppiamento di monete
Luca e Sara scelgono una faccia della propria moneta: se scelgono la stessa
faccia, Sara deve pagare a Luca 1 euro, altrimenti è Luca a dover pagare a
Sara 1 euro. Il gioco strategico è illustrato in Tabella 1.3, in cui Luca deve
scegliere una riga e Sara una colonna.
testa
croce
testa
(1, −1) (−1, 1)
croce
(−1, 1) (1, −1)
Tabella 1.3: Accoppiamento di monete
3
In particolare è richiesto che gli insiemi di strategie siano convessi, ed un insieme
numerabile di cardinalità maggiore di 1 non è convesso.
1.2 Equilibrio di Nash
9
In questo gioco, gli interessi dei giocatori sono diametralmente opposti e
nessun profilo di strategie è in equilibrio di Nash: i profili di strategie in cui
viene scelta la stessa faccia non sono un equilibrio poiché a Sara conviene
deviare scegliendo l’altra faccia, mentre i profili di strategia in cui vengono
scelte facce diverse non sono in equilibrio poiché a Luca conviene mutare
strategia.
1.2.2
Problematiche algoritmiche
Come illustrato in [39], nelle problematiche recenti dell’informatica, sempre più interessata alla modellazione matematica di sistemi (come Internet)
in cui interagiscono agenti egoisti, la teoria dei giochi riveste una particolare
importanza, e l’equilibrio di Nash è un ottimo candidato per la soluzione di
un tale genere di gioco.
In questo paragrafo illustriamo le principali problematiche algoritmiche
legate all’equilibrio di Nash.
Prima di tutto, è naturalmente di fondamentale importanza assicurare
l’esistenza di tale equilibrio, discussa nel Paragrafo 1.2.1, poiché in generale
un equilibrio di Nash potrebbe non esistere per strategie pure.
Convergenza e tempo di convergenza
Nella teoria dei giochi classica, dato un gioco in forma strategica, si assume che i giocatori razionalmente scelgano la propria strategia, anche prevedendo le possibili mosse degli avversari, in modo da raggiungere immediatamente una condizione di equilibrio. Quando però siamo in presenza di
un numero di giocatori elevato, come avviene in uno scenario reale, tale assunzione sembra essere troppo forte, sia poiché laddove esistono più profili
di strategie in equilibrio di Nash nasce il problema di selezionarne uno, sia
poiché il gioco molto spesso è ad informazione incompleta. Per questo, prendendo spunto dalla teoria dei giochi evolutiva ([48]) e da altri lavori in campo
informatico (si veda [16, 15]), in questa tesi consideriamo il raggiungimento
di un equilibrio di Nash come il risultato di un processo evolutivo in cui ogni
1.2 Equilibrio di Nash
10
giocatore di volta in volta sceglie una strategia in modo da massimizzare la
propria utilità. Laddove nessun giocatore trae beneficio dal mutare la propria strategia, il profilo di strategie correnti è per definizione un equilibrio di
Nash.
Per gioco convergente si intende un gioco in cui la libera evoluzione dei
giocatori conduce sempre ad una situazione di equilibrio. Dunque, un gioco
convergente possiede sempre almeno un equilibrio di Nash, ma non è detto
che in un gioco non convergente non ne esista nessuno.
Un importante parametro è infine il numero di passi (tempo di
convergenza) necessario al raggiungimento di una situazione di equilibrio.
Complessità computazionale
Un altro importante aspetto è quello di individuare algoritmi efficienti
per computare equilibri di Nash. In generale infatti non è noto se esista un
algoritmo polinomiale che calcoli un equilibrio in strategie miste neanche nel
caso di 2 giocatori ([39]).
Inoltre, è interessante anche l’analisi dal punto di vista computazionale
delle funzioni di utilità dei vari giocatori.
Prezzo dell’anarchia
Molto spesso, come ad esempio nel problema del routing in una rete
di comunicazione ([44, 34]), oltre alla soluzione del gioco non cooperativo
data dall’equilibrio di Nash, si è interessati all’ottimizzazione di una funzione
sociale4 W.
Ciò premesso, è interessante valutare quanto la soluzione in equilibrio
di Nash si allontani da quella ottima del problema, ovvero da quella che
ottimizza la funzione sociale.
Sia N l’insieme delle soluzioni del gioco in equilibrio di Nash e W ∗ il
valore ottimo raggiungibile della funzione sociale W. Il coordination ratio o
4
Ad esempio la funzione sociale potrebbe essere la somma delle utilità di tutti i
giocatori.
1.3 Load Balancing
11
prezzo dell’anarchia del gioco G è
ρ(G) = sup
N ∈N
W(N )
W∗
se la funzione sociale è da minimizzare, e
ρ(G) = inf
N ∈N
W(N )
W∗
se la funzione sociale è da massimizzare.
Tornando all’esempio del dilemma dei prigionieri (Tabella 1.1) e considerando come funzione sociale la somma delle utilità dei due prigionieri, si può
osservare come l’unico equilibrio di Nash ha un valore sociale pari a −10,
mentre il valore ottimo della funzione sociale è −2: il coordination ratio del
gioco è 5.
Nei prossimi paragrafi presentiamo due problemi affrontati nella letteratura algoritmica in ambito non cooperativo: il problema del Load balancing
ed il problema del Selfish Routing. I più importanti risultati sono tratti dal
survey [10] di Artur Czumaj.
1.3
Load Balancing
Il problema del Load Balancing (bilanciamento di carico) è stato introdotto da Koutsoupias e Papadimitriou in [33]. Si tratta della versione non
cooperativa del problema dello scheduling con m processori indipendenti con
velocità v1 , . . . , vm e n task con pesi w1 , . . . , wn , ognuno dei quali diviene un
agente che ha a disposizione come insieme di strategie l’insieme dei processori. L’obiettivo sociale è quello di allocare i task ai processori in modo da
minimizzare il massimo carico dei processori.
Dunque, dato un profilo di strategie S = (s1 , . . . , sn ), con si ∈
{1, 2, . . . , m} ∀i ∈ {1, 2, . . . , n}, il costo del task i è
X
1
·
wk
vji k:j =j
k
i
1.3 Load Balancing
12
ed il load del processore j è
1 X
·
wk .
vj k:j =j
k
Inoltre, la funzione sociale è
W=
1 X
·
wk
j∈{1,2,...,m} vj
k:j =j
max
k
e l’ottimo sociale è
W∗ =
1 X
·
wk .
(s1 ,...,sn )∈{1,2,...,m}n j∈{1,2,...,m} vj
k:j =j
min
max
k
Computare l’ottimo sociale è N P-hard anche nel caso di processori con
uguale velocità, come è mostrato in [33].
L’esistenza dell’Equilibrio di Nash in strategie pure è provata in [19], dove è anche mostrato come sia N P-hard computare il migliore ed il peggiore
equilibrio di Nash, e come al contrario esista un semplice algoritmo polinomiale per individuarne uno generico. Inoltre Feldmann in [17] ha ideato uno
PTAS (schema di approssimazione con tempo polinomiale) per computare
l’equilibrio di Nash con minimo costo sociale.
In letteratura la stima del prezzo dell’anarchia è stata effettuata in relazione ad equilibri di Nash in strategie miste. Si tenga comunque presente che
una strategia pura è un caso particolare di strategia mista, e che dunque il
prezzo dell’anarchia non può che migliorare considerando solo strategie pure.
In una strategia mista, ogni agente i sceglie un vettore di probabilità
Pm j
j
tale che
j=1 pi = 1, in cui pi rappresenta la probabilità
(p1i , p2i , . . . , pm
i )
che l’agente i scelga il processore j. In questo modo, ogni task sceglie un
processore in modo casuale secondo la propria distribuzione di probabilità.
Il load atteso del processore j è
n
1 X
`j =
·
wi pji .
vj i=1
Per un task i, il costo atteso sul processore j laddove esso sia il processore
scelto da i è
cji =
wi
1 X
wi
+ ·
wt pjt = `j + (1 − pji ) .
vj
vj t6=i
vj
1.3 Load Balancing
13
Possiamo ora caratterizzare l’equilibrio di Nash in strategie miste. Le probabilità pji con i ∈ {1, 2, . . . , n} e j ∈ {1, 2, . . . , m} definiscono un equilibrio
di Nash in strategie miste se e solo se ∀i ∈ {1, 2, . . . , n}
pji > 0 ⇒ cji ≤ cqi , ∀q ∈ {1, . . . , m}.
In altre parole, nessun agente è incentivato a mutare la propria strategia,
ferme restando le strategie altrui.
Ora possiamo definire in modo preciso il prezzo dell’anarchia. Esprimiamo
innanzitutto il load Cj del processore j a seguito della scelta dei task:
n
1 X
Cj =
·
wi Jij ,
vj i=1
dove Jij sono variabili aleatorie binarie (a valori 0 e 1) tali che Pr[Jij = 1] =
pji . Dunque, la funzione sociale corrispondente ad un equilibrio in strategie
miste è pari al load massimo atteso, ossia
W = E[ max Cj ]
j∈{1,...,m}
e il prezzo dell’anarchia è
W
,
W∗
dove il massimo è sull’insieme di tutti gli equilibri di Nash.
ρ = max
Già Koutsoupias e Papadimitriou in [33] hanno ottenuto diversi risultati
circa il prezzo dell’anarchia:
• per due processori con uguale velocità, il prezzo dell’anarchia è pari a
3/2;
• per due processori generici (non necessariamente con la stessa velocità)
il prezzo dell’anarchia è almeno pari a
√
1+ 5
;
2
• per
con uguale velocità, il prezzo dell’anarchia è
m processori
√
log m
Ω log log m ed è al più 3 + 4m ln m;
1.4 Selfish Routing
14
• per m processori generici q
(non necessariamente con
la stessa velocità) il
Pm vj √
v1
prezzo dell’anarchia è O
j=1 vm log m , dove vj è la velocità
vm
del processore j, e v1 ≥ v2 ≥ · · · ≥ vm .
Inoltre, Czumaj e Vöcking in [11] hanno raffinato la stima per m
processori
con la stessa velocità, ottenendo che il prezzo dell’anarchia è
log m
Θ log log m .
Infine, sempre in [11] sono forniti delle stime tight per il prezzo dell’anarchia nel caso di m processori generici, raffinando la stima di Koutsoupias e
Papadimitriou: il coordination ratio per m processori è




log m
log m 
Θ min
,
.
 log log log m log log vm1 
log
vm
L’analisi nel caso di funzioni di costo non lineari, o di differenti scenari,
esula dagli scopi di questa tesi. Per eventuali approfondimenti si rimanda al
survey [10] di Artur Czumaj.
1.4
Selfish Routing
A differenza del Load Balancing appena illustrato, nel problema del Selfish
Routing (instradamento egoistico) gli agenti sono delle coppie di nodi in una
rete di comunicazione, le quali hanno l’esigenza di comunicare. Nella nostra
analisi, assumeremo che ogni agente è associato ad una frazione trascurabile
del traffico totale (ogni agente potrebbe rappresentare un’automobile in un
sistema autostradale); per l’estensione dei risultati qui riportati a scenari più
reali si veda [44].
Consideriamo una rete diretta G = (V, E) con insieme di nodi V ed
insieme di archi E, e k coppie di nodi (agenti ) {s1 , t1 }, {s2 , t2 }, . . . , {sk , tk };
ad ogni agente {si , ti } è associato un traffico ri . Denotiamo con Pi l’insieme
S
dei percorsi semplici si−ti , e definiamo P = ki=1 Pi . Un flusso è una funzione
f : P → R≥0 , e per un flusso f ed un arco e definiamo
X
fe =
fπ .
π∈P:e∈π
1.4 Selfish Routing
15
Un flusso f si dice ammissibile se per ogni agente i vale
X
fπ = ri .
π∈Pi
Per ogni arco e ∈ E è data una funzione di latenza `e (·) dipendente dal
carico, non negativa, continua e non decrescente. La latenza di un percorso π
rispetto ad un flusso f è naturalmente definita come la somma delle latenze
degli archi del percorso:
`π (f ) =
X
`e (fe ).
e∈π
Infine, dato un flusso f , la funzione sociale è
X
X
W =
`π (f )fπ =
`e (fe )fe .
π∈P
e∈E
Diamo ora due caratterizzazioni dell’equilibrio di Nash:
• Un flusso f ammissibile è in equilibrio di Nash se per ogni i ∈ {1, . . . , k},
π1 , π2 ∈ Pi e δ ∈ [0, fπ1 ] abbiamo
`π1 (f ) ≤ `π2 (f˜),
dove
f˜π =



 fπ − δ se π = π1
fπ + δ se π = π2


 f
altrimenti.
π
In altre parole, in un flusso in equilibrio di Nash nessun agente ha
convenienza a mutare il proprio cammino.
Facendo tendere δ a 0, la continuità e la monotonia delle funzioni di
latenza danno luogo alla seguente caratterizzazione.
• Un flusso f ammissibile è in equilibrio di Nash se e solo se per ogni
i ∈ {1, . . . , k}, π1 , π2 ∈ Pi con fπ1 > 0, vale
`π1 (f ) ≤ `π2 (f ).
1.4 Selfish Routing
16
Un’importante conseguenza di questa caratterizzazione è che in flusso
f in equilibrio tutti i percorsi si−ti ai quali f assegna un flusso positivo
hanno uguale latenza, che denotiamo con Li (f ). Pertanto, è possibile
esprimere la funzione sociale W per un flusso f in equilibrio di Nash
nella forma
W =
k
X
Li (f )ri .
i=1
Si noti come le definizioni di equilibrio sono date per strategie pure. In
ogni modo, come mostrato in [27] per l’assunzione fatta secondo la quale ogni
agente controlla una frazione trascurabile del traffico totale, tale definizione
è sostanzialmente equivalente a quella di equilibri in strategie miste.
Beckmann ed altri [4] hanno dato una caratterizzazione molto elegante di
flusso ottimo (che minimizzi la funzione sociale) come flusso in equilibrio di
Nash con un insieme differente di funzioni di latenza. Dato un arco e ∈ E,
denotiamo con `∗e il costo marginale del flusso in aumento sell’arco e, ovvero
`∗e (x) = `e (x) + x · `0e (x).
Sotto l’assunzione di funzioni di latenza standard, ovvero derivabili e tali
che x · `0e (x) sia convessa su [0, +∞), si ha che un flusso è ottimo se e solo se
è in equilibrio di Nash per l’istanza che si ottiene sostituendo le funzioni di
latenza `e con `∗e .
Da ciò deriva la dimostrazione di esistenza dell’equilibrio di Nash, e il
fatto che il costo sociale di ogni equilibrio è lo stesso.
Occupiamoci ora del prezzo dell’anarchia:
• nel caso di funzioni di latenza generiche, il coordination ratio può essere
arbitrariamente elevato (si veda [10], § 3.3);
• per funzioni di latenza lineari, già in [44] Roughgarden e Tardos hanno
effettuato una stima tight secondo la quale il coordination ratio è pari
a
4
3
≈ 1.333.
1.4 Selfish Routing
17
• In [43], Roughgarden ha ideato una tecnica più generale per la stima
del prezzo dell’anarchia, grazie alla quale è riuscito ad individuare il
coordination ratio per classi più ampie di funzioni di latenza standard:
Funzione di latenza
Rappresentazione tipica
Quadratica
ax2 + bx + c
Cubica
ax3 + bx2 + cx + d
Pp
i
i=0 ai x
Polinomio di grado ≤ p
Prezzo dell’anarchia
√
3 3
√
≈ 1.626
3 3−2 √
3
4
4
√
3
4
4−3
√
(1+p) p 1+p
p
√
=
Θ
p
ln p
(1+p) 1+p−p
Per risultati riguardanti ulteriori classi di funzioni di latenza ed eventuali approfondimenti si rimanda ai lavori [44] e [43] di Roughgarden ed al
survey [10] di Artur Czumaj.
Capitolo 2
Reti ottiche
In questo capitolo viene presentato il modello delle reti ottiche, ed elencati
i principali risultati presenti in letteratura circa il problema del routing in reti
ottiche. Il modello descritto è utilizzato anche per tutti i capitoli successivi
della tesi.
Il problema del routing in reti ottiche è stato largamente studiato dal
punto di vista centralizzato, sia in uno scenario statico, in cui le coppie che
richiedono la comunicazione sono tutte inizialmente note all’algoritmo, sia
in uno scenario on-line e dinamico in cui le richieste arrivano nel tempo e
devono essere servite senza alcuna conoscenza di quelle future.
I principali risultati vengono solo enunciati, ad eccezione di alcuni necessari per i capitoli successivi della tesi, che invece vengono illustrati e dimostrati
in dettaglio.
2.1
Introduzione
Il traffico Internet è aumentato drasticamente negli ultimi anni, cosı̀ come
la richiesta di banda da parte degli utenti. Per questo, l’attuale infrastruttura
elettronica della rete potrebbe non essere adeguata a soddisfare le esigenze
dei prossimi anni, rendendo potenzialmente necessarie nuove tecnologie.
Una fibra ottica offre molta più ampiezza di banda di un convenzionale
2.1 Introduzione
19
cavo in rame, avendone una nell’ordine dei 50T Hz [45]. Inoltre, il suo costo è
accessibile, la probabilità di errore è estemamente bassa (tipicamente 10−12 ,
contro 10−6 dei cavi in rame), e l’attenuazione e la distorsione di segnale sono
molto contenute. Per questi motivi, la fibra ottica è il mezzo di trasmissione
dati più adatto per trasmissioni ad alta velocità e su larga o media scala [41].
Negli ultimi decenni, le fibre ottiche sono state impiegate in due successive generazioni di reti [41]. Nella prima, il loro ruolo era semplicemente quello
di provvedere alla trasmissione per lunghi collegamenti che necessitavano di
ampia banda e bassa percentuale di errore. Tutte le funzioni di switching
e/o routing venivano gestite elettronicamente in modo classico. Il collo di
bottiglia nelle velocità di trasmissione era costituito proprio da questi terminali elettronici presenti agli estremi della fibra ottica (l’ampiezza di banda
è limitata a 10Gb/s in sistemi commerciali); esempi di reti ottiche di prima
generazione sono le reti SONET e SDH.
Viceversa, nella seconda generazione di reti ottiche, funzionalità come il
routing e lo switching sono gestite dal livello ottico della rete ([26]). L’elevata ampiezza di banda è sfruttata tramite la tecnica della multiplazione a
divisione di frequenza (WDM ), che partiziona la banda in più canali ognuno
dei quali utilizza una diversa lunghezza d’onda (o colore) e riesce a lavorare
alle massime velocità permesse da un cavo in rame ([9, 7, 32, 40]).
Le reti ottiche WDM possono essere classificate in due categorie:
broadcast-and-select e switched. Ambedue le categorie possono essere ulteriormente divise differenziando le reti ottiche a singolo hop (chiamate alloptical ), nelle quali il segnale viaggia lungo tutto il percorso di comunicazione
come luce e quindi può subire unicamente conversioni ottiche, da quelle multihop nelle quali invece il segnale può essere convertito (e riconvertito) in (e
dalla) forma elettronica.
Nelle reti broadcast-and-select, la trasmissione per ogni nodo è inviata
in broadcast a tutti i nodi della rete, ed è compito del ricevente estrarre il
proprio segnale da tutti quelli che gli giungono. Sebbene tali reti siano poco
costose e molto semplici da realizzare poiché impiegano unicamente compo-
2.2 Modello
20
nenti ottici passivi, esse hanno gravi limitazioni che rendono improponibile la
loro estensione a reti di area locale. Inoltre, necessitano di un elevato numero
di lunghezze d’onda anche per soddisfare un modesto traffico.
Una rete ottica switched è formata da nodi interconnessi da link in fibra
ottica. I nodi possono essere terminali (che inviano e ricevono dati), switch
(che direzionano i dati ricevuti in input ad una o più porte di output) o
altro; essi comunicano inviando segnali di lunghezze d’onda differenti lungo
gli archi di comunicazione della rete. In questa tipologia di rete, la stessa
lunghezza d’onda può essere impiegata in comunicazioni di coppie di nodi
differenti, che non condividano alcun link della rete.
Per reti all-optical con conversione ottica di lunghezza d’onda in [8] sono
riportati i maggiori risultati presenti in letteratura.
In questa tesi ci occuperemo di reti ottiche switched, all-optical e senza
conversione ottica di lunghezze d’onda. In una tale rete, una comunicazione
tra due nodi richiede la presenza di un percorso lungo il quale venga impiegata
una unica lunghezza d’onda che sia differente da quelle utilizzate dalle altre
comunicazioni che si servono degli archi dello stesso percorso.
2.2
Modello
Ci sono molti modi naturali con i quali una rete ottica può essere modellata. In questa tesi sarà utilizzato perlopiù il modello descritto nel Paragrafo
2.2.1, che fa uso di un grafo non diretto per descrivere la topologia della rete.
Verrà poi descritto un altro modello largamente presente in letteratura,
che fa uso di grafi diretti simmetrici per descrivere la topologia della rete.
2.2.1
Reti ottiche non dirette
In questo modello la rete di comunicazione è un grafo non diretto G =
(V, E), in cui V ed E rappresentano rispettivamente l’insieme dei nodi e degli
archi della rete.
2.2 Modello
21
Definizione 2.1 (Richiesta). Una richiesta è una coppia di nodi {x, y} che
ha l’esigenza di comunicare.
Si noti che una richiesta di comunicazione è bidirezionale.
Definizione 2.2 (Percorso). Un percorso P (α), con α = {x, y}, è un
insieme di archi consecutivi che connettono i nodi x ed y.
℘α è l’insieme di tutti i percorsi presenti nella rete che connettono i nodi
x ed y.
Estendendo la definizione agli archi, Eα = {e ∈ E| e ∈ P (α), P (α) ∈ ℘α }
Definizione 2.3 (Istanza). Un’istanza I è una collezione di richieste. Si
noti che una richiesta {x, y} può apparire più di una volta in un’istanza.
Definizione 2.4 (Routing puro). Un routing puro R = {P (x, y)|{x, y} ∈
I} per un’istanza I in un grafo G è un insieme di percorsi per le richieste in
istanza.
Indichiamo inoltre con R({x, y}) il percorso associato nel routing puro R
alla richiesta {x, y}, ovvero R({x, y}) = P ({x, y}) con P ({x, y}) ∈ R.
Definizione 2.5 (Routing completo). Un routing completo o più semplicemente un routing R = (RR , cR ) per un’istanza I in G è una coppia in cui
RR è un routing puro per I in G e cR : I → W (con W = {1, 2, 3, . . .} insieme di lunghezze d’onda) è una funzione che associa una lunghezza d’onda
ad ogni richiesta dell’istanza.
Indichiamo inoltre con C(R) il numero di lunghezze d’onda impiegate dal
routing R.
Definizione 2.6 (Grafo dei conflitti). Il grafo dei conflitti associato al
routing puro R è il grafo non diretto Gc = (R, F ) in cui due nodi (percorsi
di routing) sono adiacenti se e solo se condividono un arco in G.
Definizione 2.7 (Numero cromatico). Il numero cromatico associato ad
un grafo G è il numero minimo di colori necessario per colorare i nodi di G
in modo tale che due nodi adiacenti siano colorati con colori differenti.
2.2 Modello
22
Definizione 2.8 (Problema). Data la rete con topologia G e l’istanza I, il
problema (G, I) consiste nell’individuare un routing R per l’istanza I, ovvero
nell’assegnare ad ogni richiesta {x, y} ∈ I un percorso ed una lunghezza
d’onda (un colore) in modo che non esista una coppia di percorsi con lo
stesso colore che condividano un arco del grafo G (condizione nodale).
Utilizzando la definizione di grafo dei conflitti, possiamo equivalentemente
dire che risolvere il problema (G, I) consiste nell’individuare un routing puro
R, ed una colorazione dei vertici del grafo dei conflitti (R, F ) tale che due
vertici adiacenti sono colorati con colori differenti.
Denotiamo con w(G, I, R) il numero cromatico del grafo dei conflitti
(R, F ). Sia inoltre w(G, I) = minR w(G, I, R). In altre parole w(G, I, R)
è il minimo numero di lunghezze d’onda necessarie per il routing puro R,
e w(G, I) (o più brevemente w se non c’è ambiguità) è il minimo numero
di lunghezze d’onda utilizzate dal routing ottimo R∗ del problema (G, I),
ovvero C(R∗ ) = w.
2.2.2
Reti ottiche dirette
In questo modello di rete ottica, la topologia della rete è rappresentata
da un grafo diretto simmetrico, cioè da un grafo G = (V, E) in cui
(x, y) ∈ E ⇒ (y, x) ∈ E.
Definizione 2.9 (Richiesta). Una richiesta è una coppia ordinata di nodi
(x, y). Il nodo x ha l’esigenza di comunicare con il nodo y.
Si noti che una richiesta di comunicazione è unidirezionale.
Definizione 2.10 (Cammino). Un cammino P ((x, y)) è un insieme di archi
consecutivi che connettono il nodo x al nodo y.
Tutte le altre definizioni presentate nel paragrafo 2.2.1 si modificano in
modo naturale per la descrizione di questo modello, tenendo conto che le
richieste sono unidirezionali e che ai percorsi si sostituiscono i cammini.
Per non creare ambiguità di notazione, indicheremo sempre ~· tutti i
parametri che si riferiscono a questo modello:
2.2 Modello
23
• w(G,
~
I, R) è il minimo numero di lunghezze d’onda necessarie per il
routing puro R;
• w(G,
~
I) (o più brevemente w
~ se non c’è ambiguità) è il minimo numero di lunghezze d’onda utilizzate dal routing ottimo R∗ del problema
(G, I), ovvero C(R∗ ) = w.
~
2.2.3
Un parametro correlato ed alcuni risultati
La definizione seguente introduce un nuovo parametro utile per limitare
inferiormente la soluzione ottima del problema, sia nel caso di topologie con
grafo diretto che non diretto [3].
Definizione 2.11 (Load). Data una rete non diretta G = (V, E) ed un
routing R per un’istanza I, il load π(G, I, R, e) di un arco e ∈ E è il numero
di percorsi di R contenenti e.
Inoltre, il load π(G, I, R) del routing R in G è il massimo load di ogni
arco di G rispetto al routing R, cioè π(G, I, R) = maxe∈E π(G, I, R, e).
Infine, il load π(G, I) (o π se non c’è ambiguità) di un’istanza I in una
rete G è il minimo load di G in tutti i routing R per l’istanza I, cioè π(G, I) =
minR π(G, I, R).
La definizione si estende in modo naturale alle reti dirette, per le quali il
parametro di load è indicato ~π .
Lemma 2.2.1. w(G, I) ≥ π(G, I) (w(G,
~
I) ≥ ~π (G, I)) per ogni istanza I e
rete G.
In altre parole, il load è un lower bound per la soluzione ottima del
problema sia nel caso non diretto che in quello diretto.
Lemma 2.2.2. Ogni routing su reti non dirette induce un routing su reti
dirette, e un’assegnazione di lunghezze d’onda ammissibile per reti non dirette
è anche ammissibile per reti dirette. Dunque w(G, I) ≥ w(G,
~
I).
Nota 2.1. A prima vista potrebbe sembrare che, essendo π ≤ 2~π , valga anche w ≤ 2w,
~ ma ciò non è vero.
Se infatti si considera la rete
2.3 Routing statico
24
G = {{0, 1, 2, 3}, {{0, 1}, {0, 2}, {0, 3}}} e l’istanza I = {(1, 2), (2, 3), (3, 1)},
w = 3 e w
~ = 1. Inoltre in [1] è mostrato come il rapporto
w
w
~
può essere
arbitrariamente grande.
2.2.4
Istanze speciali
In una rete con topologia G = (V, E) è possibile definire istanze speciali1 :
• L’istanza All-to-All è l’istanza
IA = {{x, y}|x, y ∈ V ∧ x 6= y}
in cui ogni nodo ha l’esigenza di comunicare con tutti gli altri.
• Un’istanza One-to-All è
I0 = {{x0 , y}|y ∈ V ∧ x0 6= y}
dove x0 ∈ V . In altre parole, è un’istanza in cui un nodo ha l’esigenza
di comunicare con tutti gli altri.
• Un’istanza One-to-Many è un sottoinsieme di una qualche istanza Oneto-All
• Una k-relazione è un’istanza Ik in cui ogni nodo è coinvolto in non più
di k richieste. Una permutazione è una 1-relazione.
2.3
Routing statico
In uno scenario statico, tutte le richieste in istanza sono note all’algoritmo
all’inizio della computazione.
Un generico problema (G, I) su reti ottiche dirette è stato dimostrato essere N P-hard da Erlebach e Jansen in [12]. In particolare, in [12] è mostrato
1
Le istanze sono definite per reti non dirette, ma la loro estensione a reti dirette è
immediata.
2.3 Routing statico
25
essere N P-hard per alberi ed anelli. In [13] questi risultati sono stati estesi
ad alberi binari. La N P-completezza per il modello non diretto era conosciuta già prima dell’avvento delle reti ottiche WDM. In dettaglio, in [25] è
provata la N P-completezza per alberi, estesa in [12] anche agli anelli. Infine,
in [13] il problema è stato dimostrato essere efficientemente risolvibile per
alberi non diretti con grado limitato.
Quest’ultimo risultato, confrontato con quello di N P-hardness per alberi
binari diretti, potrebbe far pensare che il caso diretto è più difficile di quello
non diretto. Ciò in generale non è vero: in una rete a stella, nel caso diretto il
problema può essere efficientemente computato, mentre nel caso non diretto
rimane N P-completo.
Risultati presenti in letteratura per istanze particolari sono riassunti
ed elencati in [3]. Riportiamo di seguito i maggiori risultati per topologie
particolari di rete, analizzate anche in questa tesi dal punto di vista non
cooperativo.
Catene
Il problema del routing su catene è efficientemente computabile2 sia per
reti dirette che non dirette, ed in [22] è mostrato come sia equivalente alla
colorazione di grafi a intervalli. Inoltre, si ha che il numero di colori necessari
e sufficienti è pari al massimo load π delle richieste.
Alberi
Per quanto riguarda reti dirette, Kaklamanis ed altri hanno dimostrato il
seguente teorema.
Teorema 2.3.1 ([29]). Esiste un algoritmo efficiente per risolvere il problema del routing (G, I) per ogni istanza I ed albero G che usa al più
lunghezze d’onda.
2
Computabile da un algoritmo con complessità temporale polinomiale.
5~
π (G,I)
3
2.3 Routing statico
26
Inoltre, in ogni rete diretta con topologia ad albero esistono problemi con
load ~π arbitrariamente grande, tali che
w
~
~
π
> 54 .
Erlebach ed altri in [14] hanno elaborato anche un algoritmo efficiente
greedy con lo stesso rapporto di approssimazione.
Per le reti ottiche non dirette vale invece il seguente teorema.
Teorema 2.3.2 (Erlebach e Jansen [12]). Esiste un algoritmo efficiente
per risolvere il problema del routing (G, I) per ogni istanza I ed albero G che
usa al più b1.1w(G, I) + 0.8c lunghezze d’onda.
Sempre nel caso non diretto, ci sono esempi in cui il rapporto
w
π
tende
asintoticamente a 3/2.
Anelli
Per le topologie ad anello si è soliti in letteratura separare il problema dell’assegnazione dei percorsi di routing da quello dell’assegnazione di lunghezze
d’onda.
Il teorema seguente ci assicura che è possibile trovare in modo efficiente
un’assegnazione di percorsi che minimizzi il load.
Teorema 2.3.3 (Frank ed altri [20]). Esiste un algoritmo con complessità temporale lineare per trovare per ogni istanza I e anello non diretto A
un’assegnazione di percorsi R tale che π(A, I, R) = π(A, I).
Una volta fissati i percorsi, il problema dell’assegnamento di lunghezze
d’onda diviene in entrambi i modelli (diretto e non) equivalente al problema di colorazione di vertici in grafi ad archi circolari, che è provato essere
N P-completo in [21]. Tuttavia, esiste un algoritmo efficiente con un buon
rapporto di approssimazione.
Dato un routing puro R per un’istanza I in una rete con topologia ad
anello A, Tucker [47] ha formulato un algoritmo polinomiale che risolve il
problema dell’assegnazione di colori usandone al più 2π(A, I, R) − 1 (Tucker
ha anche mostrato come esistano istanze in cui tale numero di colori è necessario). Combinato con il precedente teorema, questo risultato fornisce un
2.4 Routing on-line
27
efficiente algoritmo 2-approssimante per il problema in anelli non diretti. I
risultati sono comunque estendibili ad anelli diretti ([35]).
2.4
Routing on-line
In uno scenario on-line, le richieste arrivano all’algoritmo in momenti
temporali distinti. Appena giunge una richiesta, l’algoritmo deve decidere
il suo routing, ed inoltre questa scelta è definitiva, nel senso che l’arrivo di
nuove richieste non può far mutare il routing di quelle già presenti.
In letteratura il problema è stato studiato soprattutto in relazione a
specifiche topologie di rete, come è possibile rilevare in [18].
Per quanto riguarda le catene, il problema è equivalente alla colorazione on-line di un grafo ad intervalli, essendo in questo caso tale il grafo dei
conflitti. Questo problema è stato studiato da Kierstead e Trotter [30] che
presentano un algoritmo on-line ottimale 3-competitivo che usa al più 3π − 2
colori. L’algoritmo di Slusarek presentato nel Paragrafo 2.4.1 estende questi
risultati agli anelli.
Per quanto riguarda gli anelli, un semplice approccio al problema impiegato da diversi autori ([23, 35]) consiste nel tagliare l’anello in un arco per
risolvere il problema sulla catena risultante. Naturalmente tutti i rapporti di
competitività devono essere raddoppiati poiché il taglio dell’anello induce un
load che è al più il doppio di quello ottimo.
In presenza di percorsi prefissati, il problema si riduce alla colorazione di
un grafo ad archi circolari che è stato investigato nella versione on-line da
Slusarek.
2.4.1
Un algoritmo on-line per anelli
Questo algoritmo presentato da Slusarek in [46] effettua l’assegnazione online di lunghezze d’onda alle richieste (con percorsi prefissati) che giungono
in istanti temporali differenti. Si dimostra come questo algoritmo usi al più
2.4 Routing on-line
28
3L − 2 lunghezze d’onda, dove L = π(An , I, R) è il load delle richieste in
istanza nel routing puro prefissato R.
Definizioni e notazione
R denota il routing puro prefissato (per ogni richiesta α, R(α) è il percorso
corrispondente ad α).
L’insieme di lunghezze d’onda viene partizionato in ripiani contenenti più
livelli; ognuno di questi ultimi è associato ad un colore. Dunque assegnare
un colore ad una richiesta α = {xα , yα } vuol dire assegnarle un ripiano sh(α)
ed un livello lv(α) relativo ad esso.
Shi ⊆ I, i = 0, 1, . . . è l’insieme delle richieste a cui è stato assegnato il
ripiano i.
Per ogni arco e dell’anello ed insieme F di richieste, l’overlap r(e|F )
indica il numero di richieste in F che utilizzano l’arco e; in modo naturale
tale definizione si estende ad un percorso o più in generale ad un insieme di
archi P :
r(P |F ) = max r(e|F ).
e∈P
Infine, nell’analisi dell’algoritmo Fj ⊆ I denota l’insieme di richieste
{α1 , α2 , . . . , αj−1 } giunte all’algoritmo prima di αj , e Ti ⊆ I denota le richieste assegnate dopo la conclusione dell’algoritmo ai ripiani Sh0 ∪Sh1 ∪. . .∪Shi .
Pertanto, l’espressione
r(R(αj )|Fj ∩ Ti )
indica il massimo overlap lungo il percorso di αj rispetto a tutti i primi i
ripiani esattamente nel momento in cui la richiesta αj giunge all’algoritmo.
L’algoritmo
L’algoritmo distribuisce le richieste nei ripiani in modo tale da mantenere
contenuta la sovrapposizione all’interno di ogni ripiano. Più precisamente, ad
una data richiesta α l’algoritmo assegna il ripiano i con indice più piccolo, tale
che l’overlap del percorso R(α) rispetto alle richieste in Sh0 ∪ Sh1 ∪ . . . ∪ Shi
2.4 Routing on-line
29
sia al più i. Una volta individuato il ripiano, l’algoritmo assegna il livello più
piccolo disponibile ad α, seguendo una strategia F irst − F it.
Input Una sequenza di richieste (α1 , α2 , . . . , αn )
Per ogni i, Shi := ∅;
for j = 1, 2, . . . , n
leggi la prossima richiesta αj ;
i := 0;
while r(R(αj )|Sh0 ∪ Sh1 ∪ . . . ∪ Shi ) > i do
i := i + 1;
sh(αj ) := i;
l := 1;
while esiste α0 ∈ Shi tale che lv(α0 ) = l e R(αj ) ∩ R(α0 ) 6= ∅ do
l := l + 1;
lv(αj ) := l;
Shi := Shi ∪ {αj };
next
Analisi dell’algoritmo
Lemma 2.4.1. Se p < q, per ogni i
r(R(αp )|Fp ∩ Ti ) ≤ r(R(αp )|Fq ∩ Ti ).
Dimostrazione. Il lemma segue immediatamente dal fatto che Fp ⊆ Fq .
Lemma 2.4.2. Se R(αp ) ∩ R(αq ) 6= ∅ e sh(αp ) = sh(αq ) = i con p 6= q e
i > 0, allora
r(R(αp ) ∩ R(αq )|Fmax{p,q} ∩ Ti−1 ) ≤ i − 1.
Si noti come R(αp ) ∩ R(αq ) può essere visto come un insieme di uno o
due percorsi (l’ultimo caso si ha se e solo se R(αp ) e R(αq ) coprono l’intero
anello).
2.4 Routing on-line
30
Intuitivamente, se a due percorsi con disgiunti è assegnato lo stesso ripiano, allora non è la loro intersezione a non aver permesso che a loro fosse
assegnato un ripiano più basso.
Dimostrazione. Senza perdita di generalità, sia p < q, e supponiamo per
assurdo che
r(R(αp ) ∩ R(αq )|Fq ∩ Ti−1 ) > i − 1.
Allora, poiché Ap ∈ Shi e Aq è colorato dopo Ap , deve essere
r(R(αp ) ∩ R(αq )|Fq ∩ Ti ) > i
che contraddice Aq ∈ Shi .
Lemma 2.4.3. Per ogni i, se sh(αp ) = sh(αq ) = i con p 6= q, allora né
R(αp ) ⊆ R(αq ) né R(αq ) ⊆ R(αp ).
Dimostrazione. Per i = 0 la tesi è ovvia.
Se i > 0, procediamo per assurdo assumendo senza perdita di generalità
che R(αp ) ⊆ R(αq ) e distinguiamo due casi.
• Se p > q, dal Lemma 2.4.2
r(R(αp )|Fp ∩ Ti−1 ) ≤ i − 1;
• se p < q, dal Lemma 2.4.2
r(R(αp )|Fq ∩ Ti−1 ) ≤ i − 1,
e dal Lemma 2.4.1
r(R(αp )|Fp ∩ Ti−1 ) ≤ r(R(αp )|Fq ∩ Ti−1 ) ≤ i − 1.
In ambedue i casi, dunque, alla richiesta αp sarebbe dovuto essere
assegnato un ripiano più basso Shj con j < i: una contraddizione.
Lemma 2.4.4. Nel ripiano Sh0 è utilizzato solo un livello. Per ogni i > 0,
il più grande livello usato nel ripiano Shi è al più 3.
2.4 Routing on-line
31
Dimostrazione. Il lemma è ovvio per il ripiano Sh0 .
Fissato un i > 0 procediamo per assurdo supponendo che alla richiesta
αj sia stato assegnato il livello 4 del ripiano i-esimo. Poiché i livelli sono
assegnati con la strategia First-Fit, R(αj ) ha intersezione non vuota con i
percorsi di almeno altre tre richieste, sempre posizionati sul ripiano Shi con
i livelli 1, 2 e 3. Per il Lemma 2.4.3, nessuno di essi può essere contenuto in
R(αj ), e quindi almeno due di loro devono intersecare R(αj ) in uno dei due
archi estremi. Siano αk e αl le richieste corrispondenti a tali percorsi, e sia
e0 l’arco estremo di R(αj ) in questione; senza perdita di generalità, sia αl la
richiesta il cui percorso è contenuto nell’unione dei percorsi delle altre due
richieste.
Applicando il Lemma 2.4.2 a αj e αl otteniamo
r(R(αj ) ∩ R(αl )|Fmax{j,l} ∩ Ti−1 ) ≤ i − 1,
ed applicandolo a αk e αl otteniamo
r(R(αk ) ∩ R(αl )|Fmax{k,l} ∩ Ti−1 ) ≤ i − 1.
Dunque, essendo R(αl ) = (R(αl ) ∪ R(αk )) ∪ (R(αl ) ∪ R(αj )) e l ≤
min{max{j, l}, max{k, l}} otteniamo
r(R(αl )|Fl ∩ Ti−1 ) ≤ i − 1,
e quindi l’algoritmo avrenne dovuto assegnare alla richiesta αl un ripiano più
basso Shi0 con i0 < i: una contraddizione.
Lemma 2.4.5. Il numero n di ripiani usati dall’algoritmo è al più L.
Dimostrazione. Consideriamo una qualsiasi richiesta αj cui l’algoritmo ha
assegnato il ripiano più alto Shi . Per la scelta dell’algoritmo, deve essere
r(R(αj )|Fj ∩ Ti−1 ) > i − 1.
Dunque, per un qualche arco e ∈ R(αj ) deve valere
r(e|Fj+1 ) > i.
2.4 Routing on-line
32
Poiché i denotava l’indice del ripiano più alto, essendo i ripiani numerati
da 0, si ha
n = i + 1 ≤ r(e|Fj+1 ) ≤ L.
Essendo il load L è un lower bound al numero minimo di colori necessario, dal Lemma 2.4.4 e dal Lemma 2.4.5 segue il risultato di competitività
dell’algoritmo.
Teorema 2.4.6 (Slusarek [46]). Il numero di colori usato dall’algoritmo
on-line di Slusarek per colorare un insieme di richieste con percorsi prefissati
inducenti un load L è al più 3L − 2.
2.4.2
Algoritmo on-line per alberi O(log n)-competitivo
In questo paragrafo illustriamo un algoritmo on-line per alberi proposto da Bartal
e Leonardi [2], i quali hanno anche provato il lower bound
log |I|
Ω log log |I| per algoritmi deterministici, ottenuto su un albero di profondità
log |I|.
Definizione 2.12 (Grafo d-induttivo). Un grafo è d-induttivo se e solo se
i suoi n vertici possono essere numerati da 1 a n in modo che ogni vertice sia
adiacente al più a d vertici con un numero maggiore.
Irani in [28] ha mostrato come la strategia First-Fit, che assegna ad ogni
vertice il colore più basso disponibile, colori on-line un grafo d-induttivo
costituito da n nodi con O(d log n) colori.
Il seguente teorema di Bartal e Leonardi, combinato con il risultato appena esposto, dimostra come la strategia First-Fit risolva il problema del
routing per alberi (T ree, I) utilizzando O(log |I|) colori.
Teorema 2.4.7. Sia T un albero; il grafo dei conflitti associato al problema
(T,I) è 2(π(T, I) − 1)-induttivo.
2.5 Routing dinamico
33
Dimostrazione. Mostriamo come tutte le richieste (corrispondenti ai vertici
del grafo dei conflitti) possono essere numerate in modo tale da essere in
conflitto con al più 2(π(T, I) − 1) richieste con un numero più alto.
Attuiamo un processo di modifica dell’albero mentre assegnamo numeri
progressivi alle richieste. Ogni richiesta è associata ad un percorso sull’albero;
tali percorsi vengono accorciati in modo opportuno durante il processo di
modifica, fino a quando i loro estremi vengono a coincidere: un tale percorso
sarà chiamato concluso. Il processo di modifica avviene rimuovendo foglie
dall’albero, e quindi accorciando tutti i percorsi che avevano un unico estremo
coincidente con esse. Se un percorso invece è concluso e dunque entrambi i
suoi estremi coincidono con una foglia, la richiesta a lui corrispondente viene
numerata ed il percorso rimosso completamente dall’albero.
Consideriamo una generica richiesta α associata con un percorso concluso
ad una foglia l. Tra tutte le richieste con numero più alto, tale richiesta può
essere in conflitto solo con quelle associate con altri percorsi che in quel
momento hanno l come estremo. Più precisamente, nel grafo originale, il
percorso associato ad α usa al più due archi adiacenti a l, e dunque può
essere in conflitto con al più 2(π(T, I) − 1) altre richieste con numero non
ancora assegnato (e quindi più alto).
2.5
Routing dinamico
Lo scenario dinamico si differenzia da quello on-line, generalizzandolo,
unicamente per il fatto che le richieste, oltre a poter arrivare in tempi diversi, possono anche andare via in qualsiasi momento. Anche in questo caso,
quando giunge una richiesta, l’algoritmo deve decidere il suo routing, ed
inoltre questa scelta è definitiva, nel senso che l’arrivo o la partenza di altre
richieste non può far mutare il routing di quelle presenti.
In letteratura il problema è stato studiato da Gerstel ed altri [24, 23]
in riferimento a topologie ad anello e albero, nell’ambito di reti ottiche non
dirette.
2.5 Routing dinamico
34
Anelli
Anche l’approccio seguito in [23] prevede di suddividere il problema del
routing in quello del routing puro ed in quello dell’assegnazione di lunghezze
d’onda.
Per quanto riguarda l’assegnazione delle lunghezze d’onda dato un routing puro fissato R, in [23] è presentato un algoritmo che utilizza al più
π(An , I, R) + π(An , I, R)dlog2 ne colori in un anello An costituito da n nodi.
Inoltre, è anche stimato un lower bound nel caso dinamico pari a
π(An , I, R) + 0.5π(An , I, R) log2 n colori.
Infine, viene analizzato il comportamento dell’algoritmo First-Fit che
assegna sempre il colore più piccolo disponibile ad una richiesta.
Teorema 2.5.1 (Gerstel). Il numero di colori utilizzati dall’algoritmo
First-Fit, dato un routing puro R per un’istanza I in un anello An , è al
più 2.53π(An , I, R) log2 n + 5π(An , I, R).
Dimostrazione. Sia W (H, L) il massimo colore utilizzato da un percorso di
lunghezza al più H a seguito dell’applicazione dell’algoritmo First-Fit ad una
rete con topologia ad anello An con load al più L.
Dimostriamo dapprima per induzione su H che per H ≥ 1,
W (3H, L) ≤ 4L − 3 + W (H, L).
Consideriamo un generico percorso p = {e1 , e2 , . . . , ek } di lunghezza k ≤ 3H.
Procediamo per casi:
• Se k ≤ H, a p può essere assegnato un colore al più pari a W (H, L)
per ipotesi induttiva.
• Se H < k ≤ 3H, mostriamo come nell’insieme W ∗ = {W (H, L) +
1, W (H, L) + 2, . . . , W (H, L) + 4L − 3} sia presente un colore che può
essere assegnato a p.
Siano e1 , edk/3e , ed2k/3e , ek gli archi critici per p. Poiché i percorsi
che utilizzano colori in W ∗ hanno lunghezza almeno pari ad H + 1 >
2.5 Routing dinamico
35
k/3, ognuno di essi deve utilizzare almeno un arco critico. Per questo
possiamo affermare che il numero di tali percorsi è al più 4(L − 1).
Poiché in W ∗ sono presenti 4(L − 1) + 1 colori, certamente ne esiste
uno disponibile per p.
Il teorema segue dal fatto che, essendo W (1, L) = L,
W (H, L) ≤ (4L − 3)dlog3 he + L
e dal fatto che la lunghezza di un percorso è al più n.
Alberi
Per reti con topologia ad albero, sempre in [23] è presentato un algoritmo
che risolve il problema del routing utilizzando al più (2π−1)dlog2 ne lunghezze
d’onda.
Capitolo 3
Prezzo dell’anarchia
in reti ottiche
In questo capitolo viene affrontato il problema del routing in reti ottiche
in un contesto non cooperativo, in cui ogni coppia di nodi della rete presente
in istanza è un agente egoista, ovvero un giocatore alla ricerca della strategia
che per lui risulta essere migliore.
Utilizzeremo in particolare il concetto di equilibrio di Nash in strategie
pure descritto nel Paragrafo 1.2: nel momento in cui nessun agente trae vantaggio dal mutare la propria strategia di routing ferme restando le strategie
altrui, si è pervenuti in una situazione di equilibrio che è la soluzione non
cooperativa del problema del routing.
L’obiettivo è quello di incentivare gli agenti a raggiungere, sebbene operino in modo egoistico e non cooperativo, una soluzione non lontana dalla
soluzione ottima, che abbia cioè un basso prezzo dell’anarchia 1 .
Abbiamo individuato diversi scenari in cui possono trovarsi gli agenti, a
seconda dell’informazione detenuta circa lo stato della rete e l’istanza del problema; per ognuno di tali scenari proponiamo alcune funzioni di pagamento,
che hanno lo scopo di raggiungere il nostro obiettivo.
1
La funzione sociale considerata in questa tesi è il numero di lunghezze d’onda utilizzate
per effettuare il routing
3.1 Modello
3.1
37
Modello
La gran parte del modello cui faremo riferimento è già stata descritta nel
paragrafo 2.2.1.
Per la nostra analisi nel caso non cooperativo, si rendono necessarie anche
le seguenti definizioni.
Definizione 3.1 (Agente). Ogni richiesta α = {x, y} ∈ I è un agente.
Definizione 3.2 (Funzione di prezzatura). Dato l’insieme delle lunghezze
d’onda (o colori) disponibili W = {1, 2, 3, . . .}, una funzione di prezzatura
f : W → R>0 è una funzione che associa ad ogni colore un prezzo positivo.
Senza perdita di generalità assumiamo f non decrescente2 .
Definizione 3.3 (Stato della rete). Lo stato della rete di comunicazione
G indotto da un routing R è una funzione σR : E → 2W che associa ad ogni
arco della rete l’insieme delle lunghezze d’onda utilizzate lungo esso.
A
la restrizione della funzione σR al dominio A ⊆ E.
Si indica con σR
Laddove chiara dal contesto, l’indicazione notazionale del routing R verrà
omessa per una maggiore leggibilità.
Definizione 3.4 (Stato dei percorsi della rete). Sia ℘ =
S
α∈I
℘α . Lo
stato dei percorsi della rete di comunicazione G indotto dal routing R è
una funzione σ̄R : ℘ → 2W che associa ad ogni percorso della rete l’insieme
delle lunghezze d’onda utilizzate lungo almeno un arco del percorso. Più
S
formalmente, σ̄R (P (x, y)) = e∈P (x,y) σR (e).
A
Si indica con σ̄R
la restrizione della funzione σ̄R al dominio A ⊆ ℘.
Laddove chiara dal contesto, l’indicazione notazionale del routing R verrà
omessa per una maggiore leggibilità.
Definizione 3.5 (Funzione di pagamento e livello di informazione).
Data una funzione di prezzatura f e un routing R relativo ad un’istanza I
su una rete G, una funzione di pagamento pR : I → R≥0 (o semplicemente
2
Essendo il dominio di f discreto, è sempre possibile effettuare un riordinamento dei
colori che renda f non decrescente
3.1 Modello
38
p : I → R≥0 ) è una funzione non negativa che associa ad ogni agente un costo
da corrispondere al gestore della rete di comunicazione per la fruizione del
servizio.
Ogni funzione di pagamento pR (β) = ∞ per ogni agente β la cui richiesta
di comunicazione non è soddisfatta dal routing R.3 Ciò vuol dire che gli
agenti sono disposti a comunicare ad ogni costo.
In generale una funzione di pagamento pR potrebbe dipendere da un
insieme di informazioni più ristretto del routing R ad essa associato, ma
comunque indotto da esso. Per precisare meglio ciò, introduciamo il concetto
di livello di informazione 4 :
Informazione minimale Questo livello di informazione dà ad ogni singolo
agente unicamente informazione su quali lunghezze d’onda sono disponibili lungo i vari percorsi che connettono i due nodi relativi all’agente
stesso.
In questo caso la funzione di pagamento p relativa all’agente α non
può dipendere dall’istanza I e dallo stato della rete di comunicazione; può dipendere da σ̄ ℘α , cioè dallo stato dei percorsi della rete di
comunicazione con dominio ristretto ai percorsi relativi all’agente α.
Informazione intermedia Questo livello di informazione dà ad ogni singolo agente la conoscenza di quali lunghezze d’onda sono disponibili e
quali occupate in ogni arco utilizzato dai percorsi che connettono i due
nodi relativi all’agente stesso.
In questo caso la funzione di pagamento p relativa all’agente α non può
dipendere dall’istanza I, ma può dipendere dallo stato σ Eα della rete
di comunicazione con dominio ristretto agli archi relativi all’agente α.
3
4
vedi nota 3.1
Come evidenziato nei successivi paragrafi, il livello di informazione in una rete ottica
reale può dipendere da limitazioni tecnologiche della rete come da politiche di privacy
attuate dal gestore o imposte dalla legge; si tenga conto a proposito del fatto che una
funzione di pagamento in un contesto non cooperativo e fortemente decentralizzato deve
essere computata dal singolo agente che richiede il servizio di comunicazione
3.1 Modello
39
Informazione completa Questo livello di informazione dà ad ogni singolo
agente informazione completa sull’istanza del problema e sullo stato
corrente della rete.
In questo caso la funzione di pagamento p di ogni agente può dipendere
dall’istanza I e dal routing R.
In modo naturale, in qualsiasi livello di informazione pR=(R,c) (α) può dipendere anche dalla lunghezza d’onda c(α) e dal percorso R(α) dell’agente α
nel routing R.
Si noti che anche con il livello di informazione minimale un agente è in
grado di posizionarsi su un percorso con una lunghezza d’onda valida, tale
cioè da non interferire con nessuna altra lunghezza d’onda presente lungo
lo stesso percorso, rispettando in questo modo la condizione nodale per un
problema su reti ottiche, illustrata nella Definizione 2.8.
Definizione 3.6 (Routing in equilibrio di Nash). Un routing R è in
equilibrio di Nash se e solo se per ogni agente α ∈ I e per ogni routing R0
che differisce da R unicamente per il percorso e/o il colore dell’agente α si
ha
pR (α) ≤ pR0 (α)
Nota 3.1. I routing considerati nel caso non cooperativo sono anche i routing
parziali, ovvero quelli in cui c’è solo una parziale assegnazione di percorsi e
colori agli agenti. Ciò comunque non pregiudica la soluzione del problema in
quanto nel caso non cooperativo siamo interessati a routing in equilibrio di
Nash e abbiamo che un routing parziale non può mai essere in equilibrio di
Nash poiché per ogni agente β non servito nel routing R non è verificata la
condizione richiesta nella definizione precedente, essendo pR (β) = ∞.
Definizione 3.7 (Gioco e coordination ratio). Il gioco G = (G, I, f, p)
degli agenti in I sulla rete G indotto da una funzione di pagamento p e dalla
funzione di prezzatura f ha |I| agenti, ognuno dei quali possiede come insieme
di strategie ℘α × W e funzione di utilità uα = −p(α).
3.1 Modello
40
Sia N l’insieme dei routing del gioco in equilibrio di Nash. Il coordination
ratio o prezzo dell’anarchia del gioco G è
ρ(G) = sup
R∈N
c(R)
w(G, I)
Definizione 3.8 (Evoluzione del gioco e mosse). L’ evoluzione del gioco
G = (G, I, f, p) è una sequenza di quintuple (mosse)
(α, Pold (α), colorold , Pnew (α), colornew )
dove α è un agente, Pold (α) ∈ ℘α ∪{undef}, Pnew (α) ∈ ℘α e colorold , colornew ∈
W . La semantica di una mossa è che l’agente α, avendone convenienza, muta
il suo routing dal percorso Pold (α)5 con lunghezza d’onda colorold al percorso
Pnew (α) con lunghezza d’onda colornew .
Un agente non può effettuare una mossa in cui assume un percorso ed un
colore tali da violare la condizione nodale delle reti ottiche secondo la quale
tutti i percorsi di routing che condividono un arco devono avere assegnati
colori differenti.
All’inizio del gioco evolutivo si parte da una situazione di routing (anche
parziale) R0 = (R0 , c0 ) qualsiasi che rispetti la condizione nodale per le reti
ottiche.
Sia Rold = (Rold , cold ) il routing presente prima del verificarsi di una
mossa. Dopo la mossa, il routing Rold muta nel routing Rnew = (Rnew , cnew )
in cui Rnew = Rold \ {Pold (α)} ∪ {Pnew (α)} e
(
colornew se γ = α
cnew (γ) =
cold (γ)
altrimenti
Il verificarsi di una mossa implica che
pRold (α) > pRnew (α)
Il gioco termina laddove nessun agente ha convenienza nell’effettuare una
mossa, ovvero quando si ottiene un equilibrio di Nash.
5
Se l’agente inizialmente non è servito, la sua prima mossa ha questa componente pari
ad undef.
3.1 Modello
41
Definizione 3.9 (Grafo dell’evoluzione di gioco). Il grafo dell’evoluzione
di gioco G = (G, I, f, p) è il grafo diretto (Φ, M ) dove Φ è l’insieme dei routing
(anche parziali) che la rete ha durante ogni possibile evoluzione di gioco e
ogni arco diretto m ∈ M , m = (R1 , R2 ), è associato ad una possibile mossa
di un agente che fa mutare il routing da R1 a R2 .
Si noti che il nodo in cui un gioco eventualmente termina è un nodo
pozzo per il grafo dell’evoluzione di gioco, e che se questo grafo è aciclico la
convergenza ad un equilibrio di Nash è sempre assicurata in un numero finito
di mosse.
Definizione
3.10
(Gioco
convergente). Un gioco
il cui grafo
dell’evoluzione è aciclico è detto convergente.
Definizione 3.11 (Funzione di pagamento convergente). Una funzione
di pagamento che induce un gioco convergente per ogni funzione di prezzatura
è detta convergente.
Esponiamo ora un piccolo risultato che mette in evidenza la correlazione tra esistenza di un equilibrio di Nash e le caratteristiche del grafo
dell’evoluzione di gioco.
Proposizione 3.1.1. Se un gioco G è convergente, allora esiste almeno un
routing in equilibrio di Nash per G.
Dimostrazione. Essendo il grafo dell’evoluzione di gioco aciclico, deve esistere
almeno un nodo pozzo, cioè senza archi uscenti. Tale nodo rappresenta un
routing in equilibrio di Nash poiché se tale routing non fosse un equilibrio
di Nash, allora sarebbe possibile da parte di qualche agente effettuare una
mossa, e ciò contraddirebbe il fatto che questo routing è associato ad un nodo
pozzo.
Nota 3.2. Si noti che viceversa la ciclicità del grafo dell’evoluzione di gioco
non implica la non esistenza di un equilibrio di Nash, in quanto un grafo
ciclico può comunque contenere un nodo pozzo.
3.2 Una classe di funzioni di pagamento convergenti
3.2
42
La classe Π di funzioni di pagamento
convergenti
In questo paragrafo definiamo una classe di funzioni di pagamento che inducono un gioco convergente. A tale scopo è necessario introdurre la seguente
definizione.
Definizione 3.12 (Ordinamento lessicografico). Date due sequenze di
reali Ψ = (testa, Ψ̃) e Ψ0 = (testa0 , Ψ̃0 ) di uguale lunghezza l, dove Ψ̃ e Ψ̃0
sono a loro volta due sequenze di reali ottenute escludendo i primi valori
testa, testa0 ∈ R da Ψ e Ψ0 rispettivamente, l’ordinamento lessicografico ≺ è
cosı̀ definito per induzione sulla lunghezza l:
• se l = 1,
Ψ ≺ Ψ0 ⇔ testa < testa0
• se l > 1,
Ψ ≺ Ψ0 ⇔ (testa < testa0 ∨ (testa = testa0 ∧ Ψ̃ ≺ Ψ̃0 ))
Esponiamo ora la notazione utilizzata in questo paragrafo:
• µ = (α, Pold (α), colorold , Pnew (α), colornew ) è una generica mossa del
gioco effettuata dall’agente α che induce il passaggio dal routing Rold
al routing Rnew ;
• A è l’insieme degli agenti che condividevano almeno un arco del loro
percorso con α nel routing Rold e che non condividono nessun arco con
α nel routing Rnew ;
• B è l’insieme degli agenti che condividono almeno un arco del loro
percorso con α nel routing Rnew .
Denotiamo con Π la classe di funzioni di pagamento π che per ogni
possibile mossa del gioco rispettino le seguenti condizioni:
∀β ∈ A, πRnew (β) ≤ πRold (β)
(3.1)
3.3 Una classe di funzioni di pagamento inducenti
un gioco con alto prezzo dell’anarchia
43
∀β ∈ B, πRnew (β) > πRold (β) ⇒ πRnew (β) ≤ πRnew (α)
(3.2)
Teorema 3.2.1. Le funzioni di pagamento della classe Π inducono un gioco
convergente.
Dimostrazione. Sia Ψold la sequenza dei costi πRold (β) ∀β ∈ I ordinati in
modo non crescente, e sia Ψnew la sequenza dei costi πRnew (β) ∀β ∈ I ordinati in modo non crescente, ovvero la nuova sequenza dei costi derivanti
dall’esecuzione da parte dell’agente α della mossa µ.
Per definizione della classe Π, la mossa µ dell’agente α può far innalzare
il costo di ogni altro agente al più fino a πRnew (α). Essendo inoltre
πRnew (α) ≤ πRold (α)
otteniamo
Ψnew ≺ Ψold
cioè la sequenza Ψnew è secondo l’ordinamento lessicografico minore della
sequenza Ψold .
Poiché la sequenza Ψ0 = 0, 0, 0, . . . è il bottom dell’ordinamento lessicografico, e ogni possibile mossa di un agente è associata ad un arco del grafo
dell’evoluzione di gioco, ne consegue che tale grafo non può contenere alcun
ciclo, e questo conclude la dimostrazione.
Nota 3.3. Il numero di passi in cui il gioco converge non è in generale
polinomiale in |I|.
3.3
La classe Ξ di funzioni di pagamento inducenti un gioco con alto prezzo
dell’anarchia
In questo paragrafo definiamo una classe di funzioni di pagamento che
inducono un gioco G = (G, I, f, p) con coordination ratio ρ =
|I|
,
w(G,I)
che
3.3 Una classe di funzioni di pagamento inducenti
un gioco con alto prezzo dell’anarchia
44
è evidentemente il peggior coordination ratio possibile in quanto qualsiasi
soluzione ammissibile per un problema utilizza al più |I| colori e w(G, I) è la
soluzione ottima del problema.
Denotiamo con Ξ = Ξ0 ∪ Ξ00 la classe di funzioni di pagamento ξR=(R,c)
che rispettino almeno una delle seguenti condizioni:
Sottoclasse Ξ0 : ∀α ∈ I, ξ(α) dipende unicamente dal colore c(α) ed inoltre
ξR (α) ≥ ξR0 =(R0 ,c0 ) (α) ⇐ c(α) ≥ c0 (α),
ovvero il costo per ogni agente dipende unicamente dal proprio colore
assunto nel routing ed ad ogni agente α non conviene mai fare una
mossa (α, Pold (α), colorold , Pnew (α), colornew ) in cui colornew ≥ colorold .
Sottoclasse Ξ00 : ∀α ∈ I,
ξ(α) = maxe∈R(α) g(σ(e))
dove g : 2W → R è tale che per ogni A e B insiemi di colori
A \ {d} ⊆ B ⇒ g(A) ≤ g(B ∪ {d0 })
con d ∈ A, d0 ≥ d e d0 ∈
/ B. In altre parole, l’immagine (g(B ∪ {d0 }))
secondo g di un primo insieme (B ∪ {d0 }) che contiene almeno tutti gli
elementi di un secondo insieme (A) tranne al più un elemento (d) che nel
primo insieme deve eventualmente essere sostituito da uno strettamente
maggiore (d0 ), non può essere minore dell’immagine (g(A)) del secondo
insieme.
Teorema 3.3.1.
Ξ⊆Π
Dimostrazione. Dimostriamo che per ogni funzione di pagamento p,
p ∈ Ξ0 ⇒ p ∈ Π
e
p ∈ Ξ00 ⇒ p ∈ Π
3.3 Una classe di funzioni di pagamento inducenti
un gioco con alto prezzo dell’anarchia
45
Sia (α, Pold (α), colorold , Pnew (α), colornew ) una generica mossa del gioco
effettuata dall’agente α che induce il passaggio dal routing Rold al routing
Rnew .
Se p ∈ Ξ0 , allora entrambe le condizioni di appartenenza alla classe Π 3.1
e 3.2 sono verificate in quanto ∀β 6= α, β ∈ I, pRnew (β) = pRold (β)
Se p ∈ Ξ00 , allora la condizione 3.1 è verificata in quanto, posto d = d0 ,
d ∈ A, d ∈
/ B e C = B ∪ {d}, si ha
A ⊆ C ⇒ A \ {d} ⊆ B ⇒ g(A) ≤ g(C)
e dunque i costi degli agenti che in Rnew non condividono più alcun arco con
α non possono aumentare. La condizione 3.2 è verificata per la struttura
della funzione di pagamento p(α) = maxe∈R(α) g(σ(e)), in quanto l’operatore
massimo assicura che laddove il costo degli agenti che vengono a condividere
almeno un arco con α in Rnew cresca, non può mai superare il costo pRnew (α).
Corollario 3.3.2. Le funzioni di pagamento della classe Ξ sono convergenti.
Teorema 3.3.3. Le funzioni di pagamento della classe Ξ inducono un gioco
G = (G, I, f, p) il cui coordination ratio ρ =
|I|
.
w(G,I)
Dimostrazione. Si consideri una rete avente come topologia un anello G di
|I| nodi (v1 , . . . , v|I| ), e l’istanza I = {{vi , v(i+1)mod |I| }|i ∈ {1, . . . , |I|}}.
Il routing R∗ = (R∗ , c∗ ) dove ∀i ∈ {1, . . . , |I|}
R∗ ({vi , v(i+1)mod |I| }) = {{vi , v(i+1)mod |I| }}
e
c∗ ({vi , v(i+1)mod |I| ) = 1
è tale che C(R∗ ) = 1 e dunque w(G, I)=1.
Se ora consideriamo il routing R = (R, c) dove ∀i ∈ {1, . . . , |I|}
R({vi , v(i+1)mod |I| }) = {{vj mod |I| , v(j+1)mod |I| }|j ∈ {i + 1, . . . , i + |I| − 1}}
3.4 Informazione completa
46
e
c({vi , v(i+1)mod |I| ) = i
abbiamo che R è in equilibrio di Nash per definizione delle funzioni ξ ∈ Ξ.
Prima di tutto notiamo che nel routing R, σ({vi , v(i+1)mod |I| }) = {1, . . . , i −
1, i + 1, . . . , |I|} ∀i ∈ {1, . . . , |I|}, ovvero ogni arco {vi , v(i+1)mod |I| } dell’anello
è occupato da tutti i colori tranne il colore i. La dimostrazione prosegue
quindi per casi. A seconda della sottoclasse della funzione ξ abbiamo:
Sottoclasse Ξ0 Nessun agente {vi , v(i+1)mod |I| }, i ∈ {1, . . . , |I|} ha convenienza nell’effettuare una mossa poiché non può in nessun modo
acquisire un colore minore di i;
Sottoclasse Ξ00 Nessun agente α = {vi , v(i+1)mod |I| }, i ∈ {1, . . . , |I|} ha convenienza nell’effettuare una mossa poiché sia se si spostasse sull’unico
arco {vi , v(i+1)mod |I| }, che rimanesse sul percorso di |I| − 1 archi cambiando colore, si ritroverebbe con un nuovo percorso (in un routing R0 )
contenente almeno un arco con insieme dei colori
B ∪ {d0 }|B ⊇ σ(e) \ c(α) ∀e ∈ R(α), d0 ≥ c(α)
e dunque risulterebbe ξR0 (α) ≥ ξR (α).
Essendo C(R) = |I|, otteniamo che il coordination ratio ρ ≥ |I|.
Il teorema per w(G, I) = 1 segue dall’osservazione che per ogni routing
R ammissibile si ha C(R) ≤ |I|
La dimostrazione per valori w(G, I) > 1 si ottiene semplicemente modificando l’istanza ripetendo ogni richiesta w(G, I) volte. In questo modo
abbiamo in modo del tutto simile un routing in equilibrio di Nash che usa
sempre |I| colori, ottenendo quindi un coordination ratio ρ =
3.4
|I|
w(G,I)
Informazione completa
In questo paragrafo consideriamo funzioni di pagamento nel contesto di
reti con informazione completa. In tale contesto la funzione di pagamento
può quindi dipendere sia dall’istanza I che dal routing corrente R.
3.4 Informazione completa
47
Il seguente teorema dimostra come qualsiasi algoritmo centralizzato può
essere in modo opportuno utilizzato anche per il caso non cooperativo, facendo sı̀ che il coordination ratio sia 1 o k se l’algoritmo utilizzato è ottimo
o k-approssimante rispettivamente.
Teorema 3.4.1. Sia A un qualsiasi algoritmo che risolva il problema (G, I)
con rapporto di approssimazione k (k = 1 se A è ottimo) e avente come
output il routing R̃ = (R̃, c̃).
Allora, dato il




A
pR (α) =



routing R = (R, c), la funzione di pagamento
0 se R(α) = R̃(α) ∧ c(α) = c̃(α)
2 se (R(α) 6= R̃(α) ∨ c(α) 6= c̃(α)) ∧ c(α) ≤ C(R̃)
1 se (R(α) 6= R̃(α) ∨ c(α) 6= c̃(α)) ∧ c(α) > C(R̃)
è convergente, e l’unico equilibrio di Nash possibile per il gioco G da lei indotto
è R̃. Il coordination ratio di G è k, la complessità computazionale della
funzione pA è al più la stessa dell’algoritmo A e il numero di mosse in cui
G converge è al più 3|I|.
Dimostrazione.
Convergenza Dimostriamo dapprima la convergenza del gioco G in al più
3|I| mosse. Poiché la funzione di pagamento è tale che la mossa di un
agente non fa mutare il costo di nessun altro agente, ed ha codominio
finito di cardinalità 3, ogni agente può effettuare durante il gioco al più
3 mosse, e dunque il gioco converge in 3|I| mosse.
Unicità Mostriamo ora come l’unico equilibrio di Nash di G sia R̃.
Supponiamo per assurdo che in un routing R in equilibrio di Nash
esista almeno un agente α per il quale p(α) = 2. L’agente α potrebbe
certamente effettuare una mossa semplicemente assumendo un colore
c(α) > C(R̃) in modo da assumere costo 1, e ciò contraddice che R è
in equilibrio di Nash.
Supponiamo ora per assurdo che in un routing R in equilibrio di Nash
esista almeno un agente α per il quale p(α) = 1. Tale agente nel routing
3.5 Informazione minimale
48
R ha dunque assegnato un colore c(α) > C(R̃). Avendo già dimostrato
che in un equilibrio di Nash nessun agente ha costo 2, per la definizione
della funzione di pagamento possiamo affermare che nessun agente nel
routing R sta occupando un colore c(α) ≤ C(R̃) senza che R(α) =
R̃(α) ∧ c(α) = c̃(α), ovvero senza che si trovi sullo stesso percorso e
con lo stesso colore del routing R̃. Per l’agente α è quindi possibile
effettuare una mossa che lo porti sullo stesso percorso e colore di R̃, in
modo da assumere costo 0, e ciò contraddice che R è in equilibrio di
Nash.
Abbiamo mostrato come in un routing R in equilibrio di Nash pR (α) =
0 ∀α ∈ I; per la definizione di pA
R ogni agente si trova sullo stesso
percorso e colore del routing R̃, e dunque R = R̃.
Le rimanenti asserzioni del teorema sono facilmente verificabili: il coordination ratio di G è semplicemente il rapporto di approssimazione di A poiché
l’unico equilibrio di Nash per G è proprio il routing R̃, ed infine ogni agente
per calcolare la funzione di pagamento deve individuare il percorso e il colore
che gli assegnerebbe l’algoritmo A, e questo vuol dire nel peggiore dei casi
computare nella sua interezza A.
3.5
Informazione minimale
Sebbene i risultati ottenuti nel paragrafo precedente relativo al livello di
informazione completa siano soddisfacenti poiché sono stati individuati giochi
velocemente convergenti e con coordination ratio pari a quello di qualsiasi
algoritmo efficiente centralizzato, va sottolineato che l’assunzione che ogni
agente ha una visione dell’intera istanza e dell’intero routing è molto forte, e
in reti ottiche reali ciò potrebbe essere non realizzabile per motivi tecnologici
e non desiderabile per problematiche legali legate ad esempio alla privacy.
Per questi motivi in questo e nel prossimo paragrafo verranno esposte funzioni di pagamento con un livello di informazione più ristretta, ed analizzati
3.5 Informazione minimale
49
i giochi indotti da tali funzioni secondo i criteri dell’esistenza dell’equilibrio,
della convergenza del gioco e del prezzo dell’anarchia.
Il livello di informazione minimale, considerato in questo paragrafo, dà ad
ogni singolo agente unicamente informazione su quali lunghezze d’onda sono
disponibili lungo i vari percorsi che connettono i due nodi relativi all’agente
stesso.
La funzione di pagamento p relativa all’agente α non può dipendere dall’istanza I e dallo stato della rete di comunicazione; può dipendere da σ̄ ℘α ,
cioè dallo stato dei percorsi della rete di comunicazione con dominio ristretto
ai percorsi relativi all’agente α, oltre che, naturalmente, dal percorso e dal
colore in uso dall’agente α.
Analizziamo ora due funzioni di pagamento convergenti. Possiamo però notare come la perdita di informazione fa sı̀ che le funzioni analizzate
inducano un gioco con alto prezzo dell’anarchia.
La funzione di pagamento pI
pIR (α) = f (c(α))
Questa funzione di pagamento fa sı̀ che ogni agente paghi unicamente in
funzione del colore che usa nel routing. Intuitivamente, essendo la funzione
di prezzatura f non decrescente, si vuole indurre ogni agente a posizionarsi su
un percorso qualsiasi ma con il colore più basso possibile, in modo da tentare
di minimizzare il numero totale di colori utilizzati.
Teorema 3.5.1. La funzione di pagamento pI appartiene alla classe Ξ.
Dimostrazione. La funzione di pagamento pI appartiene alla sottoclasse Ξ0
di Ξ in quanto il costo per un agente α nel routing R = (R, c) dipende
unicamente da c(α), e la funzione di pagamento è non decrescente al crescere
del colore c(α) (poiché la funzione di prezzatura f è per definizione non
decrescente).
3.5 Informazione minimale
50
Corollario 3.5.2. La funzione di pagamento pI è convergente ed induce un
gioco G = (G, I, g, p) con coordination ratio ρ =
|I|
.
w(G,I)
Teorema 3.5.3. La funzione di pagamento pI induce un gioco G =
(G, I, g, p) che converge in al più |I|2 mosse.
Dimostrazione. Sotto l’assunzione che nessun agente faccia mosse stupide
assumendo un colore strettamente maggiore di |I|, il teorema segue dall’osservazione che, poiché le mosse di un agente non fanno mutare i costi degli
altri agenti, ogni agente può effettuare al più |I| mosse.
La funzione di pagamento pII
pII
R=(R,c) (α) =
max
k∈σ̄ Pα (R(α))
f (k)
Questa funzione di pagamento fa sı̀ che ogni agente paghi in funzione del
più alto colore (tra il suo e quelli utilizzati da altri agenti) che incontra lungo
il proprio percorso di routing.
Teorema 3.5.4. La funzione di pagamento pII appartiene alla classe Ξ.
Dimostrazione. Mostriamo che la funzione di pagamento pII appartiene alla
sottoclasse Ξ00 di Ξ.
Notiamo innanzitutto che la funzione pII può essere equivalentemente
formulata nel seguente modo:
pII
R (α) = max
max f (k)
e∈R(α) k∈σ Eα (e)
Per dimostrare l’appartenenza a Ξ00 è sufficiente mostrare che g(σ(e)) =
maxk∈σ(e) f (k) goda, per ogni A e B insiemi di colori, della proprietà
A \ {d} ⊆ B ⇒ g(A) ≤ g(B ∪ {d0 })
con d ∈ A, d0 ≥ d e d0 ∈
/ B.
3.6 Informazione intermedia
51
Essendo A \ {d} ⊆ B e poiché, per la non decrescenza di f , f (d) ≤ f (d0 ),
abbiamo
g(B ∪ {d0 }) = max{f (d0 ), max f (k)} ≥ max{f (d), max f (k)} = g(A)
k∈B
k∈A\{d}
Corollario 3.5.5. La funzione di pagamento pII è convergente ed induce un
gioco G = (G, I, g, p) con coordination ratio ρ =
3.6
|I|
.
w(G,I)
Informazione intermedia
Nel tentativo di recuperare il prezzo pagato in termini di coordination
ratio passando dal livello di informazione completa a quello minimale, in
questo paragrafo consideriamo il livello di informazione intermedia, che dà ad
ogni singolo agente unicamente informazione su quali lunghezze d’onda sono
disponibili e quali occupate in ogni arco utilizzato dai percorsi che connettono
i due nodi relativi all’agente stesso.
La funzione di pagamento p relativa all’agente α non può dipendere dall’istanza I, ma può dipendere dallo stato σ Eα della rete di comunicazione con
dominio ristretto agli archi relativi all’agente α, oltre che, naturalmente, dal
percorso e dal colore in uso dall’agente α.
La funzione di pagamento pIII
pIII
R=(R,c) (α) = max
e∈R(α)
X
f (k)
k∈σ Eα (e)
Questa funzione di pagamento fa sı̀ che ogni arco sia prezzato con la
somma delle immagini (secondo la funzione di prezzatura f ) dei colori ad
esso associati. Ogni agente paga il prezzo del massimo arco del proprio
percorso di routing.
Teorema 3.6.1. La funzione di pagamento pIII appartiene alla classe Ξ.
3.6 Informazione intermedia
52
Dimostrazione. Mostriamo che la funzione di pagamento pIII appartiene alla
sottoclasse Ξ00 di Ξ.
Per dimostrare l’appartenenza a Ξ00 è sufficiente mostrare che g(σ(e)) =
P
k∈σ(e)
f (k) goda, per ogni A e B insiemi di colori, della proprietà
A \ {d} ⊆ B ⇒ g(A) ≤ g(B ∪ {d0 })
con d ∈ A, d0 ≥ d e d0 ∈
/ B.
Essendo A \ {d} ⊆ B ed essendo f positiva e non decrescente, abbiamo
g(B ∪ {d0 }) = f (d0 ) +
X
X
f (k) ≥ f (d) +
k∈B
f (k) = g(A)
k∈A\{d}
Corollario 3.6.2. La funzione di pagamento pIII è convergente ed induce
un gioco G = (G, I, g, p) con coordination ratio ρ =
3.6.1
|I|
.
w(G,I)
Funzioni di pagamento non convergenti
Le funzioni di pagamento analizzate finora sono convergenti, ma
purtroppo inducono un gioco con pessimo coordination ratio.
Tutte le altre funzioni di pagamento più naturali analizzate, esposte di
seguito, sono risultate purtroppo essere non convergenti, e per quasi tutte è
stata dimostrata essere non garantita l’esistenza dell’equilibrio di Nash nel
gioco da loro indotto.
La funzione di pagamento pIV
pIV
R=(R,c) (α) =
X
e∈R(α)
max f (k)
k∈σ Eα (e)
Questa funzione di pagamento fa sı̀ che ogni arco sia prezzato in funzione
del massimo colore ad esso associato. Ogni agente paga la somma dei prezzi
degli archi del proprio percorso di routing.
3.6 Informazione intermedia
53
Teorema 3.6.3. Nei giochi indotti dalla funzione di pagamento pIV non è assicurata l’esistenza dell’equilibrio di Nash per nessuna funzione di prezzatura
f non limitata superiormente.
Dimostrazione. Mostriamo come nel problema determinato dal grafo in
Figura 3.1 e dall’istanza
I = {{a, ci }, {b, di } |i ∈ {1, 2, . . . , n, n + 1}}
| {z }
m volte
l’equilibrio di Nash non esiste per nessuna funzione di prezzatura f non
limitata superiormente.
I parametri m, n, h e k dipendono dalla funzione di prezzatura f e devono
essere scelti opportunamente come mostrato in questa dimostrazione.
Imponiamo ora alcune condizioni che dimostriamo essere sufficienti per
la non esistenza dell’equilibrio di Nash.
Innanzitutto imponiamo tre condizioni tecniche:
n > m > 1,
(3.3)
f (n + 1) > f (n),
(3.4)
f (m + 1) > f (m).
(3.5)
Chiaramente, gli agenti {b, di } in una situazione di equilibrio di Nash
possono utilizzare al più il colore m + 1 (o un colore x tale che f (x) =
f (m + 1)), laddove l’arco {b, ci } sia utilizzato da una richiesta {a, ci } con un
colore al più pari ad m, e possono utilizzare al più il colore m altrimenti.
Consideriamo ora gli agenti {a, ci }: per la condizione tecnica 3.4 e per le
seguenti condizioni che imponiamo
2f (n) < (h + k)f (1),
(3.6)
2f (n) < hf (1) + f (m + 1),
(3.7)
(k + 1)f (m) < 2f (n + 1),
(3.8)
3.6 Informazione intermedia
54
d2
ka
rch
i
c2
k archi
dn+1
cn+1
c1
b
d1
k archi
h archi
a
Figura 3.1: In questo grafo tra i nodi a e b ci sono due cammini, uno costituito
da un unico arco e l’altro da h archi; inoltre tra ogni coppia di nodi b e ci ci
sono due cammini, uno costituito da un unico arco e l’altro da k archi.
3.6 Informazione intermedia
55
(k + 1)f (m) < (h + k)f (1),
(3.9)
(k + 1)f (m) < hf (1) + f (m + 1),
(3.10)
esattamente n di essi devono utilizzare nel proprio percorso di routing l’arco
{a, b} con i colori da 1 a n. Si noti come nelle condizioni 3.7 e 3.10 la presenza
nel membro di destra della quantità f (m + 1) in luogo di f (1) è giustificata
dalla ulteriore condizione
2f (m + 1) < (k + 1)f (1)
(3.11)
che imponiamo, secondo la quale nell’arco {b, ci } devono confluire gli m agenti
{b, di } qualora possano utilizzare un colore al più pari a m + 1.
Analizziamo poi le possibili situazioni per casi:
• Se sull’arco {a, b} fosse libero un colore x al più pari ad m, e tale colore
x fosse disponibile anche sull’arco {b, ci }, la richiesta {a, ci } non sarebbe
in equilibrio usando un colore almeno pari a n + 1 o passando per la
catena di h archi per le condizioni 3.6, 3.7 e 3.11.
• Se sull’arco {a, b} fosse libero un colore x al più pari ad m, e tale colore
x non fosse disponibile sull’arco {b, ci }, ma quindi fosse disponibile
sulla catena di k archi corrispondente, la richiesta {a, ci } non sarebbe
in equilibrio usando un colore almeno pari a n + 1 o passando per la
catena di h archi per le condizioni 3.8, 3.9, 3.10 e 3.11.
• Se sull’arco {a, b} fosse libero un colore x compreso nell’intervallo [m +
1, n], la richiesta {a, ci } non sarebbe in equilibrio usando un colore
almeno pari a n+1 o passando per la catena di h archi per le condizioni
3.6, 3.7 e 3.11, in quanto il colore x non può essere occupato dalle
richieste {b, di } (in una situazione di equilibrio) sull’arco {b, ci }.
Siano ora α l’agente {a, cı̄ } rimasto escluso dalla precedente analisi e
β1 , . . . , βm gli m agenti {b, cı̄ }.
α non sarebbe in equilibrio attraversando la catena di k archi poiché
imponiamo
2f (n + 1) < (h + k)f (1),
(3.12)
3.6 Informazione intermedia
56
2f (n + 1) < (1 + k)f (n + 1).
(3.13)
α non sarebbe in equilibrio attraversando la catena di h archi con un colore
maggiore o pari a m + 1 poiché imponiamo
2f (n + 1) < (h + 1)f (m + 1).
(3.14)
Se l’arco {b, cı̄ } è libero, α non sarebbe in equilibrio sul percorso costituito
dai due archi {a, b} e {b, cı̄ } dove il primo colore che può utilizzare è n + 1
poiché imponiamo
(h + 1)f (1) < 2f (n + 1).
(3.15)
Se l’arco {b, cı̄ } è occupato dagli agenti β, α non sarebbe in equilibrio sul
percorso costituito dalla catena di h archi e dall’arco {b, cı̄ } pur utilizzando
il colore 1 poiché imponiamo
2f (n + 1) < hf (1) + f (m + 1).
(3.16)
Infine per la 3.11 gli agenti β non sono in equilibrio sulla catena di k archi
quando sull’arco {b, cı̄ } non è presente un colore superiore a m + 1, e non
sono in equilibrio sull’unico arco {b, cı̄ } quando su di esso è presente un colore
almeno pari a n + 1 poiché imponiamo
kf (m) < f (n + 1).
(3.17)
Mostriamo ora come l’agente α e gli agenti β non possano mai trovarsi in
una situazione di equilibrio di Nash, procedendo per casi.
• L’agente α si posiziona sulla catena di h archi con un colore pari al
più a m (per la 3.14), ed esiste almeno un agente β̄ posizionato sulla
catena di k archi.
Questa situazione non è di equilibrio poiché β̄ per la 3.11 può effettuare
una mossa spostandosi sull’arco {b, cı̄ }.
• L’agente α si posiziona sulla catena di h archi con un colore pari al più
a m (per la 3.14), e tutti gli agenti β sono posizionati sull’arco {b, cı̄ }.
3.6 Informazione intermedia
57
Questa situazione non è di equilibrio poiché α per la 3.16 può effettuare
una mossa spostandosi sul percorso di due archi utilizzando il colore
n + 1.
• L’agente α si posiziona sull’arco {a, b} con un colore almeno pari a n+1
ed esiste almeno un agente β̄ posizionato sull’unico arco {b, cı̄ }.
Questa situazione non è di equilibrio poiché β̄ per la 3.17 può effettuare
una mossa spostandosi sulla catena di k archi.
• L’agente α si posiziona sull’arco {a, b} con un colore almeno pari a n+1
e tutti gli agenti β sono posizionati sulla catena di k archi.
Questa situazione non è di equilibrio poiché α per la 3.15 può effettuare
una mossa spostandosi sulla catena di h archi.
Concludiamo la dimostrazione illustrando come sia possibile verificare
tutte le condizioni imposte.
Notiamo che alcune condizioni sono implicate da altre:
3.16 ∧ 3.3 ∧ 3.5 ⇒ 3.14 in quanto
2f (n + 1) < hf (1) + f (m + 1) < hf (m + 1) + f (m + 1) = (h + 1)f (m + 1);
3.16 ⇒ 3.7 in quanto
2f (n) ≤ 2f (n + 1) < hf (1) + f (m + 1);
3.11 ∧ 3.16 ⇒ 3.12 in quanto
2f (n + 1) < hf (1) + f (m + 1) < hf (1) + kf (1) = (h + k)f (1);
3.12 ⇒ 3.6 in quanto
2f (n) ≤ 2f (n + 1) < (h + k)f (1);
3.11 ∧ 3.3 ∧ 3.5 ⇒ 3.13 in quanto
k>
f (m + 1)
> 1 ⇒ 2f (n + 1) < (1 + k)f (n + 1);
f (1)
3.6 Informazione intermedia
58
3.17 ⇒ 3.8 in quanto
(k + 1)f (m) = kf (m) + f (m) < f (n + 1) + f (n + 1) = 2f (n + 1);
3.8 ∧ 3.12 ⇒ 3.9 in quanto
(k + 1)f (m) < 2f (n + 1) < (h + k)f (1);
3.8 ∧ 3.16 ⇒ 3.9 in quanto
(k + 1)f (m) < 2f (n + 1) < hf (1) + f (m + 1).
Dalle rimanenti condizioni 3.11, 3.15, 3.16 e 3.17 ricaviamo
2f (n + 1) − f (1)
2f (n + 1) − f (m + 1)
<h<
f (1)
f (1)
e
f (n + 1)
2f (m + 1) − f (1)
<k<
.
f (1)
f (m)
L’esistenza di h e k interi è assicurata da f (m + 1) > 2f (1) e f (n +
1) >
2f (m)f (m+1)
f (1)
che rendono gli intervalli suddetti di ampiezza strettamente
maggiore di 1.
Infine, per rispettare anche le condizioni tecniche è sufficiente scegliere



 f (m + 1) > 2f (1)
m tale che
ed
n tale che
f (m + 1) > f (m)


 m>1



 f (n + 1) >
2f (m)f (m+1)
f (1)
f (n + 1) > f (n)


 n > m.
Essendo per ipotesi la funzione f non limitata superiormente, tutte le
richieste sono soddisfacibili.
Corollario 3.6.4. La funzione di pagamento pIV non è convergente.
3.6 Informazione intermedia
59
Le funzioni di pagamento pV , pV I , pV II e pV III
Queste funzioni di pagamento sono accomunate dal fatto che il prezzo di
ogni arco viene equamente ripartito tra tutti gli agenti che lo utilizzano.
X maxk∈σEα (e) f (k)
|σ Eα (e)|
pVR=(R,c) (α) =
e∈R(α)
maxk∈σEα (e) f (k)
e∈R(α)
|σ Eα (e)|
I
pVR=(R,c)
(α) = max
Nelle funzioni pV e pV I ogni arco è prezzato in funzione del massimo
colore ad esso associato. La funzione pV fa sı̀ che ogni agente paghi la somma
dei prezzi ripartiti degli archi del proprio percorso di routing, mentre nella
funzione pV I ogni agente paga il massimo prezzo ripartito degli archi del
proprio percorso di routing.
P
II
pVR=(R,c)
(α) =
X
e∈R(α)
k∈σ Eα (e) f (k)
|σ Eα (e)|
P
III
pVR=(R,c)
(α) = max
e∈R(α)
k∈σ Eα (e) f (k)
|σ Eα (e)|
Nelle funzioni pV II e pV III ogni arco è prezzato con la somma delle immagini (secondo la funzione di prezzatura f ) dei colori ad esso associati. La
funzione pV II fa sı̀ che ogni agente paghi la somma dei prezzi ripartiti degli
archi del proprio percorso di routing, mentre nella funzione pV III ogni agente
paga il massimo prezzo ripartito degli archi del proprio percorso di routing.
Teorema 3.6.5. Nei giochi indotti dalle funzioni di pagamento pV e pV I
non è assicurata l’esistenza dell’equilibrio di Nash per nessuna funzione di
prezzatura f tale che ∃k : f (k) > 2f (1).
Dimostrazione. Mostriamo come nel problema determinato dal grafo in
Figura 3.2 e dall’istanza
I = {{a, ci }, {b, ci }|i ∈ {1, 2, . . . , n}}
3.6 Informazione intermedia
60
2
1
Figura 3.2: In questo grafo tra ogni coppia di nodi b e ci ci sono due archi.
3.6 Informazione intermedia
61
l’equilibrio di Nash non esiste per nessuna funzione di prezzatura f tale che
∃k : f (k) > 2f (1).
Il parametro n dipende dalla funzione di prezzatura f e deve essere scelto
opportunamente: sia n il più piccolo intero che verifichi f (n) > 2f (1).
Si noti che in ogni routing deve esistere un agente {a, ci } che utilizza un
colore almeno pari a n. Sia α = {a, cı̄ } uno di questi agenti e sia β = {b, cı̄ }.
Chiaramente β deve utilizzare in un routing in equilibrio di Nash un colore
strettamente minore di n.
Mostriamo ora come l’agente α e l’agente β non possano mai trovarsi in
una situazione di equilibrio di Nash, procedendo per casi.
• L’agente α e l’agente β si posizionano sullo stesso arco.
Questa situazione non è di equilibrio poiché β può effettuare una mossa
in modo da non condividere l’arco con α, in quanto
f (1) <
f (n)
.
2
Si noti che dal punto di vista di β le due funzioni di pagamento pV e
pV I sono indifferenti poiché tutti i possibili percorsi di β sono costituiti
da un solo arco.
• L’agente α e l’agente β si posizionano su archi differenti.
Questa situazione non è di equilibrio poiché α può effettuare una mossa
in modo da condividere l’arco con β, in quanto
f (n)
< f (n).
2
Si noti che in una situazione di equilibrio di Nash l’arco {a, b} deve
costare per ogni agente {a, ci } esattamente
f (n)
.
n
Dunque α può effet-
tuare la suddetta mossa banalmente con la funzione di pagamento pV ,
e poiché
f (n)
n
< f (n) con la funzione di pagamento pV I .
3.6 Informazione intermedia
62
Corollario 3.6.6. La funzioni di pagamento pV e pV I non sono convergenti.
Teorema 3.6.7. Nei giochi indotti dalle funzioni di pagamento pV II e pV III
non è assicurata l’esistenza dell’equilibrio di Nash per nessuna funzione di
prezzatura f tale che ∃k : f (k) > f (1), ovvero per nessuna funzione di
prezzatura f non costante.
Dimostrazione. Questa dimostrazione ricalca quella del teorema 3.6.5.
Mostriamo come nel problema determinato dal grafo in Figura 3.2 e
dall’istanza
I = {{a, ci }, {b, ci }|i ∈ {1, 2, . . . , n}}
l’equilibrio di Nash non esiste per nessuna funzione di prezzatura f tale che
∃k : f (k) > f (1).
Il parametro n dipende dalla funzione di prezzatura f e deve essere scelto
opportunamente: sia n il più piccolo intero che verifichi f (n) > f (1).
Si noti che in ogni routing deve esistere un agente {a, ci } che utilizza un
colore almeno pari a n. Sia α = {a, cı̄ } tale agente, e sia β = {b, cı̄ }.
Chiaramente β deve utilizzare in un routing in equilibrio di Nash un colore
strettamente minore di n.
Mostriamo ora come l’agente α e l’agente β non possano mai trovarsi in
una situazione di equilibrio di Nash, procedendo per casi.
• L’agente α e l’agente β si posizionano sullo stesso arco.
Questa situazione non è di equilibrio poiché β può effettuare una mossa
in modo da non condividere l’arco con α, in quanto
f (1) <
f (1) + f (n)
.
2
Si noti che dal punto di vista di β le due funzioni di pagamento pV II e
pV III sono indifferenti poiché tutti i possibili percorsi di β sono costituiti
da un solo arco.
• L’agente α e l’agente β si posizionano su archi differenti.
3.6 Informazione intermedia
63
Questa situazione non è di equilibrio poiché α può effettuare una mossa
in modo da condividere l’arco con β, in quanto
f (1) + f (n)
< f (n).
2
Si noti che in una situazione di equilibrio di Nash l’arco {a, b} deve
costare per ogni agente {a, ci } esattamente
(n−1)f (1)+f (n)
.
n
Dunque α può
effettuare la suddetta mossa banalmente con la funzione di pagamento
pV I , e poiché
(n−1)f (1)+f (n)
n
< f (n) con la funzione di pagamento pV III .
Corollario 3.6.8. La funzioni di pagamento pV II e pV III non sono
convergenti.
Per le funzioni di pagamento pV II e pV III abbiamo una caratterizzazione
dei giochi indotti per ogni funzione di prezzatura f . Otteniamo infatti i
seguenti risultati per f costante.
Teorema 3.6.9. Se la funzione di prezzatura f è costante, la funzione di
pagamento pV II induce un gioco convergente in al più |I| mosse.
Dimostrazione. Ogni routing (non parziale) costa ad ogni agente 1 e dunque
è in equilibrio di Nash. Ciò vuol dire che ogni agente può effettuare un’unica
mossa e il gioco converge in al più |I| mosse.
Teorema 3.6.10. Se la funzione di prezzatura f è costante, la funzione di
pagamento pV III induce un gioco G = ((V, E), I, f, pV III ) convergente in al
più |E| · |I| mosse.
Dimostrazione. Ogni arco del percorso costa 1 ad ogni agente e dunque un
agente α = {x, y} è in equilibrio di Nash se e solo se si posiziona sul percorso
minimo tra x e y, ed inoltre una mossa di un agente non influisce sui costi
degli altri agenti. Ciò vuol dire che ogni agente può effettuare al più |E|
mosse.
3.6 Informazione intermedia
64
Nota 3.4. L’assunzione di una funzione di prezzatura costante è molto forte
e in verità poco ragionevole. Il coordination ratio ottenuto in questo modo è
facilmente verificabile essere pessimo.
La funzione di pagamento pIX
pIX
R=(R,c) (α) =
X
X
f (k)
e∈R(α) k∈σ Eα (e)
Questa funzione di pagamento fa sı̀ che ogni arco sia prezzato con la
somma delle immagini (secondo la funzione di prezzatura f ) dei colori ad
esso associati. Ogni agente paga la somma dei prezzi degli archi del proprio
percorso di routing.
Per questa funzione di pagamento non si è riuscito a dimostrare la non
esistenza dell’equilibrio di Nash, anche se la non convergenza della funzione
la fa fortemente sospettare.
Teorema 3.6.11. Non è assicurato che la funzione di pagamento pIX sia
convergente per nessuna funzione di prezzatura f tale che ∃k : f (k) > f (1) +
f (2).
Dimostrazione. Nel problema determinato dal grafo in Figura 3.3 e
dall’istanza
I = {α = {a, c}, β = {d, c}},
il grafo dell’evoluzione di gioco è ciclico per ogni funzione di prezzatura f
tale che ∃k : f (k) > f (1) + f (2).
I parametri n, h e k dipendono dalla funzione di prezzatura f e devono
essere scelti opportunamente come mostrato in questa dimostrazione.
Sia q l’arco {a, b}, q 0 il percorso formato dalla catena di h archi e dall’arco
{d, b}, s l’arco {b, c}, s0 la catena di k archi e r l’arco {d, b}.
Mostriamo come le seguenti condizioni siano sufficienti a dimostrare la
ciclicità del grafo dell’evoluzione di gioco:
(k + 1)f (2) < 2f (n) + f (n + 1),
(3.18)
3.6 Informazione intermedia
65
Figura 3.3: In questo grafo tra i nodi a e d c’è una catena di h archi, e tra i
nodi b e c ci sono due cammini, uno costituito da un unico arco e l’altro da
k archi.
2f (n) + f (1) < (k + 1)f (2),
(3.19)
(h + 2)f (1) + f (2) < 2f (n + 1),
(3.20)
2f (n + 1) < (h + 2)f (1) + f (n).
(3.21)
Si consideri il routing iniziale R0 = (R0 , c0 )
R0
R0
c0
pVRIII
(·)
0
α
q, s n + 1
2f (c + 1) + f (c)
β
r, s
2f (c) + f (c + 1)
n
β effettua la mossa
(β, {r, s}, n, {r, s0 }, 2)
in virtù della 3.18, facendo evolvere il gioco nel routing R1 = (R1 , c1 )
α effettua la mossa
(α, {q, s}, n + 1, {q 0 , s}, 1)
in virtù della 3.20, facendo evolvere il gioco nel routing R2 = (R2 , c2 )
3.6 Informazione intermedia
66
R1
R1
α
r, s
β
0
r, s
c1
pVRIII
(·)
1
n+1
2f (c + 1)
2
(k + 1)f (2)
R2
R2
c2
pVRIII
(·)
2
α
q0, s
1
(h + 2)f (1) + f (2)
β
r, s0
2
(k + 1)f (2) + f (1)
β effettua la mossa
(β, {r, s0 }, 2, {r, s}, n)
in virtù della 3.19, facendo evolvere il gioco nel routing R3 = (R3 , c3 )
R3
R3
c3
pVRIII
(·)
3
α
q0, s
1
(h + 2)f (1) + 2f (n)
β
r, s
n
2(f (n) + f (1))
α infine effettua la mossa
(α, {q 0 , s}, 1, {q, s}, n + 1)
in virtù della 3.21, facendo evolvere il gioco nel routing iniziale R0 .
Abbiamo dunque individuato un ciclo nel grafo dell’evoluzione di gioco.
Per completare la dimostrazione basta notare che per verificare le
condizioni 3.18, 3.19, 3.20 e 3.21 è sufficiente scegliere
0<
e
0<
2f (n) + f (1) − f (2)
2f (n) + f (n + 1) − f (2)
<k<
f (2)
f (2)
2f (n + 1) − f (n) − 2f (1)
2f (n1) − f (2) − 2f (1)
<h<
.
f (1)
f (1)
La scelta di
n : f (n) > f (1) + f (2)
3.6 Informazione intermedia
67
assicura che h e k esistano interi poiché rende l’ampiezza dei suddetti
intervalli strettamente maggiore di 1.
Capitolo 4
Riduzione del prezzo
dell’anarchia in reti ottiche con
topologie particolari
I risultati mostrati nel capitolo precedente per reti con topologia arbitraria, nel caso non di un livello di informazione minimale o intermedio non
sono del tutto soddisfacenti, poiché non permettono di ottenere equilibri con
un prezzo dell’anarchia inferiore al peggiore possibile. Per tale motivo in
questo capitolo analizziamo reti ottiche con topologie specifiche.
In particolare vengono riportati i risultati ottenuti per il problema del
routing in reti ottiche non cooperative con topologia ad anello, catena ed
albero.
4.1
Anelli
Un anello An = ({v1 , v2 , . . . , vn }, {{vi , v(i+1) mod n }|i ∈ {1, 2, . . . , n}}) è un
grafo che consiste di un unico ciclo di lunghezza n ≥ 3.
È una topologia molto diffusa in reti ottiche di comunicazione.
Nell’analisi che abbiamo effettuato, il problema del routing è stato separato nel problema dell’assegnazione di percorsi (routing puro) e nel proble-
4.1 Anelli
69
ma dell’allocazione di lunghezze d’onda, seguendo lo stesso approccio molto
diffuso in letteratura per algoritmi on-line o dinamici (si veda ad esempio
[23]).
4.1.1
Il problema del routing puro
Si noti innanzitutto che in un anello per ogni possibile richiesta sono
presenti esattamente due percorsi, l’unione dei quali genera l’intero anello.
Nelle funzioni di costo che consideriamo nei paragrafi successivi, i percorsi
sono assegnati secondo due modalità.
Percorsi su una linea In questo caso l’anello viene privato dell’arco
{vn , v1 } e dunque l’assegnazione dei percorsi viene effettuata sulla linea
risultante.
Percorsi minimi In questo caso ad ogni agente viene assegnato un percorso
con il minor numero di archi.
Dimostriamo ora che entrambi gli approcci comportano un load, πline e
πshort rispettivamente, che è al più il doppio del load ottimo π.
Teorema 4.1.1.
πline ≤ 2π
Dimostrazione. Partizioniamo gli agenti in due insiemi, L e M , in modo che
l’insieme M contenga tutti e soli gli agenti che, in un’assegnazione di percorsi
R∗ inducente il load ottimo π, passano per l’arco {vn , v1 }.
Risulta evidente che gli agenti dell’insieme L possiedono in R∗ lo stesso
percorso che viene loro assegnato nel routing puro Rline effettuato sulla linea,
comportando dunque un load al più pari a π.
Infine, per la definizione di load, |M | ≤ π e dunque assegnando agli agenti
in M un percorso in Rline differente da quello di R∗ , il load πline può crescere
al più di π.
4.1 Anelli
70
Teorema 4.1.2.
πshort ≤ 2π
Dimostrazione. Sia e
π(G, I, Rshort , e)
=
=
{vi , v(i+1) mod n } un arco dell’anello tale che
π(G, I, Rshort ).
Se consideriamo l’arco e0
=
{v(i+b n2 c) mod n , v(i+1+b n2 c) mod n } opposto ad e, possiamo notare che nessuna
richiesta che in Rshort attraversa e può attraversare anche e0 . Quindi, in
ogni routing che non fa passare x richieste per e, queste x richieste devono
di forza passare per e0 . Dunque nessun routing puro può ottenere un load
strettamente minore di
4.1.2
πshort
.
2
Informazione minimale
Ricordiamo che il livello di informazione minimale, considerato in questo paragrafo, dà ad ogni singolo agente unicamente informazione su quali
lunghezze d’onda sono disponibili lungo i due percorsi che connettono i nodi
relativi all’agente stesso.
La funzione di pagamento p relativa all’agente α non può dipendere dall’istanza I e dallo stato della rete di comunicazione; può dipendere da σ̄ ℘α ,
cioè dallo stato dei percorsi della rete di comunicazione con dominio ristretto
ai percorsi relativi all’agente α, oltre che, naturalmente, dal percorso e dal
colore in uso dall’agente α.
Funzione di pagamento asimmetrica
Tutte le funzioni di pagamento discusse finora in questa tesi sono funzioni
simmetriche rispetto agli archi della rete. La funzione pX presentata di seguito è invece asimmetrica, nel senso che gli archi della rete di comunicazione
non vengono considerati tutti allo stesso modo, ma, nel caso specifico, un
arco è altamente costoso, in modo da ridurre di fatto l’anello ad una linea
poiché in un routing in equilibrio di Nash esso non può essere presente in
nessun percorso.
4.1 Anelli
71
(
pX
R=(R,c) (α)
=
se {vn , v1 } ∈ R(α)
1
1−
1
c(α)
altrimenti
In questo modo, nessun agente può essere in equilibrio attraversando l’arco {vn , v1 }, ed inoltre ogni agente è incentivato a scegliere il colore più basso
possibile.
Teorema 4.1.3. La funzione di pagamento pX appartiene alla classe Π.
Dimostrazione. La funzione di pagamento pX rispetta in modo banale le condizioni 3.1 e 3.2 poiché la mossa di un agente non può modificare il pagamento
di nessun altro agente.
Corollario 4.1.4. La funzione di pagamento pX è convergente.
Teorema 4.1.5. La funzione di pagamento pX induce un gioco G =
(G, I, g, p) che converge in al più |I|2 mosse.
Dimostrazione. Sotto l’assunzione che nessun agente faccia mosse stupide
assumendo un colore strettamente maggiore di |I|, il teorema segue dall’osservazione che, poiché le mosse di un agente non fanno mutare i costi degli
altri agenti, ogni agente può effettuare al più |I| mosse.
Il seguente risultato ottenuto da Kierstead è necessario per stimare il
coordination ratio del gioco indotto dalla funzione di pagamento pX .
Lemma 4.1.6 (Kierstead [31]). La strategia First-Fit colora on-line un
grafo a intervalli con al più 25.72π colori, dove un grafo a intervalli è il
grafo dei conflitti che si ottiene quando la topologia della rete è una linea.
Teorema 4.1.7. La funzione di pagamento pX induce su una rete con
topologia ad anello un gioco con coordination ratio ρ = 51.44.
Dimostrazione. Notiamo prima di tutto che un routing R in equilibrio di
Nash per la funzione di pagamento pX può essere pensato come il risultato
dell’applicazione della strategia First-Fit alla colorazione dei percorsi (fissati
4.1 Anelli
72
a priori) corrispondenti alle richieste in istanza, presentati ad un algoritmo
on-line in ordine non decrescente rispetto al colore ottenuto in R.
Per la definizione di pX , in R nessun agente può utilizzare l’arco {vn , v1 }
e quindi il grafo dei conflitti associato al problema è un grafo a intervalli.
Il teorema segue dalla composizione del Teorema 4.1.1 e del Lemma 4.1.6.
Funzione di pagamento simmetrica
La funzione di pagamento pXI presentata in questo paragrafo ha il pregio,
confrontata con pX , di essere simmetrica rispetto agli archi della rete, ma ha
il difetto di indurre un gioco il cui coordination non è costante, ma dipende
dalla lunghezza n dell’anello.
pXI
R=(R,c) = |R(α)| −
1
c(α)
Intuitivamente, un routing è in equilibrio di Nash se e solo se ogni richiesta
si posiziona su un percorso minimo con il colore più basso disponibile1 .
Anche in questa funzione di costo, dunque, un routing R in equilibrio
di Nash può essere pensato come il risultato dell’applicazione della strategia
First-Fit alla colorazione dei percorsi minimi (fissati a priori) corrispondenti
alle richieste in istanza, presentati ad un algoritmo on-line in ordine non
decrescente rispetto al colore ottenuto in R.
Esattamente allo stesso modo della funzione di pagamento pX , valgono
anche per questa funzione di pagamento i seguenti teoremi.
Teorema 4.1.8. La funzione di pagamento pXI appartiene alla classe Π.
Corollario 4.1.9. La funzione di pagamento pXI è convergente.
Teorema 4.1.10. La funzione di pagamento pXI induce un gioco G =
(G, I, g, p) che converge in al più |I|2 mosse.
1
È semplice verificare come questa funzione di pagamento, se applicata a reti con
topologia arbitraria, induce un gioco convergente ma con prezzo dell’anarchia pessimo
4.1 Anelli
73
Infine, notiamo come anche in questo caso un routing R in equilibrio di
Nash per la funzione di pagamento pXI può essere pensato come il risultato
dell’applicazione della strategia First-Fit alla colorazione dei percorsi (fissati
a priori) corrispondenti alle richieste in istanza, presentati all’algoritmo online in ordine non decrescente rispetto al colore ottenuto in R. Dunque, il
prossimo teorema segue dal risultato di Gerstel (Teorema 2.5.1) e dal Teorema
4.1.2.
Teorema 4.1.11. La funzione di pagamento pXI induce su una rete con
topologia ad anello An un gioco con coordination ratio ρ = 5.06 log2 n + 10.
4.1.3
Informazione intermedia
Ricordiamo che il livello di informazione intermedia dà ad ogni singolo
agente unicamente informazione su quali lunghezze d’onda sono disponibili e
quali occupate in ogni arco utilizzato dai due percorsi che connettono i nodi
relativi all’agente stesso.
La funzione di pagamento p relativa all’agente α non può dipendere dall’istanza I, ma può dipendere dallo stato σ Eα della rete di comunicazione con
dominio ristretto agli archi relativi all’agente α, oltre che, naturalmente, dal
percorso e dal colore in uso dall’agente α.
Mostriamo come grazie all’ampliamento del livello di informazione si riesce ad ottenere una funzione di pagamento simmetrica con coordination ratio
costante e abbastanza contenuto.
L’algoritmo on-line di Slusarek
Il nostro scopo è quello di indurre gli agenti a simulare il comportamento
dell’algoritmo on-line proposto da Slusarek e presentato in questa tesi nel
paragrafo 2.4.1; per questo motivo, faremo uso di definizioni e notazioni
introdotte nel suddetto paragrafo.
4.1 Anelli
74
0
1
2
3
4
5
...
0
0
2
5
9
14
20
...
1
1
4
8
13
19
...
...
2
3
7
12
18
...
...
...
3
6
11
17
...
...
...
...
4
10
16
...
...
...
...
...
5
15
...
...
...
...
...
...
...
...
...
...
...
...
...
...
Tabella 4.1: Enumerazione a coda di colomba
L’enumerazione a coda di colomba
Per l’emulazione dell’algoritmo di Slusarek nel contesto di un gioco evolutivo con agenti egoisti, abbiamo bisogno di riservare un numero infinito di
livelli ad ogni ripiano.
A questo scopo, utilizziamo la tecnica a coda di colomba per l’enumerazione dei colori, grazie alla quale è possibile mettere in corrispondenza biunivoca
l’insieme N con l’insieme N2 .
L’enumerazione illustrata dalla Tabella 4.1 è realizzata dalle funzioni
dove : N2 → N e dalla sua inversa dove−1 : N → N2 definite di seguito:
(i + j)(i + j + 1)
dove(i, j) =
+j ,
2
k(k + 1)
k(k + 1)
−1
dove (n) = k − n +
,n −
,
2
2
j√
k
con k = 1+8n−1
.
2
Una funzione di pagamento con basso prezzo dell’anarchia
Partizioniamo l’insieme W delle lunghezze d’onda nei due insiemi W1 e
W2 in modo che W2 = {2i |i = 0, 1, 2, . . .} sia l’insieme delle lunghezze d’onda
dette di sfrido. Cosı̀ ad ogni ripiano è associato un numero infinito di livelli:
4.1 Anelli
75
i primi tre livelli (solo il primo livello per il ripiano 0) sono associati a colori
piccoli in W1 , e i successivi livelli a colori di sfrido presenti in W2 assegnati
ai vari ripiani secondo una tecnica a coda di colomba.
Sia sh(i) il ripiano associato al colore i. Formalizzando l’assegnazione dei
livelli ai ripiani, abbiamo che
(
dove−1
1 (log2 i) se log2 i ∈ N
sh(i) =
i−1−dlog2 ie
e altrimenti
d
3
in cui dove : N2 → N è la funzione che mappa una coppia di naturali
in un naturale e dove−1 : N → N2 la sua inversa (dove−1
indica la prima
1
componente della coppia dove−1 ).
pXII
R=(R,c) (α) =
= min
(
jnk
1
, |R(α)| + n max{0, load(α, R) − sh(c(α))} −
2
2 + sh(c(α)) −
)
1
2c(α)
dove
load(α, R) = max |{d|d ∈ σ(e) ∧ d 6= c(α) ∧ sh(d) ≤ sh(c(α))}|
e∈R(α)
è il massimo numero di richieste, presenti fino al ripiano di α, che condividono
un arco del percorso di α.
Intuitivamente, un routing è in equilibrio di Nash se e solo se ogni richiesta
si posiziona sul percorso minimo, nel ripiano che le assegnerebbe l’algoritmo
di Slusarek, e all’interno del ripiano di propria pertinenza con il livello più
basso disponibile.
Lemma 4.1.12. Il terzo livello del ripiano h ha associato un colore al più
pari a k = 3h + blog2 3hc + 3.
Dimostrazione. Consideriamo la prima approssimazione del colore associato
al terzo livello del ripiano h data da k 0 = 3(h + 1) − 2. Questa prima approssimazione non tiene conto di nessun colore destinato allo sfrido. Il numero di
tali colori presenti nell’intervallo [1, k 0 ] è j 0 = 1 + blog2 k 0 c. Possiamo ottenere
4.1 Anelli
76
quindi una seconda approssimazione k 00 = k 0 +j 0 , che però non tiene conto dei
j 00 colori destinati allo sfrido presenti nell’intervallo [k 0 + 1, k 00 ] di ampiezza
j 0 −1; mostriamo ora che il numero di colori di sfrido j 00 del suddetto intervallo è al più 1 dimostrando una asserzione più forte, ovvero che non può essere
presente nell’intervallo [k 0 + 1, k 00 + 1] più di una potenza di 2. Procedendo
per assurdo, se fossero presenti nell’intervallo [k 0 +1, k 00 +1] due o più potenze
di due, l’ampiezza di tale intervallo dovrebbe essere strettamente maggiore
0
0
0
0
di 2j +1 − 2j = 2j , poiché k 0 + 1 > 2j −1 . La contraddizione segue poiché
l’ampiezza di tale intervallo è pari a j 0 e ∀n, n < 2n .
Il teorema segue dalla considerazione che, avendo dimostrato che nell’intervallo [k 0 + 1, k 00 + 1] è presente al più una potenza di due, il colore associato
al terzo livello del ripiano h è pari a k 00 o k 00 + 1.
Teorema 4.1.13. Il gioco G = (An , I, f, pXII ) indotto dalla funzione di
pagamento pXII converge ed ha coordination ratio ρ = 6 + O( log(π)
).
π
Dimostrazione. Consideriamo una generica evoluzione di gioco, a partire dal
momento in cui tutti gli agenti sono entrati nel gioco (a partire cioè da un
routing non parziale), e mostriamo come essa debba essere finita. Partizioniamo I in due insiemi, A e B, in modo che in A sono presenti tutti e
soli gli agenti che nel resto dell’evoluzione non effettuano mosse che facciano
aumentare il proprio ripiano. Sia k ≥ 0 il numero di agenti presenti in A
all’inizio dell’evoluzione di gioco; vogliamo mostrare come ogni numero finito
di mosse il numero degli agenti presenti in A debba crescere, in modo tale da
dimostrare che in un numero finito di mosse si ha A = I e dunque il gioco
converge non essendo possibile che gli agenti effettuino una sequenza infinita
di mosse senza mai salire di ripiano.
Notiamo prima di tutto come, essendo per costruzione infinito il numero
di livelli di ogni ripiano, ogni agente α può sempre effettuare una mossa che lo
porti su un ripiano i tale che i ≥ load(α, R) ; inoltre quelle che fanno spostare
un agente con un percorso minimo e su un tale ripiano sono le uniche mosse
possibili per un agente, poiché sono le sole che rendono il pagamento per un
agente strettamente minore di b n2 c.
4.1 Anelli
77
Consideriamo una mossa effettuata dall’agente α1 che si sposta nel ripiano
s1 . La dimostrazione procede per casi:
1. α1 rimane senza effettuare mosse che facciano aumentare il proprio
ripiano per tutta la durata dell’evoluzione.
In questo caso α1 entra a far parte di A.
2. Esiste un momento nell’evoluzione degli agenti in cui l’agente α1
effettua una mossa che lo faccia salire di ripiano.
Ciò deve essere dovuto ad un agente α2 che ha effettuato una mossa
che lo ha portato in un ripiano s2 < s1 , e cioè ad un agente che si è posizionato su un ripiano più basso del ripiano di α1 , in quanto altrimenti
per definizione della funzione di pagamento, non essendo aumentato il
load fino al ripiano s1 , α1 non avrebbe potuto salire di ripiano.
Per tale agente si ripropongono i due casi, ma essendo i ripiani al più π
per l’analisi dell’algoritmo di Slusarek, deve esistere un agente αj con
j ≤ π per cui deve verificarsi il primo caso.
Per concludere la dimostrazione di convergenza, basta osservare che in
un numero finito di mosse tutti gli agenti devono entrare in gioco poiché
se x di loro non lo facessero, i rimanenti |I| − x raggiungerebbero in un
numero finito di mosse una situazione di equilibrio, come mostrato fin qui
nella dimostrazione.
Ogni routing R in equilibrio di Nash è evidentemente un possibile output
(senza tener conto dei colori di sfrido) per l’algoritmo on-line di Slusarek
a cui le richieste vengono presentate in ordine non decrescente rispetto al
colore che assumono in R. Per il Teorema 2.4.6, il massimo colore utilizzato
è dunque al più quello associato al terzo livello del ripiano π, che è limitato
superiormente da 3π + blog2 3πc + 3 per il Lemma 4.1.12. Dal Teorema 4.1.2
segue che il gioco G ha coordination ratio ρ = 6 + O( log(π)
).
π
4.2 Catene
4.2
78
Catene
Una catena Cn = ({v1 , v2 , . . . , vn }, {{vi , vi+1 }|i ∈ {1, 2, . . . , n − 1}}) è un
semplice grafo aciclico.
Come l’anello, è una topologia molto diffusa in reti ottiche di
comunicazione.
Il problema della determinazione del routing si riduce a quello dell’assegnazione di lunghezze d’onda ai percorsi unici corrispondenti agli agenti in
istanza.
Le funzioni che analizziamo per questa topologia sono ambedue simmetriche; una di esse è computabile nel livello di informazione minimale, mentre
l’altra necessita del livello di informazione intermedia.
4.2.1
Informazione minimale
La funzione di pagamento minimale è la funzione pI già illustrata nel
paragrafo 3.5, in cui è mostrata essere convergente in al più |I|2 passi.
pIR (α) = f (c(α))
Questa funzione di pagamento fa sı̀ che ogni agente paghi unicamente in
funzione del colore che usa nel routing. Intuitivamente, essendo la funzione
di prezzatura f non decrescente, si vuole indurre ogni agente ad assumere
il colore più basso possibile, in modo da tentare di minimizzare il numero
totale di colori utilizzati.
Poiché un routing R in equilibrio di Nash per la funzione di pagamento pI
può essere pensato come il risultato dell’applicazione della strategia First-Fit
alla colorazione dei percorsi (fissati a priori) corrispondenti alle richieste in
istanza, presentati ad un algoritmo on-line in ordine non decrescente rispetto
al colore ottenuto in R, il prossimo teorema segue dal Lemma 4.1.6 dovuto
a Kierstead.
Teorema 4.2.1. La funzione di pagamento pI induce su una rete con
topologia a catena un gioco convergente con coordination ratio ρ = 25.72.
4.3 Alberi
4.2.2
79
Informazione intermedia
La funzione di pagamento che vogliamo considerare in questa sezione è
nuovamente una funzione che imita l’esecuzione dell’algoritmo di Slusarek,
che naturalmente anche nel caso della catena è 3-competitivo.
pXIII
R=(R,c) (α) =
(
1
= min n, 1 + 2n max{0, load(α, R) − sh(c(α))} −
2 + sh(c(α)) −
)
1
2c(α)
dove load e sh sono definiti come nel paragrafo 4.1.3, e dunque è sempre
assicurato che un agente possa spostarsi su un ripiano, poiché il numero di
livelli assegnati ad ogni ripiano è infinito grazie all’utilizzo della tecnica di
numerazione a coda di colomba.
Per come è strutturata la funzione di pagamento, una volta entrato nel
gioco, un agente effettua una mossa solo se questa lo porta a posizionarsi su
un ripiano i tale che i ≥ load(α, R). Ripetendo la stessa analisi effettuata
nel caso degli anelli, e considerando che quando la topologia è a catena non è
presente il fattore moltiplicativo 2 per il load, si dimostra il seguente teorema.
Teorema 4.2.2. Il gioco G = (Cn , I, f, pXIII ) indotto dalla funzione di
pagamento pXIII converge ed ha coordination ratio ρ = 3 + O( log(π)
).
π
4.3
Alberi
Anche la topologia ad albero, come quelle ad anello e a catena, è molto
diffusa nelle reti ottiche di comunicazione.
Poiché un albero è un grafo aciclico, tra una coppia di nodi esiste un unico
percorso possibile, e dunque il problema del routing si riduce alla ricerca di
un’opportuna assegnazione di lunghezze d’onda alle richieste.
La funzione di pagamento studiata per questa topologia è la funzione pI
già illustrata nel paragrafo 3.5, in cui è mostrata essere convergente in al più
|I|2 passi.
4.3 Alberi
80
pIR (α) = f (c(α))
Questa funzione di pagamento fa sı̀ che ogni agente paghi unicamente in
funzione del colore che usa nel routing. Intuitivamente, essendo la funzione
di prezzatura f non decrescente, si vuole indurre ogni agente ad assumere
il colore più basso possibile, in modo da tentare di minimizzare il numero
totale di colori utilizzati.
Poiché un routing R in equilibrio di Nash per la funzione di pagamento pI
può essere pensato come il risultato dell’applicazione della strategia First-Fit
alla colorazione dei percorsi (fissati a priori) corrispondenti alle richieste in
istanza, presentati ad un algoritmo on-line in ordine non decrescente rispetto
al colore ottenuto in R, il prossimo teorema segue dal risultato di Bartal
(Teorema 2.4.7).
Teorema 4.3.1. La funzione di pagamento pI induce su una rete con topologia ad albero T un gioco G = (T, I, f, pI ) convergente con coordination ratio
ρ = O(log |I|).
Capitolo 5
Reti ottiche dirette e
conclusioni
In questa tesi è stato affrontato il problema del routing su reti ottiche con
multiplazione a divisione di frequenza (WDM ) in ambito non cooperativo.
Allo scopo di indurre gli agenti a raggiungere in modo egoistico e non cooperativo una soluzione di routing che utilizzi un basso numero di lunghezze
d’onda, abbiamo formulato diverse funzioni di pagamento, ideate per topologie generiche e/o particolari di rete, e per ognuna di esse abbiamo verificato
l’esistenza dell’equilibrio e la convergenza, e stimato il coordination ratio.
Nella Tabella 5.1 è presente uno schema riepilogativo di tutte le funzioni di
pagamento analizzate.
5.1
Risultati ottenuti
Abbiamo individuato tre scenari per la computazione delle funzioni
di pagamento, a seconda dell’informazione a disposizione degli agenti per
computare il proprio costo.
• Nel caso di informazione completa, in cui ogni agente è a conoscenza
dell’intera istanza e dello stato della rete di comunicazione, sono stati
raggiunti risultati pienamente soddisfacenti per ogni topologia di rete,
5.1 Risultati ottenuti
82
Topologia
Livello
Esist.
rete
informazione
equil.
pA
generica
completa
sı̀
sı̀, 3|I| mosse
vedi Nota 5.1
pI
generica
minimale
sı̀
sı̀, |I|2 mosse
|I|
w
pI
catena
minimale
sı̀
sı̀, |I|2 mosse
25.72
pI
albero
minimale
sı̀
sı̀, |I|2 mosse
O(log |I|)
pII
generica
minimale
sı̀
sı̀
pIII
generica
intermedia
sı̀
sı̀
|I|
w
|I|
w
pIV
generica
intermedia
no
no
-
V
generica
intermedia
no
no
-
pV I
generica
intermedia
no
no
-
pV II
generica
intermedia
no
no
-
pV III
generica
intermedia
no
no
-
pIX
generica
intermedia
?
no
-
2
p
X
Convergenza
Coordination
ratio
anello
minimale
sı̀
sı̀, |I| mosse
51.44
pXI
anello An
minimale
sı̀
sı̀, |I|2 mosse
5.06 log2 n + 10
pXII
anello
intermedia
sı̀
sı̀
6 + O( log(π)
)
π
pXIII
catena
intermedia
sı̀
sı̀
)
3 + O( log(π)
π
p
Tabella 5.1:
Funzioni di pagamento analizzate dal punto di vista
dell’esistenza dell’equilibrio, della convergenza e del coordination ratio o
prezzo dell’anarchia nei giochi indotti.
Nota 5.1.
Il coordination ratio è pari al rapporto di approssimazione dell’algoritmo
centralizzato A.
5.2 Estensione dei risultati a reti ottiche dirette
83
grazie alla funzione di pagamento pA convergente in un numero lineare
di mosse ed inducente un gioco con coordination ratio pari al rapporto
di approssimazione di qualsiasi algoritmo efficiente centralizzato A.
• Nel caso di informazione minimale, in cui ogni agente ha informazione unicamente su quali lunghezze d’onda sono disponibili lungo i vari
percorsi che connettono i due nodi relativi all’agente stesso, sono state individuate per ogni topologia di rete funzioni convergenti, ma con
pessimo prezzo dell’anarchia, ovvero con un coordination ratio pari a
quello che si otterrebbe assegnando un colore diverso ad ogni agente.
Restringendoci però a reti con topologie specifiche, abbiamo ottenuto
prezzi dell’anarchia molto più contenuti, ed in particolare costanti per
anelli e catene, e logaritmici per alberi.
• Nel caso di informazione intermedia, in cui ogni agente ha conoscenza
di quali lunghezze d’onda sono disponibili e quali occupate in ogni arco utilizzato dai percorsi che connettono i due nodi relativi all’agente
stesso, si è riusciti a migliorare sensibilmente i risultati per reti con
topologia ad anello e a catena, riuscendo ad ottenere valori di coordination ratio prossimi a 6 e 3 rispettivamente. Per quanto riguarda
invece reti con topologia generica, purtroppo, quasi tutte le funzioni di
pagamento più naturali analizzate si sono rivelate non convergenti, e
comunque sempre con un pessimo coordination ratio.
Nei prossimi paragrafi estendiamo tali risultati al modello di reti ottiche
simmetriche dirette, ed enunciamo i principali problemi rimasti aperti, che
possono essere oggetto di successivi lavori in questo ambito.
5.2
Estensione dei risultati a reti ottiche
dirette
Nei capitoli 3 e 4 di questa tesi si è fatto sempre riferimento ad un modello
di reti ottiche non dirette, in cui la rete era modellata da un grafo non diretto.
5.2 Estensione dei risultati a reti ottiche dirette
84
Ora vogliamo per quanto possibile estendere i risultati ottenuti per il
suddetto modello al modello di reti ottiche simmetriche dirette, largamente
analizzato in letteratura, utilizzato nelle reti ottiche reali e descritto nel Paragrafo 2.2.2, in cui la rete è modellata da un grafo diretto simmetrico, cioè
da un grafo G = (V, E) in cui (x, y) ∈ E ⇒ (y, x) ∈ E.
5.2.1
Reti con topologia generica
I risultati ottenuti nel paragrafo 3.4 relativamente al livello di
informazione completa sono immediatamente trasportabili al caso diretto.
Lo stesso vale per la classe Π di funzioni, descritta nel paragrafo 3.2.
Per quanto invece concerne la classe Ξ descritta nel paragrafo 3.3, e quindi
anche le funzioni di pagamento pI e pII del livello di informazione minimale,
e pIII di quello intermedio, non è possibile affermare che il coordination ratio
ρ delle funzioni di pagamento sia pari a
|I|
,
w(G,I)
~
ossia al coordination peg-
giore possibile; riusciamo tuttavia ad affermare che ρ ≥
|I|
2w(G,I)
~
modificando
l’istanza utilizzata nella prova del Teorema 3.3.3 raddoppiando il numero di
agenti: I = {(vi , v(i+1)mod |I| ), (v(i+1)mod |I| , vi )|i ∈ {1, . . . , |I|}}. Si ottiene allo
stesso modo un routing ottimo che utilizza un solo colore, e un rooting in
equilibrio di Nash che utilizza
|I|
2
colori.
Tutte le funzioni di pagamento descritte nel Paragrafo 3.6.1 sono non
convergenti anche nel caso non diretto, e tutte le dimostrazioni sono adattabili
semplicemente orientando in modo opportuno le richieste delle istanze in esse
utilizzate.
5.2.2
Reti con topologie particolari
Anelli
Quando abbiamo affrontato nel Paragrafo 4.1 il problema del routing in
reti ad anello, lo abbiamo suddiviso in due sottoproblemi: individuazione del
percorso di routing (tra i due possibili) e colorazione dei percorsi di routing.
Entrambi gli approcci impiegati per l’individuazione dei percorsi di routing
5.3 Problemi aperti
85
(riduzione alla linea e percorsi minimi) si trasferiscono in modo naturale al
problema nel caso diretto di individuazione di cammini mantenendo entrambi
il rapporto di approssimazione 2 per quanto riguarda il load.
Inoltre, è facile vedere come nel caso diretto tutte le funzioni di pagamento
presentate pX , pXI e pXII mantengono le stesse caratteristiche di convergenza,
ed inducono giochi con i medesimi prezzi dell’anarchia del caso non diretto.1
Catene ed alberi
Anche per queste topologie (analizzate nel caso non diretto nei paragrafi
4.2 e 4.3) in cui il problema di routing si riduce a quello dell’assegnazione
di lunghezze d’onda poiché i cammini sono unici, i risultati ottenuti con le
funzioni di pagamento pI per entrambe le topologie e pXIII per la topologia
a catena si estendono in modo naturale al caso diretto.
Si noti che per quanto riguarda gli alberi l’estensione è possibile poiché il
Teorema 2.4.7 di Bartal è valido sia nel caso diretto che non diretto.
5.3
Problemi aperti
Mentre il caso di informazione completa è stato completamente compreso
e descritto nel Paragrafo 3.4, negli altri livelli di informazione più ristretta il maggiore problema aperto è quello della determinazione di funzioni di
pagamento per reti con topologia generica convergenti ed aventi un prezzo
dell’anarchia contenuto: nel caso di reti ottiche non dirette, è estremamente
interessante ottenere un coordination ratio strettamente minore del peggiore
possibile, che viene realizzato assegnando un colore diverso ad ogni agente.
1
Nel caso diretto, la funzione pX deve essere opportunamente adattata disincentivando
gli agenti all’utilizzo sia dell’arco (vn , v1 ) che dell’arco (v1 , vn ):
(
1
se (vn , v1 ) o (v1 , vn ) ∈ R(α)
pX
R=(R,c) (α) =
1
1 − c(α) altrimenti
5.3 Problemi aperti
86
Per quanto concerne le reti ottiche dirette, poi, è interessante il problema
della stima precisa del coordination ratio per le funzioni di pagamento della
classe Ξ.
Inoltre, anche per topologie particolari, è auspicabile un miglioramento
del prezzo dell’anarchia, soprattutto per le reti ad albero per cui il coordination ratio raggiunto ha una dipendenza logaritmica nella dimensione
dell’istanza.
Infine, l’analisi e l’ideazione di funzioni di pagamento per le più comuni
istanze con configurazioni di comunicazione fissate, descritte nel paragrafo
2.2.4, è una interessante questione da affrontare sia nell’ambito di reti con
topologie generiche che particolari.
Bibliografia
[1] Alok Aggarwal, Amotz Bar-Noy, Don Coppersmith, Rajiv Ramaswami,
Baruch Schieber, e Madhu Sudan. Efficient routing and scheduling algorithms for optical networks. In Symposium on Discrete Algorithms,
1994.
[2] Y. Bartal e S. Leonardi. On-line routing in all-optical networks. Theoretical Computer Science - special issue for ICALP ’97, 221(1-2):19–39,
1999.
[3] B. Beauquier, J. C. Bermond, L. Gargano, P. Hell, S. Perennes, e U. Vaccaro. Graph problems arising from wavelength-routing in all-optical
networks. In Proceedings of the 2nd Workshop on Optics and Computer
Science, part of IPPS’97, 1997.
[4] M. Beckmann, C. B. McGuire, e C. B. Winston.
Studies in the
Economimices of Transportation. Yale University Press, 1956.
[5] V. Bilò, M. Flammini, e L. Moscardelli. On Nash Equilibria in NonCooperative All-Optical Networks. Dattiloscritto, 2004.
[6] V. Bilò e L. Moscardelli. The price of anarchy in all-optical networks.
In Proceedings of the 11th Colloquium on Structural Information and
Communication Complexity (SIROCCO), volume 3104, pp. 13–22, 2004.
[7] C. A. Brackett.
Dense wavelength division multiplexing networks:
principles and applications.
IEEE Journal on Selected Areas in
Communications, 8:948–964, 1990.
BIBLIOGRAFIA
88
[8] I. Caragiannis, Ch. Kaklamanis, e P. Persiano. Wavelength routing in
all-optical tree networks: A survey. Bulletin of the European Association
for Theoretical Computer Science, 76:104, 2002.
[9] N. K. Chung, K. Nosu, e G. Winzer. Special issue on dense WDM
networks. IEEE Journal on Selected Areas in Communications, 8, 1990.
[10] A. Czumaj.
Handbook of Scheduling:
Algorithms, Models, and
Performance Analysis. Chapter 42. CRC Press, 2004.
[11] A. Czumaj e B. Vöcking. Tight bounds for the worst-case equilibria. In
In Proceedings of the 13th Annual ACMSIAM Symposium on Discrete
Algorithms (SODA), pp. 413–420, 2002.
[12] T. Erlebach e K. Jansen. Scheduling of virtual connections in fast networks. Proc. of Parallel Systems and Algorithms (PASA), pp. 13–32,
1996.
[13] T. Erlebach e K. Jansen. Call scheduling in trees, rings and meshes. In
Proc. of HICSS, 1997.
[14] T. Erlebach, K. Jansen, C. Kaklamanis, M. Mihail, e P. Persiano. Optimal wavelength routing on directed fiber trees. Theoretical Computer
Science, (1-2):119–137, 1999.
[15] Eyal Even-Dar, Alex Kesselman, e Yishay Mansour. Convergence Time
to Nash Equilibria. Manoscritto.
[16] A. Fabrikant, C. H. Papadimitriou, e K. Talwar. The complexity of pure
Nash equilibria. Manoscritto.
[17] R. Feldmann, M. Gairing, T. Lĺucking, B. Monien, e M. Rode. Nashification and the coordination ratio for a selfish routing game. In Proceedings
of the 30th Annual International Colloquium on Automata, Languages
and Programming (ICALP), 2003.
BIBLIOGRAFIA
89
[18] A. Fiat e G. Woeginger. On-line Algorithms. Springer-Verlag, 1998.
[19] D. Fotakis, S. Kontogiannis, E. Koutsoupias, M. Mavronicolas, e P. Spirakis. The structure and complexity of nash equilibria for a selfish routing game. In Proceedings of the 30th Annual International Colloquium
on Automata, Languages and Programming (ICALP), volume 2380, pp.
123–134, 2002.
[20] A. Frank, T. Nishizeki, N. Saito, H. Suzuki, e E. Tardos. Algorithms for
routing around a rectangle. Discrete Applied Mathematics, 40:363–378,
1992.
[21] M. R. Garey, D. S. Johnson, G. L. Miller, e C. H. Papadimitriou.
The complexity of coloring circular arcs and chords. SIAM Journal
on Algebraic and Discrete Methods, 1(2):216–227, 1980.
[22] L. Gargano e U. Vaccaro. Routing in All–Optical Networks: Algorithmic and Graph–Theoretic Problems (in Numbers, Information and
Complexity). Kluwer Academic, 2000.
[23] O. Gerstel, G. H. Sasaki, S. Kutten, e R. Ramaswami. Worst-case analysis of dynamic wavelength allocation in optical networks. IEEE Trans.
Networking, 7:833–845, 1999.
[24] O. Gerstel, G. H. Sasaki, e R. Ramaswami. Dynamic channel assignment for WDM optical networks with little or no wavelength conversion. In Proc. 34th Allerton Conference on Communication, Control,
and Computing, 1996.
[25] M. C. Golumbic e R. E. Jamison. The edge intersection graphs of paths
in a tree. Journal of Combinatorial Theory, Series B(38):8–22, 1985.
[26] P. E. Green. Fiber-Optic Communication Networks. Prentice Hall, 1992.
[27] A. Haurie e P. Marcotte. On the relationship between Nash-Cournot
and Wardrop equilibria. Networks, 15:295–308, 1985.
BIBLIOGRAFIA
90
[28] S. Irani. Coloring inductive graphs on-line. Algorithmica, 11:53–73,
1994.
[29] C. Kaklamanis e G. Persiano. Constrained bipartite edge coloring with
applications to wavelength routing. Manoscritto, 1996.
[30] H. A. Kierstead e W. T. Trotter. An extremal problem in recursive
combinatorics. Congressus Numerantium, 33:143–153, 1981.
[31] H.A. Kierstead e J. Qin. Coloring interval graphs with first-fit. Discrete
Mathematics, 144:47–57, 1995.
[32] R. Klasing. Methods and problems of wavelength-routing in all-optical
networks. In Proceedings of the MFCS’98 Workshop on Communication,
August 24-25, Brno, Czech Republic, pp. 1–9, 1998.
[33] E. Koutsoupias e C.H. Papadimitriou. Worst-case equilibria. In Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer
Science (STACS), volume 1563 di LNCS, pp. 387–396, 1999.
[34] M. Mavronicolas e P. Spirakis. The price of selfish routing. In Proceedings of the 33rd Annual ACM Symposium on the Theory of Computing
(STOC), pp. 510–519, 2001.
[35] M. Mihail, C. Kaklamanis, e S. Rao.
Efficient access to optical
bandwidth-wavelength routing on directed fiber trees, rings, and trees
of rings. Proc. of 36th FOCS, pp. 548–557, 1995.
[36] J. F. Nash. Equilibrium points in n-person games. In Proceedings of the
National Academy of Sciences, volume 36, pp. 48–49, 1950.
[37] J. F. Nash.
Non-cooperatives games.
In Annals of Mathematics,
volume 54, pp. 286–295, 1951.
[38] G. Owen. Game theory. Academic Press, 3rd edizione, 1995.
BIBLIOGRAFIA
91
[39] Christos H. Papadimitriou. Algorithms, games, and the Internet. Lecture
Notes in Computer Science, 2076:1–11, 2001.
[40] R. Ramaswami.
Multi-wavelength lightwave networks for computer
communication. IEEE Communications Magazine, 31:78–88, 1993.
[41] Rajiv Ramaswami e Kumar N. Sivarajan. Optical networks, a practical
perspective. Morgan Kaufmann Publishers, 2002.
[42] R. W. Rosenthal.
A class of games possessing pure-strategy Nash
equilibria. International Journal of Game Theory, 2:65–67, 1973.
[43] T. Roughgarden. The price of anarchy is independent of the network
topology. In Proceedings of the 34th Annual ACM Symposium on Theory
of Computing (STOC), pp. 428–437, 2002.
[44] T. Roughgarden e E. Tardos. How bad is selfish routing? Journal of
ACM, 49(2):236–259, 2002.
[45] C. Siva, Ram Murthy, e Mohan Gurusamy. WDM optical networks,
concepts, design and algorithms. Prentice Hall, 2002.
[46] M. Slusarek.
Optimal on-line coloring of circular arc graphs.
Informatique Théorique et Applications, 29(5):423–429, 1995.
[47] A. Tucker. Coloring a family of circular arcs. SIAM Journal of Applied
Mathematics, 29(3):493–502, 1975.
[48] Jorgen W. Weibull. Evolutionary Game Theory. MIT Press, prima
edizione, 1997.