GIOCHI, Teoria dei

GIOCHI, Teoria dei

La t. dei g. è un modello matematico per lo studio delle "situazioni competitive", in cui cioè sono presenti più persone (o gruppi di persone, o organizzazioni) dette appunto "giocatori", con autonoma capacità di decisione e con interessi contrastanti. Tali sono i g. di società (come bridge, poker, tressette, scacchi) che hanno dato il nome alla t., e ne costituiscono il più tipico esempio di applicazione perché, essendo ben precisate le norme che li regolano, possono essere facilmente schematizzati in un modello matematico. Le situazioni prese in considerazione dalla t. dei g. rientrano, tuttavia, in molti campi meno futili (economico, militare, ecc.) sia pur con la grossa difficoltà di chiarire a quantificare i diversi elementi che concorrono a determinare la situazione. La t. dei g., a parte i precursori (tra cui è da citare E. Borel), è stata introdotta da un lavoro congiunto del matematico J. Von Neumann e dell'economista O. Morgestern, ed è stata successivamente sviluppata soprattutto nell'ambito della "ricerca operativa" (v. operativa, ricerca, in App. III, 11, p. 315). La t. dei g. è collegata alla "teoria delle decisioni" (v. decisioni, teoria delle, in quest'App.) della quale, secondo alcuni, fa parte.

Il caso più semplice, e l'unico per il quale siano stati ottenuti risultati abbastanza conclusivi, è quello dei "g. a due giocatori, a somma nulla", intendendosi con ciò che gl'interessi dei due giocatori sono in diretta antitesi: tutto ciò che uno dei due giocatori perde viene guadagnato dall'altro. Questo tipo di g. viene rappresentato con il seguente modello matematico: si indicano con x₁,..., x_m (supponiamo per semplicità in numero finito) le alternative possibili del primo giocatore; con y₁,..., y_n le alternative del secondo; con a_ij il guadagno (espresso, per es., in lire) del primo giocatore se egli sceglie l'alternativa x_i e l'altro l'alternativa y_j (il guadagno è inteso in senso algebrico: se aij è negativo, si tratta di una perdita). Per la proprietà di somma nulla, a_ij è anche la perdita (sempre in senso algebrico) del secondo giocatore. Si suppone che ciascun giocatore faccia la sua scelta senza conoscere la scelta dell'avversario. La "tabella o (matrice) dei pagamenti" formata dai valori a_ij riassume gli elementi del g. che vengono presi in considerazione per il suo studio matematico, indipendentemente dalle circostanze materiali del suo svolgimento, cioè ne costituisce il modello matematico. I, a tab. 1 presenta un esempio di g., rappresentato appunto mediante la tabella dei pagamenti (l'ultima riga e l'ultima colonna sono aggiunte per elaborazioni successive).

È evidente come tale modello possa rappresentare alcuni g. molto semplici (per es. il "pari e dispari", dove ciascun giocatore ha due alternative); meno evidente che a esso si possono ricondurre g. molto più complessi, e in particolare g. "a più mosse". Occorre per questo condensare ìn un'unica scelta tutte le scelte da fare nel corso del g.; cioè prevedere tutte le situazioni in cui un giocatore si può venire a trovare, e per ciascuna di esse fissare la linea da seguire. Questo complesso di scelte prende il nome di "strategia", e lo svolgimenento del g. viene così ricondotto alla scelta di una tra più strategie possibili da parte di ciascun giocatore: la scelta delle strategie determina il risultato. Il g. si dice allora "in forma normale". È chiaro che la riduzione del g. a forma normale può essere molto complessa, anche per g. relativamente semplici, o addirittura materialmente impossibile (come, almeno allo stato attuale dell'evoluzione degli elaboratori elettronici, per gli scacchi); è però concettualmente possibile, e permette di applicare, anche a g. complessi, alcuni risultati teorici. Per es., risulta da un teorema generale che, se i giocatori potessero padroneggiare la complessità del g. degli scacchi, il risultato di ogni partita sarebbe determinato.

