Strumenti della Teoria dei Giochi per l’Informatica
A.A. 2009/2010
Sebastiano Panichella
1
Scenario
 L’emergente 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:
p 1 e p2 due giocatori;
p1 che p2 vogliono andare da
 siano
 sia
S (Sorgente) a D (Destinazione);
 le strade disponibili per andare da S a D sono due, A e B
A
S
D
B
p1 /
p2
A
B
A
4
3
2
2
B
1
1
3
4
Tabella dei payoff
2
Motivazioni
 I Congestion Game hanno attirato l’attenzione 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 un’unica strategia
 Per il meccanismo noto come “Nash dynamics”, dove a ogni passo qualche
giocatore cambia la sua strategia verso un’altra ritenuta più conveniente, è
garantita la convergenza a un “pure Nash equilibria”.
3
Congestion Game
 Definizione di Congestion Game:
 n giocatori
 p , , p  ;
1
n
 a ciascun giocatore i viene assegnato un insieme finito di strategie
S i (ossia un insieme di risorse disponibili all’i-esimo giocatore);
 a ciascun giocatore i viene assegnata una funzione di costo
ci : S1   Sn  N che desidera minimizzare (il costo di ogni
strategia dipende solo dal numero di giocatori che usano la risorsa
in questione)
Maggiore è il numero dei
giocatori che utilizzano
una risorsa
Maggiore
è il
costo
4
Congestion Game
| si |
 Formalmente il costo per pi è
 Uno stato
d  f 
r
r
rsi
s  ( s1 ,, sn )  S1 
funzione di costo (non negativa)
numero di giocatori che
usano la risorsa “e”
 Sn è una qualsiasi combinazione di
strategie per gli n giocatori.
 equilibrio di Nash puro: uno stato
s  ( s1 ,, sn )  S1 
 Sn
è un equilibrio di Nash se
pi
Per ogni
giocatore
'

s
ci ( s1 , , si , , sn )  ci ( s1 ,, s ,, sn )
i  Si
'
i
Il costo della strategia
scelta da pi
Il giocatore pi non è
incentivato a
cambiare
Per ogni
altra strategia
5
Classe di Congestion Game
 Nella Classe di Congestion Game che consideriamo:
 i giocatori condividono un insieme di risorse (gioco simmetrico)
E  e1,, em  chiamate archi
 l’insieme di strategie,
Si , di un giocatore pi è una collezione
arbitraria di sottoinsiemi di E
 la strategia del giocatore pi,
 a ogni arco
si  Si è un sottoinsieme di E
e  E è associata una funzione di costo (o ritardo)
non decrescente
de : 1,, n  N
6
Classe di Congestion Game
 Se t giocatori utilizzano l’arco e ciascuno di essi pagherà un costo de(t)
Esempio
dstrada(1)=2
In generale
dstrada(2)=4
dstrada(t)=
2t
dstrada(3)=8
 In uno stato s=(s1 ,…, sn) il costo del giocatore pi è
ci ( s)  de  f s  e  
esi
numero di giocatori che usano
l’arco “e” nello stato “s”
7
Funzioni Potenziali
 Funzione potenziale: i giochi a congestione sono in possesso una
precisa funzione potenziale definita come
fs e
  s    de  t 
eE t 1
Sommiamo i costi
sostenuti in base
ai giocatori che
lo utilizzano
Per ogni arco
 proprietà: il cambiamento in 𝜙 rispecchia esattamente la variazione dei
costi del giocatore
se il giocatore pi
cambia la sua strategia
da si a s’i
  s     s '   ci  s   ci  s ' 
Variazione del
potenziale
=
Variazione del
costo per pi
8
Funzioni Potenziali
 Osservazione:
Se a ogni passo
permettiamo ai
giocatori di modificare
la propria strategia
(più conveniente)
diminuirà

fino a raggiungere un minimo locale
ossia
ma
Niente ci assicura “la
rapida convergenza” a
un equilibrio di Nash
un equilibrio di Nash puro
9
Accuratezza
Approssimazione di equilibri di
Nash
ottimo
Tempo
10
Definizioni
 ε-equilibrio di Nash: sia
  0,1 , uno stato s  (s1 ,, sn )  S1   Sn
