Teoria 2c (giochi cooperativi): TU-games, valore Shapley

Messaggioda Fioravante Patrone » 19/03/2008, 22:30

Nel post "teoria 1c" abbiamo visto come è definito il nucleo di un TU-game.

E' un importante concetto di soluzione, ma ha alcuni difetti: può essere vuoto e, qualora vuoto non sia, può essere un insieme che contiene troppe imputazioni.

Si può individuare un qualche altro concetto che non manifesti questi due difetti, potendo al tempo stesso essere considerato una soluzione ragionevole?

Un possibile "piano di attacco" ci porta a considerare i "contributi marginali" dei giocatori. Cosa si intende per contributo marginale? Una proposta ragionevole è considerare $v(S \cup {i}) - v(S)$ quale contributo marginale del giocatore $i$ alla coalizione $S$. L'uso di questo termine suggestivo utilizzato è appropriato: il giocatore $i$ è proprio come la "terra marginale" che si aggiunge $S$, quelle già coltivate, nella famosa analisi della rendita da parte di Ricardo. Comunque, ad di là della terminologia, sembra ragionevole correlare la parte del bottino che "tocca" al giocatore $i$ con i suoi contributi marginali alle varie coalizioni. Anzi, si potrebbe molto semplicemente assegnare ad ogni giocatore la somma dei suoi contributi marginale alle varie coalizioni. E' facile immaginare che possa venire un numero troppo grande (come se stessimo promettendo a tutti la Luna), ma a questo si può porre facilmente rimedio: basta fare una suddivisione di $v(N)$ (il "bottino") che sia proporzionale ai contributi marginali di ogni giocatore. Tra l'altro, questo lo si può fare in un modo molto semplice, ottenendo anche una formula non troppo maneggevole ma abbastanza elegante ($n$ è la cardinalità di $N$, ovvero il numero di elementi dell'insieme finito $N$):

$\Phi_i(v) = \frac{1}{n!}\sum_{\pi} [ v( S_{i,\pi} \cap {i} ) - v(S_{i,\pi}) ]$

Qui $\pi$ indica una generica permutazione. Data una permutazione $\pi$, immaginiamo che i giocatori "arrivino uno ad uno" secondo l'ordinamento creato dalla permutazione. Ad esempio, se $N = {1,2,3}$ e $\pi$ è la permutazione $231$, immaginiamo che prima "arrivi" $2$, poi $3$ ed infine $1$. Ebbene, $S_{i,\pi}$ sta ad indicare il gruppo di giocatori presenti, secondo lo "ordine d'arrivo" indotto da $\pi$, prima che tocchi ad $i$. Nel nostro esempio, $S_{1, \pi} = {2,3}$.

Ovviamente $n!$ è il numero di permutazioni che possiamo fare di $N$. Quindi la formula sopra ci dà il contributo marginale medio del giocatore $i$ rispetto a tutte le possibili permutazioni di $N$.

E' facile verificare che $\sum_{i \in N} \Phi_i (v)= v(N)$ (somme "telescopiche"). Si verifica anche facilmente che $\Phi_i (v) \ge v({i})$, se il gioco è superadditivo. Quindi, la formula ci dà una imputazione, se il gioco $v$ è superadditivo.

Il vettore $(\Phi_i (v) )_{i \in N}$ è detto valore Shapley del gioco $v$.

Vedremo in seguito quali interessanti proprietà abbia questa soluzione.
Per ora, mi limito a considerare cosa succede nel gioco di maggioranza, che avevamo considerato a proposito del nucleo. Come tutto fa prevedere, data la simmetria dell'approccio, il valore Shapley per il gioco di maggioranza assegna $1/3$ a ciascun giocatore (i calcoli sono lasciati al lettore :twisted: )
Avatar utente
Fioravante Patrone
Cannot live without
Cannot live without
 
Messaggio: 3073 di 10811
Iscritto il: 09/06/2006, 19:18
Località: Temporaneamente a Novi Ligure ;-)

Torna a Matematica per l'Economia e per le Scienze Naturali

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite