Teoria dei giochi.

3. Soluzione numerica di un gioco non cooperativo

3.1 Calcolo dell’equilibrio di Nash in strategie pure

Gli equilibri di Nash in strategie pure non vengono calcolati applicando la definizione, ma il concetto di miglior risposta, cioè si analizza quale strategia massimizza il payoff di un giocatore, per ogni insieme fissato di strategie degli altri giocatori (la miglior risposta può non essere unica). Le n-uple di strategie formate solo da reciproche migliori risposte sono equilibri di Nash.

3.2 Calcolo dell’equilibrio di Nash in strategie miste

Nel caso di un gioco a due giocatori esiste un modo relativamente semplice per determinare gli equilibri di Nash in strategie miste.

Si consideri l’Esempio 1.2.2. Se il giocatore I gioca la strategia mista (p, 1 − p) e il giocatore II gioca la strategia mista (q, 1 − q) la vincita attesa del giocatore I è data da:

v_I(p) = 2pq + 0(1 − p)q + 0p(1 − q) + 1(1 − p)(1 − q) = 3pq − p − q + 1 = (3q − 1)p − (q − 1)

Il secondo termine non dipende da p, cioè dal giocatore I; si hanno quindi tre casi:

• 3q − 1 > 0 ⇒ p = 1 (strategia pura)
• 3q − 1 = 0 ⇒ p qualsiasi
• 3q − 1 < 0 ⇒ p = 0 (strategia pura)

Analogamente la vincita attesa del giocatore II è data da:

v_II(q) = 1pq +0(1−p)q +0p(1−q)+2(1−p)(1−q) = 3pq −2p−2q +2 = (3p−2)q −2(p−1)

a cui corrispondono i tre casi:

• 3p − 2 > 0 ⇒ q = 1 (strategia pura)
• 3p − 2 = 0 ⇒ q qualsiasi
• 3p − 2 < 0 ⇒ q = 0 (strategia pura)

Quindi, oltre agli equilibri di Nash in strategie pure (T, T ) e (P, P ), si ha un equilibrio in strategie miste se:

cioè ((2/3, 1/3), (1/3, 2/3)).

Osservazione 3.2.1

• La vincita attesa è v_I = v_II = 2/3, cioè inferiore alla vincita minima derivante da un accordo (non vincolante) per una strategia pura.

3.3 Soluzione per dominanza

Esempio 3.3.1 (Gioco a due giocatori a somma zero) Sia dato il gioco in forma normale:

La prima colonna è dominata (debolmente) dalla terza:

A questo punto la seconda riga è dominata (debolmente) dalla prima (e dalla terza):

A questo punto la seconda colonna è dominata (fortemente) dalla terza:

A questo punto la prima riga è dominata (debolmente) dalla terza:

Infine poiché la quarta colonna è dominata (fortemente) dalla terza:

la cui soluzione è (3, 3). Si può osservare che la soluzione è un punto di sella.

Esempio 3.3.2 (Gioco a tre giocatori) Sia dato il gioco in forma strategica:

Per il giocatore III la strategia D domina (debolmente) la strategia S, per cui si ha:

Per il giocatore I la strategia B domina (fortemente) la strategia T , per cui si ha:

A questo punto per il giocatore II le strategie L ed R sono indifferenti, per cui si hanno due equilibri di Nash (B, L, D) e (B, R, D).

Osservazione 3.3.1

• Si noti che alla seconda iterazione si poteva applicare la dominanza (debole) della strategia R rispetto alla strategia L per il giocatore II e successivamente la dominanza (forte) della strategia B rispetto alla strategia T , ottenendo solo l’equilibrio (B, R, D).

3.4 Soluzione con la programmazione lineare

Un gioco a due giocatori a somma zero senza punti di sella può essere risolto tramite la programmazione lineare.

Supponendo che il giocatore I utilizzi la strategia x = (x₁, x₂, . . . , x_n) ricordando che:

si ha:

Poiché il valore del gioco è:

si ha il programma lineare:

In modo analogo per il giocatore II si ha il programma lineare:

I due programmi risultano tra loro duali e quindi è facile determinare le strategie miste ottimali e il valore del gioco.

Osservazione 3.4.1

• In realtà la soluzione tramite un problema lineare è possibile anche nel caso di un gioco non a somma zero, ma in questo caso il risultato è meno elegante in quanto non sussiste la relazione di dualità.

3.5 Soluzione a ritroso (Backward Induction)

Sia G un gioco non cooperativo finito, rappresentato in forma estesa. Per semplificare la trattazione si può supporre che il gioco sia ad informazione perfetta. Se tutti i giocatori hanno preferenze razionali, cioè preferiscono un payoff non minore, allora è possibile determinare una soluzione del gioco, cioè una strategia ottimale dei giocatori, applicando una semplice metodologia, detta induzione a ritroso. L’idea di base è che la razionalità dei giocatori permette di “prevedere” il loro comportamento, per cui è possibile decidere la scelta di un giocatore sulla base delle scelte dei suoi successori e quindi iniziare l’analisi del gioco dalla fine, cioè dalle ultime mosse fino alla prima.

Formalmente si considerano le situazioni in cui le mosse disponibili portano comunque alla conclusione del gioco, dette nodi pre-terminali (se il gioco è finito esiste certamente almeno una tale situazione); in questo caso il giocatore sceglierà “certamente” la mossa che gli assicura il miglior payoff. Questo permette di dire che tutte le volte che il gioco giunge in quella situazione, allora anche la terminazione è “decisa” e quindi si può sostituire il nodo pre-terminale con un nodo terminale al quale si associa il vettore payoff corrispondente alla mossa fatta. Procedendo a ritroso in questo modo tutti i nodi diventano (prima o poi) nodi terminali e l’insieme delle mosse fatte identificano un profilo di strategie per i giocatori.

Esempio 3.5.1 (Payoff distinti) Applicando l’induzione a ritroso al seguente gioco il forma estesa si ha:

La procedura identifica il profilo di strategie ((B, G), D) con payoff (5, 2).

La procedura è più complessa se ad una determinata situazione corrispondono più nodi terminali con lo stesso payoff per il giocatore chiamato a muovere, ma differenti per gli altri. In questo caso a seconda della scelta fatta l’iterazione successiva può avere risultati molto diversi. Operativamente si considera una continuazione del procedimento per ogni scelta massimizzante possibile, applicando successivamente altre considerazioni risolutive (giochi ad informazione incompleta).

Esempio 3.5.2 (Payoff non distinti) Modificando il payoff del giocatore II in corrispondenza della sua scelta C come indicato si ottiene:

La procedura identifica due terminazioni:

• il profilo di strategie ((A, G), C) con payoff (10, 3)
• il profilo di strategie ((B, G), D) con payoff (5, 2)

ma trascura il profilo di strategie ((A, G), D) con payoff (4, 3). La scelta dipende dal modello decisionale adottato.

Osservazione 3.5.1

• La procedura può dare risultati discutibili se il gioco non è ad informazione perfetta.
• Se il giocatore II scegliesse D invece di C, danneggiando il giocatore I, questo potrebbe scegliere F invece di G, con una piccola perdita per sé, danneggiando il giocatore II (strategia di minaccia).

Se ad un gioco in forma estesa ad informazione perfetta si associa la corrispondente forma strategica questa può essere risolta per dominanza (debole) iterata eliminando iterativamente le strategie “scartate” in ciascuna iterazione dell’eliminazione a ritroso.

Esempio 3.5.3 (Induzione a ritroso e dominanza iterata) Riprendendo l’Esempio 3.5.1 si ha:

La strategia AG domina (debolmente) le strategie AE e AF e la strategia BG domina (debolmente) le strategie BE e BF :

La strategia D domina (debolmente) la strategia C:

Infine la strategia BG domina (fortemente) la strategia AG; quindi si ottiene la stessa soluzione trovata in precedenza, cioè il profilo (BG, D) con payoff (5, 2).

3.6 Soluzione di Maxmin

Se il gioco è rappresentato in forma strategica potrebbe non essere applicabile la soluzione per dominanza e potrebbe non essere facile risalire alla forma estesa. In questi casi una buona soluzione può essere la ricerca della strategia di maxmin, cioè quella strategia che garantisce il miglior risultato qualsiasi sia la scelta degli altri giocatori. Questo approccio è valido per i giocatori avversi al rischio.

