Gioco cooperativo

In teoria dei giochi si distingue tra giochi cooperativi e giochi non cooperativi.

Nei giochi cooperativi esiste la possibilità che i giocatori stipulino degli accordi vincolanti, mentre questo non accade nei giochi non cooperativi.

Introduzione

I giochi a $n$ giocatori hanno una natura diversa rispetto ai giochi a somma nulla (a due giocatori), nei quali gli interessi dei due giocatori sono in opposizione tra loro, in conflitto diretto. Nei giochi a tre o più giocatori può comparire la cooperazione. La decisione (strategia) di un partecipante può essere svantaggiosa per entrambi gli altri giocatori, oppure vantaggiosa per uno e svantaggiosa per l’altro: la possibilità di un "parallelismo" nelle decisioni tra i giocatori conduce alla formazione di coalizioni. La teoria dei giochi cooperativi esamina i giochi in cui i giocatori si accordano per formare coalizioni, ossia per formare uno dei possibili sottoinsiemi costituito da $m$ degli $n$ partecipanti al gioco.

Le coalizioni

Il numero di coalizioni possibili costituibili da un insieme $R=\{1,2,\cdots ,n\}$ di $n$ giocatori è pari a $2^{n}$. Ai fini pratici una coalizione $G\subseteq R$ si considera come un singolo giocatore: i restanti giocatori $R-G$ si riuniranno in un'altra coalizione che costituirà la così detta coalizione opposta. Sotto questo punto di vista, assegnata una qualsiasi coalizione $G$, nel gioco si troveranno in lotta due colazioni $G$ e $R-G$ ed il gioco potrà essere inteso come un gioco antagonista tra due “persone’’. Quando $G=R$ il gioco di riduce al un gioco di una persona singola dove le decisioni possibili della coalizione avversa $R-G=\{\varnothing \}$ si riducono alla sola ed unica strategia: quella di non fare nulla. Stesso discorso vale qualora si avesse $G=\{\varnothing \}$

Assegnata la coalizione $G$, con $A$, la relativa matrice dei pagamenti e costituita la contro-coalizione $G^{c}=R-G$, con matrice dei pagamenti $B$, il gioco tra i due può dunque essere ricondotto a

• un gioco a somma costante e dunque a somma nulla allorquando $A+B=0$ ovvero $B=-A$,

• un gioco a somma non costante, cioè a doppia matrice $[A,B]$.

Il valore di una coalizione $v(G)$ viene misurato tramite la funzione caratteristica, cioè per mezzo di una funzione $v$ a valori reali definita sull’insieme di tutti i sottoinsiemi $G\subseteq R$ tale che

$v(G)$ = valore del gioco per la coalizione $G$

Si indichi con ${\mathbf {x} }$ e ${\mathbf {y} }$ le strategie miste rispettivamente della coalizione $G$ e della coalizione opposta $G^{c}$. In sostanza $v(G)$ è la vincita minima che la coalizione $G$ si assicura mediante la scelta di un’appropriata strategia maximin

$\max _{\mathbf {x} }\min _{j}{\mathbf {x} }\cdot {\mathbf {a} }^{j}=v(G)$

allorquando la coalizione avversa $R-G$ fa di tutto per impedirgli di ottenere una vincita superiore a $v(R-G)$ minimizzando le proprie perdite mediante la scelta di un’opportuna strategia minimax:

$\min _{\mathbf {y} }\max _{i}{\mathbf {a} }_{i}\cdot {\mathbf {y} }=v(R-G)$

In un gioco a somma non costante il teorema del minimax non sussiste: massimizzare le proprie vincite non è la stessa cosa di minimizzare le vincite dell’avversario in quanto un giocatore dovrebbe ignorare le vincite che potrebbe conseguire (guardando alla matrice $B$) per concentrare tutti i suoi sforzi nel recare il maggior danno al giocatore avversario (guardando cioè alla matrice $A$). Premesso ciò, resta inteso che anche nel caso di giochi a somma non nulla, la liquidazione del gioco può essere intesa come la somma corrispondente al valore di un gioco a somma zero una volta che si ipotizzi che la contro-coalizione $G^{c}$ agisca minimizzando la vincita della coalizione $G$ in riferimento alla matrice $A$, piuttosto che massimizzando il proprio guadagno in riferimento alla matrice $B$.

