Teoria dei Giochi: Strategie e Algoritmi

L C R L L R R

●​ se il portiere sceglie Center → 10p + 100p + 5p , cioè 10p + 100(1 – p – p ) + 5p

L C R L L R R

●​ se il portiere sceglie Right → 10p + 15p + 40p , cioè 10p + 15(1 – p – p ) + 40p

L C R L L R R

Risolvendo il sistema di equazioni, si ottiene p 0.3555, p 0.457, p 0.188

≈ ≈ ≈

L R C 31

Teoria dei Giochi: Strategie e Algoritmi

Il tiratore invece ha expected payoff pari a:

●​ se il tiratore sceglie Left → 45q + 90q + 90q , cioè 45q + 90(1 – q – q ) + 90q

L C R L L R R

●​ se il tiratore sceglie Center → 85q + 0q + 85q , cioè 85q + 0(1 – q – q ) + 85q

L C R L L R R

●​ se il tiratore sceglie Right → 95q + 95q + 60q , cioè 95q + 95(1 – q – q ) + 60q

L C R L L R R

Risolvendo il sistema di equazioni, si ottiene q 0.325, q 0.561, q 0.113

≈ ≈ ≈

L R C

Concettualmente non è diverso da prima ma si può notare come all’aumentare del numero di

mosse i calcolo diventano più complessi.

2.19 Mixed Equilibria - 2 Players 3 Strategies w/ Unused Strategies

Fino ad ora abbiamo incontrato giochi con mixed strategies dove le probabilità di usare le strategie

erano tutte positive. Ma se alcune strategie avessero una probabilità di utilizzo pari a 0?

Ci sono metodi per affrontare questi giochi e su cui si basano vari algoritmi di risoluzione di game

theory library.

Trial and Error: non è possibile a priori sapere se un game ha un equilibrio con una strategia

con percentuale nulla; ma si possono fare assunzioni sulle combinazioni possibili di strategie da

non usare.

Ragionando su questo game assumiamo che nessun giocatore usi la strategia center;

risolvendo il gioco otteniamo le seguenti probabilità:

●​ gli expected payoff del tiratore sono

○​ se sceglie Left → 45q + 90q , cioè 45q + 90(1 – q );

L R L L

○​ se sceglie Right → 95q + 60q , cioè 95q + 60(1 – q ).

L R L L

​ Perciò 45q + 90(1 – q ) 95q + 60(1 – q ), da cui q 0.375 e q 1 – q 0.6250.

= = = =

L L L L L R L

●​ gli expected payoff del portiere sono

○​ se sceglie Left → 55p + 5p , cioè 55p + 5(1 – p );

L R L L

○​ se sceglie Right → 10p + 40p , cioè 10p + 40(1 – p ).

L R L L

​ Perciò 55p + 5(1 – p ) 10p + 40(1 – p ), da cui p 0.4375 e p 1 – p 0.5625.

= = = =

L L L L L R L

Abbiamo trovato un equilibrio mixed ma facendo un assunzione che deve essere verificata.

Ad un giocatore non conviene usare una strategia quando conviene usare le altre: si deve

controllare se il payoff ottenuto usando center è più piccolo rispetto alle strategie che non

lo coinvolgono.

Prima calcolo il payoff atteso nel caso in cui il tiratore non considera la mossa Center e il caso nel

quale la considera: l’expected payoff del tiratore (usando Left o Right, o un misto di entrambi)

contro il q–mix del portiere è 45 0.375 + 90 0.6250 = 73.13,

× × 32

Teoria dei Giochi: Strategie e Algoritmi

che è maggiore dell’expected payoff che il tiratore avrebbe usando la strategia Center contro il

q–mix del portiere 70 0.375 + 70 0.6250 = 70.

× ×

Dopo di che calcolo il payoff atteso nel caso in cui il goalie non considera la mossa center e il caso

nel quale la considera: l’expected payoff del portiere (usando Left o Right, o un misto di entrambi)

contro il p–mix del tiratore è 55 0.4375 + 5 0.5625 = 26.87,

× ×

che è maggiore dell’expected payoff che il portiere avrebbe usando la strategia Center contro il

p–mix del tiratore 10 0.4375 + 5 0.5625 = 7.18.

× ×

Entrambi i giocatori hanno un benefico nell’escludere la strategia center nelle mixed strategies,

dunque per entrambi le scelte left e right sono mutual best-response. Oltre le tre strategie può

diventare molto costoso poter testare tutte le possibilità tramite il trial and error.

2.20 Mixed Equilibria - Any number of strategies

Consideriamo due giocatori aventi disponibili le strategie pure R , R , …, R per il player Row e

1 2 n

C , C , …, C per il player Column. Procediamo a considerare una sequenza di passi per un

1 2 n

algoritmo.

2.20.1 Step 1

Selezioniamo un candidato S per il mixed equilibrium, dunque Row utilizzerebbe una strategia g

mentre Column utilizza la strategia h per le mixed strategies.

Assumiamo un insieme di probabilità p–mix e q–mix per i due giocatori con valori rispettivi per

le strategie selezionate pari a P e Q .

i i

Possiamo rinominare le strategie affinché consideriamo due insiemi: quelle fino alla strategia

selezionata che comprende tutte le strategie quelle utilizzate e quelle dopo la strategia

selezionata che comprende tutte le strategie che non vengono utilizzate.

Possiamo sempre rietichettare le strategia in modo che Row usi (nel p–mix) solamente le prime g

strategie R , R , …, R e non usi le rimanenti m – g strategie pure R , R , …, R .

1 2 g g+1 g+2 m

Analogamente, possiamo rietichettare le strategia in modo che Column usi (nel q–mix) solamente

le prime h strategie C , C , …, C e non usi le rimanenti n – h strategie pure C , C , …, C .

