1 Strumenti della Teoria dei Giochi per lInformatica A.A. 2009/2010 Sebastiano Panichella.

1 Strumenti della Teoria dei Giochi per lInformatica A.A. 2009/2010 Sebastiano Panichella

Scenario Lemergente ricerca di algoritmi di game theory ha portato a una fondamentale riesaminazione dei classici concetti relativi agli equilibri di Nash, con grosse prospettive computazionali Tratteremo i Congestion Game Esempio di Congestion Game: siano e due giocatori; sia che vogliono andare da S (Sorgente) a D (Destinazione); le strade disponibili per andare da S a D sono due, A e B SD A B Tabella dei payoff /AB A4 32 B1 3 4 2

I Congestion Game hanno attirato lattenzione dei ricercatori per varie ragioni: Riguardano una gran parte di scenari con problemi di allocazione delle risorse, e di routing dove sempre presente un equilibrio di Nash puro: a differenza di altri giochi, hanno sempre un N.E. dove ogni giocatore sceglie ununica strategia Per il meccanismo noto come Nash dynamics, dove a ogni passo qualche giocatore cambia la sua strategia verso unaltra ritenuta pi conveniente, garantita la convergenza a un pure Nash equilibria. Motivazioni 3

Definizione di Congestion Game: n giocatori ; a ciascun giocatore i viene assegnato un insieme finito di strategie (ossia un insieme di risorse disponibili alli-esimo giocatore); a ciascun giocatore i viene assegnata una funzione di costo che desidera minimizzare (il costo di ogni strategia dipende solo dal numero di giocatori che usano la risorsa in questione) Congestion Game Maggiore il numero dei giocatori che utilizzano una risorsa Maggiore il costo 4

Formalmente il costo per p i Uno stato una qualsiasi combinazione di strategie per gli n giocatori. equilibrio di Nash puro: uno stato un equilibrio di Nash se numero di giocatori che usano la risorsa e funzione di costo (non negativa) Congestion Game Per ogni giocatore Il costo della strategia scelta da p i Il giocatore p i non incentivato a cambiare Per ogni altra strategia 5

Nella Classe di Congestion Game che consideriamo: i giocatori condividono un insieme di risorse (gioco simmetrico) chiamate archi linsieme di strategie,, di un giocatore p i una collezione arbitraria di sottoinsiemi di E la strategia del giocatore p i, un sottoinsieme di E a ogni arco associata una funzione di costo (o ritardo) non decrescente Classe di Congestion Game 6

Se t giocatori utilizzano larco e ciascuno di essi pagher un costo d e (t) In uno stato s=(s 1,, s n ) il costo del giocatore p i numero di giocatori che usano larco e nello stato s Classe di Congestion Game d strada ( 1 )= 2 d strada ( 2 )= 4 d strada ( 3 )= 8 Esempio In generale d strada (t)= 7

Funzione potenziale: i giochi a congestione sono in possesso una precisa funzione potenziale definita come propriet: il cambiamento in rispecchia esattamente la variazione dei costi del giocatore Per ogni arco Funzioni Potenziali Sommiamo i costi sostenuti in base ai giocatori che lo utilizzano Variazione del potenziale se il giocatore p i cambia la sua strategia da s i a s i Variazione del costo per p i = 8

Osservazione: Funzioni Potenziali Se a ogni passo permettiamo ai giocatori di modificare la propria strategia (pi conveniente) fino a raggiungere un minimo locale diminuir ossia un equilibrio di Nash puro ma Niente ci assicura la rapida convergenza a un equilibrio di Nash 9

Approssimazione di equilibri di Nash ottimo Accuratezza Tempo 10

Definizioni -equilibrio di Nash: sia, uno stato un -equilibrio di Nash se Dinamiche best response -approssimate: dinamiche best response nelle quali ciascun giocatore pu fare solo -mosse, ossia movimenti che migliorano il costo di un fattore maggiore di . Pi formalmente se il giocatore p i si sposta da s i a s i allora Per ogni giocatore Per ogni strategia Il giocatore p i non ha pi di un -incentivo a cambiare strategia 11

