# 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.