jump to navigation

Jak sprawiedliwie podzielić rachunek za taksówkę? 03/26/2016

Posted by Mikołaj Morzy in nauka.
trackback

Lloyd Shapley

Dwa tygodnie temu zmarł Lloyd Shapley, laureat Nagrody Nobla w roku 2012, matematyk i ekonomista, którego idee znajdują liczne zastosowania w informatyce, szczególnie w obszarze teorii gier i analizy danych. Jego najbardziej znanym odkryciem (opisanym nota bene w doktoracie) było rozwiązanie problemu gier kooperacyjnych, znane odtąd jako wartość Shapleya. Pomysł prosty i genialny, który bardzo łatwo jest zobrazować wykorzystując przykład.

Trzy osoby planują wspólny powrót do domu taksówką. Załóżmy, że mieszkają w linii prostej, tj. taksówka przejeżdża najpier obok domu Alicji, potem mija dom Bartka, a na koniec dojeżdża do domu Cecylii. Jeśli Alicja wróci sama, zapłaci za taksówkę 10 złotych. Samotny powrót Bartka będzie kosztował 25 złotych, natomiast najdalej mieszkająca Cecylia będzie musiała zapłacić 40 złotych. Alicja, Bartek i Cecylia postanawiają wracać razem. Ile każde z nich powinno zapłacić za wspólny kurs? W oczywisty sposób Alicja powinna zapłacić mniej niż 10 złotych, w przeciwnym wypadku nie ma powodu, żeby wracała (i finansowała powrót pozostałej dwójki), podobnie Bartek powinien zapłacić mniej niż 25 złotych, ale ile dokładnie? Na to właśnie pytanie odpowiedział Shapley.

W grze kooperacyjnej występuje zbiór graczy N=\{1,\ldots,n\}, oraz pojęcie koalicji, czyli dowolnego podzbioru graczy. W naszym przypadku możliwe koalicje to A, B, C, AB, AC, BC, ABC (AB to Alicja i Bartek wracający jedną taksówką, Cecylia wraca sama). Ważne jest też pojęcie funkcji charakterystycznej, która przypisuje każdej koalicji graczy pewną liczbę, zwaną wartością koalicji. Otóż Shapley podał jedyny sprawiedliwy sposób przydziału wypłat do graczy (w naszym przypadku wysokości składki na taksówkę jaką powinna dorzucić każda osoba), bazujący na pojęciu kontrybucji marginalnej. Idea jest bardzo prosta: dla każdego gracza patrzymy, ile wynosi wartość każdej koalicji w której może brać udział gracz w porównaniu z wartością tej samej koalicji bez danego gracza. Wypłata dla każdego gracza jest średnią wszystkich możliwych kontrybucji marginalnych dla tego gracza. Znów przywołując nasz przykład, każda osoba patrzy, ile zapłaciłaby w każdej możliwej konfiguracji powrotów taksówką do domu i wyciąga średnią.

Spróbujmy więc podpowiedzieć Alicji, Bartkowi i Cecylii, jak powinni podzielić swój rachunek. Jeśli pojadą każde swoją taksówką, to zapłacą: A=10, B=25, C=40. Jeśli będą jechać parami, to rachunki wyniosą AB=25 (Alicja jedzie z Bartkiem, końcowy rachunek wyniesie 25 złotych), AC=40, BC=40 (każda osoba jadąca z Cecylią musi oczekiwać końcoweg rachunku w wysokości 40 złotych), wreszcie jeśli pojadą we trójkę, to ABC=40. Aby policzyć kontrybucje marginalne, można zastosować prosty trick i wykorzystać permutacje pasażerów taksówki. Wyobraźmy sobie, że nasi znajomi umawiają się, że płacą w kolejności ABC, czyli najpierw Alicja płaci 10 zł, potem Bartek płaci 15 zł, na koniec Cecylia płaci 15 zł (łączny rachunek wynosi 40 zł). A co byłoby, gdyby umówili się, że płacą w kolejności ACB? Wówczas najpierw Alicja płaci 10 zł, potem Cecylia płaci za odcinek „do siebie” czyli 30 zł, a Bartek jedzie za darmo. A permutacja BAC? Najpierw Bartek płaci swoje 25 zł, potem Alicja (ale jej przejazd już został opłacony przez Bartka), w końcu Cecylia dopłaca 15 zł do 40 zł. Wszystkie możliwe permutacje są takie:

permutacja A B C
ABC 10 15 15
ACB 10 0 30
BAC 0 25 15
BCA 0 25 15
CAB 0 0 40
CBA 0 0 40

Na koniec wyliczamy średnie w każdej kolumnie i uzyskujemy dla Alicji 8 zł 30 gr, dla Bartka 10 zł 83 gr, dla Cecylii 25 zł 83 gr (razem daje to pełny rachunek 40 zł).

Dlaczego jest to podział sprawiedliwy, w jakim sensie sprawiedliwy, i dlaczego jedyny? Za to właśnie Shapley dostał Nobla. Zaproponowany przez niego sposób podziału jest jedynym, który spełnia cztery fundamentalne własności:

  • wydajność: suma wypłat wszystkich graczy jest równa wartości gry (czyli suma składki jest równa rachunkowi za taksówkę)
  • symetria: jeśli dwoje graczy miałoby identyczne kontrybucje marginalne do każdej możliwej koalicji, to ich wypłaty byłyby identyczne (gdyby Alicja i Bartek mieszkali razem, to ich składka byłaby taka sama)
  • liniowość: jeśli dwie gry koalicyjne zostałyby połączone, to wypłata każdego gracza w grze łączonej byłaby równa sumie wypłat w osobno rozgrywanych grach
  • pusty gracz: jeśli jakiś gracz nie wnosi kontrybucji marginalnej do żadnej gry, to jego wypłata wynosi 0.

