Teoria dei giochi.

2. Giochi non cooperativi

2.1 Introduzione

In questa classe di giochi, introdotta da von Neumann e Morgenstern (1944), i giocatori non possono stipulare accordi vincolanti (o comunicare), indipendentemente dal fatto che i loro obiettivi siano contrastanti o comuni e possano quindi avere interesse ad accordarsi.

Esempio 2.1.1 (Congestione) Per andare da A a B sono possibili tre strade con differenti tempi di percorrenza, che dipendono dalla lunghezza e da altri fattori, in particolare dal traffico, per cui se più persone scelgono la stessa strada il corrispondente tempo aumenta.

Si considerino tre utenti e si supponga che l’aumento sia di due minuti se una strada è scelta da due utenti e di cinque minuti se è scelta dai tre utenti. Il gioco può essere rappresentato in forma strategica dalle tabelle seguenti.

In questo caso l’obiettivo dei giocatori è comune (ma non è identico, in quanto ognuno vuole minimizzare il proprio tempo di percorrenza), ma la cooperazione, nella realtà, è impossibile per la difficoltà di accordarsi su chi percorre le strade più lente.

2.2 Equilibrio di Nash

Il più semplice e importante concetto di soluzione per un gioco non cooperativo è l’equilibrio di Nash (1950a).

Definizione 2.2.1 Dato un gioco G si dice che la n-upla di strategie (σ₁^∗, σ₂^∗, . . . , σ_n^∗) con σ_i^∗ ∈ Σ_i costituisce un equilibrio, o è in equilibrio, se nessun giocatore ha interesse ad essere l’unico che cambia strategia, cioè se:

Ovviamente possono esistere differenti strategie per uno o più giocatori a cui corrispondono payoff migliori, come nel caso del dilemma del prigioniero in cui l’equilibrio risulta inefficiente e il risultato più ovvio per un “supervisore” non è di equilibrio.

Un gioco può avere più equilibri come nell’Esempio 1.2.2 in cui le soluzioni (T, T) e (P, P) sono di equilibrio.

2.3 Giochi a somma zero

Definizione 2.3.1 Un gioco G si dice a somma zero se per ogni terminazione del gioco la somma dei payoff è nulla.

In altre parole tutto quello che viene guadagnato da qualche giocatore viene perso da qualche altro giocatore.

Nel caso più semplice a due giocatori la matrice dei pagamenti può essere espressa indicando la vincita, positiva o negativa, del primo giocatore poiché la vincita del secondo è in ogni caso l’opposto. Si può utilizzare una matrice A in cui la riga i è associata alla strategia σ_i del giocatore I, la colonna j alla strategia σ_j del giocatore II e l’elemento a_ij rappresenta quanto il primo giocatore riceve dal secondo se giocano la coppia di strategie (σ_i, σ_j).

Definizione 2.3.2 La rappresentazione tramite la matrice A è detta forma normale.

2.3.1 Gioco a due giocatori a somma zero in forma normale

Un equilibrio di Nash è rappresentato da una coppia di strategie σ_i ∈ Σ₁ e σ_j ∈ Σ₂ tali che l’elemento a_ij risulta essere il più grande della colonna j e il più piccolo della riga i; l’equilibrio viene detto anche punto di sella.

Esempio 2.3.1 (Punto di sella)

Nel gioco in forma normale rappresentato a lato la strategia (σ₁, σ₂) costituisce un equilibrio anche se entrambi i giocatori hanno a disposizione dei payoff migliori.

L’esistenza di un punto di sella o equilibrio di Nash non impone ai giocatori la scelta delle corrispondenti strategie; nell’esempio precedente il giocatore I sa di poter ottenere payoff superiori a 3 unità e il giocatore II sa di poter pagare payoff inferiori a 3 unità; d’altra parte il giocatore I sa che scegliendo la terza strategia può ottenere 7 unità ma può pagarne 1 se il giocatore II sceglie la seconda strategia e il giocatore II sa che scegliendo la terza strategia può ottenere 2 unità ma può pagarne 4 se il giocatore I sceglie la prima strategia.

Teorema 2.3.1 In un gioco a due persone a somma zero se (σ_i, σ_j) e (σ_h, σ_k) sono equilibri di Nash, allora lo sono anche (σ_i, σ_k) e (σ_h, σ_j).