-N.E. e Dinamiche -Nash Se pi di un giocatore ha una -mossa disponibile, solo il giocatore il cui relativo guadagno il pi grande effettuer la sua mossa. In altre parole, il giocatore p i effettua la sua mossa se, tale mossa massimizza il rapporto Se i giocatori non hanno pi -mosse da effettuare I giocatori hanno raggiunto un -equilibrio di Nash Costo ottenuto nel caso in cui il giocatore effettua la mossa s i Minore tale costo e maggiore il rapporto R Costo Precedente 12

Definizioni Bounded Jump: dato un grafo G(V,E) con funzione di peso sugli archi, diciamo che larco e soddisfa la condizione di -bounded jump se sia t 0 il numero di giocatori costante 1 la sua funzione di costo soddisfa la condizione costo dellarco e per ( t +1 ) giocatori costo dellarco e per t giocatori quando un nuovo player sceglie di utilizzare un determinato arco, il costo che pagheranno tutti i giocatori che lo usano sar incrementato di un fattore di al pi 13

ENUNCIATO In un gioco a congestione simmetrico dove, ogni arco soddisfa la condizione -bounded jump, se nelle dinamiche -approssimate nello stato s la prossima mossa fatto dal giocatore p i,allora Lemma 3.2 Per ogni giocatore p j diverso dal giocatore p i Il costo del giocatore p j al pi volte il costo del giocatore p i 14

Lemma 3.2 DIMOSTRAZIONE Supponiamo che il gioco si trovi in uno stato Supponiamo che un giocatore p i voglia effettuare una mossa da s i a s i con guadagno relativo Supponiamo che un altro giocatore p jp i voglia effettuare la stessa mossa,ossia, si muove da s j a s j = s i con guadagno relativo Per come abbiamo definito il gioco, solo il giocatore con il massimo guadagno relativo effettua la sua mossa; quindi se nel gioco, solo il giocatore p i effettua la sua mossa, deve valere che R jR i 15

Lemma 3.2 Ossia A questo punto, confrontiamo il costo che il giocatore p i paga per effettuare la sua mossa con quanto avrebbe pagato il giocatore p j per effettuare la sua mossa da s j (se vedessimo vincere luno o laltro giocatore): arco che il giocatore p i vuole usare, possiamo avere che (1)(1) Per la condizione di bounded jump abbiamo che. 1. p i sta gi usando larco e prima della mossa p j paga al pi per usare larco e p i paga per usare larco e (perch p j stesso potrebbe essere il nuovo giocatore che utilizza larco e) 16

Lemma 3.2 2. p i non sta gi usando larco e prima della mossa p j paga al pi lo stesso prezzo p i paga per usare larco e Sommando su tutti gli archi abbiamo che (2)(2) Sostituendo la ( 2 ) nella disequazione ( 1 ) abbiamo che 17

18 Lemma 3.2 Semplificando, abbiamo

Il fattore di approssimazione > 0 Bounded condition Limite superiore al costo di ciascun giocatore Teorema 3.1 ENUNCIATO In qualsiasi gioco a congestione simmetrico, dove n il numero di giocatori tutti gli archi soddisfano l-bounded jump condition C un limite superiore al costo di ciascun giocatore le dinamiche -approssimate convergono partendo da un qualsiasi stato iniziale in numero di passi pari a 19

Teorema 3.1 il costo che paga il giocatore di almeno volte il pi grande costo di ogni giocatore DIMOSTRAZIONE Dal Lemma 3.2 sappiamo che se p i il giocatore che si muove da s i a s i allora Siccome Il potenziale costo complessivo Il costo del giocatore p i la media del potenziale 20

Teorema 3.1 Da cui, dopo un movimento di p i stato s allo stato s Variazione del potenziale Variazione del costo per p i = Trattandosi di un -mossa la variazione del costo per p i pi di -volte il costo dello stato precedente s Dato che In generale Nello stato iniziale = max = potenziale iniziale; dato che Ad ogni passo Numero totale di passi per la convergenza 21

PLS-completezza di giochi con Bounded Jump Proposition 3.3 Il problema della ricerca di un equilibrio di Nash in giochi a congestione simmetrici che soddisfano la condizione di bounded jump con = 2 PLS-completo Mentre un -equilibrio di Nash viene raggiunto in un numero di passi polinomiale ( il Teorema 3.1 ) lo stesso non accade per un equilibrio di Nash puro I risultati finora ottenuti sugli equilibri di Nash esatti non hanno effetti hanno effetti significativi sugli -equilibri di Nash 22

LEsempio Anche se gode della Bounded Jump condition questo semplice problema di allocazione di risorse d strada ( 1 )= 2 d strada ( 2 )= 4 d strada ( 3 )= 8 Esempio In generale d strada (t)= PLS-completo 23

Meccanismi di coordinamento Osservazione: finora abbiamo sempre utilizzato un meccanismo di coordinamento nel quale il giocatore con il maggiore incentivo fa la prima mossa 1) Domanda: quando vengono utilizzati altri meccanismi di coordinamento cosa succede? Per queste varianti dell -Nash dynamics, il teorema 3.1 ancora valido (convergenza polinomiale a -equilibri di Nash)? 2) Domanda: quando non viene utilizzato nessun meccanismo di coordinamento cosa succede? E possibile convergere polinomiale a - equilibri di Nash? 24

Varianti della -Nash dynamics Largest gain dynamics: ad ogni passo, tra tutti i giocatori con un - mossa disponibili, quello che si muove quello il cui miglioramento dei costi (assoluto) il maggiore. Una variante della -Nash dynamics Costo Precedente Costo del giocatore se effettua la mossa s i Unaltra variante della -Nash dynamics Heaviest first dynamics: ad ogni passo, tra tutti i giocatori con un -mossa disponibili, si consente la mossa al giocatore con il maggior costo corrente 25

1) Domanda: per queste varianti dell -Nash dynamics, il teorema 3.1 ancora valido? Varianti della -Nash dynamics Dai teoremi Teorema 3.4 Il Teorema 3.1 continua a essere valido anche nel Largest gain dynamics. Teorema 3.5 Il Teorema 3.1 continua a essere valido anche per Heaviest first -Nash dynamics Risposta: Si 26

2) Domanda: quando non viene utilizzato nessun meccanismo di coordinamento cosa succede? E possibile convergere polinomiale a - equilibri di Nash? The unrestricted dynamics un meccanismo in cui i giocatori: possono muoversi in un ordine arbitrario sono soggetti ad una sola condizione necessaria: a ogni giocatore deve essere data la possibilit di fare la propria mossa entro un certo limite di tempo Osservazione: finora abbiamo sempre utilizzato un meccanismo di coordinamento nel quale il giocatore con il maggiore incentivo fa la prima mossa Le dinamiche senza restrizioni 27

Pi formalmente la dinamica senza restrizioni una sequenza di q 1, q 2,,q n dove ogni q t indica un giocatore al passo t al giocatore q t data la possibilit di muoversi Le dinamiche senza restrizioni Si Fa la mossa q t ha un -mossa? No Non fa nulla Vogliamo che per qualche costante T ogni giocatore p i compaia almeno una volta in ogni intervallo di sequenza con lunghezza T 28

Esempio: La Round-Robin dynamics Le dinamiche senza restrizioni A turno a ogni player p i viene data la possibilit di fare la sua mossa 29

Le dinamiche senza restrizioni 2) Domanda: quando non viene utilizzato nessun meccanismo di coordinamento cosa succede? E possibile convergere polinomiale a - equilibri di Nash? Risposta: Si Dal Teorema 4.1 In ogni gioco a congestione simmetrico con n giocatori i cui archi soddisfano -bounded jump condition, qualsiasi -Nash- dynamics, in cui a ogni giocatore viene data la possibilit di fare la propria mossa all'interno di ogni intervallo di tempo di lunghezza t, converge da qualsiasi stato iniziale in un numero di passi pari a un limite superiore al costo di ogni giocatore 30