Si analizza quale è il peggior payoff che il giocatore può conseguire una volta fissata la sua strategia, cioè supponendo che gli altri giocatori giochino “contro” di lui (minimo payoff). A questo punto il giocatore sceglie la strategia per lui più vantaggiosa (massimo dei minimi payoff).

Esempio 3.6.1 (Maxmin) Si consideri il seguente gioco in forma strategica:

Non esistono relazioni di dominanza tra le strategie di entrambi i giocatori, per cui ha senso cercare la strategia di maxmin. Se il giocatore I sceglie T il minimo payoff è -2; se sceglie M il minimo payoff è -2; se sceglie B il minimo payoff è -1; quindi la sua strategia di maxmin è B. Se il giocatore II sceglie L il minimo payoff è -2; se sceglie C il minimo payoff è 2; se sceglie R il minimo payoff è -1; quindi la sua strategia di maxmin è C. Il payoff corrispondente al profilo di strategie di maxmin (B, C) è (-1, 4), cioè il giocatore I consegue il risultato minimo atteso, mentre il giocatore II riceve un payoff superiore.

La soluzione di maxmin è un concetto di soluzione generale, a differenza di altri. Parte dall’ipotesi che gli altri giocatori trascurino completamente il loro payoff e giochino solo per danneggiare il giocatore in oggetto, che è vera solo nel caso di giochi ad interessi contrastanti, ad esempio i giochi a somma nulla.

3.7 Duopolio: Cournot, collusione e Stackelberg

Due imprese producono un bene omogeneo e scelgono quantità non negative x e y. La quantità totale è Q = x + y, il prezzo è P(Q) = max{a − Q, 0} e il costo marginale comune è k, senza costi fissi. Assumiamo 0 < k < a e poniamo A = a − k. Nel tratto con prezzo positivo i profitti sono π₁ = x(A − x − y) e π₂ = y(A − x − y). La produzione di ciascuna impresa influenza il prezzo ricevuto anche dall’altra.

3.7.1 Concorrenza simultanea di Cournot

Tenendo fissa y, la prima impresa massimizza una parabola concava in x. La sua migliore risposta è x = max{(A − y)/2, 0}; simmetricamente, y = max{(A − x)/2, 0}. L’equilibrio è l’intersezione delle due risposte: x = y = A/3. Ne seguono Q = 2A/3, P = a − 2A/3 e π₁ = π₂ = A²/9. Nessuna impresa può aumentare il proprio profitto modificando da sola la quantità, data quella dell’altra.

3.7.2 Massimizzazione del profitto congiunto

Se le imprese massimizzano insieme il profitto totale, scelgono Q per massimizzare Q(A − Q). La quantità ottimale è Q = A/2; con ripartizione simmetrica ciascuna produce A/4, il prezzo è a − A/2 e il profitto di ciascuna è A²/8. Rispetto a Cournot la quantità totale diminuisce, il prezzo aumenta e il profitto di entrambe cresce.

Questo accordo non è però un equilibrio del gioco simultaneo senza vincoli: se l’altra produce A/4, la migliore risposta è 3A/8, non A/4. La singola impresa ha quindi incentivo ad aumentare la produzione rispetto al piano concordato. Il confronto distingue la convenienza collettiva per le imprese dalla stabilità individuale dell’accordo; non rappresenta il benessere dei consumatori, che non sono giocatori attivi nel modello.

3.7.3 Scelte sequenziali di Stackelberg

Supponiamo ora che la prima impresa, il leader, scelga una quantità osservabile e si impegni a produrla prima della scelta della seconda, il follower. La risposta del follower è y(x) = max{(A − x)/2, 0}. Anticipandola, il leader massimizza x(A − x)/2 nel tratto rilevante e sceglie x = A/2; il follower produce y = A/4. La quantità totale è 3A/4, il prezzo a − 3A/4 e i profitti sono rispettivamente A²/8 e A²/16. L’impegno credibile sulla prima quantità e la sua osservabilità sono essenziali per questo risultato.

Con a = 14 e k = 2, quindi A = 12, i tre modelli danno i seguenti valori.

Le differenze dipendono dalla struttura delle decisioni: simultaneità, accordo congiunto o impegno sequenziale. Il vantaggio della prima mossa qui ottenuto è una proprietà di questo modello, non una regola universale dei giochi.