Esempio 2.3.2 (Equilibri multipli)

Nel gioco in forma normale rappresentato a lato le strategie (σ₁, σ₂) e (σ₂, σ₃) sono equilibri di Nash e lo sono anche (σ₁, σ₃) e (σ₂, σ₂).

Osservazione 2.3.1

• Nel caso in cui il gioco non sia a somma zero il precedente teorema non sussiste, come nel caso della battaglia dei sessi.

L’obiettivo dei giocatori è massimizzare il proprio payoff, cioè massimizzare la vincita o minimizzare la perdita; se i giocatori scelgono σ_i e σ_j, con payoff a_ij il giocatore I cerca di massimizzarlo intervenendo solo sulla scelta di σ_i e il giocatore II cerca di minimizzarlo intervenendo solo sulla scelta di σ_j. La non conoscenza della strategia scelta dall’altro giocatore impedisce di poter raggiungere con certezza l’obiettivo, ma l’esistenza di un punto di sella fa si che ragionevolmente entrambi scelgano quella coppia di strategie.

2.3.2 Gioco a due giocatori a somma zero senza equilibri di Nash

La maggior parte dei giochi non ha punti di sella, come il gioco a lato;

in questo caso il primo giocatore con la prima strategia si garantisce una vincita minima 2 (gain-floor) e il secondo giocatore con la seconda strategia si garantisce una perdita massima 3 (loss-ceiling).

La vincita minima per il giocatore I si indica con v_I^′ e si ha:

La perdita massima per il giocatore II si indica con v_I^′ _I e si ha:

È facile verificare che v_I^′ ≤ v_I^′ _I; se v_I^′ = v_I^′ _I allora esiste un punto di sella.

In generale un comportamento “razionale” fa si che il giocatore I vinca almeno v_I^′ e il giocatore II perda al più v_I^′ _I e il risultato è il peggiore se l’altro giocatore può sfruttare la “razionalità” e prevedere la mossa. Pertanto per migliorare il risultato è necessario non giocare “razionalmente”, cioè non giocare solo la strategia di vincita minima o di perdita massima.

Esempio 2.3.3 (Pari e dispari modificato) I due giocatori possono lanciare 1, 2, 3; il giocatore I vince se la somma dei numeri è pari, altrimenti vince il giocatore II.

Apparentemente il gioco è favorevole al giocatore I che può vincere in 5 casi su 9. D’altra parte il giocatore II potrebbe giocare 2 e quindi avrebbe 2 risultati vincenti su 3; ma a questo punto il giocatore I giocando 2 è “sicuro” di vincere. Analogamente il giocatore I potrebbe giocare 1 (o 3) per avere 2 risultati vincenti su 3 e a questo punto il giocatore II giocando 2 è “sicuro” di vincere.

Cercare di aumentare le proprie possibilità di vincere porta alla sconfitta “sicura”.

Osservazione 2.3.2

• Si possono evidenziare alcuni limiti dell’equilibrio di Nash (in strategie pure):
• inefficienza (dilemma del prigioniero);
• non unicità (battaglia dei sessi);
• non esistenza (pari e dispari).

2.4 Strategie miste

Definizione 2.4.1 Si chiama strategia mista per un giocatore una distribuzione di probabilità sull’insieme delle sue strategie pure.

Nell’Esempio 2.3.3 il giocatore II che parte svantaggiato può riequilibrare le sue possibilità giocando a caso, con probabilità 0.5 sia 1 che 2 (o altre strategie equivalenti); in questo modo il primo giocatore non può in alcun modo avere maggiori probabilità di vincere.

Se l’insieme delle strategie pure è formato da n elementi una strategia mista si può indicare con un vettore x = (x₁, x₂, . . . , x_n) con x_i ≥ 0 e ∑_i=1,...,n x_i = 1.

L’insieme delle strategie miste del giocatore I si indica con X e l’insieme delle strategie miste del giocatore II si indica con Y .

Definizione 2.4.2 Dato un gioco G a due giocatori a somma zero in forma normale con matrice A è detta vincita attesa se il giocatore I gioca la strategia mista x ∈ X e il giocatore II gioca la strategia mista y ∈ Y la quantità:

È possibile definire la vincita minima per il giocatore I se sceglie la strategia mista x ∈ X come:

e la perdita massima per il giocatore II se sceglie la strategia mista y ∈ Y come:

dove A_.j e A_i. sono la colonna j e la riga i di A e le seconde uguaglianze derivano dal fatto che il minimo e il massimo cercati si ottengono con strategie pure.

L’obiettivo del giocatore I è massimizzare v(x) ottenendo la quantità:

e quello del giocatore II è minimizzare v(y) ottenendo la quantità:

Definizione 2.4.3 La strategia mista x che permette al giocatore I di ottenere v_I è detta maximin; la strategia mista y che permette al giocatore II di ottenere v_II è detta minimax.

v_I e v_II sono detti valore del gioco per i giocatori I e II, rispettivamente.

Teorema 2.4.1 (Teorema del minmax (von Neumann, 1928)) v_I = v_II.

Osservazione 2.4.1

• Il valore v_I = v_II viene detto valore del gioco.
• Nel caso in cui il gioco non sia a somma zero il precedente teorema non sussiste.

2.5 Dominanza

Talvolta le dimensioni del problema, cioè il numero di strategie, possono essere ridotte eliminando alcune strategie.

Definizione 2.5.1 Dato un gioco G a due giocatori a somma zero in forma normale, con matrice A, si dice che la strategia σ_i domina la strategia σ_h per il giocatore I se a_ij ≥ a_hj, j = 1, . . . , m e a_ij > a_hj per almeno un indice j e la strategia σ_j domina la strategia σ_k per il giocatore II se a_ij ≤ a_ik, i = 1, . . . , n e a_ij < a_ik per almeno un indice i.

Teorema 2.5.1 Se una strategia è dominata, esiste una strategia mista ottimale che non utilizza la strategia dominata; inoltre una strategia mista ottimale per il gioco senza la riga (o colonna) i è ottimale anche per il gioco dato.

La definizione e il teorema precedenti si possono estendere al caso di giochi a più giocatori non a somma zero.

Definizione 2.5.2 La strategia σ_h domina la strategia σ_k per il giocatore i se f_i(σ_h, σ_−i) ≥ f_i(σ_k, σ_−i), per ogni (n − 1)-upla di strategie σ_−i ∈ ∏_k≠i Σ_k e f_i(σ_h, σ_−i) > f_i(σ_k, σ−i) per almeno una (n − 1)-upla di strategie σ_−i.

Osservazione 2.5.1

• A volte si distingue tra dominanza debole, quelle che sono state definite in precedenza e forte, quando si hanno tutte disuguaglianze strette. Ai fini dell’applicazione del teorema di riduzione del gioco la distinzione è irrilevante; tale riduzione è possibile anche nel caso in cui si abbiano tutte uguaglianze (indifferenza).
• Il concetto di dominanza può essere applicato anche al gioco ridotto, indipendentemente dalle caratteristiche del gioco dato (dominanza iterata). In questo caso se si applicano eliminazioni per dominanza debole o indifferenza si può perdere qualche equilibrio di Nash. Questo fatto è irrilevante se si vuol determinare se esistono equilibri di Nash, o almeno un equilibio di Nash.

2.6 Inefficienza dell’equilibrio di Nash e instabilità

L’esempio seguente mostra un semplice caso teorico in cui l’aumento delle strategie dei giocatori può generare soluzioni instabili ed equilibri inefficienti. Si consideri il gioco in forma strategica:

(T, L) è l’unico equilibrio di Nash ed è efficiente, ma se si aggiungono le strategie B e R, rispettivamente, con opportuni payoff si ha:

In questo caso (B, R) è l’unico equilibrio di Nash ma è inefficiente.

Un altro semplice caso deriva da una situazione di traffico.

Esempio 2.6.1 (Paradosso di Braess, 1968) Si considerino 6 utenti che devono spostarsi da A a B e possono utilizzare due strade, rappresentate dai percorsi A−1−B e A−2−B. I tratti 1 − B e A − 2, essendo lunghi e ampi, hanno un tempo di percorrenza elevato ma risentono poco della congestione; ad esempio c’è un tempo fisso 60 e un fattore di congestione 2n dove n è il numero di utenti che percorre la strada. I tratti A − 1 e 2 − B sono brevi e stretti, per cui il tempo di percorrenza è basso ma risente molto della congestione; ad esempio c’è un tempo fisso 10 e un fattore di congestione 10n.

In queste condizioni è facile verificare che la soluzione ottimale si ottiene quando ogni strada è percorsa da tre utenti, ciascuno con un tempo di percorrenza dato da 10 + 10 × 3 + 60 + 2 × 3 = 106. Questa soluzione è anche un equilibrio di Nash, cioè è stabile. Successivamente viene costruita una strada a senso unico che collega 1 e 2, il cui tempo fisso è 8 e il fattore di congestione è 3n.

In questa nuova situazione un utente del percorso A − 1 − B ha interesse a passare sul percorso A−1−2−B poiché il suo tempo diventa 10+10×3+8+3×1+10 +10×4 = 101. Si noti che i due utenti sul percorso A − 1 − B impiegano 10 + 10 × 3 + 60 + 2 × 2 = 104, mentre i tre sul percorso A − 2 − B impiegano 60 + 2 × 3 + 10 + 10 × 4 = 116. Se un utente del percorso A − 2 − B passa sul percorso A − 1 − 2 − B il suo tempo diventa 10 + 10 × 4 + 8 + 3 × 2 + 10 + 10 × 4 = 114, che è il tempo che impiegano tutti, che è peggiore del tempo ottenuto senza utilizzare la strada 1 − 2. La nuova soluzione è ancora un equilibrio di Nash, cioè è stabile. Ovviamente gli utenti potrebbero tornare alla configurazione precedente, che però adesso risulta instabile.

2.7 Raffinamenti dell’equilibrio di Nash

Come si è detto uno dei limiti dell’equilibrio di Nash è la non unicità. Per ovviare a questo sono stati proposti numerosi raffinamenti dell’equilibrio di Nash, tra i quali l’equilibrio perfetto nei sottogiochi (applicabile alla forma estesa, in cui un sottogioco deve iniziare da un nodo che costituisce da solo un insieme di informazione, includere tutti i suoi successori e non spezzare alcun insieme di informazione), che si ricollega alla programmazione dinamica di Bellman (Selten, 1965), l’equilibrio correlato che incorpora aspetti di comunicazione tra i giocatori (Aumann, 1974) e l’equilibrio perfetto o “della mano tremante” che considera le perturbazioni (Selten, 1975). Nessuno di questi ha risolto il problema, né da un punto di vista quantitativo (unicità), né da quello qualitativo (scelta di un “buon” equilibrio).

Esempio 2.7.1 (Equilibrio perfetto nei sottogiochi) Il gioco seguente ha due equilibri di Nash (B, L) e (B, R), tra loro indifferenti.

Se il gioco dovesse iniziare dalla mossa di II la scelta R è preferibile alla scelta L (per il giocatore II), per cui l’equilibrio (B, R) è perfetto nei sottogiochi.

Esempio 2.7.2 (Equilibrio perfetto) Il gioco rappresentato dalla tabella seguente ha due equilibri di Nash (T, L) e (B, R). Il primo sembrerebbe più vantaggioso, ma è più rischioso in caso di perturbazioni. Nel primo caso un “errore” non danneggia chi lo commette, ma danneggia fortemente l’altro. Nel secondo caso si ha un danno solo nel caso di un proprio errore.

2.7.1 Strategie correlate

In precedenza si è accennato alle strategie correlate. Il seguente esempio permette di chiarire qualche aspetto.

Esempio 2.7.3 (Gioco dell’incrocio) Due automobilisti ad un incrocio possono scegliere se passare (P ) o fermarsi (F ). Passare se l’altro si ferma permette di guadagnare 5, fermarsi entrambi comporta una perdita 1, ma se passano entrambi la perdita è maggiore . . .

È facile verificare che esistono due equilibri di Nash in strategie pure (P, F ) e (F, P ) e un equilibrio in strategie miste ((3/8, 5/8), (3/8, 5/8)). Le soluzioni di Nash in strategie pure hanno un valore atteso 5 per chi passa e 0 per chi si ferma (quindi la somma è 5), mentre la soluzione di Nash in strategie miste ha un valore atteso negativo per entrambi −5/8 ma soprattutto non garantiscono di evitare l’incidente; la scelta di fermarsi comunque è la più sicura ma ha un valore atteso negativo, salvo nel caso improbabile che l’altro passi comunque. Si può allora correlare la strategia ad un evento esterno: il semaforo. Utilizzando un ciclo semaforico che fa passare le auto provenienti dalle due direzioni al 50 per cento, si ottiene un valore atteso 2.5 per entrambi (e la somma è ancora 5) e una notevole sicurezza se i giocatori accettano la strategia correlata, cioè rispettano il codice della strada.