è un ε-equilibrio di Nash se
 pi , ci ( s1 , , s'i , , sn )  (1  ε )ci ( s1 , , si , , sn )  s'i  S i
Per ogni
giocatore
Il giocatore pi non ha più di un
ε-incentivo a cambiare strategia
Per ogni
strategia
 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 pi si sposta da si a si’ allora
ci ( s1 , , s'i , , sn )  (1   )ci ( s1 , , si , , sn )
11
ε-N.E. e Dinamiche ε-Nash
Se i giocatori non hanno
più ε-mosse da effettuare
I giocatori hanno raggiunto
un ε-equilibrio di 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 pi effettua la sua mossa se, tale mossa massimizza il rapporto
R
ci  s   ci ( s1 , , s'i , , sn )
ci ( s )
Costo ottenuto nel caso in
cui il giocatore effettua la
mossa si’
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
d : E  , diciamo che l’arco “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
de  t  1    de t 
costo dell’arco e per
(t +1) giocatori
costo dell’arco 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
Lemma 3.2
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 pi ,allora
 j  i c j  s   α ci  s 
Per ogni giocatore
pj diverso dal
giocatore pi
Il costo del giocatore pj è
al più α volte il costo del
giocatore pi
14
Lemma 3.2
DIMOSTRAZIONE
• Supponiamo che il gioco si trovi in uno stato s  ( s1 , , sn )
• Supponiamo che un giocatore pi voglia effettuare una mossa da si a si’
con guadagno relativo
ci  s   ci ( s1,, s'i ,, sn )
Ri 
ci ( s)
• Supponiamo che un altro giocatore pj≠pi voglia effettuare la stessa
mossa,ossia, si muove da sj a sj’’ = si’ con guadagno relativo
Rj 
c j  s   c j ( s1 ,, s j '',, sn )
c j ( s)
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 pi effettua la sua mossa, deve valere che Rj≤Ri
15
Lemma 3.2
Ossia
c j ( s)  c j ( s1 ,, s'j' ,, sn )
c j ( s)
ci ( s)  ci ( s1 ,, s'i ,, sn )

ci ( s )
(1)
A questo punto, confrontiamo il costo ci ( s1,, s'i ,, sn ) che il giocatore
pi paga per effettuare la sua mossa con quanto avrebbe pagato il
giocatore pj per effettuare la sua mossa da sj’’ (se vedessimo vincere l’uno
o l’altro giocatore): ∀ arco e  (s1, , si ', , sn ) che il giocatore pi vuole
usare, possiamo avere che
1. pi sta già usando l’arco
“e” prima della mossa
pi paga
de  f s (e) 
per usare l’arco e
pj paga al più de  f s (e)  1 per usare l’arco e
(perchè pj stesso potrebbe essere il nuovo
giocatore che utilizza l’arco e)
Per la condizione di “bounded jump” abbiamo che
de  f s (e)  1   de  f s (e. ) 
16
Lemma 3.2
2.
pi non sta già usando
l’arco e prima della mossa
Sommando su tutti gli archi
pi paga de  f s (e)  1 per usare l’arco e
pj paga al più lo stesso prezzo de  f s (e)  1
e  si ' abbiamo che
c j ( s1 ,, s''j ,, sn )   ci ( s1,, s'i ,, sn )
(2)
Sostituendo la (2) nella disequazione (1) abbiamo che
c j ( s)  c j ( s1 ,, s''j ,, sn )
c j ( s)
Rj
'
c
(
s
)

c
(
s
,

,
s
i
i
1
i , , sn )
 c j ( s)   ci ( s1 ,, s ,, sn ) 
ci ( s )
c j ( s)
'
j
Ri
17
Lemma 3.2
c j ( s)  ci ( s1 ,, s'j ,, sn ) ci ( s) ci ( s1 ,, s'i , , sn )





c j ( s)
c j ( s)
ci ( s)
ci ( s )
 1
 

 ci ( s1 ,, s'j ,, sn )
c j ( s)
 ci ( s1 ,, s'j ,, sn )
c j ( s)
 ci ( s1 ,, s'j ,, sn )
c j ( s)
ci ( s1 ,, s'i ,, sn )
 1

ci ( s)
ci ( s1 ,, s'i ,, sn )


ci ( s)
ci ( s1 ,, s'i ,, sn )


ci ( s)
Semplificando, abbiamo

c j ( s)

1
ci ( s )
 j  i c j  s   α ci  s 
18
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
 n 

log(
n

C
)
 

Il fattore di
approssimazione
>0
Bounded
condition
Limite superiore al
costo di ciascun
giocatore
19
Teorema 3.1
DIMOSTRAZIONE
Dal Lemma 3.2 sappiamo che se pi è il giocatore che si muove da si a si’ allora
 j  i c j  s    ci  s 
Siccome
 ci  s  
1

il costo che paga il giocatore è di almeno 1
volte il più grande costo di ogni giocatore 
n
 stato s abbiamo  (s)   ci (s) allora ci (s) 
i
Il potenziale
c j s
1
 (s)
αn
≤ costo complessivo
Il costo del giocatore pi ≥
1
α la media del potenziale
20
Teorema 3.1
Dato che
Da cui, dopo un movimento di pi stato s allo stato s’
ci (s) 
1
 (s)
αn
  s     s'   ci  s   ci  s'    ci  s   ε  (s)
αn
Variazione del
potenziale
In generale
=
Variazione del
costo per pi
Trattandosi di un ε-mossa la variazione
del costo per pi è più di ε-volte il costo
dello stato precedente s
Nello stato iniziale 𝜙 =𝜙max = potenziale iniziale; dato che
Ad ogni passo



 n
Numero totale di passi per la convergenza
 n

log

(
s
)
 
 e dal momento che max  nC


21
PLS-completezza di giochi con
Bounded Jump
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
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
non hanno effetti
I risultati finora ottenuti
hanno effetti significativi
sugli equilibri di Nash esatti
sugli ε-equilibri di Nash
22
L’Esempio
 Anche se gode della Bounded Jump condition questo
semplice problema di allocazione di risorse
Esempio
dstrada(1)=2
In generale
dstrada(2)=4
dstrada(t)=
2t
dstrada(3)=8
è 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
Una variante 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.
Cerchiamo il giocatore che massimizza R  ci  s   ci ( s1 ,, s'i ,, sn )
Costo Precedente
Un’altra variante della ε-Nash dynamics
Costo del giocatore
se effettua la mossa
si’
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
Cerchiamo il giocatore con ci  s  più grande
25
Varianti della ε-Nash dynamics
1) Domanda: per queste varianti dell’ ε-Nash dynamics, il teorema 3.1
è ancora valido?
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
Le dinamiche senza “restrizioni”
 Osservazione: finora abbiamo sempre utilizzato un meccanismo di
coordinamento nel quale il giocatore con il maggiore incentivo fa la
prima mossa
 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
27
Le dinamiche senza “restrizioni”
 Più formalmente la dinamica senza restrizioni è
 una sequenza di
q1 ,q2 ,… ,qn dove
ogni qt indica un giocatore
 al passo t al giocatore qt
è data la possibilità di muoversi
Si
qt ha un ε-mossa?
No
Fa la mossa
Non fa nulla
 Vogliamo che per qualche costante T ogni giocatore pi compaia
almeno una volta in ogni intervallo di sequenza con lunghezza T
28
Le dinamiche senza “restrizioni”
 Esempio:
La “Round-Robin” dynamics
 A turno a ogni player pi 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 ε-Nashdynamics, 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
 n(α  1)

log
(
nC
)
T
 ε (1  ε )



è un limite
superiore al costo
di ogni giocatore
  s0     st  
ε (1  ε ) 0

n(α  1)
30
Le dinamiche senza “restrizioni”
Per provare il teorema 4.1 è utile enunciare (e dimostrare) il seguente
Lemma:
Lemma 4.2 Sia ci (s) il costo sostenuto dal giocatore pi nello stato s ,
e sia ci (s’) il costo di pi “in uno stato futuro s’ in cui non si è mosso”.
Allora


  s     s'    ci  s   ci  s'  .
“Concettualmente”
mette in relazione
il miglioramento della
funzione potenziale
la variazione del costo per pi,
anche quando il giocatore
non fa nessuna mossa per
molti steps
31
Le dinamiche senza “restrizioni”
Dimostrazione lemma
Sappiamo che

ci  s   ci  s'    de  f s  e    de  f s'  e  
eSi

la variazione del costo
per pi
I contributi positivi a questa somma sono dati
dagli archi e che altri giocatori hanno liberato
f s  e   f s' (e)
Sapendo che e il primo giocatore pj che rinuncia a e aveva un costo di
almeno de ( f s  e)  allora la funzione potenziale migliora di almeno
εde ( f s  e) 
32
Le dinamiche senza “restrizioni”
ε-volte quanto
ci guadagna pi
Il miglioramento totale di 𝜙 è
  s     s'  

e: f ( e )  f
s

εde ( f s  e)    ci  s   ci  s' 
s'
Dimostrazione Teorema 4.1
(e )
Convergenza in
al più

 n(α  1)

log
(
nC
)
T
 ε (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
ε (1  ε ) 0

n(α  1)
valore che ha
assunto la funzione
potenziale all'inizio
dell'intervallo
33
Le dinamiche senza “restrizioni”
 Siano
s 0 , s1 ,, sT
gli stati durante questo intervallo
(non necessariamente differenti)
 Sia ph il giocatore con il maggior costo in s0
 Sia t ≥ 0 la prima volta in cui,durante l’intervallo, al giocatore ph è data
la possibilità di muoversi
Avremo due casi:
• Caso(i): al tempo t , ph ha un ε-mossa a disposizione
• Caso(ii): al tempo t , ph non ha un ε-mossa a disposizione
34
Le dinamiche senza “restrizioni”
Caso(i)
dal Lemma 4.2, abbiamo la garanzia che

  s 0     s t   ε ch  s 0   ch  s t 

la variazione del costo per ph,
il miglioramento della
funzione potenziale anche quando il giocatore non fa
nessuna mossa per molti steps
Dopo l’ ε-mossa di ph , 𝜙 sarà migliorata di almeno
ε
εch  s 0     s 0 
n
ε-Media del
potenziale iniziale
Convergenza
in al più
 n(α  1)

log
(
nC
)
T
 ε (1  ε )



Il teorema è soddisfatto
35
Le dinamiche senza “restrizioni”
Caso(ii)
Non avendo un ε-mossa a disposizione non vogliamo che ph possa fare un
ε-mossa adottando semplicemente la strategia di un altro giocatore, pi
• Al momento t, dobbiamo avere
Costo di ph
per simulare
la mossa di pi
pi  ph
t
t
α  ci ( s t )  ch  s   εch  s 
  ci  st   ch  s t  1   

Utilità di ph
per simulare
la mossa di pi
  ci  st 
 ch  s t  (3)
1   
36
Le dinamiche senza “restrizioni”
Analizzeremo due casi:
(1° caso)
Consideriamo un giocatore pi, a cui è data la possibilità di fare la sua mossa
al tempo t’ > t ossia, dopo che a ph è stata data la possibilità di muoversi
(2° caso)
Consideriamo l’ultimo giocatore, pi ,a cui è data la possibilità di fare la sua
mossa al tempo t’ < t
37
Le dinamiche senza “restrizioni”
(1° caso)
Sia pi , un giocatore che fa la sua mossa al tempo t’ > t ossia, dopo che a ph
è stata data la possibilità di muoversi, avremo che
 
 
 
ch  s t   ch  s 0  e ci s t'  ci s t  ci s 0
=
=
α
da ch  s  
ci ( s t ) (3)
1 ε
t
La variazione
della funzione =
potenziale
 s     s '     ci  st ' 
0
t
 
abbiamo che ci s t' 
1 ε
ch s 0
α
 
0
1 ε
(1

ε
)

(
s
)
ε
ch s 0  ε
α
α
n
 
Il teorema è soddisfatto
38
Le dinamiche senza “restrizioni”
(2° caso)
Sia pi , l’ultimo giocatore che fa la sua mossa al tempo t’ < t,
α
dalla proprietà ch  s  
ci ( s t ) (3)
1 ε
α
t
t'
possiamo affermare che ch  s  
ci s (4)
1 ε
t
 
Nell’istante t’
Infatti da (3) la condizione
deve essere soddisfatta da pi
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
Le dinamiche senza “restrizioni”
 Allora la variazione di potenziale
Deriva dal LEMMA 4.2

massimo miglioramento
ottenuto da pi per la sua mossa
  s 0     s t   ε ch  s 0   c h  s t 
   
  s     s   max ε (ci s
0
t
t'
 
   , ε ch s 0  ch s t
1  ε

 ε max 
(ch s t , ch s 0  ch s t 
 α

 
 
 
Deriva
dalla condizione
ch  s t  
α
ci ( s t )
1 ε
(3)
40

Le dinamiche senza “restrizioni”
 Allora la variazione di potenziale
Deriva dal LEMMA 4.2

massimo miglioramento
ottenuto da pi per la sua mossa
  s 0     s t   ε ch  s 0   c h  s t 
   
  s     s   max ε (ci s
0
t
t'
 
   , ε ch s 0  ch s t
1  ε

 ε max 
ch s t , ch s 0  ch s t 
 α

 
è minima quando
α
t
ch s 
ch s 0
α 1 ε
 
 
 
allora  s 0
 
 
 
0

s
ε
(1

ε
)
ε
(1

ε
)
  st 
ch s 0 
α 1 ε
α 1
n
 
 
È soddisfatta
41

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
3) Domanda: se generalizziamo il gioco permettendo a ciascun
giocatore di dichiarare il proprio ε (che in un certo qual modo indica la
“tolleranza” all’infelicità 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 pi ha un proprio valore ε, che
chiameremo εi che specifica la sua “tolleranza” all’infelicità
ε-equilibrio di Nash: per ε  (εi )  [0,1) , uno stato
s  ( s1 ,, sn )  S1   Sn è un ε- equilibrio di Nash se
n
 pi , ci ( s1 , , s'i , , sn )  (1  εi )ci ( s1 , , si , , sn )  s'i  S i
Per ogni
giocatore
Il giocatore pi non ha più di un
εi-incentivo a cambiare strategia
Per ogni
strategia
43
Giocatori eterogenei
Dinamiche best response ε-approssimate: dinamiche best response nelle
quali ciascun giocatore pi può fare solo εi-mosse, ossia movimenti che
migliorano il costo di un fattore maggiore di εi. più formalmente se il
giocatore pi si sposta da si a si’ allora
ci ( s1 ,, s'i ,, sn )  (1   i )ci ( s1 ,, si ,, sn )
Cambiare strategia non conviene più di εi volte
il costo della strategia attuale
44
Giocatori eterogenei
 Vedremo che

nα
questa dinamica converge in O (
log(nC )) passi
εmin (1  εmax )
εmin  mini εi e εmax  maxi εi
 il numero di passi di tempo in cui un giocatore con tolleranza εi
"sarà" infelice "(cioè, avrà un ε-move disponibile) è essenzialmente
 nα

log(nC ) 
 εmin

O
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 pi .
 “volte” in cui
Allora, ε  0, ci sono al massimo 
nα
log(
nC
)


 ε (1  εmax )

qualche giocatore pj con εj ≥ ε sarà in grado di muoversi prima che l’ εNash dynamics converga
Dimostrazione Teorema 5.2
Sia s =(s1,…,sn), uno stato in cui un giocatore pj con εj ≥ ε ha una εj -move
disponibile. Ai fini della prova è sufficiente dimostrare che la riduzione
della funzione potenziale 𝜙 è almeno
ε j 1  εmax 
αn
 ( s)
pi  max   i
46
Giocatori eterogenei
 Sia pi il giocatore che si muove “attualmente” dallo stato s a
. s'  ( s1,, s'i ,, sn ).
 Sia ph il giocatore con il “maggior costo” in s
Analizzeremo due casi:
• Caso(i): ph
= pi , ossia, pi ha il maggior costo
• Caso(ii): ph ≠ pi ossia, pi non ha il maggior costo
47
Giocatori eterogenei
Caso(i)
Se il ph= pi allora abbiamo già finito, dal momento che ad ogni
passo il potenziale si riduce di almeno
ch ( s ) 
Convergenza
in al più n.
passi pari a
 ( s)
n
  ch ( s )  
 ( s)
n
 n(α  1)

log (nC )T 

 ε j (1  εmax )

Il teorema è soddisfatto
48
Giocatori eterogenei
Caso(ii):
ph ≠ pi ossia, pi non ha il maggior costo
Supponiamo che ph possa muoversi da s a s’’ simulando la strategia
s’i del giocatore pi .
Siccome non vogliamo che ph possa muoversi da s, dato che non è il suo
turno
Analizziamo due casi:
• Caso(1): la mossa da s a s’’ non deve essere una εh-move per ph
• Caso(2): il guadagno relativo per ph non è più grande del guadagno
relativo che ottiene consentendo a pi di effettuare la sua mossa.
49
Giocatori eterogenei
• Caso(1): la mossa da s a s’’ non deve essere una εh-move per ph
Sappiamo che
• ch  s   ch ( s'' )  εhch ( s)
 ch ( s'' )  ch  s   εhch ( s)
• ch ( s'' )  α (1  ε j )ci ( s)
 ch ( s'' )  αci ( s)
(Dal teorema 3.1)
Combinando le due disequazioni, abbiamo
ch  s   εhch ( s)  ch ( s'' )  αci ( s)
1  εh
ci  s  
ch ( s )
α
Allora
ch  s   αci ( s)  εhch ( s)
  j ci  s  
 j 1  εh 
α
ch ( s )
ε j 1  εh 
la variazione di potenziale   s    ( s' )   j ci  s  
 ( s)
αn
Il teorema è
soddisfatto
50
Giocatori eterogenei
• Caso(2): il guadagno relativo per ph non è più grande del guadagno
relativo che ottiene consentendo a pi di effettuare la sua mossa ,ossia,
ch  s   ch ( s'' )
ch ( s )
Dato che
ch ( s'' )  αci ( s' )
Siccome
Rh
n

ci  s   ci ( s' )
ci ( s )
Ri
c h ( s )   ci ( s )
 stato s abbiamo  (s)   ci (s) allora ci (s) 
i
1
 (s)
αn
Allora
j
la variazione di potenziale   s    ( s' ) 
 ( s)
n
□
51