Teoria dei giochi - Teorema di Bondareva-Shapley
Salve, avrei un dubbio riguardante la dimostrazione del teorema di Bondareva-Shapley (scusate se ho sbagliato sezione ma questa mi sembrava la più appropriata).
Per definizione, un'imputazione è un vettore $\alpha \in \R^n $ tale che
(1) $ \alpha_i \le v(i) $ $\forall i \in N $
(2) $ \sum_{i \in N} \alpha_i=v(N) $
dove N è la coalizione con tutti i giocatori.
Possiamo inoltre provare che un'imputazione appartiene al nucleo se e solo se
(3) $ \sum_{i \in N} \alpha_i \ge v(S) $ $ \forall S \ne N$
Ora, la dimostrazione del teorema di Bondareva-Shapley inizia notando che il nucleo non è vuoto se il risultato del problema di ottimizzazione
$ \min_\alpha \sum_{i \in N} \alpha_i $
$ s.t. (3) $
è minore o uguale a $v(N)$.
La mia domanda è: se, per ogni imputazione (2) deve essere verificata (per definizione), com'è possibile che il risultato del problema di ottimizzazione sia diverso da $v(N)$?
Scusate se la domanda è banale ma sto studiando queste cose per la prima volta.
Per definizione, un'imputazione è un vettore $\alpha \in \R^n $ tale che
(1) $ \alpha_i \le v(i) $ $\forall i \in N $
(2) $ \sum_{i \in N} \alpha_i=v(N) $
dove N è la coalizione con tutti i giocatori.
Possiamo inoltre provare che un'imputazione appartiene al nucleo se e solo se
(3) $ \sum_{i \in N} \alpha_i \ge v(S) $ $ \forall S \ne N$
Ora, la dimostrazione del teorema di Bondareva-Shapley inizia notando che il nucleo non è vuoto se il risultato del problema di ottimizzazione
$ \min_\alpha \sum_{i \in N} \alpha_i $
$ s.t. (3) $
è minore o uguale a $v(N)$.
La mia domanda è: se, per ogni imputazione (2) deve essere verificata (per definizione), com'è possibile che il risultato del problema di ottimizzazione sia diverso da $v(N)$?
Scusate se la domanda è banale ma sto studiando queste cose per la prima volta.
Risposte
In realtà nella 3° condizione che hai scritto c'è anche v(n) ed è per questo che puoi riscriverlo anche sotto...questo ti serve per arrivare al fatto che puoi valutare l'esistenza del nucleo osservando soltanto le bilanciate (e in particolare solo le bilanciate minimali), o meglio...il succo è che la somma del valore delle coalizioni moltiplicate ciascuna per un coefficiente minore di uno non supera comunque il valore della grande coalizione..
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo