Marinelli Claudia. 2 I ntroduzione alla TEORIA DEI GIOCHI D Definizione (Gioco strategico) Un...

Marinelli Claudia

2

Introduzione alla TEORIA DEI GIOCHI

Definizione (Gioco strategico)

Un gioco strategico è un modello di interazione tra soggetti che devono decidere quali azioni compiere

per raggiungere un determinato obiettivo.

Definizione (Teoria dei giochi)

E’ la scienza che studia i giochi strategici.


3

Un gioco strategico consiste di:

un insieme di giocatori;

per ogni giocatore, un insieme di azioni;

per ogni giocatore, preferenze sull’insieme di

profili.


4

Funzione di payoff

E’ possibile rappresentare le preferenze attraverso una funzione di guadagno(payoff), che associa un numero ad ogni profilo in modo tale che i profili con numeri più alti sono preferiti rispetto a quelli con numeri più bassi.

Più precisamente, la funzione di payoff rappresenta le preferenze di un soggetto se per ogni coppia di profili , risulta:

se e solo se il soggetto preferisce il profilo al profilo .


)()( ba

a b

a b

5

Problema: Quali azioni saranno scelte dai giocatori?

Ogni giocatore cerca di massimizzare il proprio guadagno.

In generale, l’azione migliore per un giocatore dipende dall’azione degli altri partecipanti.

Il giocatore deve formulare una teoria sulle azioni degli altri giocatori.


6

EQULIBRI DI NASH

Definizione (EQULIBRIO DI NASH)

Un equilibrio di Nash è un profilo di azione con la proprietà che nessun giocatore può fare meglio scegliendo un’azione differente da , assumendo che ogni altro giocatore aderisce a .

Nello stato idealizzato in cui i giocatori di ogni partita del game sono scelti in maniera casuale da una collezione di popolazioni, un equilibrio di Nash corrisponde ad uno stato stabile.

Se, ogni volta che viene fatta una partita, il profilo delle azioni è quello dell’equilibrio di Nash , allora nessun giocatore ha qualche ragione per scegliere un’azione differente dalla propria componente di .

Equilibri di Nash

*a

*a

ji ia*

ja*

*a

i

7

Questa definizione non implica nè che ogni gioco strategico ha un equilibrio di Nash nè che ce ne sia al più uno per ogni gioco strategico.

Uno dei giochi strategici più noti è il “Dilemma Del Prigioniero”. Il suo nome viene da una storia che coinvolgeva due sospetti in un crimine; la sua importanza viene dalla grande varietà di situazioni in cui i partecipanti hanno a che fare con decisioni simili a quelle messe di fronte ai due sospetti della storia.

Equilibri di Nash

8

Esempio : “ Il Dilemma del Prigioniero”

Due sospetti in un grave crimine sono messi in due celle separate. Ci sono abbastanza prove da incolpare ognuno dei due di un crimine minore, ma non abbastanza prove da incolpare uno dei due del crimine maggiore, a meno che uno dei due non agisca da informatore contro l’altro (Quiet). Se entrambi stanno zitti (Fink), ognuno dei due sarà accusato del crimine minore e saranno condannati ad un anno di prigione. Se uno e solo uno dei due confessa, egli sarà liberato e sarà usato come testimone contro l’altro, che sarà condannato a quattro anni di prigione. Se entrambi confessano, saranno condannati entrambi a tre anni di prigione.

Equilibri di Nash – “Il Dilemma del prigioniero”

9

Modello• Giocatori : I due sospetti.

• Azioni {Quiet,Fink}

• Preferenze L’ordine dei profili di azione dal migliore al peggiore:

primo sospetto (Fink,Quiet) lui viene liberato (Quiet,Quiet) lui viene condannato ad un

anno di prigione (Fink,Fink) lui viene condannato a tre anni

di prigione (Quiet,Fink) lui viene condannato a quattro

anni di prigione


10

secondo sospettoPer gli stessi motivi, l’ordine dei profili di azione delsecondo sospetto è:

(Quiet,Fink) (Quiet,Quiet) (Fink,Fink) (Fink,Quiet).

Possiamo rappresentare il gioco in maniera compatta in una tavola. Per prima cosa scegliamo le funzioni di payoff che rappresentano gli ordinamenti delle preferenze dei due sospetti.


11

Per il primo sospetto abbiamo bisogno di una funzione

per la quale

Fink) (Quiet, Fink) (Fink, Quiet) (Quiet, Quiet) (Fink, 1111

Una semplice specifica sarebbe

Allo stesso modo, per il secondo sospetto potremmo scegliere la funzione per la quale

.

3 Quiet) (Fink,1 1 Fink) (Fink, 1

2 Quiet) (Quiet,

3 Fink) (Quiet,

2

2

0 Quiet) (Fink,

1 Fink) (Fink,

2

2

2


2 Quiet) (Quiet,1 0. Fink) (Quiet, 1

12

Usando queste rappresentazioni, il gioco è illustrato nellaseguente figura .

sospetto 2 Quiet Fink

Quiet sospetto 1

Fink

2,2 0,3

3,0 1,1

Esaminando le quattro possibili coppie di azioni possiamo vedere che la coppia (Fink,Fink) è l’unico equilibrio di Nash.


13

La coppia (Fink,Fink) è un equilibrio di Nash perché:

Se fissiamo che il secondo giocatore sceglie Fink, per il primo giocatore è meglio scegliere Fink piuttosto che Quiet, dato che nel primo caso avrebbe un guadagno di 1 maggiore del guadagno di 0 che avrebbe nel secondo caso.

Analogamente, se fissiamo che il primo giocatore sceglie Fink, per il secondo giocatore è meglio scegliere Fink piuttosto che Quiet, dato che nel primo caso avrebbe un guadagno di 1 maggiore del guadagno di 0 che avrebbe nel secondo caso.


14

Pertanto, se uno dei due giocatori si sposta unilateralmente

da Fink a Quiet passerebbe da un guadagno positivo ad un

guadagno nullo.

Nessun altro profilo è un equilibrio di Nash:

• (Quiet,Quiet) non è un equilibrio di Nash perché sia al primo che al secondo giocatore conviene cambiare unilaterlamente la propria azione dato che, in tal caso, passerebbe da un guadagno di 2 ad un guadagno di 3.

• (Fink,Quiet) non è un equilibrio di Nash perché al secondo giocatore conviene cambiare unilateralmente la propria azione dato che, in tal caso, passerebbe da un guadagno di 0 ad un guadagno di 1.


15

• (Quiet,Fink) non è un equilibrio di Nash perché al primo giocatore conviene cambiare unilateralmente la propria azione dato che, in tal caso, passerebbe da un guadagno di 0 ad un guadagno di 1.


Nel dilemma del prigioniero, il problema principale è se i

giocatori devono cooperare o no.

Nel seguente gioco, i giocatori sono daccordo nel

cooperare, ma sono in disaccordo sulla migliore soluzione.

16

Esempio: “Bach o Stravinsky?”

Due persone vogliono uscire insieme.

Ci sono due concerti disponibili: uno di musica di Bach ed uno di musica di Stravinsky. Una persona preferisce Bach e l’altra preferisce Stravinsky.

Se essi vanno a concerti differenti, entrambi saranno scontenti allo stesso modo.

Equilibri di Nash – “Bach o Stravinsky?”

17

Bach Stravinsky

Bach

Stravinsky


2,1 0,0

0,0 1,2

• (Bach,Bach):

Se il giocatore 1 si sposta da Bach a Stravinsky, il proprio payoff decresce da 2 a 0;

se il giocatore 2 passa da Bach a Stravinsky il suo payoff decresce da 1 a 0.

Pertanto questo è un equilibrio di Nash.

18

• (Bach,Stravinsky): Se il giocatore 1 si sposta da Bach a Stravinsky, il suo payoff cresce da 0 a 1, quindi questo non può

essere un equilibrio di Nash.

• (Stravinsky,Stravinsky):Se il giocatore 1 si sposta da Stravinsky aBach, il proprio payoff decresce da 1 a 0;

se il giocatore 2 passa da Stravinsky a Bach il suo payoff decresce da 2 a 0.

Pertanto questo è un equilibrio di Nash.


19

Bach Stravinsky

Bach

Stravinsky

• (Stravinsky,Bach): Se il giocatore 2 si sposta da Bach a Stravinsky, ilsuo payoff cresce da 0 a 2, quindi questo non può essere un equilibrio di Nash.


2,1 0,0

0,0 1,2

20

Concludiamo, quindi, che il gioco ha due equilibri di Nash,

che corrispondono agli stati in cui entrambi i giocatoriscelgono la stessa azione.

Come il dilemma del prigioniero, questo esempio modella

una grande varietà di situazioni.

Vediamo ora un caso di gioco puramente conflittuale.


21

Esempio: “Matching Pennies”

Due persone, ognuna delle quali ha una moneta, devono

simultaneamente mostrare un lato (Testa o Croce) delle

loro monete. Se entrambi mostrano lo stesso lato, la

seconda persona paga un euro alla prima persona; se

mostrano lati differenti, la prima persona paga un euro alla seconda persona. Ogni persona è attenta solo alla

quantità di soldi che riceve e, ovviamente, preferisce

ricevere piuttosto che dare.

Equilibri di Nash – “Matching Pennies”

22

Un gioco strategico che modella questa situazione èmostrato nella figura

Testa Croce

Testa

Croce

In questo gioco, gli interessi dei giocatori sonodiametralmente opposti (un gioco del genere è detto“strettamente competitivo”): il giocatore 1 preferirebbe

farela stessa azione del giocatore 2, mentre quest’ultimopreferirebbe fare un’azione diversa da quella del giocatore

1.

1,-1 -1,1

-1,1 1,-1


23

Controllando ognuna delle quattro possibili coppie di azioni

possiamo immediatamente vedere che questo gioco non

ha un equilibrio di Nash. Infatti:

(Testa,Testa) non può essere un equilibrio di Nash perché all’agente 2 conviene passare

da Testa a Croce portando, così, il suo guadagno da -1 a +1.

(Croce,Croce) non può essere un equilibrio di Nash perché all’agente 2 conviene passare

da Croce a Testa portando, così, il suo guadagno da -1 a +1


24

(Testa,Croce) non può essere un equilibrio di Nash perché all’agente 1 conviene

passare da Testa a Croce portando, così, il suo guadagno da -1 a +1.

(Croce,Testa) non può essere un equilibrio di Nash perché all’agente 2 conviene

passare da Croce a Testa portando, così, il suo guadagno da -1 a +1.


25

Prezzo dell’anarchiaPrezzo dell’anarchia

Koutsoupias, Papadimitriou

• DefinizioneDati un gioco e una funzione socialefunzione sociale (somma delle funzioni di payoff di tutti i giocatori) ,sia l’insieme di tutti gli equilibri di Nash e lo stato di che ottimizza . Il prezzo dell’anarchia

del gioco rispetto a è definito come:

• Misura la perdita di ottimalità di un sistema non regolato a causa della mancanza di cooperazione tra i giocatori e di coordinazione centrale.

G fN

OPTG f

NsG f

sup)(

)(

)(

OPTf

sf

)( fGfG

Equilibri di Nash – Prezzo dell’anarchia

26

Per spiegare come definire e misurare la qualità di uno

stato stabile, riprendiamo l’esempio del “Dilemma del

prigioniero”, in cui il problema principale è se i giocatori

devono cooperare o no.

Se i due sospetti potessero cooperare, si accorderebbero sullo stato (Quiet,Quiet) = OPT.

Ne consegue che il prezzo dell’anarchia risulta essere:

2

1)( fG


27

Subottimalità degli Equilibri di NashSubottimalità degli Equilibri di Nash

In generale, un comportamento egoistico di agenti che popolano un sistema non cooperativo può risultare in uno stato stabile, il cui valore sociale può essere lontano dall’ottimo sociale.


28

ROUTING EGOISTICO: INTERNET

Un problema fondamentale nella gestione di traffico a larga scala e nelle reti di comunicazione è quello del routing del traffico per ottimizzare le prestazioni della rete.

ProblemaData una quantità di traffico tra ogni coppia di nodi della rete, trovare i percorsi che minimizzano la somma dei tempi di attesa (latenza totale).

Routing egoistico della rete

29

Risulta spesso difficile (quasi impossibile) imporre strategie di routing ottimali o quasi-ottimali sul traffico di una rete.

Una delle prime strategie proposte è la valutazione di un costo marginale, anche noto come congestione.

Si considera che su ogni arco ogni utente deve pagare un costo (tempo) aggiuntivo, pari al ritardo dovuto alla presenza di altri utenti su tale arco.

Molti decenni dopo, alcuni ricercatori, utilizzando tale strategia, sono riusciti a scoprire che, sotto alcune assunzioni, è possibile far fronte all’inefficienza del routing, scegliendo appropriatamente gli archi della rete.


30

Caratteristiche di Internet

Le reti sono formate da nodi dislocati in modo eterogeneo nel mondo e sono caratterizzate da un’architettura aperta che gli permette una continua e incontrollata crescita;

gli utenti della rete si comportano,generalmente, in maniera “egoistica” (selfish agents);

il tempo di attesa per un collegamento è dipendente dal carico del link (congestione della rete);


31

Modellizzazione del problemaE’ chiaro che un sistema del genere può essere ben

modellato utilizzando la teoria dei giochi.

giocatori utenti della rete

azioni possibili percorsi attraverso cui gli utenti possono trasmettere il proprio traffico

Assunzioni:• tutti gli utenti agiscono in modo del tutto egoistico;

• il traffico di un utente è inoltrato tutto su di uno stesso percorso e contemporaneamente;

• ogni utente controlla una frazione trascurabile dell’intero flusso.


32

Modello di una rete

• Un grafo diretto G = (V,E);

• k coppie origine-destinazione ;

• ammontare del traffico da , i = 1,2, ...,k;

• un insieme di cammini da ;

• un insieme ;

• per ogni arco con traffico , una funzione di latenza ;

) t,(s ..., ), t,(s kk11

ir ii ta s

iP ii ta s

Eei )(xli

x

i

iPP

Routing egoistico della rete-Modello

33

• è non negativa, differenziabile e non decrescente;

• un vettore di flusso = quantità di traffico del tratto

in ;

• per ogni arco il flusso ;

• un flusso si dice ammissibile se per ogni i:

• chiamiamo la tripla un’ istanza.

)(xli

Pf

ii t-s P

Ee

PeP Pe ff:

),,( lrG

iPP P rfi

f


34

• La latenza di un cammino risulta essere:

• il costo di tutti i flussi = latenza totale, risulta:

Flussi e Teoria dei giochi

flusso la moltitudine di agenti non cooperativi

latenza totale funzione (o benessere)

sociale

Pe eeP flfl )()(

P

Ee eee

PPP fflfflfC )()()(

P

)( fC


35

nessun effetto

di congestione

Ognuno dei due cammini porta metà del traffico complessivo.

Esempio: Una unità di traffico deve andare da s a t

il ritardo dipende

dalla congestione

s t

xxl )(

1)( xl

1/2

1/2


36

Esempio: “Paradosso di Braess”(1968)

Sia s s un quartiere, t una stazione ferroviaria. Due conducenti vogliono andare e tornare da s a t.

Per il momento, assumiamo che ci siano due rotte che non interferiscono tra loro, ognuna comprendente una strada lunga e larga, e una corta e stretta. Per simmetria, ci aspettiamo che ognuno dei due cammini porti metà del traffico complessivo, cosicché tutti i conducenti impiegano 90 minuti (1,5) per viaggiare da s a t.

Routing egoistico-”Paradosso di Braess"

37

v

w

x1

s t

x1

1/2

1/2

0

Latenza= 1+0.5 =1.5


Supponiamo ora, con l’obiettivo di diminuire i tempi, di poter introdurre una strada molto corta e molto larga che collega direttamente i punti intermedi delle due strade, con funzione di latenza nulla(indipendente dalla congestione della strada).

38

Come reagiscono i conducenti?

Ogni conducente può risparmiare 30 minuti di viaggio (assumendo che gli altri utenti non cambino rotta), seguendo il cammino s → v → w → t.

Supponiamo che tutti i conducenti, volendo usare la nuova

strada, devino i loro cammini precedenti, per seguire il cammino s → v → w → t.

v

w

x 1

s t

x1

0

Latenza = 1+1 =2


39

A causa della forte congestione sui tratti (s, v) e (w, t), tutti i

conducenti impiegano 2 ore per andare e tornare da s a t.

Inoltre questa congestione implica che nessuno dei due

cammini precedenti risulti essere migliore, in questo modo

nessuno dei conducenti è incentivato a cambiare strada.

Ancora peggio, ogni altro modello di traffico è instabile: tutti

i conducenti sarebbero incentivati a cambiare cammino.

E’ quindi ragionevole aspettarsi che tutti i conducenti seguano il cammino s → v → w → t e che quindi

impieghino 30 minuti in più(0.5) del modello originale. Ne

segue:

3

4

1.5

2)( fG


40

Flussi di NashFlussi di Nash

Definizione

Un flusso ammissibile per l’istanza è a a

Equilibrio di NashEquilibrio di Nash se per ogni e

, , dove

se

se

altrimenti

P

P

P

P

f

f

f

f

~

f ),,( lrG

PP ,,...,ki 21}1{ ],0[

1Pf )~

()(21

flfl PP

1PP 2PP

Routing egoistico della rete-Flussi di Nash

41

Principio di WardropPrincipio di Wardrop

• Lemma Un flusso ammissibile per l’istanza è aEquilibrio di Nash se e solo sese e solo se per ogni e , con , vale

In particolare, tutti i cammini a cui la assegna quantità positiva di flusso hanno la stessa latenza, si indica con .

f ),,( lrG ,...,k}{i 1

iPPP 21, 01Pf

).()(21

flfl PP

f

)( fLi


42

• Proposizione

Se è un flusso a Equilibrio di Nash per l’istanza

, allora

k

iii rfLfC

1

)()(

f),,( lrG


43

Flussi ottimaliFlussi ottimali

Un flusso ottimale è un flusso che minimizza la latenza totale.

Programmazione Convessa

s.a.

dove

fcMinfMinCEe

ee

)()(

PP

P f

Eeff

,...,k}{irf

P

PePpe

iPP

P

i

0

1

:

fflfc eeeee )()(

Routing egoistico della rete-Flussi ottimali

44

Soluzione (flusso ottimale)

• La funzione obiettivo è convessa,

ottimo locale = ottimo globale;

• Siano

Lemma 1

Un flusso è ottimale per un programma convesso

della forma(NPL) se e solo se per ogni e

,con vale

fflfc eeeee )()(

)(xcdx

dc ee

Pe

eeP fcfc )()(

(f)c(f)c PP 21

,...,k}{i 1P,PP 21

,01Pf

f


45

Interpretazione di Beckmann

Corollario

Sia un’istanza con funzione convessa

per ogni arco , con costo marginale . Allora un flusso ammissibile per è ottimale se e solo se è un flusso di Nash per l’istanza .

eeeeeeeeeeee fflflfflfcfl )()())(()()(*

)(G,r,l *(G,r,l)f

(G,r,l) (x)lx e*le


46

Esistenza Esistenza di Equilibri di Nashdi Equilibri di Nash

Lemma

Un’ istanza , con funzione di latenza continua, non decrescente, ammette un flusso ammissibile di Nash. Inoltre, se sono flussi di Nash, allora

(G,r,l)

ff, ~

.)fC(C(f)~

Routing egoistico della rete-Equilibri di Nash

47

Il prezzo dell’ anarchia nella reteIl prezzo dell’ anarchia nella rete Definizione

Per un’ istanza con un flusso ottimale e un flusso di Nash , il prezzo dell’anarchia

limite superiore buono ma non ottimo

)C(f

C(f)ρ(G,r,l)

*

Corollario: se , con , allora

),,( lrG

dttlxlxx

ee 0

1

(G,r,l)

f

*f

Routing egoistico della rete-Prezzo dell’anarchia

48

Corollario: se con intero

positivo e reali non negativi, allora

Es.

Osservazione

In particolare, questo corollario afferma che in un’istanza con funzione di latenza linearefunzione di latenza lineare (cioè

ogni funzione di latenza ha la forma

con ), il costo di un

flusso di Nash è al più il doppio del costo del flusso

di minima latenza.

p

i

iiee xaxl

0 ,)( p

iea ,

1),,( plrG

3),,(,)( 2 lrG 2,p xxle


)(xle

)()()( xbxaxl eee 0, ee ba

49


Risultati Bicriteri

TeoremaSe è un flusso di Nash per e è ammissibile per , allora

Teorema Se è un flusso di Nash per e è ammissibile

per , allora

.)C(fC(f) *r,l)(G,2f *f(G,r,l)

*f(G,r,l)fγ)r,l)(G,( 1 .

1)C(f

γC(f) *

50

Per ogni arco

denotiamo la funzione del costo marginale

Altri risultati per funzioni di latenza lineari Lemma

Sia un’istanza con funzioni di latenza

per ogni . Allora

a) un flusso è di Nash in se e solo se per ogni coppia i sorgente-destinazione e con ,


Ee )0,( eeeee ba bxa(x)l

e eeee fbfafC 2)(

eee bxaxl 2)(*

bxa(x)l eee Ee

PPP, 0Pf

Pe

eeePe

eee bfabfa

f G

(G,r,l)

51

b)un flusso è ottimale in se e solo se per ogni