Le dinamiche senza restrizioni Per provare il teorema 4.1 utile enunciare (e dimostrare) il seguente Lemma: Lemma 4.2 Sia c i (s) il costo sostenuto dal giocatore p i nello stato s, e sia c i (s) il costo di p i in uno stato futuro s in cui non si mosso. Allora Concettualmente mette in relazione il miglioramento della funzione potenziale nessuna mossa per molti steps la variazione del costo per p i, anche quando il giocatore non fa nessuna mossa per molti steps 31

Dimostrazione lemma Le dinamiche senza restrizioni Sappiamo che la variazione del costo per p i I contributi positivi a questa somma sono dati dagli archi e che altri giocatori hanno liberato Sapendo che il primo giocatore p j che rinuncia a e aveva un costo di almeno allora la funzione potenziale migliora di almeno 32

valore che ha assunto la funzione potenziale all'inizio dell'intervallo Il miglioramento totale di Le dinamiche senza restrizioni Dimostrazione Teorema 4.1 Ai fini della prova sufficiente mostrare che durante ogni intervallo in cui a ogni giocatore data la possibilit di effettuare una mossa, la funzione potenziale diminuisce di almeno Convergenza in al pi -volte quanto ci guadagna p i 33

Siano gli stati durante questo intervallo (non necessariamente differenti) Le dinamiche senza restrizioni Sia p h il giocatore con il maggior costo in s 0 Sia t 0 la prima volta in cui,durante lintervallo, al giocatore p h data la possibilit di muoversi Avremo due casi: Caso(i): al tempo t, p h ha un -mossa a disposizione Caso(ii): al tempo t, p h non ha un -mossa a disposizione 34

Le dinamiche senza restrizioni Caso(i) dal Lemma 4.2, abbiamo la garanzia che il miglioramento della funzione potenziale nessuna mossa per molti steps la variazione del costo per p h, anche quando il giocatore non fa nessuna mossa per molti steps Dopo l -mossa di p h, sar migliorata di almeno -Media del potenziale iniziale Il teorema soddisfatto Convergenza in al pi 35

Le dinamiche senza restrizioni Caso(ii) Non avendo un -mossa a disposizione non vogliamo che p h possa fare un -mossa adottando semplicemente la strategia di un altro giocatore, p i Al momento t, dobbiamo avere Costo di p h per simulare la mossa di p i Utilit di p h per simulare la mossa di p i 36

Le dinamiche senza restrizioni ( 1 caso) Consideriamo un giocatore p i, a cui data la possibilit di fare la sua mossa al tempo t > t ossia, dopo che a p h stata data la possibilit di muoversi ( 2 caso) Consideriamo lultimo giocatore, p i,a cui data la possibilit di fare la sua mossa al tempo t < t Analizzeremo due casi: 37

( 1 caso) Sia p i, un giocatore che fa la sua mossa al tempo t > t ossia, dopo che a p h stata data la possibilit di muoversi, avremo che Le dinamiche senza restrizioni = = La variazione della funzione = potenziale Il teorema soddisfatto 38

Le dinamiche senza restrizioni ( 2 caso) Sia p i, lultimo giocatore che fa la sua mossa al tempo t < t, Nellistante t Infatti da ( 3 ) la condizione deve essere soddisfatta da p i anche al tempo t (e anche subito dopo) Dato che fare la mossa pu solo ridurre il suo costo, soddisfa la condizione anche al tempo t 39

Allora la variazione di potenziale Le dinamiche senza restrizioni Deriva dalla condizione massimo miglioramento ottenuto da p i per la sua mossa Deriva dal LEMMA 4.2 40

