Valor de Shapley

Archiu:Lloyd Shapley 2 2012.jpg

Lloyd Shapley en 2012

En la teoria de jocs, el valor de Shapley, nomenat en honor de Lloyd Shapley, qui ho va introduir en 1953, és un método de distribució de riquees en la teoria de jocs cooperatius.^[1]^[2] Per a cada joc cooperatiu s'assigna un únic repartiment (entre els jugadors) del benefici total generat per la coalició de tots els jugadors. El valor de Shapley es caracterisa per una colecció de propietats desijables o axioma que es descriuen a continuació. Hart (1989) oferix un anàlisis del tema.^[3]^[4]

La configuració és com seguix: una coalició de jugadors coopera, i obté un cert guany general de la cooperació. Ya que alguns jugadors poden contribuir més a la coalició que uns atres, o poden posseir diferent poder de negociació (per eixemple, amenaçant en destruir tot l'excedent), ¿quin repartiment final dels beneficis de la cooperació entre els jugadors devem esperar que sorgixquen en qualsevol joc en particular? O expressat d'una atra manera: ¿quina importància té cada jugador per a la cooperació global, i qué recompensa pugues ell o ella raonablement esperar? El valor de Shapley oferix una possible resposta a esta pregunta.

Definició formal

Per a formalisar esta situació, utilisem la noció d'un joc de coalició: comencem en un grup N (de n jugadors) i una funció $v : 2^{N} \to ℝ$ en $v (\emptyset) = 0$ , a on $\emptyset$ denota el conjunt buit. La funció $v$ que assigna subconjunts d'actors reals es diu funció característica.

La funció $v$ té el següent significat: si S és una coalició de jugadors, llavors v(S), cridat el valor de la coalició $S$ , descriu la suma total dels pagaments als membres de S que es pot obtindre per dita cooperació.

El valor de Shapley és una manera de distribuir els guanys totals als jugadors, suponent que tots colaboren formant una gran coalició. És una distribució "justa" en el sentit de que és l'única distribució en certes propietats desijables que s'enumeren a continuació. D'acort en el valor de Shapley, la cantitat que el jugador i obté durant un joc de coalició $(v, N)$ és:

ϕ_{i} (v) = \sum_{S \subseteq N ∖ {i}} \frac{| S |! (n - | S | - 1)!}{n!} (v (S \cup {i}) - v (S))

A on n és el número total de jugadors i la suma s'estén sobre tots els subconjunts de N que no conté el jugador i. La fòrmula es pot interpretar de la següent manera: imaginar que la coalició està formant un actor al mateix temps, en cada actor exigint la seua contribució v (S ∪ {i}) - v (S) com una compensació justa, i després per a cada actor prendre el promig d'esta contribució sobre les diferents possibles permutació en la que es pot formar la coalició.

Una fòrmula alternativa equivalent per al valor de Shapley és:

ϕ_{i} (v) = \frac{1}{| N |!} \sum_{R} [v (P_{i}^{R} \cup {i}) - v (P_{i}^{R})]

a on la suma s'estén sobretot $| N |!$ ordenant $R$ dels jugadors i $P_{i}^{R}$ és el conjunt de jugadors en $N$ que precedixen $i$ en l'orde $R$ .

Eixemple

Considere la possibilitat d'una descripció simplificada d'un negoci. Tenim un propietari o, que no treballa, sino que aporta el capital fonamental, lo que significa que sense ell no es poden obtindre guanys. Després tenim k treballadors w₁, ..., w_k, cada u dels quals contribuïx en una cantitat p de l'utilitat total. Per lo tant, la coalició és N = {O, w₁, ..., w_k} w i el valor v v(S) = 0 si o no és un membre de S i V(S) = mp si S conté el propietari i m treballadors. Calcular el valor de Shapley per a este joc de coalició du a un valor de kp / 2 per al propietari i p / 2 per a cada treballador.

Este joc és un joc de coalició, equivalent a que els jugadors tinguen guants esquerres i drets i deguen formar parelles per a donar-los valor. Si tenim

N = {1, 2, 3}

a on els jugadors 1 i 2 tenen guants de la mà dreta i el jugador 3 té un guant de la mà esquerra.

La funció de valor d'este joc de coalició és:

v (S) = {\begin{matrix} 1, & Si S \in {{1, 3}, {2, 3}, {1, 2, 3}} \\ 0, & De cualquier otro modo \end{matrix}

Quan la fòrmula per a calcular el valor de Shapley és:

ϕ_{i} (v) = \frac{1}{| N |!} \sum_{R} [v (P_{i}^{R} \cup {i}) - v (P_{i}^{R})]

A on $R$ és un ordenament dels jugadors i $P_{i}^{R}$ és el conjunt d'actors en $N$ que precedixen $i$ en l'orde $R$

La següent taula mostra les contribucions marginals del jugador 1:

Order $R$	$M C_{1}$
$1, 2, 3$	$v ({1}) - v (\emptyset) = 0 - 0 = 0$
$1, 3, 2$	$v ({1}) - v (\emptyset) = 0 - 0 = 0$
$2, 1, 3$	$v ({1, 2}) - v ({2}) = 0 - 0 = 0$
$2, 3, 1$	$v ({1, 2, 3}) - v ({2, 3}) = 1 - 1 = 0$
$3, 1, 2$	$v ({1, 3}) - v ({3}) = 1 - 0 = 1$
$3, 2, 1$	$v ({1, 2, 3}) - v ({2, 3}) = 1 - 1 = 0$

ϕ_{1} (v) = (1) (\frac{1}{6}) = \frac{1}{6}

Per un argument de simetria es pot demostrar que

ϕ_{2} (v) = ϕ_{1} (v) = \frac{1}{6}

Pel axioma de l'eficiència, sabem que la suma de tots els valors de Shapley és igual a 1, lo que significa que

ϕ_{3} (v) = \frac{4}{6} = \frac{2}{3} .

El problema de l'aeroport

Artícul principal → Problema de l'aeroport.

El problema de l'aeroport és un tipo de joc de divisió justa en el que es decidix cóm distribuir el cost d'un aeroport de la pista entre els diferents actors que necessiten pistes de diferents llongituts. El problema va ser introduït per Stephen Littlechild i G. Owen en 1973. Els autors senyalen que el conjunt resultant de les taxes d'aterrisage és el valor de Shapley per a un joc definit adequadament.

Referències

↑ Lloyd S. Shapley. "A Value for n-person Games". In Contributions to the Theory of Games, volume II, by H.W. Kuhn and A.W. Tucker, editors. Annals of Mathematical Studies v. 28, pp. 307–317. Princeton University Press, 1953.
↑ Alvin E. Roth (editor). The Shapley value, essays in honor of Lloyd S. Shapley. Cambridge University Press, Cambridge, 1988.
↑ Sergiu Hart, Shapley Value, The New Palgrave: Game Theory, J. Eatwell, M. Milgate and P. Newman (Editors), Norton, pp. 210–216, 1989.
↑ A Bibliography of Cooperative Games: Value Theory by Sergiu Hart[1]

Referències

Este artícul conté una traducció derivada de «Valor de Shapley» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[1] Lloyd S. Shapley. "A Value for n-person Games". In Contributions to the Theory of Games, volume II, by H.W. Kuhn and A.W. Tucker, editors. Annals of Mathematical Studies v. 28, pp. 307–317. Princeton University Press, 1953.

[2] Alvin E. Roth (editor). The Shapley value, essays in honor of Lloyd S. Shapley. Cambridge University Press, Cambridge, 1988.

[3] Sergiu Hart, Shapley Value, The New Palgrave: Game Theory, J. Eatwell, M. Milgate and P. Newman (Editors), Norton, pp. 210–216, 1989.

[4] A Bibliography of Cooperative Games: Value Theory by Sergiu Hart[1]

[1]

[2]

[3]

[4]