Post on 16-Jul-2015
Laurea Magistrale in Informatica
Giochi di coordinamentosu grafi
Relatore:Prof. Vincenzo Auletta
Candidato:Antonio Sanfelice
Il problema Gli strumenti Il modello Modifiche proposte Conclusioni e sviluppi futuri
IL PROBLEMA
PrayStation Ouii KicksBox
PSKB
Ouii
9/103/107/10
?
PS
Ouii Ouii
KB KB
1
Il problema Gli strumenti Il modello Modifiche proposte Conclusioni e sviluppi futuri
IL PROBLEMA
• Adesione ad un nuovo standard;• Affiliazione ad un partito o ad un gruppo;• Scelta della meta per le vacanze;• Scelta di un progetto a cui lavorare.
In generale:Diffusione delle Opinioniin una rete sociale
2
Il problema Gli strumenti Il modello Modifiche proposte Conclusioni e sviluppi futuri
IL PROBLEMA
Soluzione
Una soluzione è un assegnamento opzione - individuo tale damas-simizzare il benessere sociale, ovvero la somma degli utili di tuttii membri della rete.
Condizioni
Desideriamo una soluzione che offra stabilità: una volta riusciti atrovare una soluzione con un alto benessere sociale, non voglia-mo che i giocatori cambino idea.
3
Il problema Gli strumenti Il modello Modifiche proposte Conclusioni e sviluppi futuri
GLI STRUMENTI
Teoria dei giochi
Disciplina che studia contesti in cui agenti razionali agiscono inmodo da massimizzare il proprio utile.
Gioco
• Insieme |N | = n di giocatori;• Insieme |S | = m di strategie;• Funzione di utilità u : Sn → R.
4
Il problema Gli strumenti Il modello Modifiche proposte Conclusioni e sviluppi futuri
GLI STRUMENTI
Best Response
Strategia chemassimizza l'utile data l'attuale situazione di gioco.
Equilibrio Nash
Soluzione stabile in cui nessun giocatore ha incentivi a cambiarestrategia (i.e. ogni giocatore sta giocando la sua best response).Può essere
puro: ogni giocatore sceglie una singola strategia;
misto: ogni giocatore gioca a caso secondo una distribuzionedi probabilità.
5
Il problema Gli strumenti Il modello Modifiche proposte Conclusioni e sviluppi futuri
GLI STRUMENTI
Un equilibrio Nash può essere a volte difficile da trovare o puòrivelarsi una soluzione inefficiente, particolarmente distantedall'ottimo.
α Best Response
Strategia che fa guadagnare almeno un fattoreα rispetto a quellacorrentemente giocata.
Equilibrio Nash α-approssimato
Soluzione in cui ogni giocatore, deviando, non può guadagnare piùdi α. (i.e. ogni giocatore sta giocando la sua α best response).
6
Il problema Gli strumenti Il modello Modifiche proposte Conclusioni e sviluppi futuri
IL MODELLO
Funzione di utilità
ui(s ) = wsii +
∑sj=si
γij wij j ∈ N(i )
Dove
s è un vettore di n componenti, contenente la strategiaadottata da ogni giocatore;wsi
i indica la preferenza di i per la strategia correntementegiocata;wij è l'utile generato dal coordinamento tra i e j ;γij è la frazione di utile che i riceve dal coordinamento con j.Si ha γij + γji = 1.
7
Il problema Gli strumenti Il modello Modifiche proposte Conclusioni e sviluppi futuri
PROBLEMI
• ComplessitàProblema NP-Hard, riduzione da Multiway-Cut
• Esistenza degli equilibriSe esiste un vettore γ = {γ1, γ2, . . . , γn} tale cheγij =
γiγi+γj
, ∀i, j allora esiste almeno un equilibrio Nash puro.
• Inefficienza degli equilibriSia s una soluzione in equilibrio Nash e SW(s ) =
∑i ui(s)
SW(s ) ≈ 1
m SW(OPT )
8
Il problema Gli strumenti Il modello Modifiche proposte Conclusioni e sviluppi futuri
TROVARE UNA SOLUZIONE
One-Shot α-BR
1. Assegna ad ogni giocatore la strategia k0;2. Fintanto che esiste un giocatore la cui strategia è k0 che puòeffettuare un α best response, gli si lasci cambiare strategia;
3. Restituisci il profilo ottenuto.
Algoritmo
1. k0 = argk max∑
i wki ;
2. s1 = One-Shot α-BR;3. s2 = One-Shot 1
α−1 -BR;
4. Restituisci la soluzione con il social welfare più alto.9
Il problema Gli strumenti Il modello Modifiche proposte Conclusioni e sviluppi futuri
MODIFICHE PROPOSTE
Aggiunta dell'anticoordinamento
u(s ) =∑i∈V
wsii +
∑si=sj
wij +∑si ̸=sj
wij (i, j ) ∈ E
Rispetto al modello originale:
• le garanzie sulla soluzione date dall'algoritmo si perdono;• garantita l'esistenza di un equilibrio puro, sotto le stessecondizioni;
• rispetta i limiti sulla soluzione nel caso peggiore;• nel caso migliore si potrebbe avere un equilibrio che è anchesoluzione ottima (dipende dall'istanza).
10
Il problema Gli strumenti Il modello Modifiche proposte Conclusioni e sviluppi futuri
MODIFICHE PROPOSTE
Permutare l'ordine di gioco
Dalmomento che la scelta di un giocatore dipende da quella deglialtri, i giocatori più disinteressati al coordinamento dovrebberogiocare per primi.
Effettuare una ricerca per α
Non essendoci linee guida su come scegliere α, la soluzione piùsemplice è cercare il valore che da il miglior risultato.
11
Il problema Gli strumenti Il modello Modifiche proposte Conclusioni e sviluppi futuri
RISULTATI - ORIGINALE VS. EURISTICHE
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●
●●
●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●
●
●●●●●●●
●
●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●
●
●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●
●
●●●●●●●●●●
●
●
●
●●●●●●●●●●●●●●●●●●●
●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●
●
●●●●●●●●●●●
●
●●●●●●●●●●●
●
●●●●●●●●●●●●●●●
●
●●
●
●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●
●
●●●●●●
●
●●●●●
●
●●
●
●●
●
●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●
●
●●●●●●●
●
●●●●●●●●
●
●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●
●
●●●
●●●●
●
●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●
●●●
●
●●●●●●●●●●●
●
●●
●
●●●●●●●●●
●
●●●●●●●●
●
●●
●
●●●
●
●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●
●
●●
●
●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●
●
●
●
●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●
●
●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●
●
●
●
●●●●●●
●
●●●●
●
●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●
●
●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●
●
●●●●●●●●
●
●●●●●
●
●
●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●
●●●●●●●●●●●●●●●●●●●●●●●
●
●●
●
●
●
●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●
●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●
●
●●●●●●●●
●
●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●
●
●●●
●
●●●●●
●
●●●●●●●●●
●
●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●
●
●●●●●●●●●
●
●●●●●●●●●●●
●
●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●
●
●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●
●
●●●●●
●
●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●
●
●●●●●●●●●●●●●
●
●●●●●
●
●
●
●●
●
●●
●
●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●
●
●●●
●
●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●
●
●●●●●●●●●●●●●●●●
●
●●●●●●●●
●
●
●●●●●●●●
●
●●●●
●
●●●●●●●●●
●
●●●●●
●
●●●
●
●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●
●
●●●
●
●●●●●●●●●●●●●●●●●
●
●●
●
●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●
●
●●●●●●●●●●
●●
●
●
●●●●●●●●●●●●●●
●
●●●●●●●●
●
●●●●●●●●●●●●●●●●
●
●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●
●
●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●
●
●
●
●●●●●●●●●●●●●●●●●
●
●●●●●●●●●
●
●●
●
●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●
●
●●●●
●
●●●●●●●
●
●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●
●
●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●
●
●●●
●
●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●
●
●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●
●
●●
●
●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●
●
●●●●
●●●●●
●
●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●
●
●
●
●●●
●
●●●●●●
●
●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●
●
●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●
●
●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●
●●●●●●
●
●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●
●
●
●
●●●●●●●●●●
●
●●●●●●●
●
●
●
●●●●●●●●
●
●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●
0 1000 2000 3000 4000 5000
0.92
0.94
0.96
0.98
1.00
1.02
Index
orig
inal
Gai
n
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
0 1000 2000 3000 4000 50001.
000
1.00
21.
004
1.00
61.
008
1.01
0
Index
best
BR
GG
ain
12
Il problema Gli strumenti Il modello Modifiche proposte Conclusioni e sviluppi futuri
RISULTATI - RICERCA CARATTERISTICHE
6
8
4
2
0
-2
-1
0
1
2
maxEgo
maxUtilities
maxDeg
0 -2 -4 -6 -8 -10
13
Il problema Gli strumenti Il modello Modifiche proposte Conclusioni e sviluppi futuri
RISULTATI - RICERCA DI α
●●●●●●●
●
●●●
●
●●●●●●●●●●
●
●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●
●
●●●●●●
●
●
●
●●●●●●●
●
●●●●
●
●
●
●
●●
●
●
●●●●●●
●
●●●●●
●
●
●
●●●●●●
●
●●●●●●●●
●
●
●
●●●●●
●
●
●
●●●●●
●
●●●●●●●●
●
●●●●●●
●
●●●●●
●
●●●●
●
●●●●●
●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●
●
●
●●●●●
●
●●●●●●●●●
●
●●●●●●●●●●●●
●
●
●●
●
●●
●●
●
●●●●●●●●●
●
●●●●●●
●
●●
●
●●●●●●●●●●●
●
●●
●
●●●●
●●
●●
●●
●●●●●●●●
●
●●●●●●●
●
●●●
●
●
●
●●●●●●●●●
●
●●●
●
●●●●●●●●●●●●●●●●●●
●
●●●●●●●
●
●
●●
●
●●●●●●●●
●
●
●
●
●●●
●
●●●●●●●
●
●●●●●
●
●●●●●●●●●●●●●●●
●●●
●
●●
●
●●
●
●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●
●
●●●●
●
●
●
●●●●●
●
●●●●●●●●
●
●
●
●●●
●
●●●●●●●●
●
●●●●
●
●
●●●●●●●●●●●●
●
●●●
●
●●●●●●●●●
●●●●●
●
●
●●●
●
●●●
●●
●●●●●●●●
●
●●●●●
●●
●●●●●
●●●●●●
●
●●●●●●●●●●●●●●●●●●
●
●
●
●●●●●●●●●●
●
●●●
●●
●●●●●
●●
●●●●●
●
●●●
●
●●●
●
●
●
●●●●
●
●●●●
●
●●●●●●●●
●
●
●●●●●
●
●
●
●●●●●●
●
●●●●●●●●●●
●●
●
●
●
●●●●●●
●
●●●●●
●
●●●●●●●●●●●●●●●
●
●●●●●●●●●●
●
●●●●●●
●●
●●●●
●
●●●●●●●●●●●
●
●
●
●
●
●
●
●●●●●
●
●●●●●●
●●
●●●●●●
●
●
●●
●●●●
●
●●●
●
●
●
●●●
●
●
●●●●●
●
●●●●●●●●●●●
●
●●
●
●●●●●●●●
●
●●●●●●●●●●
●
●
●
●
●
●●●●●●●●●●●●
●
●●●●
●
●
●
●●●●●●●●●
●
●●●
●
●
●●
●●●●●●●
●●
●●●●
●
●●
●
●
●
●
●
●●●●●●●●●●
●
●
●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●
●
●●●●
●
●●●●●●●●●●●●●●●●●
●
●●●●●●●●●
●
●●●●●
●●●●●●
●●●
●
●●●●●●●●●●●
●
●●●●●●●●●
●
●●●●●●●●●●●
●
●●
●
●●●●●
●●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●
●
●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●
●
●
●●●●●●
●
●●●●●●●
●
●●
●
●●●●●
●
●●●●●
●
●●●●●●
●
●●●
●
●●●●●●●●●●●●●●●●
●
●●●
●
●●●●●
●
●●●
●
●●●●●●●
●
●
●
●
●
●
●
●●●●●
●
●●●●●
●
●●●●●●
●
●●●●●●●●
●
●
●●
●
●●●
●
●●●●
●
●●●●●●●
●
●●●
●
●
●
●●
●
●●●●
●
●●●●●●
●
●●●●●●
●
●●●●●
●
●●●●●●●
●
●●●●●●●●●●●
●
●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●
●
●●●●
●
●●●●●●●●●
●
●●●●●
●
●●●
●
●●●
●
●
●●
●
●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●
●
●
●
●●●●●●●●
●
●●●●●●●●●●●●●●●●●
●
●●●●●
●
●
●
●●●●●●●●
●
●●
●
●●●
●
●●●●●●●●●●
●
●●●
●
●
●
●
●●●●●●
●
●●●●●●
●
●●●●
●●
●●●●●●●●●
●
●●●●
●
●●
●
●●
●
●
●
●●●●●●●●
●
●●●●●
●
●
●
●●●●●●
●
●
●
●
●●●●●●●●●●●●
●
●●●●
●
●●●●●
●
●●●●●●●●●●●●●
●
●●●
●
●●●●●●●●●
●
●●●●●●●●●
●
●●
●
●●●●●
●
●●
●
●
●●
●●●●●●●
●
●●●●●●●●●●●●
●
●●●●●●●●
●
●
●
●
●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●
●
●●
●
●●●●●●
●
●●●
●
●●●●●●●●●●●
●
●
●
●
●
●
●
●●●●●●●●
●●
●●●
●●
●●●●
●
●●●●●
●
●●●●●●●●
●
●●●●●
●
●●●●●●
●
●●●●●
●
●●●●●●●●●
●
●
●
●
●
●
●
●
●●
●
●
●●●●●●
●
●●●
●
●●●●●●●●●●●●
●
●●●●●●●●●●●●
●
●●●●●●●
●
●●●
●●●●
●
●●●●●●
●
●
●
●●●●●
●
●●
●
●●●●
●
●●●●
●
●●●
●
●●●●●●●
●
●●●●●●
●
●●
●
●●
●
●●●●●●●●●
●
●●●●●●
●
●●●●●●●●●●●
●
●
●●
●●●●●●●●●
●
●
●●●●
●
●●●●●●●●●●●●●●●●●●
●
●●
●
●●●●●●●●●●
●
●
●
●●●
●
●●
●
●
●
●
●
●●●●●●
●
●●●●●
●
●●●●
●
●●
●
●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●
●
●
●●
●●●●
●
●●●●●●●●●●●●●●●
●
●
●
●●●
●
●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●
●
●●
●●
●●●●●●●●●●●●●●
●
●●●●●●
●
●●●●●●●●●●●
●
●●●
●
●●●
●
●●●
●
●
●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●
●
●●●●
●
●●●
●
●●●●●
●
●●●●●●●●●●●●
●
●●●●●
●
●
●
●
●●●●●●
●
●●
●
●●●
●
●●●●
●
●●●●
●
●
●
●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●
●
●●●●●●●●●●●●
●
●●●●
●
●●●●●●
●
●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●
●
●
●●
●
●
●
●●●●●●●
●●
●●●●●●●●●●●
●
●
●
●●●●●
●●
●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●
0 500 1000 1500 2000 2500
1.00
1.02
1.04
1.06
1.08
Index
desc
endi
ngG
ain
14
Il problema Gli strumenti Il modello Modifiche proposte Conclusioni e sviluppi futuri
CONCLUSIONI E SVILUPPI FUTURI
È stato studiato un modello per la diffusione di opinioni in una retesociale e sono state proposte alcune modifiche all'algoritmorisolutivo atte a migliorare la qualità della soluzione. Alcune ideeper quanto concerne gli sviluppi futuri sono:
• Approfondire il modello con anticoordinamento;• caratterizzare le istanze del gioco per cui le euristiche dannorisultati diversi dall'algoritmo originale;
• migliorare la ricerca di α o individuare un modo per calcolarneil valore data l'istanza;
• introdurre incertezza o irrazionalità.
15
Grazieper l'attenzione