2.7.2 Equilibrio correlato

Il risultato precedente può essere interpretrato come miglior risposta e quindi generalizzato come equilibrio correlato.

Definizione 2.7.1

• Si dice strategia mista correlata per un gioco a due giocatori, una distribuzione di probabilità sul prodotto cartesiano di strategie, cioè una matrice P tale che:

• Si dice equilibrio correlato per un gioco a due giocatori a matrice doppia (A, B) una strategia mista correlata P tale che per ogni strategia σ_i del primo giocatore:

e per ogni strategia σ_j del secondo giocatore:

dove (∑_j=1,...,m a_sjp_ij)/(∑_j=1,...,m p_ij) è l’utilità attesa dal primo giocatore se gioca la strategia σ_s quando gli viene “indicata” la strategia σ_i e il secondo giocatore “accetta” l’indicazione e analogamente (∑_i=1,...,n b_itp_ij)/(∑_i=1,...,n p_ij) è l’utilità attesa dal secondo giocatore se gioca la strategia σ_t quando gli viene “indicata” la strategia σ_j e il primo giocatore “accetta” l’indicazione.

In altre parole P suggerisce in ogni situazione le strategie σ_i e σ_j da utilizzare e ogni altra strategia σ_h e σ_k è non migliore di quella suggerita se l’altro giocatore “accetta” il suggerimento.

2.7.3 Credibilità, ultimatum e reputazione

Un equilibrio perfetto nei sottogiochi deve prescrivere un equilibrio in ogni sottogioco, anche in quelli che non vengono raggiunti seguendo le strategie previste. Questa richiesta esclude le minacce che il giocatore non avrebbe interesse ad attuare qualora dovesse davvero scegliere. Nei giochi finiti a informazione perfetta l’induzione a ritroso costruisce strategie con questa proprietà; eventuali indifferenze possono lasciare più soluzioni.

Consideriamo un esempio. I sceglie T oppure B. Con B il gioco termina con payoff (1, 2); con T decide II, che sceglie L ottenendo (2, 1) oppure R ottenendo (0, 0). In forma strategica si hanno due equilibri puri, (T, L) e (B, R). Nel secondo, II minaccia R per indurre I a scegliere B. Ma, raggiunto il nodo di II, L gli rende 1 mentre R gli rende 0: la minaccia non è credibile. Solo (T, L) è perfetto nei sottogiochi.

Nell’ultimatum game, I propone come dividere 100 monete e II può accettare oppure rifiutare; il rifiuto lascia entrambi senza nulla. Se I deve offrire a II almeno una moneta, le monete sono indivisibili e ciascuno valuta soltanto la somma ricevuta, l’induzione a ritroso prescrive che II accetti ogni offerta positiva e che I trattenga 99 monete. Se invece II attribuisce disutilità a una divisione percepita come ingiusta, il rifiuto può essere coerente con le sue preferenze. La previsione dipende quindi dall’utilità ipotizzata, non soltanto dalla regola di divisione.

Il paradosso della catena di negozi mette in evidenza la tensione fra credibilità e reputazione. Un’impresa già presente affronta una sequenza finita e nota di possibili concorrenti. Dopo ogni ingresso può accettare la concorrenza oppure avviare una guerra di prezzi che danneggia entrambe le imprese. Se accettare conviene sempre una volta avvenuto l’ingresso, nell’ultimo mercato la minaccia aggressiva non è credibile; sotto le stesse ipotesi il ragionamento risale ai mercati precedenti. Per studiare una reputazione capace di modificare l’esito occorre esplicitare ciò che cambia, per esempio l’incertezza sul tipo dell’impresa o sull’orizzonte dell’interazione.