La t. dei g. mira a individuare le scelte ottime; cioè, per ciascun giocatore, la strategia che gli dà il risultato migliore. Ora il risultato del g. è determinato dalle scelte di entrambi i giocatori; e in generale una strategia di un giocatore, che risulta migliore delle altre in corrispondenza a una scelta dell'avversario, non lo è in corrispondenza ad altre scelte. Un esempio è offerto dal g. della tab.1. Se il giocatore B adotta la strategia y₁, la strategia ottima di A è x₃, che gli fa vincere 4 lire; ma se B adotta la strategia y₂, la strategia ottima per A è x₂. Si può osservare che la strategia x₄ va scartata, nella ricerca dell'ottimo, perché è "dominata" da x₃ (fornisce cioè risultati peggiori, o al massimo uguali, contro ogni strategia di B). Se, scartate successivamente le strategie dominate, si arrivasse per un giocatore a una sola strategia (o più strategie equivalenti), la scelta sarebbe obbligata; ma in molti g., come in quello esaminato, ciò non accade. Di conseguenza non esiste sempre una strategia ottima in senso assoluto, e bisogna ripiegare sulla scelta di una strategia che risulti migliore delle altre in base a qualche criterio abbastanza convincente, anche se non decisivo in senso assoluto.

A tali considerazioni risponde il criterio del "minimax", che illustreremo riferendoci alla tab. 1. Se il giocatore A vuole attenersi a un criterio di prudenza, considererà per ogni sua strategia il risultato peggiore, cioè il minimo per ogni riga, e tra tali minimi (riportati nell'ultima colonna) sceglierà il valore più alto; adotterà cioè la strategia x₂, che gli assicura comunque, "contro la migliore difesa", il guadagno di 1 lira. Un analogo discorso per B porta a considerare i massimi delle colonne (cioè la perdita più alta per ciascuna strategia) e, tra questi, il minimo. Ora nella tab. 1 si osserva che il minimo dei massimi delle colonne ha lo stesso valore del massimo dei minimi delle righe. Quando ciò accade si dice che il g. ha il "minimax", e si chiamano "strategie minimax" le strategie dei due giocatori che vi conducono. Il risultato cui si arriva, cioè il massimo dei minimi delle righe, che coincide con il minimo dei massimi delle colonne, è detto "valore del gioco". Vi sono allora buone ragioni per la scelta delle strategie minimax: infatti per ciascun giocatore il valore del g. non rappresenta più soltanto quanto egli può assicurarsi con una condotta prudenziale, ma anche il massimo cui può aspirare contro una buona difesa dell'avversario. Il minimax rappresenta inoltre un "punto di equilibrio", cioè nessun giocatore può migliorare unilateralmente il suo risultato. Si dice anche, con chiaro significato, che il g. ha un "punto di sella", perché in corrispondenza al minimax c'è un valore della tabella dei pagamenti che è sia il minimo della sua riga che il massimo della sua colonna.

Queste considerazioni risolvono (nel senso limitativo già indicato) la ricerca del comportamento ottimo quando il g. ha il minimax. Ma ciò non avviene per tutti i giochi. In quello della tab. 2, per es., A può assicurarsi un guadagno almeno uguale a 2 lire; B può assicurarsi che la perdita non superi 3 lire; nell'intervallo tra 2 e 3 lire c'è spazio per una ragionevole aspirazione, da parte di ciascun contendente, a migliorare il proprio risultato. Ciò in effetti si può ottenere se il giocatore, rinunciando a scegliere direttamente la strategia, affida la scelta a un meccanismo casuale (per es., lancio di un dado, o, seguendo un procedimento più sofisticato, con l'uso dei "numeri casuali"), guidando però tale scelta mediante la scelta in modo opportuno delle probabilità da assegnare alle varie strategie. Contemporaneamente egli dovrà convenire di valutare il risultato, che ora non è più determinato ma aleatorio, mediante il suo valor medio. Il ricorso al caso (utilizzato anche nella teoria statistica delle decisioni) può essere psicologicamente rifiutato come puerile o fatalista o rinunciatario; in realtà la grossa difficoltà è nella condizione aggiuntiva di valutare un risultato aleatorio mediante il suo valor medio, perché in generale per una persona una somma certa di un milione di lire non ha lo stesso valore di una scommessa che abbia un milione come risultato medio. Tale difficoltà si supera, o almeno si attenua, se ai valori in denaro si sostituisce la cosiddetta "utilità".

Un giocatore, così, invece di scegliere una strategia, sceglie una distribuzione di probabilità sulle strategie, o, come anche si dice, una "strategia mista". Con l'estensione alle strategie miste, i g. hanno il minimax sotto condizioni molto ampie (per es., se le "strategie pure" dei due giocatori sono in numero finito, come nei casi visti finora) e vengono quindi ricondotti alla trattazione già fatta. Il calcolo delle strategie miste minimax per i due giocatori, e del valore del g., è complicato, e si può riportare a un problema di "programmazione lineare" (v. programmazione lineare, in questa Appendice). Per il g. della tab. 2 la strategia mista minimax di A risulta essere (¹/₃, ¹/₃, ¹/₃, o) cioè corrisponde a scartare la strategia x₄ e scegliere casualmente con probabilità uguali una delle altre tre strategie pure; la strategia mista minimax di B è (⁵/₉, ²/₉, ²/₉) (assegna cioè alla strategia y₁ una probabilità più alta delle altre); e il valore del g. è 7/3; cioè il risultato del g. sarà il guadagno (medioi), da parte di A, di 2,33 lire, ovviamente intermedio tra i valori 2 e 3 visti in precedenza.

I problemi posti dai g. a due persone a somma nulla trovano così una soluzione abbastanza soddisfacente in molti casi. Purtroppo non è lo stesso per gli altri tipi di g. (a più persone o a somma non nulla) che sono i più interessanti per le applicazioni, soprattutto nel campo economico. Qui infatti intervengono quasi sempre più di due persone, o gruppi di persone; e se si isolano due "giocatori" per studiare il loro comportamento, il g. che ne risulta è in generale a somma non nulla, per la presenza di altre persone o gruppi interessati, che a volte interferiscono nella situazione: si pensi ai rapporti tra un venditore e un acquirente, ovviamente influenzati dalla presenza della concorrenza.

Per illustrare le difficoltà che sorgono con i g. a somma diversa da zero, si consideri il g. rappresentato dalla tab. 3, nella quale ciascun giocatore ha due strategie, e per ciascuna scelta delle strategie sono indicati sia il guadagno del giocatore A (il primo valore) sia quello di B. In vista dei risultati paradossali cui si arriva nell'esame di tale g., è opportuno osservare che esso rappresenta, ovviamente in forma molto semplificata, molte situazioni reali; per es., la scelta, da parte di due negozianti in concorrenza, tra prezzi bassi (strategie x₁ e y₁) e alti: la scelta di strategie analoghe da parte dei due giocatori porta a un risultato di sostanziale parità, ma con minori guadagni nel caso di scelta di prezzi bassi; se vengono scelte strategie diverse uno dei due giocatori risulta avvantaggiato. Allo stesso tipo di tabella può essere riportato (naturalmente con larga indeterminazione nella valutazione dei "guadagni") la scelta tra armamento e disarmo di due blocchi internazionali contrapposti.

Un esame della tab. 3 mostra che un comportamento apparentemente razionale di A porta alla scelta della strategia x₁, che appare migliore per lui, qualunque sia la strategia scelta da B. Analogamente B sceglierebbe y₁, con il risultato (5; 5) chiaramente inferiore per ciascuno a quello (20; 20), e, complessivamente per i due giocatori, inferiore anche a (30; −15) o (−15;30). La scelta dei due giocatori risulta ovviamente diversa se è ammessa la possibilità di una "coalizione" tra i due giocatori (si dice allora che il g. è "cooperativo"); ma ciò in alcuni casi è proibito dalle "regole del g." (per es., nel campo economico, da leggi anti-trust), in altri casi è reso poco sicuro dalla difficoltà pratica di far mantenere gli accordi.

Alcuni autori prendono lo spunto da tali osservazioni per negare l'utilità di artificiose soluzioni che abbiano valore puramente matematico, e riconoscere che situazioni del genere descritto non sono affrontabili mediante la t. dei g.; anzi addirittura che esse non si possono risolvere se non prescindendo dal "comportamento razionale" posto alla base della t., per cui ogni giocatore tende a rendere massimo il suo utile, a scapito degli altri giocatori.

Come si è già visto, dal punto di vista matematico un g. in forma normale è una terna G = (X, Y,M), dove X è l'insieme delle strategie del giocatore A, Y l'insieme delle strategie del giocatore B, ed M = M(x,y), (x ∈ X, y ∈ Y) la funzione dei pagamenti. Posto

si constata subito che per ogni coppia di strategie (x,y) si ha L_G(x) ≤ N_G(y) e, di conseguenza, l_G ≤ n_G.

Se è l_G = n_G, si dice che il g. ha il minimax, e il valore v_G = l_G = n_G si dice "valore del gioco". Se inoltre esiste una strategia x₀ ∈ X [y₀ ∈ Y] tale che L_G(x₀) = v_G[N_G(y₀) = v_G,], x₀ [y₀] si dice "strategia minimax".

Il teorema del punto di sella afferma che x₀ ∈ X e y₀ ∈ Y sono strategie minimax se e solo se M(x₀, y₀) ≤ M(x₀, y) ∀ y ∈ Y, e M(x₀, y₀) ≥ M(x, y₀) ∀ x ∈ X; si ha inoltre M(x₀, y₀) = v_G.

Se il g. G non ha il minimax, se cioè l_G 〈 n_G, si prendono in considerazione le strategie miste, cioè, come si è già visto, le distribuzioni di probabilità su X e Y. Più precisamente, indicando con ξ e η le distribuzioni di probabilità rispettivamente su X e Y; si considerano gl'insiemi Ξ e H delle distribuzioni ξ e η tali che esiste finito il valor medio M(ξ, η) = ∉M(x, y) dξ dη. Occorre naturalmente che gli spazi X e Y siano tali da rendere signifimtive tale definizioni; si può osservare, tuttavia, che in qualsiasi spazio X esistono almeno le distribuzioni di probabilità concentrate in un solo punto x; tali strategie miste vengono identificate con le corrispondenti strategie pure x. Il g. Γ = (Ξ, H,M) è "l'estensione mista" del g. G. Si dimostra facilmente che l_G ≤ l_Γ ≤ n_Γ ≤ n_G, cosicché l'estensione mista Γ può avere il minimax anche se G non lo ha.

La ricerca delle condizioni sotto le quali l'estensione mista Γ di un g. G ha il minimax costituisce una parte notevole dello studio matematico dei g. a due persone a somma nulla. Gli strumenti impiegati sono soprattutto gl'iperpiani di separazione dì insiemi convessi o, alternativamente, teoremi del punto fisso. Si dimostra facilmente che se il g. G è finito (se cioè gl'insiemi X e Y sono finiti), Γ ha il minimax, ed esistono strategie minimax ξ₀ e η₀. Nelle applicazioni più comuni gl'insiemi X e Y sono sottoinsiemi di spazi euclidei; in questo caso si ha il risultato che se X e Y sono compatti, e M(x, y) è continua, l'estensione mista Γ ammette il minimax e ha strategie minimax.

Bibl.: J. Von Neumann, O. Morgenstern, Theory of games and economic behavior, Princeton 1944; D. Blackwell, M. A. Girshick, Theory of games and statistical decisions, New York 1954; B. de Finetti, La teoria dei giochi, in Civiltà delle macchine, 1963, n. 4 e n. 5; G. Owen, Game theory, Filadelfia 1968; G. Dall'Aglio, Lezioni di teoria dei giochi e delle decisioni, Roma 1969.