Teoria dei Giochi: lezione del 16 Marzo 2017

Teoria dei Giochi: lezione del 16 Marzo 2017

Chiara Mocenni

Corso di Teoria dei Giochi e Giochi Evolutivi

Si supponga di avere a disposizione n scelte numerate per

affrontare una certa situazione. Per indicare in maniera formale la scelta, si utilizza un vettore x di n componenti (x ∈ R

). In particolare la componente i -esima x

sar` a l’unica pari ad 1 se si ` e deciso di adottare la strategia indicata con il numero i . Un vettore siffatto determina univocamente la scelta strategica che ` e stata adottata. In altri termini:

x

=

 1 se la strategia adottata ` e la i

0 se la strategia adottata non ` e la i (1)

Si pu` o pensare al profitto, normalmente chiamato payoff, come ad

una funzione π(x ) : R

−→ R che associa ad ogni vettore di scelta

x un numero reale che quantifica il profitto che il soggetto trae

dall’utilizzare la strategia scelta.

In generale per` o le scelte sono condizionate da altri fattori. Non ` e

raro trovarsi in contesti in cui il guadagno che si ottiene non

dipende esclusivamente dalle proprie decisioni; vi possono essere

ulteriori soggetti che partecipano nel processo di scelta, i quali

hanno le stesse intenzioni: massimizzare il proprio profitto. In

questi casi, succede spesso che il guadagno che si pu` o ottenere non

dipender` a solo dalle proprie scelte, ma anche da quelle altrui (e

viceversa). Se fosse possibile comunicare con gli altri partecipanti,

si potrebbe in qualche maniera trovare un accordo. In tal caso la

scelta potrebbe essere guidata da un semplice compromesso tra le

parti in gioco. Tuttavia il caso pi` u interessante si ha nel momento

in cui le scelte dei vari partecipanti sono fra loro indipendenti e

guidate solo dalla voglia di ogni soggetto di massimizzare il proprio

guadagno.

Questo tipo di interazione viene detta gioco, ed i soggetti che vi partecipano sono i giocatori. Nel caso pi` u semplice, il gioco si sviluppa tra due soggetti. Usando la definizione presentata in precedenza, si indichi con x ∈ R

come il vettore che identifica la scelta del primo soggetto su un pool di n strategie, cos`ı si indicher` a con y ∈ R

la scelta del secondo partecipante, il quale ha a disposizione m opzioni. I payoff sono dunque rappresentati da due funzioni, una per ogni soggetto:

π

(x , y ) : R

× R

−→ R payoff giocatore 1

π

(x , y ) : R

× R

−→ R payoff giocatore 2

L’obiettivo dei giocatori ora diventa quello di massimizzare il proprio payoff, ma tenendo conto di ci` o che far` a l’avversario. Il meccanismo di decisione si sviluppa a busta chiusa; le scelte di entrambi sono rese note contemporaneamente, dunque non vi ` e spazio per tentennamenti, escamotage o simili. ` E analogo al funzionamento di una asta per appalti pubblici: si scrive la propria scelta in una busta chiusa e tutte le buste vengono aperte

contemporaneamente.

La teoria dei giochi, di cui si parler` a nel seguito, ` e una branca

della matematica che ci permette di effettuare delle scelte

razionali. La razionalit` a di cui si parla ` e qualcosa di astratto,

probabilmente diverso rispetto a quella prettamente umana; essa

viene definita in base a determinati assiomi matematici, che, al

solito, cercano nel miglior modo possibile di fornire un modello

abbastanza potente e allo stesso tempo semplice da poter

descrivere e gestire situazioni reali.

La teoria dei giochi ` e uno strumento che ci aiuta a prendere decisioni. Essa ` e abbastanza robusta e si avvantaggia di svariati risultati e teoremi. Tali risultati si basano sul fatto che sono note tutte le funzioni di payoff; tutti i risultati della teoria infatti, si basano, oltre che sulla razionalit` a dei giocatori, anche sul fatto che si conoscono gi` a i payoff. In realt` a costruire le funzioni di payoff ` e spesso un lavoro arduo; ` e quasi come chiedere di quantificare la felicit` a che trae una persona dal fare una certa cosa!

In questi casi ci vengono in aiuto altri strumenti, come ad esempio

la stima del costo dell’informazione. Si assumer` a comunque che i

payoff siano ben determinati tramite qualche metodo e la teoria dei

giochi subentrer` a per dare delle risposte di tipo esecutivo, basate

su tale informazione a priori.

Il payoff del giocatore 1, cos`ı come quello del giocatore 2, sono determinati dalla coppia di strategie (i , j ), dove i ` e la strategia adottata dal giocatore 1 e j quella adoperata dal giocatore 2. Si indica con a

il payoff che il giocatore 1 ottiene se egli usa la strategia i mentre il suo avversario la strategia j . Con b

si indica il payoff del secondo giocatore: ancora, b

` e il guadagno che ottiene quando lui sceglie j e il primo giocatore sceglie i .

Segue in maniera naturale che sono state implicitamente definite due matrici di payoff A, B ∈ R

, tali che A = {a

} e

B = {b

}.

Mediante tali matrici, si caratterizzano le funzioni di payoff:

π

(x , y ) = x

Ay π

(x , y ) = x

By

Infatti, nel momento in cui x ed y sono vettori costruiti come

descritto in precedenza, allora x

Ay e x

By selezionano gli

elementi a

della matrice A e b

della matrice B, posto che x

ed

y

siano le uniche componenti di x e di y pari ad 1.

Nell’ambito della teoria dei giochi, vengono introdotte le best reply (lett. miglior risposta). Queste sono delle particolari funzioni che ci aiutano nel processo decisionale. La best reply del giocatore 1 associa ad ogni scelta strategica del giocatore 2 l’insieme delle strategie che il giocatore 1 deve adottare se vuole massimizzare il suo payoff. Si indicano con β

(j ) e β

(i ) le best reply dei giocatori. Ecco un esempio:

A =





1 3 0

2 0 4

5 9 3



 =⇒







β

(1) = {3}

β

(2) = {3}

β

(3) = {2}

In pratica, considerando che le colonne indicano le strategie del

giocatore 2, si fissa la colonna relativa alla strategia j ; si cerca in

tale colonna l’elemento massimo. La best reply sar` a dunque la

strategia i (riga) al quale corrisponde l’elemento massimo.

Un altro esempio:

A =





3 6 2

3 6 1

5 1 0



 =⇒







β

(1) = {3}

β

(2) = {1, 2}

β

(3) = {1}

In questo caso succede che, se il giocatore 2 adotta la strategia

j = 2, allora il giocatore 1 ` e indifferente nell’utilizzare le strategie

i = 1 ed i = 2, in quanto gli garantiscono lo stesso payoff. La

costruzione della best reply function del giocatore 2 ` e del tutto

analoga a quella appena descritta, salvo scambiare i ruoli alle righe

(strategie del giocatore 1) con le colonne (strategie del giocatore

2).

Si consideri il seguente gioco:

A =





3 6 20

3 6 1

5 1 0



 =⇒







β

(1) = {3}

β

(2) = {1, 2}

β

(3) = {1}

B =





4 8 2

1 1 10

3 5 5



 =⇒







β

(1) = {2}

β

(2) = {3}

β

(3) = {2, 3}

L’egoismo dei giocatori potrebbe portarli a prendere una decisione che poi potrebbe quasi certamente non rispecchiare le aspettative.

L’idea per uscirne fuori ` e quella di giungere ad un compromesso, ovvero effettuare una scelta strategica che va bene ad entrambi i giocatori. Bisogna cio` e raggiungere una situazione di equilibrio tra le parti. In termini matematici, si pu` o definire un equilibrio alla seguente maniera:

(i

, j

) ` e un equilibrio ⇐⇒

 i

∈ β

(j

)

j

∈ β

(i

) (2)

Tale nozione ` e stata formalizzata dal premio Nobel J.F.Nash da cui

il nome equilibri di Nash.

Osservando le best reply function riportate in precedenza, si ottiene che (i

, j

) = (1, 2). Infatti

i

= 1 ∈ β

(j

= 2) = {1, 2}

e

j

= 2 ∈ β

(i

= 1) = {2}.

Se il giocatore 2 fosse a conoscenza del fatto che l’avversario

sceglie i = 1, allora sicuramente sceglierebbe j = 2; questa mossa

gli garantirebbe il massimo payoff raggiungibile in relazione al fatto

che i = 1. Il giocatore 1 similmente, venendo a conoscenza del

fatto che il giocatore 2 giocher` a j = 2, si trover` a nella situazione di

dover scegliere tra i = 1 ed i = 2, nel qual caso riuscir` a comunque

a massimizzare il suo payoff. Se ai giocatori venisse data la

possibilit` a di cambiare la propria strategia una volta scelti i = 1 e

j = 2, essi non ne avrebbero motivo. Per questo si parla di

equilibrio.

L’equilibrio di Nash trovato in particolare ` e non stretto, a causa del fatto che il giocatore 1 ha due opzioni per massimizzare il suo payoff rispetto alla scelta j = 2. Nei casi in cui questa ambiguit` a non si presenta, si parler` a invece di equilibri stretti. Non ` e per` o in generale garantito che, dato un certo gioco, esista un solo

equilibrio di Nash. Si possono presentare delle situazioni in cui gli

equilibri sono pi` u di uno, o addirittura nessuno!

Il metodo della bimatrice invece e’ il seguente:

gioc. 2

strat. 1 strat. 2

strat. 1 (5, 2) ← (1, 1)

gioc. 1 ↑ ↓

strat. 2 (1, 7) ← (2, 3)

Nel momento in cui si ottiene una certa strategia che possiede solo frecce entranti, allora quella rappresenta un equilibrio di Nash stretto. In particolare il numero di frecce entranti ` e pari al massimo (2 nel caso specifico di giochi con 2 partecipanti). Nel caso

particolare si ha che la strategia (1, 1) ` e un equilibrio di Nash

stretto.

Ecco un altro esempio:

gioc. 2

strat. 1 strat. 2

strat. 1 (4, 20) ← (3, 15)

gioc. 1 l ↑

strat. 2 (4, 7) → (2, 13)

La doppia freccia sta indicare il fatto che il giocatore 1 ` e

indifferente a scegliere la sua strategia se l’avversario sceglie la

strategia 1 (otterr` a in ogni caso lo stesso payoff). Si vede che la

coppia di strategie (1, 1) ` e un equilibrio poich` e ha 2 frecce entranti,

ma in questo caso non ` e stretto, infatti ne ha anche una uscente.

Definiamo I = {1, 2, ...n} l’insieme dei giocatori, dove n ` e un intero positivo e con S

= {1, 2, ...m

} l’insieme di strategie pure per ogni giocatore i ∈ I , con m

≥ 2. Il giocatore i `e caratterizzato da un vettore x

∈ R

tale che:

x

=

 1 se la strategia adottata dal giocatore i ` e la j

0 se la strategia adottata dal giocatore i non ` e la la j . (3) L’insieme dei vettori {x

, x

, . . . , x

} viene detto profilo di

strategie.

Per ogni profilo di strategie ed ogni giocatore i ∈ I , sia

π

(x

, x

, . . . , x

) ∈ R il payoff associato al giocatore i. In teoria dei giochi, il payoff per un giocatore ` e una funzione che esprime la valutazione del suo risultato ottenuto, a seguito delle scelte operate da tutti i giocatori coinvolti. Nel caso particolare di un gioco a due giocatori le funzioni payoff, π

(x

, x

) e π

(x

, x

), vengono

rappresentate da due matrici A e B del tipo R

; notare inoltre

che in questo caso sono stati usati x

al posto di x , e x

anzich` e y .

Una strategia mista per il giocatore i ` e una distribuzione di probabilit` a sull’insieme delle sue m

strategie pure. Formalmente:

x

= Probabilit` a con cui il giocatore i user` a la strategia j (4) Alla luce di questa definizione possiamo interpretare una strategia pura come un caso particolare di una strategia mista. Dire che “il giocatore i usa la strategia pura j ” equivale a dire che “il giocatore i usa la strategia j con il 100% di probabilit` a”.

Un esempio di strategia mista ` e il seguente:

x

= 

0.4, 0.1, 0, 0.5  , (5)

dove il giocatore i ha a disposizione m

= 4 strategie.

Poich` e x

(per j = 1, 2, ..., m

) rappresentano delle probabilit` a, allora il vettore x

∈ R

appartiene al simplesso ∆

nell’m

-spazio:

∆

=







x

∈ R

:

mi

X

j =1

x

= 1







. (6)

Figura: Il simplesso ∆

con m = 3.

Figura: Rappresenta geometrica del simplesso nel caso m = 3.

Il simplesso ∆

del giocatore i ha dimensione m

− 1.

I vertici di ∆

sono i versori nell’m

-spazio, identificati da e

= (1, 0, ..., 0), e

= (0, 1, ..., 0), fino a e

= (0, 0, ..., 1).

Ogni vertice e

rappresenta la strategia mista del giocatore i che assegna probabilit` a 1 all’j -esima strategia pura. Se il giocatore i usa la strategia pura j , allora x

= e

.

Il simplesso di strategie miste ∆

` e un involucro convesso dei vertici, ed ogni x

∈ ∆

` e una combinazione convessa dei versori, o strategie pure e

:

x

=

mi

X

j =1

x

e

. (7)

Il sottoinsieme interno di ∆

` e definito come:

int(∆

) = {x

∈ ∆

: x

> 0 ∀j} (8) Le strategie miste di questo sottoinsieme vengono chiamate interne o completamente miste, ed assegnano probabilit` a positive a tutte le strategie pure dei giocatori.

L’insieme delle strategie non interne in ∆

viene chiamato frontiera (o bordo) di ∆

, definito come:

bd (∆

) = {x

∈ ∆

: x

∈ int(∆ /

)} (9)

La frontiera di ∆

` e l’insieme di strategie x

per le quali

almeno una strategia j viene giocata con probabilit` a nulla,

ovvero ∃j ∈ {1, . . . , m

} : x

= 0

Un profilo di strategie miste X = {x

, x

, ..., x

} `e un punto dello spazio delle strategie miste del gioco:

Θ = ×

∆

. (10)

Essendo Θ il prodotto di n unit` a semplici ∆

, dove ognuna di esse

` e un insieme (m

− 1)-dimensionale per ogni giocatore i ∈ I , l’insieme ` e un poliedro (m − n)-dimensionale in R

, con m = m

+ m

+ ... + m

il numero totale di strategie pure nel gioco. Un profilo di strategie X ` e detto interno se ogni componente x

` e interna. Il sottoinsieme di tali profili ` e definito come:

int(Θ) = ×

int(∆

). (11)

Similmente, il contorno di Θ, bd (Θ), ` e l’insieme dei profili non

interni x ∈ Θ.

L’introduzione del concetto di strategie miste implica una rivisitazione del concetto di payoff. Infatti, poich` e le strategie miste sono distribuzioni di probabili` a, allora anche il payoff ` e il valore atteso dei payoff che si possono guadagnare utilizzando solo strategie pure. Tale risultato vale per qualunque gioco con n giocatori.

Analizziamo il caso semplice dei giochi con 2 giocatori. Sia A ∈ R

la matrice di payoff del giocatore 1. Si supponga che il giocatore 1 decida di utilizzare la strategia pura i , mentre il giocatore 2 gioca una strategia mista x

. In media, il giocatore 1 guadagner` a la seguente quantit` a:

u

=

m2

X

j =1

a

x

,

ovvero la somma dei payoff a

pesati dalle probabilit` a x

.

Se il giocatore 1 opta per la strategia mista x

, in media guadagna:

m1

X

i =1

x

u

=

m1

X

i =1 m2

X

j =1

x

a

x

,

ovvero la somma dei payoff medi u

pesati dalle probabilit` a x

. La doppia sommatoria consente di riscrivere il payoff in forma matriciale:

m1

X

i =1 m2

X

j =1

x

a

x

= x

Ax

,

rendendo la precedente equazione in linea con la definizione di payoff delle strategie pure:

π

(x

, x

) = x

Ax

. (12) In maniera del tutto simile, il payoff del secondo giocatore sar` a

π

(x

, x

) = x

Bx

.

Consideriamo i giochi a due giocatori e due strategie. I payoff dei 2 giocatori sono rappresentati dalle seguenti matrici:

A =

 a

b

c

d



, B =

 a

c

b

d

 . e la relativa bimatrice ` e:

G 2

s1 s2

s1 (a

, a

) (b

, c

) G 1

s2 (c

, b

) (d

, d

)

Si considerino le funzioni di payoff ottenute con le matrici A e B, ed usando come vettori x = [x

1 − x

]

ed y = [y

1 − y

]

:

π

(x , y ) = x

[(a

− c

+ d

− b

)y

+ b

− d

] + (c

− d

)y

+ d

π

(x , y ) = y

[(a

− c

+ d

− b

)x

+ b

− d

] + (c

− d

)x

+ d

(13) Calcolando le derivate

1

e

1

e ponendole uguali a 0, si ottengono le seguenti soluzioni:

x

= (d

− b

)

(d

− b

) + (a

− c

) , x

= (a

− c

) (d

− b

) + (a

− c

) y

= (d

− b

)

(d

− b

) + (a

− c

) , y

= (a

− c

) (d

− b

) + (a

− c

)

(14)

Tali soluzioni sono valide se appartengono al simplesso ∆ di dimensione 2 e rappresentano l’eventuale equilibrio misto del gioco.

Gli equilibri puri invece possono essere ricavati utilizzando il

metodo della bimatrice.