Anche il centipede, presentato nel capitolo sull’informazione, mostra che la perfezione nei sottogiochi non garantisce efficienza. Le scelte osservate fuori dal percorso previsto possono inoltre indurre i giocatori a rivedere le proprie convinzioni. La forza di un concetto di soluzione consiste nel rendere precise le ipotesi e le loro implicazioni, non nell’eliminare ogni difficoltà interpretativa.

2.8 Giochi ripetuti e cooperazione

In un gioco ripetuto gli stessi partecipanti affrontano più volte un gioco di base, detto gioco di stadio. Una strategia specifica che cosa fare dopo ogni storia osservabile, non soltanto un’azione da ripetere sempre. Se le azioni passate sono osservate, il comportamento attuale può influenzare premi e punizioni futuri. La cooperazione può così essere sostenuta da incentivi anche senza un accordo vincolante.

2.8.1 Orizzonte finito

Supponiamo che il numero di periodi sia finito, noto a tutti e che il gioco di stadio abbia un unico equilibrio di Nash, considerando anche le strategie miste. Con payoff complessivi additivi, nell’ultimo periodo si gioca quell’equilibrio dopo ogni storia. Poiché la continuazione è la stessa, il ragionamento risale fino al primo periodo: la ripetizione dell’equilibrio di stadio è l’unico equilibrio perfetto nei sottogiochi. Avere un unico equilibrio soltanto fra le strategie pure non basta per questa conclusione generale.

Nel dilemma del prigioniero già introdotto, confessare (C) domina strettamente non confessare (NC). Nell’ultimo periodo entrambi confessano, indipendentemente dal passato; la stessa conclusione vale nel penultimo e, a ritroso, in tutti gli altri. Questo risultato non si estende automaticamente ai giochi con più equilibri di stadio: scegliere un diverso equilibrio futuro può rendere credibile un premio o una punizione.

Consideriamo il seguente gioco, dove ogni cella contiene i payoff dei due giocatori.

(C, C) e (S, S) sono entrambi equilibri. In due periodi, senza sconto, i giocatori possono scegliere D nel primo e C nel secondo se hanno osservato (D, D); dopo ogni altra coppia scelgono S. Rispettare il piano rende 5 + 4 = 9; deviare unilateralmente verso C nel primo periodo rende 6 + 1 = 7, mentre deviare verso S rende 0 + 1 = 1. Le continuazioni sono equilibri di stadio, quindi la punizione è credibile. Il piano è perfetto nei sottogiochi benché (D, D), giocato inizialmente, non sia un equilibrio del gioco di stadio.

2.8.2 Orizzonte infinito, sconto e strategie di punizione

Quando non esiste una scadenza finale nota, il modello a orizzonte infinito permette di rappresentare un’interazione che può continuare. Il fattore di sconto δ, con 0 < δ < 1, misura il peso attribuito al futuro: il payoff complessivo è u₀ + δu₁ + δ²u₂ + … . Un valore vicino a 1 indica maggiore pazienza. Moltiplicare la somma per 1 − δ produce il payoff medio scontato normalizzato e non cambia il confronto fra strategie.

Nel dilemma del prigioniero, una strategia di grim trigger prescrive NC finché tutti hanno sempre scelto NC e C per sempre dopo una deviazione osservata. La cooperazione perpetua dà V_coop = −2/(1 − δ). Una deviazione quando l’altro coopera dà −1 subito, seguita da −5 in ogni periodo successivo: V_dev = −1 − 5δ/(1 − δ).

Il piano regge quando V_coop ≥ V_dev. Moltiplicando per 1 − δ si ottiene −2 ≥ −1 − 4δ, cioè δ ≥ 1/4. La punizione è credibile perché (C, C) è un equilibrio di stadio: una volta iniziata, nessuno migliora passando unilateralmente a NC. Il calcolo presuppone osservazione delle azioni, payoff invariati e assenza di errori; non dimostra che la cooperazione emerga automaticamente in ogni interazione reale.

I risultati chiamati folk theorem formalizzano, sotto ipotesi specifiche sul gioco e sull’osservazione delle azioni, la possibilità di sostenere molti payoff ammissibili e individualmente razionali quando i giocatori sono abbastanza pazienti. Non affermano che qualsiasi esito sia sempre ottenibile, né selezionano un unico equilibrio. L’esempio appena svolto mostra il meccanismo essenziale: il vantaggio immediato di una deviazione viene confrontato con la perdita della cooperazione futura.