Le imputazioni

La teoria dei giochi cooperativi cerca di rispondere ad una domanda fondamentale: come la vincita o la perdita conseguita da una coalizione venga ripartita, allocata tra i suoi membri.

Le allocazioni possono essere concordate attraverso negoziazioni anteriori alla formazione della coalizione stessa. In merito all’allocazione del risultato del gioco, è ragionevole pensare che nessun membro sarebbe soddisfatto se ricevesse meno di quanto otterrebbe agendo da solo, ossia non aderendo alla coalizione. Indicato con ${\mathbf {a} }=(a_{1},a_{2},\ldots ,a_{n})$ il vettore ad n-componenti indicante l’allocazione delle vincite all’interno di una coalizione generica $G$ dove $a_{j}$ indica l’ammontare che riceverà il giocatore $j$ affiliato alla coalizione $G$, von Neumann e Morgenstern (Ref.) caratterizzano il vettore ${\mathbf {a} }$ con le due seguenti proprietà (vincoli):

1.$a_{j}\geq v(\{j\})$ per ogni $j=1,2,\ldots ,n$

2.$\sum _{j=1}^{n}a_{j}=v(R)$

La proprietà 1. (razionalità individuale) afferma che ogni membro riceve almeno tanto quanto potrebbe ottenere da solo $v(\{j\})$, la proprietà 2. (efficienza) afferma che la vincita che i giocatori possono raggiungere cooperando tutti insieme è $v(R)$: la vincita della grande-coalizione $R$ viene interamente suddivisa tra tutti i giocatori. L'insieme di tutti i vettori che soddisfano le due condizioni sopra introdotte verrà denotato con $A$ ed i suoi elementi verranno chiamati imputazioni. L'insieme $A$ può essere pensato come un sottoinsieme di uno spazio vettoriale euclideo di dimensione pari a $n$ . Il concetto di imputazione di per sé non stabilisce quali imputazioni incentivino i propri membri ad abbandonare la grande-coalizione $R$ per costituire coalizioni più piccole $G\subset R$, in particolare quando la funzione caratteristica $v$ è super-additiva.

Gioco non essenziale

Diversamente, se il gioco presenta una funzione caratteristica $v$ additiva, $v(G)+v(R-G)=v(R)$, come ad esempio nel caso dei giochi a somma costante o nulla, si dimostra che

$\sum _{j=1}^{n}v(\{j\})=v(R)$

Per i giocatori scegliere di belligerare tutti contro tutti oppure optare di schierarsi con una coalizione è una scelta fondata sulla convenienza, mentre scegliere di cooperare tutti insieme in $R$ condividendo le proprie strategie appare essere una scelta non dettata essenzialmente da una ratio di guadagno.

Gioco essenziale

Qualsiasi funzione caratteristica $v$ super-additiva ammette almeno un’imputazione ${\mathbf {a} }$.

Nella definizione di super-additività: $v(G_{1})+\ldots +v(G_{k})\leq v(G_{1}\cup \ldots \cup G_{k})$, per ogni $G_{i}\cap G_{j}=\varnothing$ con $i\neq j$ e $G_{1},\ldots ,G_{k}\subseteq R$, è sufficiente considerare $k=n$ e scegliere $G_{j}=\{j\}$ per ogni $j=1,\ldots ,n$ per avere

$\sum _{j=1}^{n}v(\{j\})\leq v(R)$

Definendo per ciascun $j=1,\ldots ,n$

$a_{j}:=v(\{j\})+{{v(R)-\sum _{j=1}^{n}v(\{j\})} \over {n}}$

si può vedere facilmente che ${\mathbf {a} }=(a_{1},a_{2},\ldots ,a_{n})$ è un’imputazione, ossia che $a_{j}\geq v(\{j\})$ per ogni $j=1,\ldots ,n$ e che $\sum _{j=1}^{n}a_{j}=v(R)$

