jump to navigation

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

Posted by Mikołaj Morzy in nauka.
9 comments

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.

Liczba która zawiera w sobie Wszechświat 03/20/2016

Posted by Mikołaj Morzy in Uncategorized.
1 comment so far

piTydzień temu, 14 marca, na całym świecie obchodzono międzynarodowy Dzień Liczby PI. Niewiele osób zdaje sobie sprawę z tego, jak głęboką i niepokojącą tajemnicę kryje w sobie ta liczba.

W matematyce liczbą normalną nazywamy taką liczbę rzeczywistą, której nieskończona sekwencja cyfr zawiera jednostajny rozkład częstości występowania każdej cyfry, każdej pary cyfr, każdej trójki cyfr, itd. Innymi słowy, jeśli liczba jest normalna, to 1/10 cyfr w jej reprezentacji stanowią „0”, 1/10 cyfr stanowią „1”, …, ale także 1/100 par cyfr stanowi kombinacja „12”, 1/100 par cyfr stanowi kombinacja „13”, itd. Co więcej, normalność wymaga, aby rozkład częstości występowania cyfr był jednorodny niezależnie od przyjętego systemu liczbowego (dziesiętny, ósemkowy, binarny, szesnastkowy, …). Ideę liczb normalnych wprowadził Emil Borel na początku XX wieku. Co ciekawe, udowodnił on, że prawie wszystkie liczby rzeczywiste są normalne. Przykładami liczb normalnych są liczba Champernowna (konkatenacja kolejnych liczb naturalnych: 0.1234567891011121314…) czy liczba Copelanda-Erdosa (konkatenacja liczb pierwszych: 0.123571113171923…). Liczby, dla których znana jest procedura ich generowania, jak w poprzednich dwóch przykładach, nie stanowią jednak tak dużego wyzwania jak liczby, które „magicznie” pojawiają się w matematyce. Do dziś nie wiadomo, czy najsłynniejsze liczby, takie jak \sqrt{2}, \pi, e, czy ln(2) są normalne, choć większość matematyków skłania się do opinii, że liczby te są normalne.

Co jednak ma normalność do tajemnicy skrywającej się w liczbie \pi? Rozwinięcie dziesiętne \pi jest nieskończone i nie wydaje się mieć w sobie ukrytego żadnego wzorca, zatem cyfry pojawiające się w owym nieskończonym rozwinięciu zachowują się losowo. Nieskończony ciąg losowych liczb zawiera w sobie każdy skończony ciąg cyfr z prawdopodobieństwem równym 1. Powtórzmy to raz jeszcze: w rozwinięciu dziesiętnym liczby \pi pojawia się każdy możliwy skończony ciąg cyfr. Jeśli literom alfabetu przypiszesz kolejne liczby, to w rozwinięciu \pi odnajdziesz każde słowo, każde zdanie, każdą książkę którą kiedykolwiek napisano. Ale odnajdziesz więcej: odnajdziesz każdą książkę, której nigdy nie napisano, odnajdziesz imiona i daty urodzin wszystkich ludzi, którzy kiedykolwiek się urodzili, i tych, którzy nie mieli szczęścia pojawić się na świecie. Dla każdego człowieka który istniał lub nie istniał, odnajdziesz jego biografię. Odnajdziesz całą historię swojego życia, ale też wszystkie historie żyć, które Ci się nie przytrafiły. W tej niepozornej liczbie tkwi zapisany cały dzisiejszy internet, wszystkie jego strony, blogi, posty i wiadomości, wraz z wszystkimi możliwymi reprezentacjami tego internetu (np. całym internetem przetłumaczonym na język kaszubski). Kiedy następnym razem spojrzysz na liczbę \pi, zdobądź się na szacunek, bo liczba ta zawiera w sobie cały Wszechświat. O ile nauka jest poezją rzeczywistości, o tyle matematyka jest tej rzeczywistości magią.

Czy wiedza o tym, że \pi zawiera w sobie każdy możliwy tekst, może być użyteczna? W końcu gdzieś w \pi tkwią odpowiedzi na największe zagadki ludzkości. Szkopuł w tym, że cała ta wiedza jest kompletnie bezużyteczna. Po pierwsze, prawie całe rozwinięcie dziesiętne \pi zawiera śmieci, nie stanowiące żadnego składnego zdania. Po drugie, nie mamy pojęcia, która część jest śmieciem, a która nie – nie możemy tego wiedzieć bo rozwinięcie jest losowe. Wreszcie po trzecie, aby zlokalizować fragment rozwinięcia musimy podać jego pozycję, co wymaga użycia dokładnie tylu bitów co znalezienie samego fragmentu. Dochodzimy do zdumiewającego paradoksu, łańcuch znaków zawierający wszystkie możliwe informacje w rzeczywistości nie zawiera żadnych informacji. Dokładnie ten właśnie paradoks przepięknie pokazał J.L.Borges w swoim opowiadaniu The Library of Babel (dla leniwych streszczenie w Wikipedii).

Zawsze jednak z czystej ciekawości możesz sprawdzić, na której pozycji w liczbie \pi znajduje się Twoja data urodzenia w serwisie Find Your Pi Day. Moja jest na pozycji 573 855.

%d bloggers like this: