Wartość Shapleya

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

Wartość Shapleya – pojęcie z teorii gier, nazwane na cześć Lloyda Shapleya, który wymyślił je w 1953 roku jako sposób podziału zysku pomiędzy graczami będącymi w koalicji[1][2]. Wartość ta jest określona jednoznacznie dla każdego gracza w grze kooperacyjnej przez odpowiednią dystrybucję całości zysku z wielkiej koalicji, tj. koalicji złożonej ze wszystkich graczy, zachowującą pewne własności[3][4]. Intuicyjnie Wartość Shapleya określa, ile dany gracz powinien się spodziewać zysku z całości, biorąc pod uwagę to, jaki średnio ma wkład w dowolnej koalicji.

Definicja[5][edytuj | edytuj kod]

Niech dana będzie gra kooperacyjna gdzie N to zbiór graczy a to funkcja, która przypisuje dowolnemu podzbiorowi (koalicji) graczy liczbę rzeczywistą: przy czym Funkcja zwana jest również funkcją koalicyjną lub charakterystyczną.

Wartością Shapleya nazwiemy wektor który zachowuje następujące własności:

1. Racjonalność grupowa (efektywność):
Suma zysków graczy jest równa zyskowi wielkiej koalicji

2. Symetria:
Jeśli funkcja jest symetryczna wobec i oraz j, to ich wartości Shapleya są również identyczne

3. Gracz nieistotny:
Wartość Shapleya gracza, który nic nie wnosi do żadnej koalicji jest równa zero.

4. Addytywność:
Jeżeli są różnymi grami kooperacyjnymi z funkcjami charakterystycznymi to:

oraz

Dla dowolnej gry koalicyjnej istnieje tylko jeden taki podział.

Do wyliczenia tej wartości można wykorzystać następujący wzór:

Wartość nazywa się też wkładem marginalnym gracza

Alternatywnie, równoważny jest również zapis:

gdzie:

permutacja zbioru graczy,
– zbiór graczy z którzy występują w permutacji przed graczem

Przykład[edytuj | edytuj kod]

Weźmy za przykład grę kooperacyjną, w której gracze posiadają rękawice, prawe i lewe, a której celem jest stworzenie par.

Mamy trzech graczy: przy czym gracz 1 i 2 posiadają prawą rękawicę, a 3 lewą.

Funkcja koalicyjna będzie wyglądać następująco:

Biorąc pod uwagę wzór wypisujemy wszystkie permutacje

Następująca tabelka wylicza wkłady marginalne gracza pierwszego.

Permutacja

Dzięki symetrii graczy 1 i 2, wiemy również, że:

a jako, że wartości sumują się do to:

Zobacz też[edytuj | edytuj kod]

Przypisy[edytuj | edytuj kod]

  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, s. 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, s. 210–216, 1989.
  4. A Bibliography of Cooperative Games: Value Theory by Sergiu Hart[1].
  5. Wstęp do teorii gier – 12. Gry Koalicyjne II – MIM UW, mst.mimuw.edu.pl [dostęp 2016-02-09].