Shapley udowodnił, że zaproponowany przez niego schemat wypłat jest jedynym schematem spełniającym te własności.

Moje zainteresowanie wartością Shapleya wzięło się stąd, że przygotowuję właśnie recenzję pracy doktorskiej, w której zapronowano użycie tego narzędzia do oceny ważności wierzchołków w sieciach społecznościowych. Mówiąc dokładniej, doktorant rozszerzył tradycyjne definicje centralności wg stopni wierzchołków, bliskości i pośrednictwa na przypadek grupowy (gdzie np. pośrednictwo jest liczone dla grupy wierzchołków a nie pojedynczego wierzchołka), a następnie doktorant wyznacza ważność każdego wierzchołka licząc marginalną kontrybucję danego wierzchołka do miary centralności każdej grupy, do której wierzchołek może należeć. Co ważniejsze, dla n wierzchołków może istnieć 2^n grup, ale w doktoracie zaproponowano bardzo pomysłowe algorytmy, które wyznaczają wartość Shapleya dla każdego wierzchołka w czasie wielomianowym. Cała praca jest niezwykle ciekawa. Częśc z wyników prezentowanych w doktoracie już opublikowano i można się z nimi zapoznać w poniższych pracach:

Michalak, Tomasz P., et al. „Efficient computation of the Shapley value for game-theoretic network centrality.” Journal of Artificial Intelligence Research (2013): 607-650.
Szczepański, Piotr L., Tomasz Michalak, and Talal Rahwan. „A new approach to betweenness centrality based on the shapley value.” Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems-Volume 1. International Foundation for Autonomous Agents and Multiagent Systems, 2012.

Reklamy

Komentarze»

1. Anna Szur - 03/27/2016

‚Na koniec wyliczamy średnie w każdej kolumnie i uzyskujemy dla Alicji 8 zł 30 gr, dla Bartka 10 zł 83 gr, dla Cecylii 25 zł 83 gr (razem daje to pełny rachunek 40 zł).’
Totally sure about this?

Aydiee - 03/27/2016

Exactly

2. Grzegorz - 03/27/2016

Ciekawy artykuł, aczkolwiek IMHO wkradł się drobny błąd.
Dla Alicji: 20/6=3,33 zł a nie 8,30.

3. Pawel - 03/27/2016

Skoro domy leżą liniowo…to po co jechac na okolo???
Inaczej mowiac: co wnosza kolejne permutacje?

taria - 03/29/2016

Ten artykuł przedstawia uproszczona wersję problemu.
Rozszerzmy go tak: trasa taksówki z O(punkt początkowy) do A kosztuje 10zł, z O do B przez A – 25 zł, z O do C przez A i B – 40zł, wszystko jak powyżej.

abec we wpisie z 03/27/2016 tłumaczy jak uzyskać sprawiedliwy podział opłaty bez uciekania się do permutacji – jesli pojedziemy trasą OABC Cecylia powinna zapłacić 25zł 83 gr.

Ale w tym momencie odzywa się Cecylia: „Bez jaj, znam trasę skrotem do mojego domu bez przejeźdżania obok Waszych i kosztuje ona 25 zł. Mogę sobie pojechać sama i zaoszczędzę 83 gr ( i co najmniej dziesięć minut mojego drogocennego czasu). Wy stracicie na tym w sumie 10,83 zł (za trasę OAB zapłacicie 25zł zamiast 3,33+10,83).
Zaproponujcie mi korzystniejszy podzial, to pojadę z Wami trasą OABC.

W jaki sposób nalezałoby teraz podzielić zapłatę za przejazd, żeby Cecylia nie miała poczucia, że Alicja i Bartek ją wykorzystują?

Żeby rozwiązać ten problem trzeba już rozważyć wszystkie opcje przejazdu przyjaciół i policzyć ich wkład do rachunku.

4. abec - 03/27/2016

Nobla? Za to?
Pierwszy odcinek jada we trójkę wiec 10 zł dzielimy na trzy.
DRUGI, warty 15″zl (25-10) jada dwie osoby, wiec 15/2=7.5zl
Ostatni za 15 zł (40-(10+15)) bierze w całości statki pasażer.
A=3,33
B=3.33+7.5=10.83
C=3,33+7,5+15=25.83
Przecież to jest problem na poziomie podstawówki, może późnej.
Dają za to Nobla?

KJ - 03/27/2016

Z tego, co wyczytałem, Nobel nie był za opracowanie sposobu, ale za udowodnienie, że to jedyny model, który spełnia wspomniane 4 warunki.

5. Gigi - 03/28/2016

a ja bym zaproponował:

A: 6,15
B: 9,23
C: 24,62

6. Maria - 06/25/2016

A dlaczego nie procentowo?
Alicja Bartek Cecylia suma
10 25 40 75
[%] ABC 0.13 0.33 0.53
CENA ABC
40 5.33 13.33 21.33


Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Wyloguj / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Wyloguj / Zmień )

Connecting to %s

%d blogerów lubi to: