W artykule Problem bankructwa z Talmudu opisaliśmy pewną tajemnicę, która tkwiła w Talmudzie Babilońskim przez setki lat. Historia była następująca. Mężczyzna, umierając, zostawił trzy żony, którym obiecał odpowiednio 100, 200 i 300 srebrnych monet. Jego majątek nie był jednak tak duży, aby spłacić te zobowiązania. Jak powinno się podzielić pozostawiony majątek między żony? Talmud rozstrzyga tę kwestię w konkretnych przypadkach: jeżeli majątek to 100 monet, to powinno się go podzielić po równo. Jeżeli 200 monet, to pierwsza żona powinna dostać 50 monet, a pozostałe po 75. Z kolei jeżeli majątek stanowi 300 monet, to powinno się go podzielić proporcjonalnie: każda żona dostanie wówczas połowę obiecanej kwoty. Skąd biorą się jednak te sposoby podziału?
Rozwiązanie tej zagadki znaleźli dopiero w 1985 roku Robert Aumann i Michael Maschler. Nie tylko przedstawili oni metodę podziału, która pasuje do wszystkich trzech scenariuszy, ale też podali kilka jej uzasadnień.
O tej metodzie i uzasadnieniach pisaliśmy w poprzednim artykule,
jednak nie powiedzieliśmy, skąd ta metoda w ogóle się wzięła.
Autorzy sami przyznają, że metodę tę znaleźli, używając gier koalicyjnych. O tym, jak można to zrobić, opowiemy w tym artykule.
Problem bankructwa matematycznie definiuje się jako ciąg nieujemnych liczb dodatnich gdzie to majątek, a to roszczenia osób, które (zgodnie z historią powyżej) będziemy nazywać żonami, przy czym majątek nie przekracza sumy roszczeń
Metodę podziału znalezioną przez Aumanna i Maschlera obrazowo opisać można systemem naczyń połączonych znajdującym się na rysunku obok.
Jest w nim naczyń o pojemności każde złożone z dwóch połów połączonych bardzo cienką rurką o pomijalnej objętości.
U podstawy wszystkie naczynia łączy równie cienka rurka.
Do tego systemu wlewamy wody i każdej żonie przyznajemy tyle majątku, ile wody znajdzie się w jej naczyniu.
Z układu widzimy, że jeżeli majątek jest mniejszy niż połowa sumy roszczeń, czyli to pierwszych żon (dla pewnego ) dostanie połowę swojego roszczenia. Pozostałe żony podzielą się resztą po równo, przy czym wyznaczamy tak, aby nie dostały mniej niż -ta żona.
Jeżeli to możemy myśleć o dzieleniu nie majątku, a jego brakującej części – pierwszym żonom będzie brakowało po połowie ich roszczeń, a pozostałe tak podzielą się resztą, aby brakowało im po tyle samo.
Łatwo sprawdzić, że metoda ta zgadza się z wariantami problemu bankructwa opisanymi w Talmudzie.
Mało żon, mały kłopot
Zastanówmy się, gdzie możemy znaleźć tę rzekomą grę koalicyjną?
Przypomnijmy, że gra koalicyjna to para gdzie jest zbiorem graczy, a funkcją, która każdej grupie graczy, nazywanej koalicją, przypisuje pewną wartość (zakładamy ).
Zacznijmy, tak jak w poprzednim artykule, od sytuacji, w której są tylko dwie żony:
Jak argumentowali w swojej pracy Aumann i Maschler na podstawie innej historii z Talmudu (sporu o ubiór), podział powinien wyglądać następująco.
Jeżeli majątek jest większy niż żądanie drugiej żony (czyli ), to cała nadwyżka powinna trafić do pierwszej żony.
Analogicznie, jeżeli majątek jest większy niż żądanie pierwszej żony (), to powinno trafić do drugiej żony.
Całą resztę, czyli sporny kawałek, dzielimy po równo między żony.
Używając notacji otrzymujemy wypłatę żony :
Podział ten zgadza się z metodą Aumanna i Maschlera, dowód obrazkowy znajduje się na marginesie.
Jak możemy zamodelować tę sytuację z użyciem gier koalicyjnych?
Możemy przyjąć, że żony są graczami, i każdej grupie żon (czyli koalicji) przypisać kwotę, jaką może sobie ona zagwarantować. Pierwsza żona sama (bez żadnych negocjacji) potrafi osiągnąć wypłatę po prostu spłacając całe roszczenie drugiej żony. Analogicznie, druga żona sama może osiągnąć
Razem żony mają do podziału Dostajemy więc następującą grę koalicyjną:
Podstawowym zagadnieniem w grach koalicyjnych jest właśnie pytanie o to, jak podzielić się wspólnie uzyskaną wypłatą:
Praktycznie wszystkie (rozsądne) metody podziału dla tej gry dają dokładnie taki podział, jaki zdefiniowaliśmy powyżej: każdej żonie dajemy wartość, jaką może osiągnąć sama, a całą resztę dzielimy po równo.
Świetnie, tu podejście teoriogrowe daje to, co chcieliśmy uzyskać!
Dużo żon, duży kłopot
A co, kiedy żon jest więcej?
Działajmy analogicznie i każdej grupie żon przypiszmy, ile mogłyby sobie zagwarantować, gdyby spłaciły roszczenia reszty.
Dla ogólnego problemu bankructwa funkcja zdefiniowana jest więc następująco:
Popatrzmy na grę, jaka powstanie dla problemu bankructwa
Widzimy, że w tej grze druga i trzecia żona mają symetryczne role – tak jak w podziale opisanym w Talmudzie.
Ponadto pierwsza żona ma mniejsze znaczenie, co także się zgadza.
Dlatego też wszystkie sensowne metody podziału rozważane w grach koalicyjnych przypiszą pierwszej żonie mniej, a pozostałym dwóm żonom tyle samo.
Jak jednak dostać konkretnie te wartości?
Wartość Shapleya, która pojawiła się na łamach Delty już kilkakrotnie, przypisałaby pierwszej żonie majątku.
Wartość Banzhafa (po znormalizowaniu) dałaby pierwszej żonie majątku.
Okazuje się natomiast, że majątku pierwszej żonie i dokładnie taki wynik jak w Talmudzie daje nukleolus!
O nukleolusie pisaliśmy w artykule Jak podzielić lody… .
Dla danego podziału
zysk koalicji to jej wypłata pomniejszona o jej wartość w grze:
Zyski wszystkich koalicji uporządkowane rosnąco tworzą listę zysków.
Nukleolus to taki podział wypłaty, dla którego lista zysków jest maksymalna leksykograficznie.
Nukleolus stara się zatem zmaksymalizować zysk koalicji, która zyskuje najmniej.
Popatrzmy na zyski koalicji przy podziale (pomijamy koalicję pustą i koalicję wszystkich żon, bo one mają oczywiście zerowy zysk).
Widzimy, że lista zysków to
Najmniejszy zysk mają koalicje oraz
Czy istnieje podział wypłaty dla którego wektor będzie leksykograficznie większy?
Nie, bo przecież jeżeli zmniejszymy wypłatę pierwszej żony to jej zysk spadnie poniżej 50:
Z kolei jeżeli zwiększymy to poniżej 50 spadnie zysk koalicji :
Musi zatem być oraz
Druga i trzecia żona uzyskane 150 muszą podzielić po równo, aby kolejny zysk, jaki pojawia się na liście zysków, nie był mniejszy niż
Jak wygląda nukleolus dla dowolnej liczby żon i dowolnych roszczeń? Okazuje się, że dokładnie tak, jak podział z metody Aumanna i Maschlera. Czemu? To teraz pokażemy.
Dowód hydroaerobowy
Skupimy się na przypadku, kiedy : jeżeli to łatwo można wykazać, że nukleolus dla problemu odwrotnego jest dopełnieniem nukleolusa dla oryginalnego problemu.
Weźmy dowolny podział Zablokujmy rurki łączące naczynia w systemie hydraulicznym i wlejmy wodę tak, aby odpowiadała podziałowi
Czym jest teraz zysk koalicji ?
Mamy dwa przypadki.
Koalicję nazwiemy wodną, jeżeli majątek nie przekracza roszczenia żon spoza :
Mamy wówczas i zysk tej koalicji jest równy ilości wody w naczyniach żon z :
Koalicję nazwiemy
powietrzną, jeżeli majątek jest nie mniejszy niż roszczenia pozostałych żon:
Jak pokazują poniższe obliczenia, zysk tej koalicji jest natomiast równy ilości powietrza w naczyniach pozostałych żon:
Jak poznać, jakiego typu jest koalicja ? Musimy sprawdzić, czy cała woda zmieściłaby się w naczyniach żon spoza W tym celu dla dowolnego ułożenia wody w naczyniach wystarczy porównać ilość wody w naczyniach żon z oraz ilość powietrza w pozostałych naczyniach. Jeżeli wody jest mniej niż powietrza, to woda się mieści, więc mamy koalicję wodną. Jeżeli powietrza jest mniej niż wody, to woda się nie mieści, i mamy koalicję powietrzną. Jeżeli jest tyle samo, to koalicja jest wodno-powietrzna (i wodna, i powietrzna).
Niech teraz będzie podziałem z metody Aumanna i Maschlera, a dowolnym innym podziałem.
Udowodnimy, że lista zysków dla jest leksykograficznie mniejsza niż dla
Niech będzie pierwszą pozycją, na której oba podziały się różnią.
Zastanówmy się, które koalicje przy podziale mają zysk mniejszy niż ?
Jeżeli jest koalicją wodną, to aby jej zysk był mniejszy niż nie może ona zawierać żony ani żadnej kolejnej (bo dla ). Stąd wniosek, że jest podzbiorem i jej zysk według i jest taki sam.
Jeżeli jest koalicją powietrzną, to aby jej zysk był mniejszy niż to ani ani żadna kolejna żona nie może być poza Stąd wniosek, że zawiera oraz podzbiór i też ma taki sam zysk według i
Ta analiza pokazuje, że każda koalicja, która ma mniejszy zysk niż według podziału ma identyczny zysk według podziału
Aby wykazać, że lista zysków dla jest leksykograficznie mniejsza niż dla wskażemy koalicję, która według ma mniejszy zysk niż a według nie.
Jeżeli oraz to taką koalicją jest Jest to koalicja wodna, co łatwo zobaczyć, odblokowując rurki łączące naczynia, czyli w podziale : ilość wody w jej naczyniu jest wówczas mniejsza bądź równa ilości powietrza w naczyniu kolejnej żony. Jej zysk to zatem
Jeżeli oraz to taką koalicją jest Ta koalicja na pewno jest bowiem koalicją powietrzną: ponownie odblokowując rurki, widzimy, że w podziale kolejna żona sama ma co najmniej tyle wody, ile powietrza ma żona Jej zysk to zatem
W końcu jeżeli to -ta żona i wszystkie kolejne dostają w tyle samo: Skoro różni się od dopiero na pozycji -tej, to albo któraś z dalszych żon, powiedzmy musi dostawać mniej niż Wówczas szukaną koalicją jest : jest to koalicja wodna, bo według podziału woda z jej naczynia nawet nie dopełni naczynia -tej żony (lub kolejnej, jeżeli ). Jej zysk to zatem
To kończy dowód.
Czy autorzy Talmudu znali pojęcie gier koalicyjnych i nukleolusa? Jest to raczej mało prawdopodobne.
Niewątpliwie udało im się jednak wpłynąć na rozwój teorii gier koalicyjnych, mimo że (zgodnie z dostępną aktualnie wiedzą) powstała ona dwa tysiące lat później.