1 2 h h+1 h+2 n

Dopodichè identifichiamo i payoff per ciascun giocatore in corrispondenza della combinazione di

strategie utilizzate per ciascuna di essi:

●​ i payoff del giocatore Row dalla strategy combination (i,j) è denotato da A ;

ij

●​ i payoff del giocatore Columns dalla strategy combination (i,j) è denotato da B ,

ij

dove i = 1, …, m e j = 1, …, n.

2.20.2 Step 2

Scriviamo l'equazione che regola il payoff atteso da ogni giocatore per ogni strategia considerata

nel mixed equilibrium dove il valore atteso per ciascuna combinazione di strategie è regolato

dalla probabilità che l’altro la utilizzi. 33

Teoria dei Giochi: Strategie e Algoritmi

Questa equazione per poter modellare correttamente al gioco deve essere soggetta a due vincoli:

1.​ La somma delle probabilità per ogni strategia considerata deve essere pari a 1.

2.​ La probabilità delle strategie non considerate deve essere pari a 0.

Ovviamente siamo in ambito probabilistico dunque non sono ammesse probabilità negative o

superiori a 1. W = P B + P B + … + P B per j = 1, 2, …, h

1 1j 2 2j g gj

con ●​ P + P + … + P = 1;

1 2 g

●​ P = P = … = P = 0.

g+1 g+2 m

Abbiamo scritto un sistema di h + 1 equazioni lineari con g + 1 (le probabilità) incognite,

possiamo risolverlo per trovare un equilibrio.

Una volta che otteniamo una soluzione essa deve soddisfare un insieme di disuguaglianze col

seguente significato: l’expected payoff ottenuto dalla soluzione è maggiore del payoff che il

giocatore (in questo caso Column) otterrebbe usando qualunque altra strategia.

Questo significa che deve essere migliore di ogni altra combinazione di strategie che il

giocatore può utilizzare.

Problema: dobbiamo ripetere lo stesso ragionamento per l’altro giocatore.

2.20.3 Step 3

Scriviamo queste equazioni per l’expected payoff del giocatore Row (contro il q–mix di

Column) V = A Q + A Q + … + A Q per i = 1, 2, …, g

i1 1 i2 2 ih h

con ●​ Q + Q + … + Q = 1;

1 2 h

●​ Q = Q = … = Q = 0.

h+1 h+2 n 34

Teoria dei Giochi: Strategie e Algoritmi

Abbiamo scritto un sistema di g + 1 equazioni lineari con h + 1 incognite, possiamo risolverlo

per trovare un equilibrio e controlliamo che la soluzione soddisfi queste disuguaglianze

V > A Q + A Q + … + A Q per i = g+1, g+2, …, n.

i1 1 i2 2 ih h

Quando queste disequazioni sono verificate abbiamo trovato il Nash equilibrium per mixed

strategies game sotto forma di un array di probabilità:

●​ P , P , …, P p–mix per il giocatore Row;

1 2 g

●​ Q , Q , …, Q q–mix per il giocatore Column.

1 2 h

Ma abbiamo ragionato solamente per una strategia candidata: il processo viene ripetuto

aggiungendo ogni una nuova strategia per ogni giocatore. C’è solo un numero finito di opzioni, ma

un numero esponenziale di combinazioni di strategie il che porta in fretta a un numero di calcoli

proibitivo. Per questa ragione sono utilizzati degli algoritmi per stabilire un numero di passi entro

i quali il processo trova almeno una soluzione.

2.21 Nashpy

NashPy è una libreria Python pensata per rappresentare e analizzare giochi strategici a due

giocatori. È utile per:

●​ rappresentare giochi in forma normale (matrici dei payoff);

●​ calcolare equilibri di Nash;

●​ analizzare strategie pure e miste;​

studiare best responses e payoffs attesi.

Può essere installata localmente seguendo le istruzioni su nashpy.readthedocs.io oppure si

può utilizzare tramite MyDesk di UniMoRe, cercando l’IDE Spyder.

NashPy usa una notazione leggermente diversa rispetto a quella dei corsi universitari. In

particolare: i payoff sono spesso chiamati utilities e le strategie sono codificate come vettori di

probabilità (es. [1, 0] per scelta pura della prima strategia)

In NashPy si possono rappresentare: strategie pure (es. [1, 0]) e trategie miste (es. [0.5, 0.5]).​

NashPy permette di calcolare i payoff attesi per entrambe i giocatori usando queste strategie

miste. Ad esempio:

NashPy consente anche di verificare se una strategia è una best response rispetto all’altra. Il

.is_best_response(sigma_r, sigma_c) restituisce una coppia di booleani: il primo

metodo sigma_r sigma_c

indica se è una best response a , il secondo se vale il viceversa.​ 35

Teoria dei Giochi: Strategie e Algoritmi

NashPy fornisce diversi metodi per trovare equilibri di Nash:

1.​ Minimax (solo per giochi a somma zero): si specifica solo la matrice di payoff del

primo giocatore. Questo metodo calcola una strategia ottimale contro l'avversario.

2.​ Support Enumeration: è il metodo più generale: restituisce tutti gli equilibri di Nash

(puri e misti). Tuttavia, è computazionalmente molto costoso. Inoltre, può dare

problemi con i giochi degeneri.

Un gioco è detto non degenere se una strategia mista con supporto di dimensione k non ha

più di k risposte pure ottimali. Nei giochi degeneri, il metodo di support enumeration può

restituire risultati incoerenti o generare avvertimenti. Esempio problematico: un gioco con

payoff simmetrici che produce infiniti equilibri misti. In questi casi, l’indifferenza tra le strategie

può essere fuorviante e non riflettere realisticamente le preferenze dei giocatori.