La relazione di dominanza tra le imputazioni

Il concetto di imputazione appare troppo ampio per consentire di rispondere deterministicamente alla domanda iniziale: come la vincita viene distribuita tra i propri membri. Ogni qualvolta infatti dovesse risultare per una generica coalizione $G$ che

$\sum _{j\in G}a_{j}<v(G)$

allora ai membri di $G$ si renderebbe disponibile la quota eccedente $v(G)$ - $\sum _{j\in G}a_{j}$. Tale ammontare potrebbe essere ripartito tra i membri di $G$ che si troverebbero così dinnanzi ad una seconda imputazione ${\mathbf {b} }=(b_{1},b_{2},\ldots ,b_{n})$ più vantaggiosa dell’imputazione precedente ${\mathbf {a} }=(a_{1},a_{2},\ldots ,a_{n})$. In sintesi ${\mathbf {b} }$ è preferibile ad ${\mathbf {a} }$.

La nozione di dominanza tra imputazioni viene espressa in termini rigorosi dalla seguente definizione: in riferimento alla medesima funzione caratteristica $v$ e rispetto al sottoinsieme $G$ di $R$, un’imputazione ${\mathbf {b} }$ domina l’imputazione ${\mathbf {a} }$ , in simboli ${\mathbf {b} }\succ {\mathbf {a} }$, se:

1. $G\neq \{\varnothing \}$

2. $b_{j}>a_{j}$ per ciascun $j\in G$

3. $\sum _{j\in G}b_{j}\leq v(G)$

Rimane pertanto da verificare se effettivamente ogni sottoinsieme $G\subseteq R$ riceve almeno tanto quanto garantito dalla cooperazione, formalmente se $\sum _{j\in G}a_{j}\geq v(G)$ per qualsiasi scelta di $G$.

Enunciato di von Neumann

Data un’imputazione ${\mathbf {a} }=(a_{1},a_{2},\ldots ,a_{n})$ si ha che $\sum _{j\in G}a_{j}\geq v(G)$ se, e soltanto se, ${\mathbf {a} }$ non è dominata da alcuna altra imputazione ${\mathbf {b} }$. Una formulazione alternativa all’enunciato sopra riportato è la seguente: data un’imputazione ${\mathbf {a} }=(a_{1},a_{2},\ldots ,a_{n})$ per la funzione caratteristica $v$, esiste un sottoinsieme qualsiasi $G$ di $R$ tale che $\sum _{j\in G}a_{j}<v(G)$ se, e soltanto se, esiste un’imputazione ${\mathbf {b} }$ che domina ${\mathbf {a} }$ rispetto a $G$, ${\mathbf {b} }\succ {\mathbf {a} }$.

La formazione delle sotto-coalizioni

Vediamo ora come i membri della grande-coalizione $R$ costituiscano coalizioni più piccole $F\subset R$ rinunciando a cooperare in $R$ nel caso in cui la funzione caratteristica $v$ sia super-additiva.

L'esistenza di un insieme $F\subset R$ per cui si abbia $\sum _{j\in F}a_{j}<v(F)$ ha come conseguenza il fatto che alcuni membri di $R$, individuati come elementi di $F$, rilevano che l'imputazione ${\mathbf {a} }$ è dominata da un’imputazione ${\mathbf {b} }$. Questi giocatori si distaccheranno dalla grande-coalizione per costituire la coalizione più piccola $F$, i giocatori rimasti in $R$ simultaneamente rilevano che ${\mathbf {b} }\succ {\mathbf {a} }$ e formeranno la coalizione $R-F$.

Si consideri, ad esempio, l'imputazione

$a_{j}:=v(\{j\})+{{v(R)-\sum _{j=1}^{n}v(\{j\})} \over {n}}$ per $j=1,\ldots ,n$

ipotizzato che $\sum _{j\in F}a_{j}<v(F)$, si prenda $0<\delta =v(F)-\sum _{j\in F}a_{j}$0 < e si consideri $b_{j}=a_{j}+\delta /|F|$ per ciascun $j\in F$.

L'allocazione che spetta alla coalizione antagonista risulta quindi essere $b_{j}=a_{j}+\epsilon$ per $j=1,\ldots ,|F^{c}|$ dove $\epsilon =v(\{j\})+{{v(R)-v(F)-\sum _{j\in F^{c}}v(\{j\})} \over {|F^{c}|}}\geq 0$

Si constata immediatamente che il vettore ${\mathbf {b} }=(b_{1},b_{2},\ldots ,b_{n})$ è un'imputazione: infatti $b_{j}\geq v(\{j\})$ per ogni $j=1,\ldots ,n$ e $\sum _{j=1}^{n}b_{j}=v(R)$ poiché

$\sum _{j=1}^{n}b_{j}=\sum _{j\in F}b_{j}+\sum _{j\in F^{c}}b_{j}=\sum _{j\in F}a_{j}+|F|\cdot \delta +\sum _{j\in F^{c}}v(\{j\})+|F^{c}|\cdot \epsilon =v(R)$

Infine, poiché risulta $b_{j}>a_{j}$ per ciascun $j\in R$ $\sum _{j\in F}b_{j}\leq v(F)$ si può concludere che ${\mathbf {b} }\succ {\mathbf {a} }$.

Soluzioni nel senso di Von Neumann-Morgenstern

Tramite il concetto di imputazione e di dominanza Von Neumann e Morgenstern definirono la soluzione di un gioco ad n-persone come quell’insieme $L$ di imputazioni che gode delle due seguenti proprietà:

1. per ciascuna imputazione $(a_{1},a_{2},\ldots ,a_{n})\not \in L$ esiste un’imputazione ${\mathbf {b} }=(b_{1},b_{2},\ldots ,b_{n})\in L$ che domina $(a_{1},a_{2},\ldots ,a_{n})$, ${\mathbf {b} }\succ {\mathbf {a} }$;

2. nessuna coppia di imputazioni di $L$ domina l’una sull’altra.

In letteratura ci si riferisce alle due proprietà come a condizioni di stabilità per l'insieme $L$ delle soluzioni: in sostanza le imputazioni che costituiscono equilibri stabili per i giocatori sono soluzioni del gioco. Il concetto di soluzione nel senso di von Neumann non cattura un'unica e ben specifica imputazione del gioco: in generale l'insieme $L$ delle soluzioni possibili è costituito da numerose imputazioni.

La situazione in cui la somma dell’ammontare ricevuto da ogni membro di $G$ è non inferiore alla liquidazione che la coalizione riceve per sé condusse ad approfondire il concetto di nucleo, ossia l’insieme delle imputazioni non dominate.

Il nucleo del gioco

Le imputazioni soddisfacenti al vincolo $\sum _{j\in G}a_{j}\geq v(G)$ si dicono costituire il nucleo (core) dell’insieme delle imputazioni $A$:

$U=\{{\mathbf {a} }\in A:\sum _{j\in G}a_{j}\geq v(G)\forall G\subseteq R\}$

Il nucleo per il momento non sembra essere ancora in grado di "catturare" la o le soluzioni dei giochi cooperativi, piuttosto costituirebbe un metodo per scartare le imputazioni che generebbero conflitti all’interno della grande coalizione $R$.

Un nucleo non vuoto indica semplicemente quali imputazioni non si devono scegliere: quelle che non risiedono nel nucleo. In generale può tuttavia accadere che il nucleo sia vuoto $U=\{\varnothing \}$ (come ad esempio nei giochi a somma costante) oppure che le imputazioni del nucleo siano ancora in numero elevato.

Il nucleo è il concetto chiave attraverso il quale analizzare i giochi cooperativi: giochi in cui i giocatori non hanno motivo di separarsi in coalizioni antagoniste, ma la strategia ottimale è cooperare tutti insieme. La matematica sovietica Olga Bondareva fornì condizioni necessarie e sufficienti affinché il nucleo di un gioco cooperativo sia non vuoto.

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file su Gioco cooperativo

Collegamenti esterni

• (EN) cooperative game, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.