Teoria 1c (giochi cooperativi): TU-games, nucleo
Come fatto nel post introduttivo, mi muovo nel contesto del modelo più semplice: TU-games.
Dal post introduttivo richiamo:
Un TU-game è $(N,v)$. Dove $N$ è un insieme finito e $v: 2^N -> RR$, con la condizione che $v(\emptyset) = 0$.
Un elemento di $RR^N$, cioè $(x_i)_(i \in N)$, viene detto allocazione.
Una allocazione che soddisfi le condizioni:
- C1 - $\sum_(i \in N) x_i = v(N)$
- C2 - $x_i \ge v({i})$
viene detta imputazione.
Nulla vieta di estendere la condizione di razionalità individuale, richiedendo anche che sia soddisfatta una condizione di razionalità "intermedia", ovvero per tutte le coalizioni:
- CS - $x(S) \ge v(S)$ per ogni $S \sube N$
Si osservi la notazione $x(S)$, che sta ad indicare: $\sum_{i \in S} x_i$, essendo $x$ una allocazione. E' d'uso frequente ed anche di un certo "significato", come vedremo quando ci occuperemo del "valore Shapley".
Diremo che una allocazione $x$ sta nel nucleo del gioco $(N,v)$ se soddisfa le condizioni C1 e CS.
Il nucleo di un gioco è ovviamente un poliedro di $RR^N$, essendo definito da una famiglia finita di disequazioni lineari. E' anche chiuso, visto che le disuguaglianze sono deboli. Ed è anche limitato (da fare per esercizio
). Insomma, è un politopo.
Peccato che il nucleo possa essere vuoto...
Basta prendere il gioco: $N = {1,2}$; $v({1}) = v({2}) = 1$, $v({1,2}) = 0$, già usato nel post "0". D'altronde, ci sono giochi senza imputazioni (come questo) ed essi hanno, a maggior ragione, nucleo vuoto.
Un po' più sorprendente è che ci siano giochi superadditivi con nucleo vuoto. L'esempio classico in materia è il seguente.
Esempio (gioco di maggioranza)
$N = {1,2,3}$;
$v({1}) = v({2}) = v({3}) = 0$;
$v({1,2}) = v({1,3}) = v({2,3}) = 1$;
$v({1,2,3}) = 1$.
Per stare nel nucleo, una allocazione $x = (x_1,x_2,x_3)$ dovrebbe soddisfare le seguenti tre condizioni:
$x_1 + x_2 \ge 1$
$x_1 + x_3 \ge 1$
$x_2 + x_3 \ge 1$
Sommando membro a membro otteniamo:
$2(x_1 + x_2 + x_3) \ge 3$
Ma $x_1 + x_2 + x_3 = 1$, e pare che non sia vero che $2 \ge 3$.
Dal post introduttivo richiamo:
Un TU-game è $(N,v)$. Dove $N$ è un insieme finito e $v: 2^N -> RR$, con la condizione che $v(\emptyset) = 0$.
Un elemento di $RR^N$, cioè $(x_i)_(i \in N)$, viene detto allocazione.
Una allocazione che soddisfi le condizioni:
- C1 - $\sum_(i \in N) x_i = v(N)$
- C2 - $x_i \ge v({i})$
viene detta imputazione.
Nulla vieta di estendere la condizione di razionalità individuale, richiedendo anche che sia soddisfatta una condizione di razionalità "intermedia", ovvero per tutte le coalizioni:
- CS - $x(S) \ge v(S)$ per ogni $S \sube N$
Si osservi la notazione $x(S)$, che sta ad indicare: $\sum_{i \in S} x_i$, essendo $x$ una allocazione. E' d'uso frequente ed anche di un certo "significato", come vedremo quando ci occuperemo del "valore Shapley".
Diremo che una allocazione $x$ sta nel nucleo del gioco $(N,v)$ se soddisfa le condizioni C1 e CS.
Il nucleo di un gioco è ovviamente un poliedro di $RR^N$, essendo definito da una famiglia finita di disequazioni lineari. E' anche chiuso, visto che le disuguaglianze sono deboli. Ed è anche limitato (da fare per esercizio
). Insomma, è un politopo.Peccato che il nucleo possa essere vuoto...
Basta prendere il gioco: $N = {1,2}$; $v({1}) = v({2}) = 1$, $v({1,2}) = 0$, già usato nel post "0". D'altronde, ci sono giochi senza imputazioni (come questo) ed essi hanno, a maggior ragione, nucleo vuoto.
Un po' più sorprendente è che ci siano giochi superadditivi con nucleo vuoto. L'esempio classico in materia è il seguente.
Esempio (gioco di maggioranza)
$N = {1,2,3}$;
$v({1}) = v({2}) = v({3}) = 0$;
$v({1,2}) = v({1,3}) = v({2,3}) = 1$;
$v({1,2,3}) = 1$.
Per stare nel nucleo, una allocazione $x = (x_1,x_2,x_3)$ dovrebbe soddisfare le seguenti tre condizioni:
$x_1 + x_2 \ge 1$
$x_1 + x_3 \ge 1$
$x_2 + x_3 \ge 1$
Sommando membro a membro otteniamo:
$2(x_1 + x_2 + x_3) \ge 3$
Ma $x_1 + x_2 + x_3 = 1$, e pare che non sia vero che $2 \ge 3$.
Risposte
Salve, sono molto interessato all'argomento. Potreste darmi un po di informazioni per quanto riguarda il "nucleolo" di un gioco. La ringrazio
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo