Teoria Dei Giochi - Strategie Dominanti PDF

Preview

Summary

teorie dei giochi...

Description

Teoria dei Giochi: Strategie Dominanti e Strategie Dominate M. Vittoria Levati Equilibrio in Strategie Dominanti Una strategia pura del giocatore i, s ∗i , si dice strettamente dominante se fornisce i risultati migliori indipendentemente da quello che fanno gli altri giocatori. Formalmente, indicando con s− i il prof lo di strategie degli altri giocatori, s∗i `e strettamente dominante per il giocatore i se πi (s ∗ i , s −i ) > πi ( si , s −i) per ogni si ∈ Si e ogni s −i ∈ S−i . Per ogni possibile strategia degli altri giocatori, la strategia s ∗i permette ad i di avere un payoff maggiore di qualsiasi altra strategia che ha i a disposizione. Un proflo di strategie s∗ tale che per ogni giocatore i la `e dominante costituisce un equilibrio in strategie strategia s∗i dominanti. Per esempio, nel Dilemma del Prigioniero, “Confessare” (C) `e una strategia strettamente dominante per entrambi i giocatori. Pertanto, il prof lo di strategie (C, C) `e un equilibrio in strategie dominanti ed `e ovviamente la soluzione del Dilemma del Prigioniero: ogni decisore razionale dovrebbe adottare la sua strategia dominante, se questa esiste. • Il Dilemma del Prigioniero `e famoso perch´e illustra chiaramente la tensione tra interesse individuale e quello collettivo. • Si tratta di una caso analogo a quello del cosiddetto “free-riding ”: – il fenomeno del free-riding si verifca quando, all’interno di un gruppo di individui, un membro evita di dare il suo contributo al bene comune/pubblico e sfrutta i contributi degli altri (il free-rider ritiene che il bene pubblico possa essere fornito ugualmente nonostante la sua astensione). Un bene pubblico è non escludibile (non si può escludere dal consumo il free-rider) e non rivale (una volta che il bene pubblico esiste tutti lo possono consumare)  illuminazione delle strade ad esempio – Free-riding `e un’espressione che prende il nome dal comportamento di colui che sale sull’autobus senza comprare il biglietto (in italiano “free-riding” può essere tradotto con “scroccare”; “free-rider” `e uno scroccone). 1

Esempio: La costruzione della scuola Due individui A e B devono decidere se investire nella costruzione di una scuola (I ) o non investire (NI). La scuola viene costruita se almeno uno degli individui si dichiara interessato alla costruzione. • Il valore individuale (ogni individuo valuta la scuola v) della scuola `e v • Il costo di costruzione della scuola `e c • Se entrambi decidono di investire nella costruzione della scuola si dividono il costo; ognuno paga c 2

Assunzione: c > v > c 2

Rappresentazione del gioco in forma strategica (normale) B I I A

NI c c

NI

v−2,v −2 v, v − c

v− c, v 0, 0

è un gioco simmetrico  sia A che B hanno stesse strategie e i payoff che ottengono sono identici in situazioni simili. La strategia nella cella in alto a sinistra, dove entrambi investono, la scuola viene costruita e ognuno paga c/2. Nella cella in alto a destra, dove A investe e B no, la scuola viene costruita (almeno un giocatore dev’essere interessato). A ha un payoff di v-c (solo lui è interessato quindi paga tutto il costo) e B può usufruire della scuola senza sostenere costi (payoff è B). Siccome c > v  v-c è negativo quindi A ha payoff negativo se investe e 0 se investe. La risposta ottima di A, se B non investe, è non investire. Stessa cosa, ma invertita vale se A non investe ma B si. A ha un payoff di v, mentre B ha un payoff di v-c. Siccome v > v-c, la risposta ottima di A, a B che investe, è non investire. Se entrambi non investono la scuola non viene costruita e il payoff di entrambi è 0.  NI è la risposta ottima di A a qualsiasi strategia scelta da B  è strategia strettamente dominante per A 2

 Siccome è strettamente simmetrico: NI è la risposta ottima anche di B a qualsiasi strategia scelta da A  è strategia strettamente dominante per B Soluzione: Entrambi i giocatori hanno una strategia strettamente dominante: “non investire”, ossia fare il “free-rider” sull’investimento dell’altro. L’unico equilibrio è in strategie dominanti. Il risultato è che la scuola non viene costruita. Il risultato è inefficiente: entrambi i giocatori starebbero meglio se investissero nella costruzione e dividessero il costo della costruzione! Strategie debolmente dominanti Una strategia pura s∗i `e debolmente dominante per il giocatore i se consente di ottenere risultati non peggiori di un’altra strategia s’ i e un risultato migliore di s Ji per almeno un prof lo di strategie degli altri. Un gioco in cui sono presenti strategie debolmente dominanti potrebbe avere piu` di un equilibrio di Nash (NE). Si consideri, per esempio, un gioco con la seguente matrice dei payoff Giocatore 2L U Giocatore 1 D