coppia i sorgente-destinazione e con

Corollario

Sia una rete in cui la funzione di latenza di ogni

arco è della forma , allora per ogni vettore

di costo , un flusso ammissibile per è ottimale se

e solo se è un flusso di Nash.

PPP, 0PfG

Pe

e*ee

Pee

*ee bfabfa 22

*f

G

xa(x)l ee el

r (G,r,l)


52

Lemma 2Lemma 2

Supponiamo che abbia funzioni di latenza linerari e che sia un flusso di Nash, allora

a) il flusso è ottimale per ,

b) il costo di crescita marginale del flusso sul cammimo rispetto a equivale alla latenza di con flusso .

Lemma 3Lemma 3

Supponiamo che abbia funzioni di latenza linerari e che sia un flusso ottimale. Sia il costo marginale di crescita del flusso su un cammino

rispetto a . Allora per ogni un flusso ammissibile in ha almeno costo

(G,r,l)

f,l)(G,r 2/2/f

P 2/fP f

k

ii

**i

* )r(fLδ)C(f1

δ)r,l)(G,( 1

*f

0δ

)(fL **i

ii ts

(G,r,l)

*f


53

Teorema

Se ha funzione di latenza lineare, allora

dim

Altri risultati per funzioni di latenza generiche Teorema

Sia un’istanza e , allora

3

4),,( lrG

(G,r,l)

nGV )((G,r,l)

2/),,( nlrG


54

Conclusione

Attualmente, non ci sono ulteriori risultati per istanze Attualmente, non ci sono ulteriori risultati per istanze con generiche funzioni di latenza, ma le buone con generiche funzioni di latenza, ma le buone prestazioni di Internet, che osserviamo prestazioni di Internet, che osserviamo quotidianamente, possono essere una prova che esiste quotidianamente, possono essere una prova che esiste una modellizzazione per tali casi con un “ragionevole” una modellizzazione per tali casi con un “ragionevole” prezzo dell’anarchia . prezzo dell’anarchia .


Marinelli Claudia. 2 I ntroduzione alla TEORIA DEI GIOCHI D Definizione (Gioco strategico) Un...

Documents

Transcript of Marinelli Claudia. 2 I ntroduzione alla TEORIA DEI GIOCHI D Definizione (Gioco strategico) Un...