Usuari:Leandro.navarro/Valor de Shapley

En la teoría de jocs, el valor de Shapley, nomenat en honor de Lloyd Shapley, qui el va introduir en 1953, es un métode de distribució de la riquesa en la teoria de jocs cooperatius. 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 caracteritza per una col·lecció de propietats desitjables o axiomes que es descriuen a continuació. Hart (1989) ofereix una anàlisi del tema.

La configuració és com segueix: una coalició de jugadors coopera, i obté un cert guany general de la cooperació. Atès que alguns jugadors poden contribuir més a la coalició que uns altres o poden tenir diferent poder de negociació (per exemple, amenaçant amb destruir tot l'excedent), Quin repartiment final dels beneficis de la cooperació entre els jugadors hem d'esperar que sorgeixi en qualsevol joc en particular? O expressat d'una altra manera: Quina importància té cada jugador per a la cooperació global, i quina recompensa pot ell o ella raonablement esperar? El valor de Shapley ofereix una possible resposta a aquesta pregunta.

Definició formal

Per fo${\displaystyle }$malitzar aquesta situació, utilitzem la noció d'u${\displaystyle }$ joc de coalició: comencem amb un grup N (de n jugadors) i una funció

v :

${\displaystyle }$

N

${\displaystyle }$

R {${\displaystyle }$ ${\displaystyle }$\;:\;2^{N}\to \mathbb {R} } amb v ( ∅ ) = 0 {\displaystyle v(\emptyset )=${\displaystyle }$} , on

${\displaystyle }$

{${\displaystyle }$ } denota el conjunt buit.${\displaystyle }$${\displaystyle }$${\displaystyle }$ La funció v que assigna subconjunts d'actors reals es diu funció característica..॥॥ La funció v {\display${\displaystyle }$tyle ${\displaystyle }$} té el següent significat: si S és una coalició de jugadors, llavors v(S), cridat el valor de la coalició S {${\displaystyle }$} , descriu la suma total dels pagaments als membres de S que es pot obtenir per aquesta cooperació.${\displaystyle }$${\displaystyle }$

El valor de Shapley és una manera de distribuir els guanys totals als jugadors, en el cas que tots col·laboren formant una gran coalició. És una distribució "justa" en el sentit que és l'única distribució amb certes propietats desitjables que s'enumeren a continuació. D'acord amb el ${\displaystyle }$valor de Shapley, la qua${\displaystyle }$titat que el jugador i obté durant un joc de coalició ( v , N ) {\displaystyle (v,N)} és:${\displaystyle }$

${\displaystyle }$

On n és el nombre 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à formada per un actor alhora, amb cada actor exigint la seva contribució v (S ∪ {i}) - v (S) com una compensació justa, i després per a cada actor prendre la mitjana d'aquesta contribució sobre les diferents possibles permutacions en la qual es pot formar la coalició.

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

$\phi _{i}(v)={\frac {1}{|N|!}}\sum _{R}\left[v(P_{i}^{R}\cup \left\{i\right\})-v(P_{i}^{R})\right]\,\!$

on la suma se extèn per todo $|N|!$ ordenant $R\,\!$ de los jugadors y $P_{i}^{R}\,\!$és el conjunto de jugadors en $N\,\!$ que precedeixen $i\,\!$ en l'ordre $R\,\!$.

Exemple

Joc de guants

Consideri la possibilitat d'una descripció simplificada d'un negoci. Tenim un propietari o, que no treballa, sinó que aporta el capital fonamental, el que significa que sense ell no es poden obtenir guanys. Llavors tenim k treballadors w₁, ..., w_k, cadascun dels quals contribueix amb una quantitat p de la utilitat total. Per tant la coalició és N = {O, w₁, ..., w_k} w i el valor v v(S) = 0 si o no es un membre de S y V(S) = mp si S conté el propietari i m treballadors. Calcular el valor de Shapley per a aquest joc de coalició porta a un valor de kp / 2 pel propietari i p / 2 per a cada treballador.

Aquest joc és un joc de coalició, equivalent al fet que els jugadors tinguin guants esquerres i drets i hagin de formar parelles per donar-los valor. Si tenim

${\displaystyle }$

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'aquest joc de coalició és:

${\displaystyle }$

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

${\displaystyle }$

On${\displaystyle }$

R {\dis${\displaystyle }$laystyle ${\displaystyle }$\,\!} és un o${\displaystyle }$denament dels jugadors ${\displaystyle }$

i P ${\displaystyle }$

R {${\displaystyle }$ P_{i}^{R}\,\!} és el conjunt d'actors en N {${\displaystyle }$ N\,\!} que precedeixen i {\displaystyle i\,\!} en l'ordre R {\displaystyle R\,\!${\displaystyle }$${\displaystyle }$${\displaystyle }$${\displaystyle }$${\displaystyle }$

La siguiente tabla muestra las contribuciones marginales del Jugador 1

O${\displaystyle }$rdre R {\displaystyle R\,\!${\displaystyle }$	${\displaystyle }$
${\displaystyle }$	${\displaystyle }$
${\displaystyle }$	${\displaystyle }$
${\displaystyle }$	${\displaystyle }$
${\displaystyle }$	${\displaystyle }$
${\displaystyle }$	${\displaystyle }$
${\displaystyle }$	${\displaystyle }$

${\displaystyle }$

Per un argument de simetria es pot demostrar que

${\displaystyle }$

A causa de l'axioma de l'eficiència, sabem que la suma de tots els valors de Shapley és igual a 1, la qual cosa significa que

${\displaystyle }$

El problema de l'aeroport

El problema de l'aeroport és un tipus de joc de divisió justa en el qual es decideix com distribuir el cost d'un aeroport de la pista entre els diferents actors que necessiten pistes de diferents longituds. El problema va ser introduït per Stephen Littlechild i G. Owen en 1973. Els autors assenyalen que el conjunt resultant de les taxes d'aterratge és el valor de Shapley per a un joc definit adequadament.

Propietats

El valor de Shapley té les següents propietats desitjables:

1. Eficiència : El guany total es distribueix:

${\displaystyle }$

2. Simetria: si i i j són dos actors que són equivalents en el sentit que:

${\displaystyle }$

per a cada subconjunt S de N que no conté i ni j, llavors φi(v) = φj(v).

3. Linealitat: Si dos jocs cooperatius descrits per les funcions de guany v i w es combinen, llavors el guany distribuït hauria de correspondre al guany derivat de v i w:

ϕ i ( v + w ) = ϕ i ( v ) + ϕ i ( w ) {\displaystyle \phi _{i}(v+w)=\phi _{i}(v)+\phi _{i}(w)} per cada i en N.${\displaystyle }$

També, per cada nombre real a:

ϕ i ( a v ) = a ϕ i ( v ) {\displaystyle \phi _{i}(av)=a\phi _{i}(v)} per cada i en N.${\displaystyle }$

4. Zero Player (Jugador Nul): El valor de Shapley

${\displaystyle }$

i ( ${\displaystyle }$ ) {\d${\displaystyle }$splaystyle \phi _{i}(v)} d'un jugador nul i en un joc v és zero.${\displaystyle }$ Un jugador jo és nul en v ${\displaystyle }$

${\displaystyle }$

{${\displaystyle }$} if v ( S ${\displaystyle }$ { i } ) = ${\displaystyle }$ ( S ) {\displaystyle v(S\cup \{i\})=v(S)} per a totes les coalicions S .${\displaystyle }$${\displaystyle }$

De fet, donat un conjunt de N jugadors, el valor de Shapley és l'únic mapa a partir del conjunt de tots els jocs de vectors de guanys que satisfà totes les quatre propietats aquí esmentades.

Definicions d'addició

1. Anònim: Si _i i j són dos actors, i w és la funció de guany que actua igual que v, excepte que els rols d'i i j s'han intercanviat, llavors φi(v) = φj(w). En essència, això significa que l'etiquetatge dels actors no juga un paper en l'assignació dels seus guanys. Aquesta funció es diu que és anònima.

2. Marginalisme: el valor de Shapley pot definir-se com una funció que utilitza només les contribucions marginals del jugador i com a arguments.