3 , 6

R 1, 4

4 2, Il giocatore 1 ha strategie Up e Down e il giocatore due ha Left e Right. Il giocatore 1 guadagna 3 e 1 se gioca Up e 4 e2 se gioca Down. Qualsiasi cosa faccia il giocatore 2, al giocatore 1 conviene scegliere Down  Down è strategia strettamente dominante per il giocatore 1. Il giocatore 2 se il giocatore 1 gioca Up, ottiene un payoff maggiore se sceglie L (guadagna 6) piuttosto che R (guadagna 4). Se il giocatore una gioca Down, il giocatore 2 ha un payoff dalla strategia Left che non peggiore di quello ottenuto dalla strategia Right  Left è una strategia debolmente dominante per il giocatore 2 (payoff migliore se 1 gioca Up e non peggiore se 1 gioca Down) D è una strategia strettamente dominante per il Giocatore 1. Mentre, L è una strategia debolmente dominante per il Giocatore 2. Left e Right consentono al giocatore 2 di avere lo stesso payoff di 3 se il giocatore 1 sceglie Down. Questo gioco ha due NE: (D, L) e (D, R).

Eliminazione Iterata di Strategie Strettamente Dominate 3

Una strategia si dice strettamente dominata per un giocatore se ne esiste un’altra che gli permette di ottenere risultati migliori qualunque cosa facciano gli altri. Siano sJi and s i’’ due strategie del giocatore i in un gioco in forma normale. Diciamo che s Ji è strettamente dominata da s i’’ se, per ogni proflo strategico degli altri giocatori (s−i ), il payoff di i è maggiore se sceglie s i’’ piuttosto che s Ji . Formalmente: π i(s Ji , s −i ) < πi (sJi J , s −i) per ogni s −i ∈ S−i . Il payoff che i ottiene se gioca si’ e gli altri giocano s- i è minore del payoff che i ottiene se gioca si’’ e gli altri giocano s-i  questo deve valere qualsiasi siano le strategie giocate dagli altri giocatori. Qui la strategia s i’ è strettamente dominata dalla strategia si’’ Una strategia dominata non sarà mai (per nessun comportamento degli altri giocatori) una risposta ottima. Pertanto, non può far parte di un equilibrio. Esempio 1 di gioco con strategie strettamente dominate Consideriamo il gioco rappresentato dalla seguente matrice: 2 S

C

1 , 1

A 1 MB

D

2, 0

1 , 1