Le dinamiche senza restrizioni Allora la variazione di potenziale massimo miglioramento ottenuto da p i per la sua mossa minima quando soddisfatta Deriva dal LEMMA 4.2 41

Le dinamiche senza restrizioni Risposta: Si 2) Domanda: quando non viene utilizzato nessun meccanismo di coordinamento cosa succede? E possibile convergere polinomiale a -equilibri di Nash? 3) Domanda: se generalizziamo il gioco permettendo a ciascun giocatore di dichiarare il proprio (che in un certo qual modo indica la tolleranza allinfelicit o, se vogliamo, la propensione a accontentarsi del giocatore). E possibile convergere polinomiale a -equilibri di Nash? Parliamo di Giocatori eterogenei 42

Giocatori eterogenei Heterogeneouse players: una generalizzazione delle impostazione precedenti dove ciascun giocatore p i ha un proprio valore , che chiameremo i che specifica la sua tolleranza allinfelicit Per ogni giocatore Per ogni strategia Il giocatore p i non ha pi di un i -incentivo a cambiare strategia -equilibrio di Nash: per, uno stato un - equilibrio di Nash se 43

Dinamiche best response -approssimate: dinamiche best response nelle quali ciascun giocatore p i pu fare solo i -mosse, ossia movimenti che migliorano il costo di un fattore maggiore di i. pi formalmente se il giocatore p i si sposta da s i a s i allora Giocatori eterogenei Cambiare strategia non conviene pi di i volte il costo della strategia attuale 44

Giocatori eterogenei Vedremo che questa dinamica converge in passi il numero di passi di tempo in cui un giocatore con tolleranza i "sar" infelice "(cio, avr un -move disponibile) essenzialmente a prescindere dagli j -valori degli altri giocatori. 45

Giocatori eterogenei Teorema 5.2 Sia max < 1 il valore massimo di i, tra tutti i giocatori p i. Allora,, ci sono al massimo volte in cui qualche giocatore p j con j sar in grado di muoversi prima che l - Nash dynamics converga Dimostrazione Teorema 5.2 Sia s =(s 1,,s n ), uno stato in cui un giocatore p j con j ha una j -move disponibile. Ai fini della prova sufficiente dimostrare che la riduzione della funzione potenziale almeno 46

Giocatori eterogenei Sia p h il giocatore con il maggior costo in s Analizzeremo due casi: Caso(i): p h = p i, ossia, p i ha il maggior costo Caso(ii): p h p i ossia, p i non ha il maggior costo Sia p i il giocatore che si muove attualmente dallo stato s a.. 47

Giocatori eterogenei Se il p h = p i allora abbiamo gi finito, dal momento che ad ogni passo il potenziale si riduce di almeno Caso(i) Il teorema soddisfatto Convergenza in al pi n. passi pari a 48

Giocatori eterogenei Supponiamo che p h possa muoversi da s a s simulando la strategia s i del giocatore p i. Siccome non vogliamo che p h possa muoversi da s, dato che non il suo turno Caso( 2 ): il guadagno relativo per p h non pi grande del guadagno relativo che ottiene consentendo a p i di effettuare la sua mossa. Analizziamo due casi: Caso( 1 ): la mossa da s a s non deve essere una h -move per p h Caso(ii): p h p i ossia, p i non ha il maggior costo 49

Sappiamo che Combinando le due disequazioni, abbiamo Giocatori eterogenei Caso( 1 ): la mossa da s a s non deve essere una h -move per p h 50 (Dal teorema 3.1) Allora Il teorema soddisfatto

51 Allora Giocatori eterogenei Dato che Caso( 2 ): il guadagno relativo per p h non pi grande del guadagno relativo che ottiene consentendo a p i di effettuare la sua mossa,ossia, Siccome

1 Strumenti della Teoria dei Giochi per lInformatica A.A. 2009/2010 Sebastiano Panichella.

Documents

Transcript of 1 Strumenti della Teoria dei Giochi per lInformatica A.A. 2009/2010 Sebastiano Panichella.