Date post: | 28-Mar-2016 |
Category: |
Documents |
Upload: | danilo-tallini |
View: | 215 times |
Download: | 0 times |
black pellicola (27,1)
di Roberto Lucchetti e Stef Tijs
Gli autori dedicano questo articolo a G. Owen in occasio-
ne del suo sessantacinquesimo compleanno.
n 1 Introduzione
La Teoria dei giochi e disciplina matematica recente. E
vero che c’e chi ne ha visto tracce nel Talmud [1] e che,
quando si cerca una data d’inizio, c’e sempre qualcuno
che scopre qualcosa di antecedente. Ma non c’e dubbio
alcuno che questa teoria nasce nel ventesimo secolo.
Convenzionalmente, la data che si cita piu spesso e quel-
la del 1944, quando esce il libro di von Neumann e Mor-
genstern [2] che e il primo trattato sistematico sull’argo-
mento. Da allora, la teoria ha fatto molti passi in avanti,
si e sviluppata in molteplici direzioni e viene usata in al-
tre discipline per le sue possibili applicazioni.
Non e possibile riassumere in poche pagine tutte le sue
principali diramazioni. Parleremo allora soltanto di alcu-
ne parti della teoria classica, ignorandone molti aspetti
che pure sono fondamentali. Ci limiteremo a quella parte
della teoria classica che parla di giochi ad informazione
completa ed in forma normale. Non solo: suddivideremo
la teoria stessa in due parti, quella relativa ai giochi non
cooperativi e quella che riguarda i giochi cooperativi
(tralasciando alcuni che non si possono strettamente ri-
condurre ad una delle due, come per esempio il problema
della contrattazione).
Dicevamo della forma normale di un gioco. In genere, un
gioco e caratterizzato da regole che ne spiegano le condi-
zioni iniziali (ad esempio, la disposizione dei pezzi su
una scacchiera), la sua evoluzione (le mosse possibili in
ogni situazione) ed infine la sua conclusione, che nei casi
piu semplici sara la vittoria di un giocatore, o di una
27
48 j lettera matematica
IN
TERVEN
TI
Invito a
La Teoria dei giochi
black pellicola (28,1)
squadra, ma che naturalmente puo invece richiedere una
descrizione piu articolata. Tradurre tutto questo in forma
matematica e un’operazione quasi mai banale, spesso af-
fascinante. La caratteristica fondamentale di questa tra-
duzione e la sua complessita. E facile rendersi rapida-
mente conto che anche giochi facilissimi richiedono una
formulazione non proprio breve. Questa forma di descri-
zione si chiama gioco in forma estesa e viene spesso
messa sotto forma di albero del gioco.
In questo contesto, assume particolare importanza il con-
cetto di strategia, che va interpretato in maniera corret-
ta. Altrimenti e fonte di errori, tanto gravi quanto comu-
ni. Ad esempio, si puo pensare che due individui – chia-
mati a votare, uno dopo l’altro ed in modo palese, a favo-
re o contro un certo provvedimento – siano posti di fron-
te allo stesso problema o, per essere piu precisi, abbiano
le stesse strategie possibili (votare a favore o contro).
Non e cosı! In realta, il secondo a votare e di fronte ad
una situazione piu complessa.
Comunque, in questa breve panoramica, ci limiteremo ai
giochi in forma normale. Il che significa che assumiamo
come date – e note – le strategie dei giocatori, cosı come
assumiamo note le loro funzioni di utilita, cioe come va-
lutano per se ogni situazione finale del gioco. In altre pa-
role, nel caso di due giocatori, supporremo l’esistenza di
due insiemi X e Y , i cui elementi sono le strategie dell’u-
no e dell’altro, e di due funzioni f1; f2 : X � Y ! R, che
rappresentano le loro funzioni di utilita (o pagamento).
Se il gioco e a due giocatori e finito – il che significa che i
due hanno un numero finito di strategie possibili – allora
si puo efficacemente descriverlo con una bimatrice, come
ad esempio la seguente:
ð4;9Þ ð3;5Þ ð1;8Þð7;4Þ ð5;1Þ ð8;0Þð8;0Þ ð2;9Þ ð0;0Þ
0@
1A
Leggerla e facile: un giocatore, convenzionalmente detto
il primo, sceglie una riga, il secondo una colonna. La ca-
sella cosı identificata contiene una coppia di numeri. Il
primo rappresenta il guadagno di chi sceglie le righe, il
secondo di chi sceglie le colonne. Nel caso in cui il gioco
sia a somma zero – quando, in ogni risultato finale, quel
che guadagna uno e esattamente quel che perde l’altro –
si scrive un solo numero nella casella (si parla in questo
caso di matrice, non di bimatrice) che, convenzionalmen-
te, rappresenta quanto il secondo paga (in senso algebri-
co) al primo.
I giochi a somma zero rappresentano un po’ le fonda-
menta della teoria, e sono stati i primi ad essere studiati.
Per questo, adesso, vediamo alcune loro proprieta.
n Giochi a somma zero
Consideriamo, ad esempio, il gioco descritto dalla se-
guente matrice:
4 3 17 5 88 2 0
0@
1A
Quale puo essere il risultato ragionevole di questo gioco?
Messo in altri termini – visto che tutti i coefficienti sono
positivi – quanto bisognerebbe dare a qualcuno per con-
vincerlo a giocare come secondo? A prima vista non e
evidente! Ma un buon ragionamento potrebbe essere il
seguente: il secondo giocatore non accettera mai di paga-
re piu di 5 perche, giocando la seconda colonna, sa di
pagare al massimo 5, contro un pagamento possibile di 8
se giocasse le altre colonne. Si dice allora che 5 e il valo-
re conservativo vs del secondo giocatore:
5 ¼ vs ¼ minj
maxi
aij :
D’altra parte il primo, facendo lo stesso ragionamento
(con segni cambiati!), sa di potersi garantire almeno 5,
giocando la seconda riga, contro guadagni probabili di 1,
se giocasse la prima, e 0 se giocasse la terza. Si dice allo-
ra che 5 e il valore conservativo vp del primo giocatore:
5 ¼ vp ¼ maxi
minj
aij :
Riassumendo: il primo non accetta meno di 5; il secondo
non paga piu di 5. A questo punto, il risultato del gioco e
molto chiaro. Possiamo, dunque, concludere che vp ¼ vs
e quanto i due giocatori converranno essere il risultato
del gioco.
Esercizio 1.1 Data una funzione f : X � Y ! R, provare
che1
vs ¼: infy
supx
f ðx;yÞ � supx
infy
f ðx;yÞ ¼: vp:
Facciamo ancora un’osservazione, dettata dall’analisi del
gioco precedente: 5, che e il risultato del gioco, viene ot-
tenuto quando i due giocano la seconda riga e colonna,
rispettivamente, e rappresenta contemporaneamente il
IN
TERVEN
TI
28
48 j lettera matematica
black pellicola (29,1)
minimo sulla riga ed il massimo sulla colonna. In formu-
la, allora, un equilibrio e dato dalla scelta di una coppia –
detta sella – ð�ii�jjÞ tale che:
ai�jj � a�ii�jj � a�iij;
per ogni i; j. Quindi l’equilibrio ha l’ulteriore interessante
proprieta che, se per caso uno dei due giocatori venisse a
sapere quel che fa l’altro, non avrebbe nessun interesse a
deviare dalla sua scelta iniziale. Inoltre vale la seguente
proposizione.
Proposizione 1.1 Sono fatti equivalenti:
� a�ii�jj e una sella;
� (a) minj a�iij ¼ maxi minj aij ¼ vp;
(b) maxi ai�jj ¼ minj maxi aij ¼ vs;
(c) vp ¼ vs.
Esercizio 1.2 Provare la Proposizione precedente.
La Proposizione 1.1 (che ancora una volta, ad una lettura
formale, appare un intrico di simboli) racconta invece co-
se molto interessanti. Guardiamo che cosa afferma la se-
conda condizione. Il gioco ha un equilibrio se vp ¼ vs e
se �jj e �ii soddisfano certe condizioni indipendenti fra loro.
Infatti �jj deve soddisfare ðbÞ, ove �ii non interviene, e �ii deve
soddisfare ðaÞ, ove �jj non interviene. Questo significa che i
giocatori non hanno nessun bisogno di coordinare le loro
azioni per arrivare all’equilibrio. Ci arrivano comunque
(se esiste, cioe se vp ¼ vs, condizione che non coinvolge
scelte dei giocatori, ma solo un calcolo) massimizzando
l’uno e minimizzando l’altro una certa funzione, che di-
pende unicamente dalle strategie del giocatore in questio-
ne.
Tutto facile dunque? Non proprio. Guardiamo un secondo
esempio:
0 1 �1�1 0 11 �1 0
0@
1A:
La matrice appena letta potrebbe ad esempio descrivere
la morra cinese, ove i giocatori contemporaneamente de-
vono decidere se scegliere tra sasso, carta e forbici. Ana-
lizzandolo, ci si accorge che le cose possono immediata-
mente complicarsi. Infatti, il primo sa di non potersi ga-
rantire a priori piu di -1 (vp ¼ �1), il secondo di non pa-
gare meno di 1 (vs ¼ 1). Il che, tradotto in linguaggio piu
terra terra, significa che, qualunque cosa facciano, i gio-
catori non possono garantirsi nulla di piu che perdere.
D’altra parte, se fissiamo una qualunque casella della
matrice, e evidente che almeno uno dei due giocatori, in
qualche caso tutti e due, non accetterebbero di ritenerla
un equilibrio.
Se allora succede che sia vp < vs, dobbiamo rassegnarci
a concludere che una teoria scientifica non puo prescri-
vere una maniera ‘‘razionale’’ per giocare? Che, per vin-
cere, bisogna affidarsi alla psicologia, o magari all’astro-
logia? Supponiamo, ad esempio, di giocare piu volte con
lo stesso avversario. Supponiamo anche che io sia cosı
ingenuo da far capire all’avversario che non tiro mai car-
ta perche proprio non mi piace. Che fara lui? Mi sembra
evidente che tirera sempre sasso. Mal che vada, pareg-
gia; altrimenti, vince. Supponiamo che io cambi un po’
strategia, diventi un po’ piu sofisticato e giochi carta con
probabilita 20%, sasso con probabilita 50% e forbici con
probabilita 30%. Cosa fara il mio avversario, che e piu
intelligente di me (...solo in questo gioco, s’intende)? Non
bisogna pensare troppo per concludere che giochera
sempre carta, il che gli permette di vincere meta delle
partite e perderne solo il 30% (forse qualcuno vede la ra-
gione per cui, anche se io faccio le mie scelte con criteri
probabilistici, il mio avversario reagisce in maniera otti-
male giocando sempre la stessa cosa).
Dunque, appare abbastanza chiaro che anche un gioco
senza equilibrio non va giocato senza cervello. Ma che si-
gnifica introdurre criteri probabilistici nelle nostre scelte?
E che idea di equilibrio introdurre in questo contesto?
IN
TERVEN
TI
48 j lettera matematica
29
Guillermo Owen
black pellicola (30,1)
Senza entrare nei dettagli, l’idea e di estendere l’insieme
delle strategie dei giocatori. Se ad esempio il primo deve
scegliere fra n righe, il suo nuovo spazio delle strategie
(detto lo spazio delle strategie miste) diventa l’insieme
dei vettori p1; ;pn tali che pi � 0, eP
pi ¼ 1. Una tale
scelta significa che egli gioca la prima riga con probabili-
ta p1, l’ennesima riga con probabilita pn. La funzione di
pagamento viene poi calcolata ovviamente come valore
atteso ed in questo nuovo gioco si cercano le sue selle,
che saranno i nuovi equilibri, in senso generalizzato, del
gioco di partenza.
Ebbene, ecco il bellissimo teorema di von Neumann con
cui chiudiamo la parte sui giochi a somma zero:
Teorema 1.1 Ogni gioco a due persone finito e a somma
zero ammette equilibrio in strategie miste.
Un’ultima osservazione. Nel gioco della morra cinese, l’u-
nica strategia di equilibrio per entrambi e di giocare con
probabilita 1/3 le tre strategie. Questo e ovvio date le
simmetrie del gioco (ogni strategia e vincente contro una
e perdente contro un’altra). E naturalmente, essendo un
gioco equo, il valore di equilibrio e zero.
n Giochi a somma non nulla
La Proposizione 1.1 puo far capire perche in un certo
senso la ‘‘vera’’ teoria dei giochi non nasce con i giochi a
somma nulla e con il teorema di minimax di von Neu-
mann. Pur essendo chiaro che si sta gia parlando di gio-
chi, ancora non e presente una vera interazione fra i par-
tecipanti. Esistono tantissimi esempi di situzioni in cui i
giocatori possono, facendo certe scelte, guadagnare (op-
pure perdere) entrambi: non e necessariamente detto
che, quando uno guadagna, l’altro debba necessariamen-
te perdere. Ad esempio, due negozianti vicini e con gli
stessi prodotti possono accordarsi per tenere alti i prezzi,
con guadagno per entrambi. C’e dunque bisogno di una
teoria nuova, piu generale, che tenga conto di queste si-
tuazioni, che sono poi le piu interessanti.
Von Neumann penso allora di trovare la strada, svilup-
pando la teoria cooperativa di cui parliamo nel prossimo
paragrafo. Quindi, nel libro con Morgenstern gia citato,
studia come si formano coalizioni fra individui e cerca di
introdurre poi un concetto di soluzione che tenga conto
del possibile formarsi di queste coalizioni. Nei primissimi
anni ’50, von Neumann si trova a Princeton, all’Institute
of Advanced Study, posticino in cui si puo incontrare an-
che gente del calibro di Einstein e Godel ed in cui girano
studentelli abbastanza dotati – come ad esempio Milnor e
Shapley – tanto per fare un paio di nomi. C’e anche uno
studente un po’ piu dotato ed un po’ piu pazzo degli altri,
J.F. Nash, fermamente deciso a mostrare al mondo le
sue qualita di matematico puro ma anche attratto dalla
Teoria dei giochi per la presenza appunto del matematico
piu famoso del mondo, J. Von Neumann. Cosı Nash si de-
dica, per la sua tesi, alla Teoria dei giochi, pur non tra-
scurando altre cose nella paura che una tesi cosı ‘‘appli-
cativa’’ non sia sufficientemente astratta da essere accet-
tata. Per nulla intimidito dall’idea di contrapporsi a von
Neumann, decide di proporre un modello alternativo e
definisce il gioco in forma normale come abbiamo gia vi-
sto sopra. Propone anche la sua idea di equilibrio e forni-
sce un teorema di esistenza, basato su tecniche di punto
fisso. Von Neumann liquido il modello di Nash ed il suo
concetto di equilibrio, definendolo null’altro che un altro
teorema di punto fisso. Anche i geni sbagliano, natural-
mente. Gli anni successivi hanno dimostrato in maniera
inequivocabile che il modello vincente (almeno per ora) e
quello di Nash. Il concetto di equilibrio da lui formulato e
di gran lunga quello piu usato, soprattutto nelle applica-
zioni ad altre discipline.
Vediamo dunque la definizione di equilibrio di Nash. Poi,
piu che occuparci di un teorema di esistenza o di indicar-
ne applicazioni, metteremo in luce il fatto che, nonostan-
te sia riconosciuto come il concetto fondamentale di
equilibrio, non sempre i risultati cui porta sono piena-
mente soddisfacenti. Un equilibrio di Nash e una coppia
di strategie ð�xx; �yyÞ tali che:
f1ð�xx; �yyÞ � f1ðx; �yyÞ;8x 2 X ; f2ð�xx; �yyÞ � f2ð�xx; yÞ;8y 2 Y :
Il significato della definizione e chiaro: una coppia di
strategie rappresenta un equilibrio se ogni giocatore,
prendendo per fissata la strategia dell’altro, non ha inte-
resse a deviare dalla strategia a lui proposta.
Esercizio 1.3 Provare che, in un gioco a somma zero, un
equilibrio di Nash e una sella del gioco e viceversa.
L’esercizio precedente mostra che il concetto di equilibrio
proposto da Nash rappresenta effettivamente un’estensio-
ne del concetto di equilibrio elaborato per i giochi a som-
ma zero. Ma valgono ancora le proprieta messe in luce
dalla Proposizione 1.1?
48 j lettera matematica
IN
TERVEN
TI
30
black pellicola (31,1)
Consideriamo il gioco seguente, chiamato la battaglia dei
sessi: Gabriella e Michele devono decidere il programma
della serata e sono indecisi se andare al cinema o a tea-
tro. Michele preferisce un film, Gabriella invece l’opera.
In ogni caso, preferiscono stare assieme. Ecco una bima-
trice2 che potrebbe ragionevolmente rappresentare il gio-
co:
ð5;10Þ ð�1;1Þð1;�1Þ ð10;5Þ
� �:
Lasciamo a chi ne ha voglia la facile verifica che entram-
be le scelte – di recarsi al cinema o a teatro – rappresen-
tano equilibri di Nash (del resto non ci vuole certo Nash
per consigliare loro di stare assieme, visto che preferisco-
no stare assieme!). Tuttavia sorge un primo problema,
che non esiste nei giochi a somma nulla: i due giocatori
non sono indifferenti rispetto ai due equilibri. Infatti, uno
ha una evidente preferenza per uno dei due equilibri;
l’altro per quello esattamente opposto. Nei giochi a som-
ma zero, questo non succede perche in ogni sella il valore
e lo stesso e quindi i giocatori sono indifferenti su quale
sella un eventuale arbitro li indirizza. Ma c’e di peggio. I
due giocatori devono coordinare le loro mosse. Se i due
non possono comunicare, ad esempio perche un cellulare
si e scaricato, come si comporteranno? E evidente il ri-
schio che succeda un pasticcio: potrebbero entrambi de-
cidere di orientarsi all’equilibrio che piace loro di piu o,
peggio ancora, fare entrambi un gesto di generosita nei
riguardi del partner e la conclusione in quest’ultimo caso
sarebbe che entrambi si trovano, da soli, nel posto sba-
gliato! Insomma, e indispensabile un coordinamento fra i
due che e invece del tutto inessenziale nei giochi stretta-
mente competitivi (che non sia necessario il coordina-
mento e che siano indifferenti su quale sella orientarsi ce
lo dice sempre la Proposizione 1.1: non e sorprendente
quante cose puo raccontare una formula?). D’altra parte,
non possiamo pensare che questo problema sia dovuto al
fatto che il concetto di equilibrio proposto da Nash non
sia adeguato: e evidente che, date le informazioni che ab-
biamo sul gioco precedente, e impossibile stabilire una
gerarchia fra le due soluzioni proposte.
Ma esistono problemi ancora piu gravi. Vediamo un altro
gioco. Cominciamo con lo scrivere i pagamenti del gioca-
tore che sceglie le righe:
1 110 10
� �:
Non c’e nessun dubbio sulla scelta che fara il giocatore!
Infatti, la prima riga gli porta guadagni superiori, qua-
lunque cosa faccia l’avversario. Non c’e dubbio che que-
sta sia una situazione ‘‘ideale’’. Ancora una volta, un gio-
catore non ha bisogno di sapere cosa fa l’altro e puo de-
cidere senza tenere conto del comportamento dell’avver-
sario. E arrivato allora il momento di mettere anche i pa-
gamenti del secondo:
ð1;1Þ ð11;0Þð0;11Þ ð10;10Þ
� �
Forse qualcuno notera che il secondo si trova nella iden-
tica situazione del primo: in effetti, il gioco e costruito su
una simmetria completa delle scelte dei due. Dunque, an-
che il primo sceglie la prima colonna, per un risultato fi-
nale che porta ad entrambi un guadagno di 1. La scelta
prima riga-prima colonna e anche chiaramente l’unico
equilibrio del gioco.
Ma c’e un problema ed e un problema serio. I due, che
per ipotesi sono razionali3, scelgono di guadagnare 1 a
testa pur avendo la possibilita di guadagnare 10 entram-
bi! E il momento di passare ai giochi cooperativi. Non e
nemmeno pensabile di mettersi qui a fare una discussio-
ne sulle implicazioni dell’esempio precedente. Ci sono li-
bri interi che parlano delle problematiche sollevate dall’e-
sempio precedente e non sono solo libri scritti da teorici
della Teoria dei giochi. Oppure, chi ne ha voglia, si puo
divertire a cercare su Internet: basta andare su un moto-
re di ricerca e digitare dilemma del prigioniero.
n Giochi cooperativi
La teoria dei giochi cooperativi si occupa di modelli ma-
tematici pensati per descrivere situazioni in cui i giocato-
ri hanno interesse a cooperare per ottenere piu di quanto
potrebbero da soli. Ad esempio, si puo pensare a situa-
zioni in cui si mettano insieme risorse produttive, oppure
al car pooling, alla condivisione di linee per ridurre i co-
sti di connessione di reti di comunicazione o di una pista
di atterraggio per chi possiede aeroplani. Il quesito fon-
damentale che nasce in situazioni come queste e: come
suddividere i vantaggi ottenuti dalla cooperazione tra i
partecipanti?
Ci sono svariati modelli matematici per studiare la coope-
razione: considereremo qui quello classico, introdotto nel
libro di von Neumann e Morgenstern [2]. I concetti fon-
damentali di soluzione per tali giochi a pagamenti laterali
sono il nucleo ed il valore Shapley, che presenteremo in
IN
TERVEN
TI
48 j lettera matematica
31
black pellicola (32,1)
seguito. Faremo anche menzione di alcuni importanti
contributi di G. Owen in questo ambito.
n Giochi a pagamenti laterali
Sia N un insieme di individui (chiamati giocatori) che
prendono in considerazione l’idea di cooperare in qual-
che progetto. Supponiamo anche che ogni sottoinsieme S
di N abbia la possibilita di lavorare assieme, formando la
coalizione S ed escludendo i giocatori che non stanno in
S. Supponiamo, ancora, di conoscere il risultato vðSÞ che
possono ottenere (globalmente) i membri della coalizione
S; se decidono di collaborare. Supponiamo, infine, che ad
ogni giocatore sia assegnato un numero che lo contraddi-
stingue e che N, detta la grande coalizione, sia l’insieme
f1; ;ng, dove n rappresenta il numero di elementi di N.
Indicheremo con 2N la famiglia dei 2n sottinsiemi di N.
Ecco la prima fondamentale definizione.
Definizione 2.1 Un gioco a pagamenti laterali,
con insieme di giocatori N, e una funzione:
v : 2N ! R
con la proprieta4 che vð;Þ ¼ 0.
Esempio 2.1 Supponiamo che un suonatore di
piano lavori in un bar, guadagnando 100 Euro a
serata, ed un cantante lavori in un altro bar,
guadagnando 300 Euro. Ricevono una proposta
per andare a lavorare assieme in un ristorante,
per un compenso globale di 700 Euro. Come sud-
dividersi la somma?
Traduciamo il problema in un gioco a due perso-
ne a pagamenti laterali. Diamo il numero 1 al
pianista ed il 2 al cantante. Allora N ¼ f1;2g e
la funzione v e la seguente:
vð;Þ ¼ 0; vðf1gÞ ¼ 100; vðf2gÞ ¼ 300; vðNÞ ¼ 700:
Possibili distribuzioni del guadagno, nell’esempio
precedente, possono essere identificate da vettori
ðx1;x2Þ 2 R2 tali che x1 þ x2 ¼ 700 e dove x1 (x2Þ e quan-
to viene assegnato al primo (secondo) giocatore. Possia-
mo anche supporre x1 � 100, x2 � 300, perche altrimenti
i due non comincerebbero neanche a discutere. Vedremo
che tutte le distribuzioni che soddisfano le precedenti
condizioni formano il cosiddetto nucleo del gioco. Ma che
fare effettivamente? A prima vista spartirsi i proventi a
meta sembra una soluzione molto ragionevole. Ma non
c’e dubbio che essa non tiene nel minimo conto il fatto
che, da solo, il secondo giocatore e in grado di guadagna-
re di piu del primo e anche questo e da tenersi in consi-
derazione. Un’altra divisione ragionevole potrebbe essere
fatta tenendo conto che, lavorando assieme, essi ottengo-
no 300 euro in piu che se lavorassero per conto proprio
(700-100-300) e quindi spartirsi in parti uguali l’extra
guadagno. In tal caso, il vettore risultante sarebbe
(250,450). Questa distribuzione dei guadagni corrisponde
al valore Shapley di questo gioco (vedi Esercizio 2.3).
Possiamo anche osservare che il valore Shapley cade nel
IN
TERVEN
TI
48 j lettera matematica
IN
TERVEN
TI
32
Samarra (Iraq),
minareto a sprirale, secolo IX
Archivio Scala, Firenze
black pellicola (33,1)
mezzo del nucleo, in questo caso il segmento con estremi
(100,600) e (400,300).
Prima di passare ad introdurre il concetto di nucleo, os-
serviamo che questi giochi sono chiamati a pagamenti la-
terali perche ad ogni coalizione viene assegnato un paga-
mento, che poi puo essere suddiviso in ogni maniera pos-
sibile fra i suoi membri. Ci sono giochi – ad esempio, i
giochi di mercato – in cui questo non e possibile ed in
questo caso la definizione di gioco cooperativo sarebe piu
complicata.
n Il nucleo
Supponiamo di avere un gioco come descritto nel para-
grafo precedente. Supponiamo anche che sia proposta
una suddivisione di vðNÞ della forma ðx1; . . . ; xnÞ e che
x1 þ x2 < vðf1;2gÞ. Ricordando che vðf1;2gÞ e quanto i
giocatori 1 e 2 possono ottenere collaborando (ed esclu-
dendo gli altri dalla loro collaborazione) e che ðx1;x2Þ e
quanto verrebbe a loro assegnato nella distribuzione pre-
cedente, c’e da ritenere che la proposta ðx1; . . . ; xnÞ non
sia stabile, nel senso che sara rifiutata dalla coalizione
f1;2g che, ritirandosi dall’accordo, starebbe meglio. Gil-
les nel 1954 ha considerato l’insieme delle proposte
x ¼ ðx1; . . . ;xnÞ che sono stabili, nel senso che:
Xi2S
xi � vðSÞ per ogni S � N :
Tali distribuzioni sono dette il nucleo del gioco v, che vie-
ne indicato con CðvÞ.
Definizione 2.2 Sia v : 2N ! R un gioco a pagamenti la-
terali. Si definisce nucleo del gioco, e si indica con CðvÞ,l’insieme:
CðvÞ ¼ fx 2 Rn :P
i2N xi ¼ vðNÞ;
Pi2S xi � vðSÞ per ogni S � Ng:
Il nucleo di un gioco ha una struttura geometrica partico-
lare. Trattandosi di un insieme limitato, definito da un
numero finito di disequazioni lineari, e un insieme con-
vesso dalla struttura particolare, chiamato politopo (cioe
un insieme che e generato da un numero finito di punti
estremali). Svolgendo l’Esercizio 2.1, possiamo vedere
che il nucleo di un gioco puo essere vuoto oppure ridursi
ad un solo elemento.
Esercizio 2.1 Mostrare che il nucleo del gioco a 3 gioca-
tori:
vð;Þ ¼ vðf1gÞ ¼ vðf2gÞ ¼ vðf3gÞ ¼ vðf1;2gÞ ¼ 0;
vðf1;3gÞ ¼ vðf2;3gÞ ¼ vðNÞ ¼ 1
consiste del vettore ð0;0;1Þ.Analogamente verificare che e vuoto il nucleo del gioco a
3 giocatori:
vð;Þ ¼ vðf1gÞ ¼ vðf2gÞ ¼ vðf3gÞ ¼ 0;
vðf1;3gÞ ¼ vðf2;3gÞ ¼ vðf1;2gÞ ¼ vðNÞ ¼ 1.
Nel primo caso, il nucleo riflette la forza del terzo giocato-
re (che diventa vincente se si coalizza con almeno un al-
tro) mentre 1 e 2, anche mettendosi assieme, non otten-
gono nulla senza 3. Che quindi si prende tutto il bottino!
Il secondo invece rappresenta la tipica situazione in cui 3
giocatori si possono spartire un bottino, se uno di loro
viene votato a maggioranza. Le coalizioni di due giocatori
diventano vincenti; hanno troppo potere rispetto alla
grande coalizione. Il gioco mette in evidenza il concetto di
pagamento laterale. Qualora una coalizione voti un nome,
i suoi componenti possono poi decidere come suddividersi
il bottino. Questo crea il problema. Supponiamo che 1 e 2
si accordino per votare 1, che poi passa la meta del botti-
no al secondo. Il terzo puo reagire proponendo al secondo
di fare coalizione e di passargli poi qualcosa piu di meta
(per convincerlo a non fare l’accordo con 1). A questo
punto, 1 puo allora cercare di convincere 3 a fare un ac-
cordo con lui, per non rimanere tagliato fuori. E evidente
che cosı non si arriva da nessuna parte! Giochi con il nu-
cleo vuoto pongono evidentemente un problema.
Diventa allora una questione interessante cercare di ca-
ratterizzare i giochi che hanno nucleo non vuoto. O. Bon-
dareva [3] e L. Shapley [4] hanno fornito, in maniera in-
dipendente, condizioni necessarie e sufficienti affinche un
gioco abbia nucleo non vuoto. Queste condizioni, sono
dette di gioco bilanciato. L’idea e appunto che un gioco e
bilanciato se le coalizioni intermedie non hanno troppo
potere rispetto alla grande coalizione. Per dimostrare il
loro risultato, essi usano la teoria della dualita per pro-
blemi di programmazione lineare. Quest’ultima ha forti
connessioni con la Teoria dei giochi. In effetti, von Neu-
mann, ispirato dal suo teorema di esistenza del valore
per giochi a somma zero (detto teorema del minimax),
IN
TERVEN
TI
48 j lettera matematica
33
black pellicola (34,1)
formulo il teorema di dualita a Dantzig, che in seguito
sviluppo il celeberrimo algoritmo del simplesso per risol-
vere problemi di programmazione lineare. Aumann di-
mostro come sia possibile provare il teorema di Bondare-
va-Shapley partendo proprio dal teorema di minimax di
von Neumann. Anche G. Owen ha fornito una dimostra-
zione elementare del teorema di minimax, usando l’indu-
zione applicata alla grandezza della matrice del gioco (la
grandezza di una matrice e la somma del numero delle
righe e delle colonne).
Esercizio 2.2 Un gioco a due persone ha nucleo non vuo-
to se e solo se vale la seguente condizione:
vðf1;2gÞ � vðf1gÞ þ vðf2gÞ;
Mostrare che, in un gioco a tre persone, una condizione
necessaria per la non vacuita del nucleo e:
vðf1;2gÞ þ vðf1;3gÞ þ vðf2;3gÞ � 2vðf1;2;3gÞ:
Classi molto interessanti di giochi nascono da problemi
di Ricerca operativa di tipo interattivo, come ad esempio
giochi di flusso, giochi sequenziali e giochi che modelliz-
zano processi produttivi lineari. Questi giochi hanno nu-
cleo non vuoto. Vediamo – come esempio – gli ultimi cita-
ti, che sono stati introdotti da G. Owen [5].
Ci sono un certo numero di risorse, diciamo r1; . . . ; rq,
che servono per produrre i beni p1; . . . ;pm. E assegnata
una matrice A di dimensioni m� q, detta matrice della
tecnologia. Il suo significato e il seguente: fissato il pro-
dotto pk, per produrne una unita, e necessario disporre
di ak1r1 þ akqrq. Il guadagno ottenuto dalla produzione di
un’ unita di prodotto pk e ck. Nel modello sono poi pre-
senti n persone che possiedono dei panieri bi 2 Rqþ,
i ¼ 1; . . . ;n, delle risorse5. Siano dunque dati
A; b1; . . . ; bn; c. Introduciamo il gioco a pagamenti laterali
definito dalla funzione v come segue6:
vðSÞ ¼ maxfhx; ci : x � 0;ATx �P
i2S big;
per ogni S 2 2N n f;g. Qui x rappresenta un piano produt-
tivo e vðSÞ e il massimo che la coalizione puo ottenere,
con l’ovvio vincolo che i piani produttivi considerati devo-
no essere praticabili, mettendo assieme le risorse (condi-
zione: ATx �P
i2S bi). Nel lavoro citato, Owen descrive in
modo semplice come trovare elementi del nucleo, consi-
derando il problema duale corrispondente, relativo alla
grande coalizione. Le soluzioni cosı trovate formano un
insieme che oggi viene chiamato insieme di Owen (vedi
anche [6]).
n Il valore Shapley
Uno dei problemi aperti della Teoria dei Giochi nei primi
anni ’50, formulato da H. Kuhn e A. Tucker, era il se-
guente: come valutare il valore (la forza) di un giocatore
in un gioco cooperativo? Una risposta molto interessante
a questo questione fu data da L. Shapley nel 1953, quan-
do nacque il valore Shapley.
Definizione 2.3 Il valore Shapley �ðvÞ del gioco v ad n
persone e il vettore di Rn tale che, per ogni i, la sua
coordinata i-esima e data da:
�iðvÞ ¼XS:i2S
ðjSj � 1Þ!ðn� jSjÞ!n!
ðvðSÞ � V ðS n figÞÞ:
Nella formula precedente, la notazione jSj vuole indicare
il numero di elementi dell’insieme S. Lasciamo un attimo
perdere il poco attraente fattore ðjSj�1Þ!ðn�jSjÞ!n! che peraltro
ha un interessante interpretazione dal punto di vista pro-
babilistico. L’idea che sta sotto la valutazione della forza
di i nell’indice di Shapley e data dal termine
vðSÞ � vðS n figÞ, che chiaramente rappresenta il contri-
buto marginale che il giocatore i porta cooperando con gli
altri elementi di S. Questi, senza di lui, sarebbero appunto
capaci di ottenere vðS n figÞ. Shapley diede tra l’altro un
interessante caratterizzazione assiomatica del suo valore.
Esercizio 2.3 Sia v un gioco a due persone e sia:
r ¼ vðNÞ � vðf1gÞ � vðf2gÞ:
Mostrare che:
�ðvÞ ¼ ðvðf1gÞ þ ðr=2Þ; vðf2gÞ þ ðr=2ÞÞ:
Calcolare il valore Shapley per il gioco a tre persone tale
che vðSÞ ¼ jSj2 per ogni S (Ci aspettiamo che il risultato
non sorprenda nessuno).
Oggigiorno esistono varie altre caratterizzazioni assioma-
tiche del valore Shapley. Ci sono anche altre formule che
individuano il valore Shapley, fra cui una dovuta a J.
Harsany (premio Nobel, con Nash, nel 1994) ed un’altra
ad Owen. Il valore Shapley e stato usato in tantissime si-
IN
TERVEN
TI
48 j lettera matematica
IN
TERVEN
TI
34
black pellicola (35,1)
tuazioni, ad esempio per misurare la forza dei partiti in
un Parlamento o di un grande azionista, rispetto ai picco-
li, in una societa per azioni. Alcune di queste applicazioni
si possono trovare in [7].
Concludiamo ricordando che una parte del Festival della
Teoria dei giochi che si tiene a Stony Brook (USA) nel lu-
glio 2003, e dedicata alla celebrazione dei 50 anni del-
l’indice di Shapley e agli 80 del suo inventore.
Speriamo infine che qualche lettore ne voglia sapere di
piu. E allora citiamo per lui i libri di Owen [5, 8, 9], di
Tijs [10], di Cardellicchio [11] e di Lucchetti [12].
Note
1 La diseguaglianza che coinvolge sup ed inf in
ordine scambiato, puo tranquillamente disgu-
stare chi guarda alla Matematica come serie di
simboli un po’ esoterici. Le cose pero cambiano
ogni volta che diamo ad una formula un inter-
pretazione ragionevole. In questo caso, vista al-
la luce della TG, essa indica che in generale e
vs � vp. Questo e ovvio! Quel che il primo e co-
munque in grado di garantirsi non puo eviden-
temente essere piu del massimo di quel che il
secondo sa di dover pagare. Se non fosse cosı,
chi ci metterebbe la parte mancante?2 Abbiamo messo Gabriella a scegliere le righe: la
prima rappresenta la scelta di andare a teatro;
Michele invece sceglie una colonna e quella di
sinistra rappresenta la scelta di andare a teatro.3 Non abbiamo definito il concetto di razionalita.
Potremmo assumere che e razionale il giocatore
che cerca un equilibrio di Nash. Se questo puo
sembrare troppo autoreferenziale, potremmo
assumere – come succede in questo esempio –
che e razionale chi rifiuta la scelta di una stra-
tegia, se ne ha a disposizione un’altra che gli
procura un guadagno maggiore, qualunque sia-
no le scelte fatte dall’altro giocatore (vedi l’arti-
colo precedente).4 ; indica l’insieme vuoto.5 cioe vettori a q dimensioni le cui componenti
sono tutte non negative.6 h�; �i indica l’usuale prodotto scalare in Rm, dise-
guaglianze fra vettori come ad esempio x � 0 si
intendono componenente per componente, AT
indica la matrice trasposta di A.
IN
TERVEN
TI
48 j lettera matematica
35
Bibliografia
[1] Aumann, R.J. e Maschler, M., Game Theoretic Analysis of a Bankruptcy Problem from the Talmud, Journal of
Economic Theory, 36 (1985), 195-213.
[2] Von Neumann, J. e Morgenstern, O., Theory of Games and economic Behaviour, Princeton University Press,
Princeton 1944.
[3] Bondareva, O.N., Some applications of linear programming to the theory of cooperative games, Problemy
Kibernetiki, 10 (1963), 119-139.
[4] Shapley, L.S., On balanced sets and cores, Naval Research Logistic Quarterly, 14 (1967), 453-460.
[5] Owen, G., On the core of linear production games, Mathematical Programming, 9 (1975), 358-370.
[6] Gellekom, J. von, Potters, J. Rayinerse, H, and Tijs, S.H., Characterization of the Owen set of linear production
games, Games and Economic Behavior, 32 (2000), 139-156.
[7] Moretti, S. and Patrone F., Teoria dei giochi ed indici di potere, IRRE Liguria, (2002), 69-108.
[8] Owen, G., Multilinear extensions of games, Management Science, 18 (1972), 64-79.
[9] Owen, G., Game theory, Academic Press, New York 1995
[10] Tijs S.H., Introduction to Game Theory, Hindustan Book Agency, New Dehli, 2003.
[11] Cardellicchio, C., Giocatori non biologici in azione: il computer e la teoria dei giochi, Editrice Proto, Bari, 2002.
[12] Lucchetti R., Di duelli, scacchi e dilemmi, Bruno Mondadori Editore, Milano, 2001.
[13] Shapley, L.S., A value for N-person game, in Contributions to the theory of games II, H.W. Kuhn and A.W. Tuc-
ker (eds.), Princeton University Press, Princeton, 1953