0 0, 0 , 3 1strategie , Il giocatore 1 ha a disposizione (Alto; Medio; Basso) e il 0 0 giocatore 2 ha disposizione 3 strategie (Sinistra; Centro; Destra). Il giocatore 1 ha payoff di 1, 2 e 1 se gioca A; ha payoff 0, 0 e 0 se gioca M; ha payoff 2, 1 e 2 se gioca B. M da a 1 dei payoff minori, qualsiasi cosa faccia il giocatore 2. • È facile vedere che in questo gioco M `e una strategia strettamente dominata per il giocatore 1. Pertanto, se 1 `e razionale, non dovrebbe mai giocarla. Possiamo eliminare M dallo spazio delle strategie del giocatore 1 (e i suoi payoff). • Ma se il giocatore 2 sa che 1 `e razionale (ossia se la razionalit`a di tutti i giocatori `e “conoscenza comune ”), 2 sa che 1 non sceglier`a mai M . Quindi 2 pu`o eliminare M dallo spazio delle azioni di 1 e il gioco diventa: 2 S A

C

D

1 , 14

2 , 0

1, 1

2

1

2,

1 B Il giocatore 2 sa che può ottenere: payoff di 1 e 1 se gioca S; payoff di 0 e 0 se gioca C; payoff di 1 e 2 se gioca D. • Ma ora (dopo l’eliminazione della strategia M per 1), C diviene strettamente dominata per il giocatore 2. • Se si `e disposti ad assumere che – 1 `e razionale e conosce i payoff, – sa che 2 conosce i payoff e sa che 1 `e razionale e conosce i pay off, allora C diviene irrilevante e il gioco pu`o essere di nuovo semplifcato 2 S

D

1 1, , 1 • A `e ora strettamente dominata per il giocatore 1. In effetti B `e (ora) la 1 strategia dominante per 1. 2 2, • Continuando ad iterare le ipotesi di conoscenza comune della razionalit`a e dei payoff, si giunge dunque al gioco semplifcato: A

2 S

D

1 B 2, 1

2, 2

nel quale ( B, D) `e un equilibrio in strategie dominanti dopo aver iterativamente eliminato le strategie strettamente dominate. • Se si `e disposti a considerare le strategie strettamente dominate come irrilevanti, (B, D) `e la SOLUZIONE del gioco originario. Siamo arrivati alla soluzione del gioco con il metodo detto di eliminazione iterata di strategie strettamente dominate. Non è possibile eliminare per lo stesso giocatore, in maniera successiva, le due strategie. Si deve partire da un giocatore, poi considerare l’altro giocatore, poi di nuovo il primo e così via (si devono alternare). Se entrambi i giocatori hanno una strategia strettamente dominata, l’importante è considerare che bisogna ripetere il procedimento ogni volta per un giocatore diverso. ► Il metodo consiste nell’eliminazione di righe e/o colonne strettamente dominate. Esempio 2 di gioco con strategie strettamente dominate 5

Consideriamo il gioco rappresentato dalla seguente matrice: B

U A

L

C

R

7 , 3

3, 1

0 , 5

D L `e 5 strettamente 5, 2 dominata dalla strategia R Per il giocatore B, la strategia (3 < 5 and 1 < 2). Il gioco pu`o ridursi a B C A

R

3 0 , , Per il giocatore A, la strategia U `e strettamente dominata dalla strategia D 1 5 (3 < 5 and 0 < 2). Il gioco pu`o essere ulteriormente semplifcato D 5 2 B

A

U

D

C

R

5 ,

2 ,

Per il giocatore B, la strategia C domina strettamente la strategia R (3 > 2). Quindi l’unico proflo di strategie che sopravvive alla eliminazione iterata delle strategie strettamente dominate `e (D,C). Ci sono giochi in cui non esistono strategie strettamente dominate da eliminare. Per esempio: B c a 2, 1

d 0, 0

0, 0

1, 2

A b

Questo gioco pu`ò risolversi usando il concetto di equilibrio di Nash. Se B gioca C, al giocatore A conviene giocare A. Se B gioca D, ad A conviene giocare B (1 > 0). Se A gioca a, al giocatore B conviene giocare c. se A gioca b, la risposta ottima di B è giocare d. Ci sono due equilibri di Nash: (a, c) e (b, d). 6

N.B. Un proflo di strategie che sopravvive all’eliminazione iterata di strategie strettamente dominate `e un equilibrio di Nash, ma non `e vero il contrario. Se risolviamo un gioco col metodo dell’eliminazione la soluzione trovata è anche equilibrio di Nash ma, al contrario, ci sono giochi che hanno equilibri di Nash non ottenuti usando l’eliminazione iterata. Ci sono esercizi che non possono essere risolti col metodo dell’eliminazione iterata (concetto di soluzione più debole), per risolvere il gioco si dovrà usare l’equilibrio di Nash (risposta ottima di un giocatore il risposta a una strategia dell’altro).

7...