Valoarea Shapley - Extensii și Aplicații

I Introducere

1. Asupra valorii Shapley

2. Jocuri cooperative cu utilităţi transferabile

I Introducere

1. Asupra valorii Shapley

În teoria jocurilor, soluţiile pentru rezolvarea jocurilor au evoluat de la soluţii complexe, cum sunt mulţimile stabile şi nucleul, la soluţii simple, cum este valoarea Shapley.

Lloyd Stowell Shapley (născut pe 2 iunie 1923) este un recunoscut matematician şi economist. El este profesor consultant la University of California, Los Angeles, afiliat departamentelor de Matematică şi Economie. A avut contribuţii în domeniul economiei matematice, în special în teoria jocurilor. De la lucrările lui von Neumann şi Morgenstern din anii '40, Lloyd Shapley a fost considerat de mulţi experţi ca fiind însăşi personificarea teoriei jocurilor

Valoarea Shapley a fost introdusă de către L. S. Shapley în articolul său din 1953, A Value for n-person Games. Aceasta este un concept de soluţie folosit pentru rezolvarea jocurilor cooperative cu utilităţi transferabile, descrise în secţiunea următoare. Aplicaţiile în care valoarea Shapley se dovedeşte a fi o soluţie optimă sunt multiple, câteva exemple fiind prezentate în această lucrare.

Valoarea Shapley este un vector n-dimensional, care, pe fiecare componentă i indică valoarea plăţii alocate jucătorului i. Definiţia formală a acesteia, precum şi unele reformulări sunt date în prima secţiune a capitolului II.

Valoarea Shapley satisface mai multe proprietăţi, dar patru dintre acestea o pot determina în mod unic. Acestea sunt aditivitatea, simetria, eficacitatea şi axioma "jucătorului inutil". Aditivitatea arată că valoarea Shapley a sumei a două funcţii caracteristice este suma valorilor Shapley a respectivelor funcţii caracteristice. Faptul că valoarea Shapley este simetrică înseamnă că dacă profitul unei coaliţii căreia i se alătură un jucător i este aceeaşi cu profitul coaliţiei căreia i se alătură un jucător j atunci valoarea Shapley pentru cei doi jucători este aceiaşi. Eficacitatea spune că suma plăţilor acordate jucătorilor este aceeaşi cu valoarea coaliţiei care conţine toţi jucătorii. Un jucător este inutil dacă profitul unei coaliţii nu depinde de prezenţa respectivului jucător în rândul membrilor ei. Valoarea Shapley alocată unui astfel de jucător este zero. Definiţiile formale ale acestor proprietăţi precum şi demonstraţia faptului că cele patru proprietăţi determină în mod unic valoarea Shapley sunt prezentate în secţiunile 2 şi 3 ale capitolului II.

O soluţie clasică în teoria jocurilor este nucleul. Un rezultat interesant este cel care situează valoarea Shapley în raport cu nucleul unui joc convex: valoarea Shapley a acestui joc este baricentrul nucleului. Demonstraţia acestui rezultat este dată în secţiunea 4 a capitolului II.

Complexitatea unui program care poate da valoarea Shapley a unui joc este exponenţială. Un algoritm este considerat optim dacă are complexitate polinomială. Pentru ca timpul de calcul să nu fie prea mare, în secţiunea 5 a capitolului II este prezentat un program care afişează valoarea Shapley pentru un joc de trei persoane.

Moulin a demonstrat că axiomele de raţionalitate individuală (garantează fiecărui agent cel puţin profitul obţinut prin consumarea propriei "părţi corecte" din totalul resurselor), monotonie a resurselor (profitul niciunui agent nu scade atunci când cantitatea resurselor care trebuie împărţite creşte), solidaritatea populaţiei (atunci când apare un nou agent în împărţirea aceloraşi bunuri, toţi agenţii anteriori fie beneficiază (slab) fie pierd (slab)) şî testul de stabilitate (suma utilităţilor unei coaliţii nu trebuie să depăşească utilitatea pe care coaliţia ar primi-o prin împărţirea tuturor bunurilor între membrii săi) nu sunt compatibile două câte două. Aceste axiome sunt dezirabile în problema împărţirii corecte. Valoarea Shapley verifică (într-o anumită măsură) aceste axiome. Axiomele, demonstraţia faptului că valoarea Shapley verifică axiomele, precum şi o adaptare a acestui rezultat în problema repartizării sunt prezentate în secţiunea 6 a capitolului II.

O situaţie mai generală este cea în care jucătorii au contribuţii diferite în cadrul unei coaliţii. Valoarea Shapley simetrică presupune că profitul se împarte egal printre membrii unei coaliţii. Generalizarea valorii Shapley în acest caz se face prin adăugarea unui sistem de ponderi. Pentru caracterizarea axiomatică a valorii Shapley ponderate, comparativ cu valoarea Shapley simetrică, se face prin înlocuirea axiomei simetriei cu alte două axiome: pozitivitatea (dacă profitul unei coaliţii este strict mai mare decât profitul oricărei subcoaliţii proprii strict incluse atunci componentele valorii Shapley sunt nenegative) şi consistenţa de parteneriat (dacă se face o realocare a profitului în interiorul unei coaliţii, fiecare jucător primeşte exact cât ar fi primit dacă se făcea alocarea profitului total). O prezentare formală a valorii Shapley ponderate, o definiţie probabilistă şî caracterizarea axiomatică sunt prezentate în secţiunile 1-4 ale capitolului III. Rezultate asemănătoare sunt obţinute şi în cazul dualului unui joc. Definiţia jocului dual şi aceste rezultate sunt prezentate în secţiunea 5 a capitolului III.

Folosindu-se valoarea Shapley ponderată, numărul jucătorilor unui joc poate fi redus în felul următor: un jucător poate reprezenta o familie sau un parteneriat. Astfel, pentru fiecare familie sau parteneriat cu n membri, jocul va avea cu n – 1 mai puţini jucători. În acest caz, ponderea unui reprezentant este dată de "mărimea" grupului pe care îl reprezintă. Unele rezultate obţinute pentru acest caz sunt prezentate în secţiunea 7 a capitolului III.

Valoarea Shapley este o soluţie punctuală pentru un joc. Hart şi Mas-Colell propun o soluţie şi mai simplă: alocarea fiecărui joc a unui singur număr real. Pentru a determina acest număr, ei au definit o funcţie potenţial din mulţimea tuturor jocurilor în mulţimea numerelor reale. Cel mai important rezultat este dat de următoarea teoremă:

TEOREMĂ: Există şi este unică o funcţie reală definită pe jocuri, numită funcţia potenţial, în cadrul căreia contribuţiile marginale ale tuturor jucătorilor sunt întotdeauna eficace. Mai mult, aceste contribuţii marginale sunt exact componentele valorii Shapley.

Definiţia funcţiei potenţial şi demonstrarea acestei teoreme sunt prezentate în capitolul IV.

În continuare este prezentat cadrul general în care poate fi definită şi aplicată valoarea Shapley.

2. Jocuri cooperative cu utilitatăţi transferabile

Cooperarea în jocuri înseamnă că jucătorii pot să comunice şi să-şi coordoneze acţiunile. O noţiune de bază în teoria jocurilor cooperative este cea de coaliţie. Orice grup de jucatori care sunt de acord să coopereze reprezintă o coaliţie.

Primul model teoretic al jocului cooperativ a fost introdus de J. von Neumann şi O. Morgenstern. Ei pornesc de la ideea că jucătorii dintr-o coaliţie îşi pun bunurile la comun şi deci principalul obiectiv al coaliţiei este să maximizeze utilitatea totală a membrilor. În acest caz valoarea unei coaliţii este dată de utilitatea totală maximă pe care o poate garanta pentru membrii săi.