Giochi di coordinamento su grafi

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

• 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

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


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


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


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 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


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


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


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


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


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


RISULTATI - RICERCA CARATTERISTICHE

6

8

4

2

0

-2

-1

0

1

2

maxEgo

maxUtilities

maxDeg

0 -2 -4 -6 -8 -10

13


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


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

Giochi di coordinamento su grafi

Science

Transcript of Giochi di coordinamento su grafi