Introduzione allaTeoria dei giochi

Dott. Francesco Del FabbroUniversità di UdineA.A. 2003-2004

Cos’è la teoria dei giochi

Esamina le situazioni in cui due o più agenti, detti giocatori agiscono secondo regole stabilite, allo scopo di ottenere una vincita (payoff) di qualche genere.

L’insieme di regole che ogni singolo giocatore segue nel determinare le mosse da effettuare (da non confondere con le regole del gioco) è detto strategia.

Un po’ di storia

Teorema di Zermelo (1913) Teorema del minimax (von Neumann 1928) The Theory of Games and Economic Behavior

(von Neumann e Morgenstern 1944) Equilibrio di Nash (1950) Negli anni ’60-’70, l’equilibrio di Nash viene

raffinato, vengono studiati i giochi dinamici e quelli con informazione incompleta.

Una classificazione

Giochi a 2 oppure ad n (n≥2) giocatori Cooperativi e competitivi:

Cooperativi: i giocatori agiscono in vista del bene comune Non cooperativi: i giocatori non possono concertare una strategia

comune Competitivi: alla vincita di uno corrisponde la perdita dell’altro

A informazione completa: se ogni giocatore possiede tutta l’informazione sullo stato attuale del gioco (es. scacchi)

Deterministici: non ci sono elementi casuali. Il gioco si dice non deterministico se il caso fa parte delle regole del gioco

A somma costante: qualunque sia lo stato finale del gioco, la somma delle vincite e delle perdite dei giocatori (considerate vincite negative) è costante.

La matrice del gioco

Supponiamo gioco deterministico a somma nulla con due giocatori. Le strategie a loro disposizione siano:

A={A1,A2,…,Am} e B={B1,B2,…,Bn} Il gioco si può rappresentare come una matrice mxn, in

cui le righe corrispondono alle m strategie del primo giocatore, le colonne alle n strategie del secondo.

Gli elementi della matrice sono valori che quantificano la vincita del primo giocatore. L’elemento vij è la vincita del primo giocatore se sceglie la strategia Ai in risposta alla Bj del secondo

La matrice del gioco

B1 B2 … Bn

A1 V11 V12 … V1n

A2 V21 V22 … V2n

… … … … …

Am Vm1 Vm2 … Vmn

Esempio: pari e dispari

0 1 2

0 1 -1 1

1 -1 1 -1

2 1 -1 1

Esempio: forbici, sasso, carta

Forbici Sasso Carta

Forbici 0 -1 1

Sasso

Carta

Esempio: forbici, sasso, carta

Forbici Sasso Carta

Forbici 0 -1 1

Sasso 1

Carta

Esempio: forbici, sasso, carta

Forbici Sasso Carta

Forbici 0 -1 1

Sasso 1 0

Carta

Esempio: forbici, sasso, carta

Forbici Sasso Carta

Forbici 0 -1 1

Sasso 1 0 -1

Carta

Esempio: forbici, sasso, carta

Forbici Sasso Carta

Forbici 0 -1 1

Sasso 1 0 -1

Carta -1

Esempio: forbici, sasso, carta

Forbici Sasso Carta

Forbici 0 -1 1

Sasso 1 0 -1

Carta -1 1

Esempio: forbici, sasso, carta

Forbici Sasso Carta

Forbici 0 -1 1

Sasso 1 0 -1

Carta -1 1 0

Strategie pure

Il problema di ciascun giocatore è stabilire quale strategia utilizzare tra quelle a sua disposizione

Può adottare numerosi criteri per effettuare la scelta

Esempio: pari e dispari modificato

0 1 2

0 1 -1 2

1 -1 2 -3

2 2 -3 4

Maximin e minimax

Due giocatori prudenti cercheranno di minimizzare la perdita.

Il giocatore A sceglierà la strategia i* che permette di massimizzare la minima vincita (criterio maximin)

Il giocatore B sceglierà la strategia j* che permette di minimizzare la massima vincita dell’avversario (ossia di massimizzare la sua minima vincita) (criterio minimax)

i* e j* sono strategie ottimali, rispettivamente per A e per B, rispetto al criterio maximin e al criterio minimax.

La massima minor vincita per il giocatore A (α) è detta valore inferiore del gioco; la minima maggior vincita di A (β) è detta valore superiore del gioco

Esempio: pari e dispari modificato

0 1 2 3 minimo

0 1 -1 2 -3 -3

1 -1 2 -3 4 -3

2 2 -3 4 -5 -5

3 -3 4 -5 6 -5

massimo 2 4 4 6

Punti di sella

Non sempre le strategie pure scelte in base al criterio maximin minimax sono le migliori possibili.

Lo sono solo nel caso in cui α=β In questo caso ogni coppia di strategie ottimali (i*,j*) è

detta punto di sella Il valore comune di α e β è detto valore di sella o valore

del gioco Quando il gioco è provvisto di un punto di sella, A e B,

parlando della loro massima perdita, fanno riferimento alla stessa casella della matrice, che dunque rappresenta l’esito del gioco meno svantaggioso per entrambi.

Strategie miste

A e B possono decidere di affidarsi al caso Ma non vorranno scegliere spesso strategie

poco vantaggiose Quindi stabiliranno a priori la probabilità con cui

scelgono una data strategia. Date m strategie di A, una strategia mista X di A

è costituita dalle probabilità con cui vengono scelte le singole strategie

Teorema Minimax (von Neumann 1928)

Per le strategie mistei valori di α e β coincidono sempre

Ossia esiste un punto di sella

Ossia esiste una strategia ottimale rispetto al criterio maximin-minimax che è anche la migliore strategia

Quindi è possibile calcolare, conoscendo le strategie possibili e i relativi payoff, quali saranno le strategie

miste scelte dai due giocatori.

Esempio: calcolo della strategia mista di un giocatore

0 1

0 11 8

1 5 11

1

X

381118

6115111

1

0

j

j

Le speranze di guadagno di A nel caso che B scelga la strategia 0 oppure la strategia 1 sono:

EsempioVincita di A

λAλ* λ0 1

Se B sceglie 1

Se B sceglie 0

3

13

2

*

3

1

93

3861110

X

Giochi non cooperativi

Non sempre il giocatore, pur cercando il massimo profitto per se, è costretto a farlo a spese dell’altro giocatore.

Ossia, non tutti i giochi sono a somma costante o nulla

È possibile che le strategie dei giocatori non determinino solo come vengono tagliate le fette, ma anche quanto è grande la torta.

Esempio: il dilemma del prigioniero

B nega B confessa

A nega (A=-1, B=-1) (A=-10, B=0)

A confessa (A=0, B=-10) (A=-6, B=-6)

Esempio: la guerra dei sessi

Partita Teatro

Partita (A=2, B=1) (A=-1, B=-1)

Teatro (A=-1, B=-1) (A=1, B=2)

Situazione di equilibrio

Il gioco si dice in equilibrio quando i giocatori hanno adottato una combinazione di

strategie tale che nessuno di loro riuscirebbe a guadagnare cambiando la

propria strategia.

Esempio: il dilemma del prigioniero

B nega B confessa

A nega (A=-1, B=-1) (A=-10, B=0)

A confessa (A=0, B=-10) (A=-6, B=-6)

Esempio: la guerra dei sessi

Partita Teatro

Partita (A=2, B=1) (A=-1, B=-1)

Teatro (A=-1, B=-1) (A=1, B=2)

Esempio: gioco senza situazioni di equilibrio

Strategia 1 Strategia 2

Strategia 1 (A=1, B=2) (A=3, B=1)

Strategia 2 (A=4, B=3) (A=2, B=4)

Teorema di Nash

Ogni gioco non cooperativo a n giocatori ammette una strategia mista X*

di equilibrio.

Giochi cooperativi

Nei giochi cooperativi i giocatori devono cooperare per raggiungere il loro obiettivo

comune

Il paradosso dei due generali

Generale A Generale B

Nemico

Il paradosso dei due generali

Generale A Generale B

Nemico

Attaccare all’alba!

Il paradosso dei due generali

Generale A Generale B

Nemico

Attaccare all’alba!

ricevuto

Il paradosso dei due generali

Generale A Generale B

Nemico

Attaccare all’alba!

ricevutoricevuto

Il paradosso dei due generali

Generale A Generale B

Nemico

Attaccare all’alba!

ricevutoricevutoeccetera…

Esempio: la corsa agli armamenti

Missili si Missili no

Missili si (A=10, B=10) (A=200, B=0)

Missili no (A=0, B=200) (A=100, B=100)