Giochi su network di connessione

Stefano Moretti

Istituto Nazionale per la Ricerca sul Cancro

Email: stefano.moretti@istge.it

Phone:010-5600500

Pavia, 24 Marzo 2009 Almo Collegio Borromeo

Phd Thesis, Tilburg Univeristy, The Netherlands:

http://arno.uvt.nl/show.cgi?fid=80868

Ricerca Operativa Un decisore, guidato da una

funzione obiettivo, affronta un problema di ottimizzazione.

La teoria quindi si concentra sulla questione di come agire in maniera ottimale e, in particolare, sulla costruzione di algoritmi efficienti.

Teoria dei Giochi cooperativi almeno due decisori interagenti

(chiamati giocatori) sono permessi accordi vincolanti possono essere permessi anche

pagamenti laterali (giochi a utilità trasferibile o TU-game, anche noti come giochi cooperativi in forma coalizionale)

RO e TdGORG Struttura (discreta) di base di un grafo,

network o sistema che soggiace a varie tipologie di problemi di ottimizzazione combinatoria.

Si assume che almeno due giocatori sono situati in corrispondenza di parti (es. vertici, lati, panieri di risorse, lavori) del sistema da ottimizzare ecc.)

Un gruppo di persone le cui case sulla montagna non siano ancora connesse ad una rete fognaria;

Le loro acque reflue devono essere raccolte in un depuratore a valle;

Per tutti e’ sufficiente, ma non necessario, essere connessi autonomamente al depuratore;

Ci si puo connettere anche attraverso altre case;

“Alcune connessioni potrebbero anche essere impedite da barriere naturali (natural reef)”;

Costruire un tubo e’ costoso.

Esempio di Situazione di connessione

Come nasce il gioco? Lavorando assieme, i giocatori

possono realizzare guadagni extra o abbassare i costi in comparazione alla situazione in cui ciascuno ottimizza individualmente.

Il nuovo problema è: come dividere i guadagni extra o i risparmi?

Ricordo che

N={1,2,…,n} e’ l’insieme dei giocatori

c:2NIR+ e’ la funzione caratteristica del gioco

che assegna ad ogni coalizione S2N un numeor reale c(S) e dove c()=0.

Un vettore xIRn e’ chiamato allocazione

Se un’allocazione e’ sia efficiente (iN xi=c(N)) che individualmente razionale (xi c({i}) per ogni iN) allora e’ chiamata imputazione

Un’imputazione e’ stabile se iS xi c(S) per ogni coalizione S non vuota

Il nucleo di un gioco <N,c> e’ l’insieme di tutte le imputazioni stabili ed e’ denotato da Core(N,c)

Un gioco cooperativo dei costi e’ una coppia ordinata <N,c> dove

8

Problemi di connessione fixed tree games, ovvero giochi

derivanti da problemi di mantenimento di network già costruiti

minimum cost spanning tree games (giochi mcst), dove invece il network di connessione deve ancora essere realizzato.

Minimum Cost Spanning Tree Situation

Utilizziamo il modello del grafo pesato completo.

1

2

3

– I cui vertici rappresentano le case

sorgente

– il vertice 0 e’ la sorgente

0– I lati rappresentano le connessioni

40

30

10

50

20

– I numeri vicino ai lati rappresentano

il costo di connessione

80

Minimum Cost Spanning Tree problem.

Problema di Ottimizzazione: come connettere ogni nodo alla sorgente 0 in maniera tale che il costo di costruzione di del network di ricoprimento (che connette tutti i nodi direttamente o indirettamente alla sorgente 0) sia minimo?

EsempioN={1,2,3}EN’={{1,0},{2,0},{2,1},{3,0},{3,1},{3,2}}Una funzione dei costi come indicata sul grafo

21

0

18

24 24

2610 20

3

Algoritmo di Kruskal

21

0

18

24 24

2610

3

Algoritmo di Prim

20

21

0

18

24 24

2610 20

3

c(1)=24

c(3)=26

c(2)=24

c(1,3)=34

c(2,3)=44

c(1,2)=42

c(1,2,3)=52

Esempio: Il gioco cooperativo dei costi <{1,2,3},c> dato dalla situazione di connessione disegnata di seguito e’ tale che:

Il gioco <{1,2,3}, c> è detto gioco mcst

21

0

18

24 24

2610 20

3

• Il predecessore di 1 e’ 0: quindi l’allocazione di Bird assegna a 1 il costo di {1,0}.

•Il predecessore di 2 e’ 1: quindi l’allocazione di Bird assegna a 2 il costo di {2,1};

• Il predecessore di 3 e’ 1: quindi l’allocazione di Bird assegna a 3 il costo di {1,3}.

w()=52

L’allocazione di Bird rispetto a (x1, x2, x3)=(24, 18 ,10) sta nel nucleo Core({1,2,3},c).

Come posso dividere il costo totale?

L’allocazione di Bird rispetto a questo albero di ricoprimento di minimo costo e’

(x1, x2, x3)=(18, 24 ,10)

L’allocazione di Bird rispetto a questo albero di ricoprimento di minimo costo e’

(x1, x2, x3)=(24, 18 ,10)

21

0

18

24 24

2610 20

3

21

0

18

24 24

2610

3

20

Entrambe le allocazioni appartengono al nucleo del gioco mcst (ed anche la loro combinazione convessa).

21

0

18

24 24

2610 20

3

1

3

2

(0,52,0)

(0,0,52)

(52,0,0)

x1+x2

+x3=52

(x1,x2,x3)

(2,24,26)

(24,24,4)

(24,2,26)

I(N,c)

(18,24,10)(24,18,10)

(8,18,26)

Core(N,c)

(8,24,20)

21

0

18

24 24

2610 20

3

(24,24,4)

(2,24,26)(24,2,26)

I(N,c)

Bird 1 Bird 2

Allocazione Bird Regola di Bird:

Esiste sempre (dato un problema di connessione).

In genere non e’ unica (ce ne sono tante quante gli alberi di ricoprimento di minimo costo).

Tutte le allocazioni di Bird Stanno nel nucleo del gioco mcst.

Altre considerazioni per valutare i metodi di allocazione: andare a vedere cosa succede quando varia la struttura del network

Si immagini di utilizzare una certa regola per allocare i costi. Può aumentare il costo dei lati: se il costo di

una connessione aumenta nessuno dovrebbe venire a pagare di meno in base alla regola di allocazione in uso (monotonia sui costi);

Uno o più giocatori lasciano il network: nessuno dei rimanenti dovrebbe essere avvantaggiato dalla loro partenza (monotonia sui giocatori).

Monotonia sui costi: comportamento di Bird.

21

0

3

4 5

83 4

3

21

0

3

6 5

83 4

3

Allocazione di Bird: (4, 3 ,3) Allocazione di Bird: (3, 5 ,3)

La regola di Bird non soddisfa la monotonia sui costi.

Monotonia sui giocatori: comportamento di Bird.

Allocazione di Bird: (5, 5 ,3) Allocazione di Bird: (3, * ,6)

21

0

5

7 5

63 7

3

1

0

7

63

3

La regola di Bird non soddisfa la monotonia sui giocatori.

21

0

3

4 8

24 5

3

Esercizio:

Si consideri la situazione mcst disegnata in figura. Determinare:

• il corrispondente gioco mcst.

• il nucleo del gioco mcst

• le allocazioni date dalla regola di Bird