Spis treści

Wstęp

1. Optymalny mement stopu

2. Eksploracja/eksploatacja

3. Sortowanie

4. Keszowanie

5. Planowanie

6. Reguła Bayesa

7. Nadmierne dopasowanie

8. Relaksacja

9. Losowość

10. Sieci

11. Teoria gier

Zakończenie

Przypisy

Bibliografia

Podziękowania

Wszystkie rozdziały dostępne są w pełnej wersji książki

Tytuł oryginału: Algorithms to Live By

Przekład: Dariusz Rossowski
Redaktor prowadzący: Maria Zalasa
Redakcja: Katarzyna Nawrocka
Konsultacja merytoryczna: prof. dr hab. Krzysztof Diks

Projekt okładki i stron tytułowych: Joanna Wasilewska/Katakanasta

Copyright © 2016 by Brian Christian and Tom Griffiths. All rights reserved.
Copyright for Polish edition and translation © Wydawnictwo JK, 2018

Wszelkie prawa zastrzeżone. Żadna część tej publikacji nie może być powielana ani rozpowszechniana za pomocą urządzeń elektronicznych, mechanicznych, kopiujących, nagrywających i innych bez uprzedniego wyrażenia zgody przez właściciela praw.

ISBN 978-83-7229-736-5
Wydanie I, Łódź 2018

Wydawnictwo JK
Wydawnictwo JK, ul. Krokusowa 3,
92-101 Łódź tel. 42 676 49 69 www.wydawnictwofeeria.pl

Konwersję do wersji elektronicznej wykonano w systemie Zecer.

Naszym rodzinom,
Autorzy

Wstęp

Wyobraźmy sobie, że szukasz mieszkania do wynajęcia w San Francisco, chyba najtrudniejszym pod tym względem mieście w USA. Boom sektora technologicznego i surowe przepisy ograniczające nowe budownictwo sprzysięgły się, by miasto stało się równie drogie co Nowy Jork i nie mniej konkurencyjne. Oferty lokali znikają w ciągu kilku minut, mieszkania są zajmowane niemal na dziko i często klucze trafiają do rąk tego, kto pierwszy siłą wciśnie czek z zaliczką administratorowi.

Taki drapieżny rynek nie pozostawia zbyt wiele miejsca na prowadzenie systematycznych poszukiwań i podejmowanie rozważnych decyzji, czym teoretycznie powinno się cechować postępowanie racjonalnego konsumenta. W odróżnieniu od, powiedzmy, klienta galerii handlowej czy sklepu internetowego, który może porównać różne możliwości przed dokonaniem zakupu, przyszły „sanfranciskanin” musi natychmiast podjąć decyzję typu albo-albo: bierze to mieszkanie, które właśnie ogląda, rezygnując ze wszystkich pozostałych, albo odchodzi i nigdy już do niego nie wraca.

Dla uproszczenia załóżmy na moment, że zależy ci tylko na tym, żeby jak najbardziej zwiększyć swoją szansę na zdobycie najlepszego z dostępnych lokali. Twoim celem jest wydostać się z krzyżowego ognia żalu i obaw, w którym się znalazłeś: z jednej strony żalu przepuszczenia nadarzającej się okazji, z drugiej obaw związanych z niesprawdzeniem innych opcji. Zderzasz się z tym dylematem od samego początku: skąd masz wiedzieć, że dane mieszkanie jest rzeczywiście najlepsze, skoro brakuje ci punktu odniesienia? A jak masz ten punkt zyskać, jeśli nie obejrzysz (i nie stracisz) pewnej liczby ofert? Im więcej zbierzesz informacji, tym łatwiej zidentyfikujesz wyjątkową ofertę, gdy się trafi – ale jednocześnie będzie coraz prawdopodobniejsze, że już ją przepuściłeś.

Co masz więc zrobić? Jak podjąć decyzję opartą na realnych przesłankach, skoro sam akt zbierania tych przesłanek zagraża rezultatowi? To okrutna zagadka z pogranicza paradoksu.

W obliczu takiego problemu większość ludzi intuicyjnie powie, że trzeba ustanowić pewną proporcję między oglądaniem kolejnych ofert a skokiem na głęboką wodę; trzeba obejrzeć wystarczająco dużo mieszkań, by określić standard, a następnie zdecydować się na to, co ten standard spełni. Idea takiej proporcji jest rzeczywiście słuszna. Większość ludzi traci jednak pewność siebie, gdy mają powiedzieć, ile może ona wynieść. Na szczęście odpowiedź ta istnieje.

Trzydzieści siedem procent.

Jeśli zależy ci na największym prawdopodobieństwie wynajęcia najlepszego mieszkania, poświęć 37% poszukiwania go (jedenaście dni, jeśli dałeś sobie miesiąc na cały proces) na chłodne zapoznawanie się z dostępnymi opcjami. Gotówkę zostaw w domu; na razie tylko kalibrujesz zakup. Ale po przekroczeniu tego punktu bądź gotów na natychmiastową decyzję – umowę wstępną, zaliczkę itd. – w pierwszym lokalu, który będzie lepszy od tych, które już oglądałeś. Nie jest to tylko intuicyjnie satysfakcjonujący kompromis między rekonesansem a decyzją. Jest to prawdopodobnie optymalna decyzja.

Mamy co do tego pewność, ponieważ znajdowanie mieszkania należy do problemów matematycznych z klasy optymalnego stopowania. W regule 37% streszcza się prosty ciąg pewnych działań – czyli algorytm, jak mówi się w informatyce – prowadzący do rozwiązania takich problemów. Okazuje się, że polowanie na apartament jest jednym z przykładów, w których optymalne stopowanie daje o sobie znać w codziennym życiu. Wybór lub przepuszczanie kolejnych opcji jest strukturą, z którą wielokrotnie mamy do czynienia pod różnymi postaciami. Ile razy powinno się okrążyć samochodem kwartał ulic w poszukiwaniu miejsca do zaparkowania? Jak daleko brnąć w ryzykowny interes przed spieniężeniem swojego udziału? Jak długo czekać na lepszą ofertę na swój dom czy samochód?

To samo wyzwanie występuje również w delikatniejszej kwestii: randkowania. Teoria optymalnego stopowania jest naukową podbudową seryjnej monogamii.

Proste algorytmy oferują rozwiązania nie tylko w poszukiwaniu mieszkań, lecz także w tych wszystkich sytuacjach życiowych, w których stajemy przed problemem znalezienia optymalnego momentu zatrzymania jakiegoś procesu. Ludzie zmagają się z tym, niekiedy z wielkim trudem, w zasadzie każdego dnia – choć z pewnością poeci wylali więcej atramentu na udręki zalotów niż parkowania. Tymczasem trud jest zbędny. Przynajmniej w sensie matematycznym problemy te są już rozwiązane.

Wszyscy znękani najemcy, kierowcy i randkowicze, których widujesz wokół, zajęci są w zasadzie ponownym wynajdowaniem koła. Nie potrzeba im psychoterapii; potrzeba im algorytmu. Terapeuta powie im, by znaleźli właściwą, komfortową proporcję między impulsywnością a nadmiernym myśleniem.

Algorytm mówi im, że ta proporcja wynosi trzydzieści siedem procent.

◆

Istnieje pewien zbiór problemów, przed którymi stają wszyscy ludzie; problemów, które są bezpośrednią konsekwencją tego, iż nasze życie toczy się w skończonej przestrzeni i czasie. Co powinniśmy zrobić – oraz co zostawić niezrobione – w ciągu danego dnia czy dekady? Z jak wielkim bałaganem powinniśmy się oswoić albo jak duży porządek staje się przesadą? Jaka ilość nowych doświadczeń w stosunku do preferowanych przyczynia się do maksymalnego spełnienia w życiu?

Może się wydawać, że są to problemy wyłącznie ludzkie – nic bardziej mylnego. Od ponad półwiecza informatycy borykają się z odpowiednikami tych codziennych dylematów i w wielu przypadkach znaleźli rozwiązania. Jak procesor ma dzielić swoją „uwagę”, by wykonać wszystko, czego życzy sobie użytkownik, z minimalnym obciążeniem i w jak najkrótszym czasie? Kiedy powinien przełączać się między różnymi zadaniami i ilu w ogóle zadań powinien się podejmować naraz? Jaki jest najlepszy sposób wykorzystania jego ograniczonych zasobów pamięciowych? Powinien zebrać jeszcze więcej danych, czy też przystąpić do obliczeń na podstawie tych, którymi już dysponuje? Sporym wyzwaniem dla ludzi bywa carpe diem – chwytanie dnia. Tymczasem otaczające nas zewsząd komputery z łatwością chwytają milisekundy. Możemy się dużo nauczyć na ich przykładzie.

Sformułowanie „algorytmy dla ludzkiego życia” wydaje się pewnie niektórym osobliwym zestawieniem. Słowo „algorytm” przywodzi powszechnie na myśl tajemne i nieprzeniknione machinacje wielkimi danymi, potężne instytucje państwowe i globalny biznes – raczej ważny element infrastruktury nowoczesnego świata niż źródło mądrości życiowej czy przewodnik po ludzkich sprawach. Jednak zasadniczo algorytmy są po prostu skończonymi ciągami działań prowadzących do rozwiązania poszczególnych problemów i mają dużo szersze zastosowanie, nieograniczające się do informatyki, od której są zresztą dużo starsze. Na długo zanim były wykorzystywane przez maszyny, korzystali z nich ludzie.

Samo słowo „algorytm” pochodzi od nazwiska perskiego matematyka Musy al-Khwārizmīego (al-Chuwarizmiego), autora podręcznika z IX wieku o technikach liczenia (księga ta była zatytułowana al-Jabr wa’l-Muqābala, a al-jabr stało się rdzeniem naszego słowa „algebra”). Jednak najstarsze znane algorytmy matematyczne pochodzą z jeszcze dawniejszych czasów. Mająca cztery tysiące lat sumeryjska tabliczka gliniana znaleziona opodal Bagdadu zawiera opis sposobu dzielenia pisemnego.

Niemniej występowanie algorytmów nie ogranicza się do matematyki. Korzystasz z algorytmu, piekąc ciasto na podstawie przepisu czy robiąc sweter na drutach według wzoru. Kiedy ostrzysz kant krzemienia, wykonując precyzyjną sekwencję uderzeń jelenim rogiem – najważniejszy etap w wytwarzaniu narzędzi z kamienia – również korzystasz z algorytmu. Algorytmy stanowią część kultury technologicznej człowieka od epoki kamienia.

◆

W książce tej omawiamy projektowanie algorytmów dla ludzi – poszukiwanie lepszych rozwiązań w odniesieniu do wyzwań, przed którymi stajemy. Spojrzenie na codzienne życie przez pryzmat informatyki ma konsekwencje przejawiające się w różnych skalach. Przede wszystkim oferuje nam praktyczne, konkretne porady odnośnie do sytuacji, przed którymi stajemy. Optymalny moment stopu podpowiada, kiedy rozglądać się dalej, a kiedy łapać okazję. Kompromis eksploracja/eksploatacja mówi, jak pogodzić poznawanie nowego z korzystaniem z tego, co lubimy. Teoria sortowania wskazuje, jak (i czy) porządkować swój gabinet. Teoria pamięci podręcznej pomaga układać szpargały w schowkach. Teoria planowania mówi, jak wypełniać swój czas.

Na następnym poziomie informatyka daje nam aparat pojęciowy do zrozumienia głębszych zasad, które ujawniają się w każdej z tych domen. Jak ujął to Carl Sagan, „nauka jest w dużo większym stopniu sposobem myślenia niż zasobem wiedzy”. Nawet w tych przypadkach, gdy życie przebiega zbyt chaotycznie, by można było odwoływać się do ścisłej analizy matematycznej czy oczekiwać gotowych rozwiązań, zastosowanie intuicji i koncepcji wynikających z prostszych postaci tych problemów daje nam możliwość zrozumienia zasadniczych występujących tu zagadnień i posunięcia się do przodu.

W najszerszym ujęciu patrzenie przez pryzmat informatyki pozwala wyciągnąć naukę na temat ludzkiego umysłu, tego, co to jest racjonalność, oraz najstarszej kwestii ze wszystkich: jak żyć. Rozpatrywanie zdolności poznawczych jako środka do rozwiązywania stawianych nam przez środowisko zadań o charakterze fundamentalnie obliczeniowym może gruntownie zmienić nasz sposób myślenia o racjonalności człowieka.

Sugestia, że analiza schematów działania komputera jest w stanie ukazać, jak powinniśmy myśleć i podejmować decyzje, do czego mieć zaufanie i jak postępować, może uderzać wielu ludzi jako nie tylko wyjątkowo redukcjonistyczna, ale po prostu głupia. Nawet gdyby informatyka miała coś do powiedzenia na temat optymalnego sposobu myślenia i działania, dlaczego mielibyśmy tego słuchać? Gdy popatrzy się na sztuczną inteligencję lub roboty z opowieści science fiction, nie wydaje się, byśmy mieli ochotę prowadzić życie na ich modłę.

Częściowo wynika to z tego, że myśląc o komputerach, mamy obraz zimnych, mechanistycznych, deterministycznych układów – maszyn stosujących sztywną logikę dedukcyjną, podejmujących decyzje po wyliczeniu wszystkich dostępnych opcji i wymieleniu ściśle poprawnej odpowiedzi bez względu na to, jak długo i intensywnie będą musiały nad nią myśleć. Rzeczywiście człowiek, który pierwszy wyobraził sobie komputery, miał na myśli coś w tym rodzaju. Alan Turing zdefiniował samo pojęcie obliczeń (computation)[1] przez analogię do matematyka, który systematycznie pokonuje kolejne etapy w rachunkach, bezbłędnie uzyskując poprawną odpowiedź.

Dla wielu może być więc zaskoczeniem, że nowoczesne komputery, stając przed trudnym problemem, nie postępują w taki sposób. Oczywiście prosta arytmetyka nie jest szczególnym wyzwaniem dla współczesnego komputera. Chodzi raczej o takie zadania, jak rozmowa z człowiekiem, naprawa uszkodzonego pliku albo rozegranie partii azjatyckiej gry go, czyli o zadania, w których zasady nie są wyraźnie sprecyzowane, brakuje części potrzebnych informacji albo znalezienie ściśle poprawnej odpowiedzi wymagałoby rozważenia astronomicznej liczby możliwości. Algorytmy opracowane przez naukowców do rozwiązywania najtrudniejszych klas problemów sprawiły, że komputery przestały być skrajnie uzależnione od wyczerpujących rachunków. Zajmowanie się zadaniami w rzeczywistym świecie wymaga oswojenia się z losowością, zawierania kompromisu między czasem a precyzją oraz używania przybliżeń.

W miarę jak komputery zostały lepiej dostrojone do problemów realnego świata, zaczęły służyć nam nie tylko algorytmami, które ludzie mogą wykorzystywać na swój użytek, lecz także standardem, z którym można porównywać nasze zdolności poznawcze. W ostatnich dziesięciu, dwudziestu latach ekonomia behawioralna snuje bardzo szczególną opowieść o ludziach – że jesteśmy irracjonalni i skłonni do pomyłek, co w dużej mierze ma wynikać z zabugowanego, pokrętnego „hardware’u” mózgowego. Ten deprecjonujący nas obraz jest coraz powszechniej przyjmowany, niemniej wciąż pozostają pewne natrętne pytania. Na przykład dlaczego w wielu zadaniach poznawczych, związanych między innymi z postrzeganiem wzrokowym, językiem i rozumowaniem przyczynowym, czterolatki nadal wypadają lepiej niż superkomputery za milion dolarów?

Rozwiązania codziennych problemów podsuwane przez informatykę sugerują inną opowieść o ludzkim umyśle. Życie obfituje w problemy, które najzwyczajniej są trudne. Błędy popełniane przez ludzi często mówią więcej o wewnętrznej złożoności problemu niż o omylności ludzkiego mózgu. Myślenie algorytmiczne o świecie, zapoznanie się z fundamentalnymi strukturami zadań, przed którymi stajemy, oraz właściwościami ich rozwiązań może pomóc nam w dostrzeżeniu tego, jak jesteśmy w tym dobrzy, oraz w lepszym zrozumieniu popełnianych przez nas błędów.

W rzeczywistości ludzie systematycznie stają przed najtrudniejszymi rodzajami problemów analizowanymi przez informatyków. Często musimy podejmować decyzje w warunkach niepewności, ograniczeń czasowych, niedoinformowania oraz szybko zmieniającego się świata. W niektórych z tych przypadków nawet najbardziej zaawansowane badania informatyczne nie zaowocowały jeszcze wydajnymi, niezawodnie działającymi algorytmami. Wydaje się, że w odniesieniu do pewnych sytuacji takie algorytmy mogą w ogóle nie istnieć.

Jednak nawet tam, gdzie nie znaleziono algorytmów doskonałych, bitwa pokoleń informatyków z najoporniejszymi problemami rzeczywistego świata przyniosła wiele spostrzeżeń. Te wypracowane w pocie czoła wskazówki kłócą się z naszym intuicyjnym rozumieniem racjonalności i absolutnie nie brzmią jak schematyczne recepty skostniałego matematyka próbującego wtłoczyć świat w sztywne formalne ramy. Są to na przykład: nie zawsze rozważaj wszystkie dostępne opcje; niekoniecznie dąż za każdym razem do rezultatu, który wydaje się najlepszy; czasami trochę pobałagań; nie podróżuj z dużą ilością bagażu; poczekaj na rozwój wypadków; zaufaj swojemu instynktowi i nie rozmyślaj zbyt długo; odpręż się; rzuć monetą; wybaczaj, ale nie zapominaj; nie udawaj, tylko bądź sobą.

Wbrew pozorom życie podług mądrości informatycznych wydaje się niezłym pomysłem. A dodatkowo, w odróżnieniu od większości innych porad, te są poparte dowodami.

◆

Tak jak opracowywanie algorytmów komputerowych było pierwotnie dziedziną, która trafiała w lukę pomiędzy różnymi dyscyplinami – jako osobliwa hybryda matematyki z inżynierią – podobnie opracowywanie algorytmów dla ludzi jest pozbawione swojej naturalnej dziedziny. Dzisiaj algorytmika czerpie nie tylko z informatyki, matematyki i inżynierii, lecz także z takich spokrewnionych z nimi dziedzin, jak statystyka czy badania operacyjne. Gdy rozważamy zaś, jak algorytmy tworzone z myślą o maszynach mogą odnosić się do ludzkiego umysłu, polegamy między innymi na kognitywistyce, psychologii, ekonomii.

My, autorzy tej książki, poruszamy się po takim interdyscyplinarnym terytorium. Brian studiował informatykę i filozofię, a potem lingwistykę, po czym podjął pracę znajdującą się na przecięciu tych dziedzin. Tom studiował psychologię i statystykę, zanim został wykładowcą University of California w Berkeley, gdzie zajmuje się przede wszystkim rozważaniem związków między zdolnościami poznawczymi człowieka a obliczeniami. Nikt nie jest jednak w stanie specjalizować się we wszystkich dziedzinach, które mają udział w opracowywaniu lepszych algorytmów funkcjonowania dla ludzi. Dlatego w ramach zbierania materiałów do książki przeprowadziliśmy wywiady z osobami, które stworzyły jedne z najsłynniejszych algorytmów ostatnich pięćdziesięciu lat. I pytaliśmy je – tych jednych z najinteligentniejszych ludzi na świecie – jak ich badania wpływały na ich podejście do własnego życia: od znajdowania małżonka do sortowania skarpetek.

Na kolejnych stronach wyruszymy na spotkanie wielkich wyzwań, przed którymi stają zarówno komputery, jak i umysły ludzi: jak zarządzać skończoną przestrzenią, skończonym czasem, ograniczoną pojemnością uwagi, nieznaną niewiadomą, niepełną informacją i nieprzewidywalną przyszłością; w jaki sposób robić to z wdziękiem i pewnością; oraz jak robić to w społeczności, której członkowie jednocześnie starają się robić to samo. Spojrzymy na matematyczną strukturę leżącą u podstaw tych wyzwań oraz na to, jak programowane są komputery – czasem całkiem niezgodnie z potocznymi wyobrażeniami – by możliwie skutecznie owym wyzwaniom sprostać. Dowiemy się też, jak pracuje ludzki umysł i jak wyglądają jego, odmienne od komputerowych, ale pokrewne im, sposoby radzenia sobie z takim samym zbiorem zadań w kontekście takich samych ograniczeń. Tym, co możemy w konsekwencji zyskać, jest nie tylko zestaw gotowców do rozwiązywania konkretnych problemów, nie tylko dostrzeżenie eleganckiego porządku u podłoża najbardziej zawikłanych ludzkich dylematów, nie tylko świadomość wspólnoty wysiłków ludzi i komputerów, lecz także coś, co ma szczególne znaczenie: nowe słownictwo do opisu otaczającego nas świata oraz szansa dowiedzenia się czegoś naprawdę nowego o sobie samych.

1. Dla jasności dodajmy, że „obliczenia” w tym sensie nie są równoznaczne z wąsko pojętym dodawaniem, odejmowaniem itd. Termin ten (od którego w angielskiej wersji powstało samo słowo „komputer”) można raczej odnieść do specyficznego wysiłku intelektualnego, którego wymaga dążenie do rozwiązania zadania (przyp. tłum.). ↩

1 Optymalny moment stopu

Kiedy przestać szukać

Choć wszyscy chrześcijanie w pierwszych słowach zaproszenia na ślub uroczyście oświadczają, iż ich małżeństwo jest wynikiem szczególnego zrządzenia Opatrzności, ja, jako filozof, chciałbym rozpatrzyć tę kwestię bardziej szczegółowo.

Johannes Kepler

Skoro przedkładasz pana Martina ponad każdego innego; skoro uważasz go za najurodziwszego spośród mężczyzn, w których towarzystwie kiedykolwiek przebywałaś, skąd biorą się twe wahania?

Jane Austen, Emma

Zjawisko to jest tak powszechne, że doradcy psychologiczni na amerykańskich uczelniach ukuli na nie specjalne określenie: turkey drop (dosł. rozstanie przy indyku). Studenci pierwszego roku wracają do domu na listopadowe Święto Dziękczynienia, marząc o spotkaniu ze swoją szkolną miłością, i cztery dni później pojawiają się na kampusie jako single.

Brian był tak podłamany po powrocie na zajęcia pierwszoroczne, że sam udał się do takiego doradcy. Jego dziewczyna z liceum wyjechała na uczelnię do innego stanu i oboje zmagali się z tą rozłąką. Zmagali się też z niepokojąco brzmiącym, bardziej filozoficznym pytaniem: czy ich związek był naprawdę dobry? Nie mieli punktu odniesienia w postaci innych bliskich relacji, który pozwoliłby go ocenić. Doradczyni Briana uznała to za klasyczny dylemat pierwszorocznych studentów i udzieliła zaskakująco nonszalanckiej rady: „Zbierz dane”.

Seryjna monogamia stawia praktykujących ją ludzi przed fundamentalnym i nieuniknionym problemem. Kiedy mogę przyjąć, że poznałem wystarczająco dużo partnerów, by stwierdzić, kto najlepiej do mnie pasuje? I co, jeśli będę gromadził te dane za cenę tego właśnie związku? Wydaje się, że to istny sercowy paragraf 22.

Jak wspomnieliśmy we wstępie, ten młodzieńczy krzyk rozpaczy należy do zadań zwanych przez matematyków problemami optymalnego momentu stopu (momentu zatrzymania) czy inaczej optymalnego stopowania (zatrzymywania) i w zasadzie znamy jego rozwiązanie: 37%.

Wszystko zależy od tego, jakie założenia na temat miłości jesteśmy skłonni przyjąć.

Problem wyboru sekretarki

Fundamentalnym dylematem w zadaniach klasy optymalnego stopowania nie jest to, którą opcję wybrać, ale ile opcji w ogóle rozważyć. Okazuje się, że ma to implikacje nie tylko dla narzeczonych i najemców, lecz także dla kierowców, właścicieli nieruchomości, włamywaczy i wielu innych.

Reguła 37%[1] wynika z najsłynniejszej zagadki tego typu, która znana jest pod nazwą problemu sekretarki. Okoliczności są podobne jak w przypadku omawianego we wstępie polowania na mieszkanie. Wyobraź sobie, że przeprowadzasz rozmowy kwalifikacyjne z grupą kandydatek na stanowisko sekretarki i twoim celem jest maksymalizacja prawdopodobieństwa, że dokonasz najlepszego wyboru. Choć nie masz pojęcia, jak przyznawać punkty poszczególnym aplikantkom, możesz z łatwością ocenić, które bardziej preferujesz (matematyk powiedziałby, że masz dostęp wyłącznie do liczb porządkowych – relatywnej pozycji danej kandydatki w stosunku do innych – a nie do liczb kardynalnych, czyli pozycji na jakiejś skali ogólnej). Rozmawiasz z kandydatkami, z każdą osobno, w losowej kolejności. Możesz zdecydować się na złożenie propozycji zatrudnienia w dowolnym momencie rozmowy i masz gwarancję, że zostanie ona przyjęta, co kończy dalsze poszukiwania. Jeśli natomiast przepuścisz kandydatkę, nie decydując się jej od razu zatrudnić, tracisz ją bezpowrotnie.

Uważa się, że problem sekretarki po raz pierwszy zaistniał na papierze – choć bez wzmiankowania sekretarek – w lutowym numerze Scientific American z 1960 roku jako jedna z wielu zagadek zawartych w poczytnych felietonach matematycznych Martina Gardnera. Niemniej pochodzenie samego zadania jest owiane tajemnicą. Nasze poszukiwania zaowocowały początkowo zaledwie spekulacjami i skłoniły nas do nieoczekiwanej fizycznej pracy detektywistycznej: wyprawy do archiwum pism Gardnera w Stanfordzie, skąd wydobyliśmy pudła z listami z połowy zeszłego stulecia. Czytanie papierowej korespondencji jest trochę podobne do podsłuchiwania osoby rozmawiającej przez telefon; słyszy się tylko połowę wymiany zdań i trzeba domyślić się drugiej. W naszym przypadku mieliśmy jedynie odpowiedzi, które Gardner otrzymał w ramach, jak się zdaje, własnego śledztwa sprzed pięćdziesięciu laty w sprawie pochodzenia problemu. Im więcej czytaliśmy, tym bardziej zagmatwana i niejasna stawała się ta historia.

Harwardzki matematyk Frederick Mosteller przypominał sobie, że usłyszał o tym problemie w 1955 roku od swego kolegi Andrew Gleasona, który z kolei znał go od kogoś innego. Leo Moser napisał z University of Alberta, że czytał o tym problemie w „notkach” R.E. Gaskella z Boeinga, który przypisuje jego autorstwo znajomemu. Roger Pinkham z Rutgers University doniósł, że usłyszał o problemie po raz pierwszy w 1955 roku od J. Shoenfielda, matematyka z Duke University, „i wydaje mi się, że mówił, że zna go od kogoś z Michigan”.

Tym „kimś z Michigan” niemal na pewno był Merrill Flood. Choć jest to postać raczej nieznana poza kręgami matematycznymi, wpływ, jaki wywarł na informatykę, jest nie do przecenienia. Przypisuje mu się spopularyzowanie problemu komiwojażera (zajmiemy się nim w rozdziale 8), sformułowanie dylematu więźnia (omówimy go w rozdziale 11) i potencjalnie nawet ukucie terminu „software”. Właśnie Flood dokonał (w 1958 roku) pierwszego znanego odkrycia reguły 37%, a samym problemem zajmował się, jak twierdzi, od roku 1949. Jednak jego autorstwo przypisuje się kilku innym matematykom.

Dość powiedzieć, że bez względu na swoje pochodzenie problem sekretarki okazał się niemal doskonałą zagadką matematyczną: łatwą do przedstawienia, piekielnie trudną do rozwiązania, zwięzłą w odpowiedzi i mającą intrygujące implikacje. W konsekwencji rozprzestrzeniał się lotem błyskawicy w kręgach matematycznych lat pięćdziesiątych, przekazywany z ust do ust, a dzięki felietonowi Gardnera w 1960 roku trafił do opinii publicznej. W ciągu dwudziestu lat pojawiło się tak wiele uwzględniających go analiz, że zaczął funkcjonować w piśmiennictwie jako samoistny temat.

A propos sekretarek, naprawdę urocze jest przyglądanie się, jak różne kultury nadają własne antropologiczne zabarwienie formalnym systemom. Na temat szachów myślimy na przykład, że w swym obrazowaniu są średniowieczno-europejskie, choć w rzeczywistości pochodzą z VIII-wiecznych Indii; zostały brutalnie „zeuropeizowane” w XV stuleciu, gdy szachowie stali się królami, wezyrowie królowymi, a słonie gońcami. Analogicznie wiele wcieleń miały problemy optymalnego stopowania, a każde z nich odzwierciedlało charakterystyczne kwestie epoki. W XIX wieku problemy takie występowały w kontekście loterii czy dam dobierających sobie adoratorów; na początku XX stulecia znajdowały wyraz w poszukiwaniu hoteli na urlop przez automobilistów oraz poszukiwaniu kobiet przez adoratorów; a w urzędniczej, zdominowanej przez mężczyzn połowie XX wieku – w wybieraniu asystentek przez szefów. Pierwsze wyraźne nawiązanie do niego pod nazwą problemu sekretarki pojawia się w artykule z 1964 roku i z czasem ta nazwa się utrwaliła.

Skąd 37%?

W poszukiwaniu sekretarki można ponieść fiasko na dwa sposoby: przez zakończenie go za wcześnie lub za późno. W pierwszym przypadku najlepsza kandydatka pozostaje niepoznana. W drugim dalej rozglądasz się za lepszą kandydatką, choć takiej już nie ma. Optymalna strategia wyraźnie wymaga znalezienia równowagi między tymi opcjami, balansowania między zbyt długim a zbyt krótkim szukaniem.

Jeśli twoim celem jest znalezienie absolutnie najlepszej kandydatki, jest jasne, że w miarę kontynuowania rekrutacji nie powinieneś się nawet zastanawiać nad zatrudnieniem osoby, która nie jest najlepsza ze spotkanych dotychczas. Jednakże samo bycie najlepszą do tej pory nie wystarcza, by złożyć danej kandydatce ofertę; zresztą już pierwsza aplikantka będzie z definicji najlepsza do tej pory. Przyjmując szerszą perspektywę, wydaje się rozsądne, że częstotliwość natykania się przez nas na osobę najlepszą do tej pory będzie spadała w miarę odbywania przez nas kolejnych rozmów. Tak na przykład druga kandydatka ma 50-procentową szansę bycia najlepszą z przesłuchiwanych do tej pory, ale u piątej kandydatki prawdopodobieństwo to wynosi już 1/5, u szóstej 1/6 itd. W rezultacie najlepsze do tej pory kandydatki będą w miarę kontynuowania rekrutacji stopniowo coraz lepsze (bo, znów z definicji, przewyższają one wszystkie poprzednie) – ale jednocześnie będą się pojawiać coraz rzadziej.

Wiemy, że zdecydowanie się na pierwszą najlepszą przesłuchiwaną kandydatkę (czyli pierwszą na liście do rekrutacji) byłoby przedwczesne. Jeśli dysponujemy setką zgłoszeń, złożenie oferty następnej najlepszej do tej pory tylko dlatego, że jest lepsza od pierwszej, też wydaje się pochopne. Co mamy więc robić?

Intuicyjnie można wpaść na kilka potencjalnych strategii. Na przykład złożyć ofertę osobie, która jako trzecia przebije wszystkie poprzedniczki – a może jako czwarta? Albo wybrać najlepszą kandydatkę, która pojawi się po długim okresie „posuchy”, długim ciągu słabych aplikantek.

Okazuje się jednak, że żadna z tych stosunkowo sensownych strategii nie zajmuje pierwszego miejsca. Optymalne rozwiązanie przyjmuje postać reguły zwanej przez nas ogląd-pogląd: z góry wyznaczasz czas przeznaczony na „rozglądanie się” (sondowanie możliwości, zbieranie danych), w którym z zasady nikogo nie wybierasz bez względu na to, jak wielkie zrobi wrażenie. Po przekroczeniu zaś tego punktu wkraczasz w fazę sformułowania poglądu i wykonania „skoku na głęboką wodę”, gotów zdecydować się na pierwszą osobę, która przyćmi najlepszą kandydatkę spośród przepytywanych w pierwszej fazie.

Można zaobserwować wyłanianie się tej reguły, rozważając problem sekretarki w najmniejszej puli kandydatek. W sytuacji pojedynczego zgłoszenia rozwiązanie problemu jest trywialne – składasz ofertę zatrudnienia! Przy dwóch kandydatkach masz prawdopodobieństwo 50/50 bez względu na to, co zrobisz. Możesz zatrudnić pierwszą (która jest jednocześnie najlepszą w pierwszej połowie puli) albo ją odrzucić i z konieczności zatrudnić drugą (która jest najlepsza w drugiej połowie puli).

Dodajmy trzecią aplikantkę i nagle sprawy nabierają rumieńców. Prawdopodobieństwo dokonania dobrego wyboru losowego wynosi jedną trzecią, czyli 33%. Przy dwóch kandydatkach nie mogliśmy uzyskać lepszego wyniku niż losowy, a czy możemy go mieć przy trzech? Okazuje się, że tak i że wszystko sprowadza się do tego, jak postąpimy z drugą. Gdy rozmawiamy z pierwszą, nie dysponujemy żadnymi informacjami – zawsze kandydatka ta będzie najlepsza z dotychczasowych. Gdy rozmawiamy z trzecią, nie mamy swobody ruchu – musimy złożyć jej ofertę, skoro odrzuciliśmy wszystkie poprzednie. Gdy jednak rozmawiamy z drugą, mamy po trochu tego i tamtego: możemy ocenić, czy jest lepsza czy gorsza od pierwszej, oraz mamy swobodę wyboru: zatrudnić ją lub odrzucić. Co dzieje się, kiedy zatrudniamy ją, jeśli jest lepsza, albo odrzucamy, jeśli jest gorsza? Okazuje się, że to optymalna strategia, gdy mamy do czynienia z trzema zgłoszeniami; dzięki temu podejściu można uzyskać równie dobry wynik w wyborze z trzech, jaki uzyskuje się w wyborze z dwóch, czyli trafiając na najlepszą kandydaturę dokładnie w połowie przypadków.[2]

Rozpisanie tych scenariuszy dla czterech kandydatek podpowiada, że i tym razem powinniśmy zacząć nasz skok od drugiej. Przy pięciu nie powinniśmy tego robić przed trzecią.

W miarę jak pula się rozrasta, granica między oglądaniem a decyzją lokuje się w 37% puli, co daje nam regułę 37%:[3] przesłuchaj pierwsze 37% kandydatek, nie wybierając żadnej, a potem bądź gotów zdecydować się na pierwszą, która okaże się lepsza od wszystkich widzianych do tej pory.

Jak się okazuje, trzymanie się tej strategii daje nam ostatecznie 37-procentowe prawdopodobieństwo zatrudnienia najlepszej osoby. To, że sama strategia oraz prawdopodobieństwo powodzenia dzięki niej sprowadzają się do tej samej liczby, stanowi przykład jednej z ciekawych symetrii matematycznych tego problemu. Poniższa tabela obrazuje optymalną strategię postępowania przy różnych liczbach kandydatek, pokazując, że w miarę powiększania tej liczby prawdopodobieństwo sukcesu – podobnie jak punkt przerzucenia się z przeprowadzania wywiadu na wybór – zmierza do 37%.

Oczywiście 63-procentowe prawdopodobieństwo porażki przy zastosowaniu najlepszej możliwej strategii jest dla nas zimnym prysznicem. Nawet jeśli będziemy postępować w sposób optymalny, i tak w większości przypadków poniesiemy fiasko, czyli nie wybierzemy najlepszej kandydatki z puli. To zła wiadomość dla tych z nas, którzy chcą postrzegać romantyczny związek w kategoriach poszukiwania „tej jedynej” czy „tego jedynego”. Ale jest i promyk nadziei. Intuicja podpowiada, że szansa na znalezienie najlepszej kandydatki powinna systematycznie spadać w miarę wzrostu ich liczby. Gdybyśmy zatrudniali kandydatki losowo, w puli 100 aplikantek mielibyśmy 1% szansy na sukces, a w puli miliona – 0,0001%. Tymczasem wynik wyliczeń stojących za problemem sekretarki się nie zmienia. Jeśli przestrzegasz optymalnego momentu zatrzymania, prawdopodobieństwo zatrudnienia najlepszej kandydatki ze stu wynosi 37%. I w grupie miliona kandydatek nadal wynosi 37%. Zatem im większa jest pula, tym wartościowsza staje się znajomość optymalnego algorytmu postępowania. To prawda, że w większości przypadków nie znajdziesz igły w tym stogu siana, niemniej optymalne stopowanie jest najlepszą metodą zmierzenia się z tym stogiem bez względu na to, jak jest ogromny.

Skok serca

Namiętność iskrząca między płciami wydaje się tak podobna niezależnie od epoki, że zawsze można uważać ją, mówiąc językiem algebraicznym, za wielkość daną.

Thomas Malthus

Wyszłam za pierwszego mężczyznę, którego pocałowałam w życiu. Kiedy mówię to swoim dzieciom, zbiera się im na wymioty.

Barbara Bush

Zanim Michael Trick został profesorem badań operacyjnych na Carnegie Mellon University, był poszukującym życiowej partnerki magistrantem. „Uderzyło mnie, że całe zagadnienie zostało już przebadane – przecież to problem sekretarki! Miałem przed sobą ciąg kandydatek, a moim celem był wybór najlepszej.” Trick wykonał więc odpowiednie rachunki. Nie wiedział, ile kobiet przyjdzie mu bliżej poznać, ale w regule 37% jest pewna elastyczność: można ją zastosować albo do liczby kandydatek, albo do czasu, w którym prowadzi się poszukiwania. Zakładając, że poszukiwania te mogłyby trwać od wieku osiemnastu do czterdziestu lat, z reguły 37% wyniknął wiek 26,1 lat jako punkt zwrotny do przejścia od „oglądu” do „poglądu”. A tak się złożyło, że był to wiek, w którym Trick akurat się znajdował. Kiedy więc trafił na kobietę, która przewyższała wszystkie spotkane dotychczas, nie miał wątpliwości, co należy zrobić. „Nie wiedziałem, czy jest Chodzącym Ideałem (założenia modelu nie pozwalają tego określić), ale było jasne, że spełnia wymogi tego kroku w algorytmie. Zatem oświadczyłem się” – napisał.

„A ona mi odmówiła.”

Matematycy zmagają się z problemami sercowymi co najmniej od XVII wieku. Legendarnego astronoma Johannesa Keplera pamięta się dziś przede wszystkim z powodu odkrycia, że planety krążą po orbitach eliptycznych, oraz jego udziału w „rewolucji kopernikańskiej”, która obejmowała też Galileusza oraz Newtona i wywróciła do góry nogami nasze pojęcie o miejscu człowieka w kosmosie. Jednak Kepler zajmował się także ziemskimi sprawami. Po śmierci swej pierwszej żony w 1611 roku podjął długie i mozolne starania mające na celu znalezienie drugiej towarzyszki życia, adorując w sumie jedenaście pań. Z pierwszych czterech najbardziej odpowiadała mu czwarta („z powodu postawnej figury i atletycznego ciała”), ale astronom nie przerwał poszukiwań. „Klamka by już zapadła – pisał – gdyby nie to, że tak miłość, jak i rozum podsunęły mi piątą niewiastę. Zniewoliła mnie swoją miłością, kornym oddaniem, roztropnością w gospodarowaniu, sumiennością oraz sercem, jakim obdarzyła moje dzieci.”

„Niemniej – napisał – szukałem dalej.”

Przyjaciele i krewni przedstawiali mu kolejne kandydatki, a on wciąż się rozglądał, choć trochę bez przekonania. Jego myśli wciąż krążyły wokół numeru pięć. Po zapoznaniu się z jedenastoma paniami Kepler postanowił zakończyć poszukiwania. „Przygotowując się do podróży do Ratyzbony, wróciłem do piątej niewiasty, zdeklarowałem się i zostałem przyjęty.” Kepler i Susanna Reuttinger pobrali się i mieli szóstkę wspólnych dzieci plus te z pierwszego małżeństwa Keplera. Biografowie opisują dalszy ciąg prywatnego życia astronoma jako pasmo błogiego spokoju i radości.

Zarówno Kepler, jak i Trick doświadczyli z pierwszej ręki – choć w przeciwny sposób – tego, jak problem sekretarki zbytnio upraszcza poszukiwanie życiowej wybranki. W klasycznym problemie kandydatki zawsze przyjmują ofertę zatrudnienia, co wyklucza odmowę, której doświadczył Trick. I nie można do nich wrócić, jeśli się je pominęło, inaczej niż w strategii Keplera.

W ciągu dziesięcioleci od postawienia problemu sekretarki przeanalizowano wiele różnych wariantów tego scenariusza, dochodząc do strategii optymalnego stopowania w kontekście różnych okoliczności. Tak na przykład możliwość odrzucenia spotyka się z prostym matematycznym rozwiązaniem: oświadczaj się szybko i często. Jeśli założymy, że ryzyko odrzucenia wynosi 50/50, taka sama analiza matematyczna, jaka przyniosła regułę 37%, mówi tu, że należy zacząć składać oferty po dojściu do jednej czwartej potencjalnych poszukiwań. W razie odrzucenia składaj dalej oferty każdej kolejnej dotychczasowo najlepiej wypadającej osobie, aż któraś ją przyjmie. W przypadku tej strategii prawdopodobieństwo ostatecznego sukcesu – czyli skutecznego oświadczenia się najlepszej kandydatce w puli – również wyniesie 25%. Nie tak źle jak na scenariusz, który godzi ewentualność odrzucenia z generalną trudnością poznania swoich własnych standardów.

Jeśli zaś chodzi o Keplera, odpowiedzialnością za nieumiejętność zakończenia poszukiwań obarczał swoją „ruchliwość i powątpiewanie”. „Czyż nie ma innego sposobu na pogodzenie mego zbolałego serca z losem – żalił się w liście do powiernika – niż przez zrozumienie, że niemożliwym jest spełnienie innych pragnień?” I w tym przypadku teoria optymalnego stopowania niesie jakąś dozę pocieszenia. Okazuje się, że ruchliwość i powątpiewanie są nie tyle oznakami defektu moralnego czy psychicznego, ile elementami najlepszej strategii w sytuacji, gdy otwarta jest furtka drugiej szansy. Jeśli można ponownie zwrócić się do wcześniejszej kandydatki, optymalny algorytm modyfikuje nieco regułę ogląd-pogląd: wprowadza dłuższy okres bez deklarowania się oraz opcję powrotu.

Przyjmijmy na przykład, że natychmiastowe oświadczyny są pewniakiem, złożone zaś poniewczasie są w połowie odrzucane. W takiej sytuacji z obliczeń wynika, że należy niezobowiązująco przyglądać się kandydatkom aż do osiągnięcia progu 61% osób, a następnie decydować się tylko, gdy któraś z pozostałych 39% okaże się najlepszą z dotychczasowych. Jeżeli po rozważeniu wszystkich kandydatur będziesz nadal singlem – jak Kepler – wracasz do najlepszej, która została pominięta. Również tym razem zostaje zachowana symetria między strategią a wynikiem; prawdopodobieństwo wyłuskania najlepszej partii w tym scenariuszu wynosi 61%.

U Keplera rozminięcie się rzeczywistości z klasycznym problemem sekretarki doprowadziło do szczęśliwego zakończenia. Ale klasyczny problem z małą korektą wyszedł też na dobre Trickowi. Po dostaniu kosza zrobił dyplom i podjął pracę w Niemczech. Tam „wszedł do baru, zakochał się w pięknej dziewczynie, po trzech tygodniach zamieszkał z nią, a potem zaprosił ją «na trochę» do Stanów”. Zgodziła się – i sześć lat później się pobrali.

Poznać się na tym, co dobre – pełna informacja

Pierwszy zestaw rozważanych przez nas zmiennych – odmowa i ponowny kontakt – przekształcił założenie klasycznego problemu sekretarki o tym, że oferty składane na czas są zawsze przyjmowane, a spóźnione zawsze trafiają do kosza. W odniesieniu do tych zmiennych najlepsze podejście pozostało takie jak pierwotnie: niezobowiązująco rozglądaj się przez pewien czas, a potem bądź gotów na błyskawiczną decyzję.

Jednak można zakwestionować jeszcze bardziej fundamentalne założenie problemu sekretarki. W klasycznej wersji nie wiemy o kandydatkach nic oprócz tego, jak wypadają we wzajemnym porównaniu. Nie mamy obiektywnego czy uprzedniego pojęcia o tym, co odróżnia dobrą od złej; ponadto gdy porównujemy dwie aplikantki, wiemy, która z nich jest lepsza, ale nie wiemy, w jakim stopniu przewyższa pozostałe. To uzasadnia absolutną konieczność fazy „rozglądania się”, w której ryzykujemy przepuszczenie znakomitej kandydatki w trakcie kalibrowania swoich oczekiwań i standardów. Matematycy nazywają taki rodzaj problemów optymalnego stopowania grami z wiedzą zerową.

Sytuacja taka jest zdecydowanie odległa od większości realnych poszukiwań mieszkania, partnera czy nawet sekretarki. Wyobraźmy więc sobie, że dysponujemy jakimś obiektywnym kryterium – na przykład że każda potencjalna sekretarka przeszła sprawdzian z pisania na komputerze i ma wynik wyrażony w centylach. Oznacza to, że wynik każdej z nich powie nam, gdzie plasuje się w gronie pozostałych, które wykonały test. Osoba uzyskująca wynik 51 jest tuż ponad średnią, mająca wynik 75 jest lepsza od trzech czwartych testowanych itd.

Załóżmy, że nasza pula kandydatek jest reprezentatywna dla całej populacji – nie zawiera odchyleń ani nie została dobrana arbitralnie. Ponadto załóżmy, że jedynym, co liczy się w przypadku kandydatek, jest szybkość pisania na komputerze. W tej sytuacji dysponujemy pełną informacją, jak nazywa się to w matematyce, i nasza sytuacja zmienia się diametralnie. „Nie są potrzebne żadne doświadczenia wstępne w celu ustalenia standardu – jak czytamy w fundamentalnej rozprawie z 1966 roku – a korzystny wybór może być niekiedy dokonany natychmiast.” Innymi słowy, jeśli kandydatka z wynikiem centylowym 95 trafi się jako pierwsza, możemy ją z miejsca i bez wahania zatrudnić – oczywiście pod warunkiem, że nie spodziewamy się trafić w puli na kogoś z wynikiem 96.

I w tym szkopuł. Jeśli naszym celem jest znowu zdobycie absolutnie najlepszej osoby na dane miejsce, ponownie musimy uwzględnić prawdopodobieństwo obecności jeszcze silniejszego kandydata. Niemniej posiadanie przez nas pełni informacji sprawia, że dysponujemy wszystkim, czego potrzeba do bezpośredniego obliczenia tej wielkości. Na przykład prawdopodobieństwo, że kolejna kandydatka będzie mieć wynik wyższy od 95 wynosi zawsze 1/20. Zatem decyzja, czy zakończyć rekrutację, sprowadza się wyłącznie do tego, jak wiele kandydatek czeka jeszcze na rozmowę. Pełnia wiedzy sprawia, że nie musimy rozglądać się przed wyrobieniem sobie poglądu. Zamiast tego możemy zastosować regułę progową, według której natychmiast akceptujemy aplikantkę lokującą się powyżej pewnego centyla. Aby ustalić ten próg, nie musimy przyjrzeć się na wstępie jakiejś grupie kandydatek. Musimy mieć natomiast jasną świadomość tego, jak długa jest jeszcze lista oczekujących.

Z rachunków wynika, że jeśli wciąż pozostaje wiele kandydatek w puli, należy przepuścić nawet bardzo dobrą w nadziei na znalezienie jeszcze lepszej, kiedy zaś liczba pozostających opcji zaczyna się kurczyć, powinniśmy być gotowi zatrudnić kogokolwiek, kto wybija się ponad średnią. To znany, choć niezbyt inspirujący wniosek: na bezrybiu i rak ryba. Ma on też drugą stronę: obfitość pozwala podnieść standardy. W obu przypadkach obliczenia wskazują, o ile konkretnie należy obniżyć lub podnieść standardy.

Najprostszym sposobem uchwycenia liczbowego wyrazu tego scenariusza jest zaczęcie od końca i cofanie się w myślach. Jeśli pula czekających na rozmowę kandydatek skurczyła się do jednej, jesteśmy oczywiście zmuszeni ją zatrudnić. Gdy jednak rozpatrujemy przedostatnią, pytanie brzmi: czy lokuje się powyżej 50 centyla? Jeśli tak, zatrudniamy ją; jeśli nie, warto postawić na ostatnią, bo prawdopodobieństwo, że będzie powyżej 50, wynosi z definicji 50/50. Analogicznie wybieraj trzecią kandydatkę od końca, jeśli ma wynik powyżej 69 centyla, czwartą od końca, jeśli jest powyżej 78, i tak dalej; jesteś tym wybredniejszy, im więcej masz kandydatek w zanadrzu. Bez względu na wszystko nigdy nie zatrudniaj osoby poniżej średniej, o ile nie wyczerpałeś absolutnie wszystkich opcji. (A skoro wciąż interesuje cię tylko znalezienie najlepszej osoby w puli, nie zatrudniaj nikogo, kto nie jest najlepszy z dotychczas widzianych.)

Szansa za zatrudnienie najlepszej kandydatki w tej wersji problemu sekretarki z pełną informacją wynosi 58%. To wciąż daleko od gwarancji, ale znacznie więcej niż wartość oferowana przez regułę 37% w grze z wiedzą zerową. Jeśli dysponujesz pełnią informacji, możesz odnieść sukces w ponad połowie przypadków bez względu na to, jak bardzo będzie się rozrastać pula.

Z gier z pełną informacją płynie nieoczekiwany i dość osobliwy morał. Masz większą szansę znaleźć złoto niż znaleźć miłość życia. Jeżeli oceniasz potencjalnych partnerów na podstawie dowolnego obiektywnego kryterium – powiedzmy, centyla ich dochodów – masz do dyspozycji znacznie więcej informacji niż wtedy, gdy nastawiasz się na niesprecyzowaną reakcję emocjonalną („miłość”), która może wymagać skalibrowania przez zbieranie doświadczeń i dokonywanie porównań.

Oczywiście nie ma obowiązku, by mierzonym parametrem był majątek netto czy tempo maszynopisania. Dowolny probierz, który zapewni pełną informację o pozycji kandydata w populacji, zmieni rozwiązanie z reguły ogląd-pogląd na regułę progową i spektakularnie podniesie szansę wybrania najwłaściwszej osoby w puli.

Istnieje wiele wariantów problemu sekretarki, które modyfikują inne jego założenia, zapewne bardziej zbliżając je do rzeczywistego poszukiwania partnera (czy asystentki). Jednak wnioski płynące z optymalnego stopowania nie ograniczają się do romansu czy zatrudniania. Dążenie do najlepszego wyboru w sytuacji, gdy opcje pojawiają się osobno, stanowi podstawową strukturę takich zadań, jak sprzedaż domu, parkowanie samochodu, a nawet zmiana pracy w momencie, gdy jest się na fali. I wszystko to są zadania, w takim czy innym stopniu, rozwiązane.

Kiedy sprzedawać

Jeśli zmienimy dwa inne aspekty klasycznego problemu sekretarki, przeniesiemy się z upojnego świata randek na rynek nieruchomości. Pisaliśmy już o wynajmowaniu mieszkania jako o problemie optymalnego momentu stopu, jednak posiadanie domu też nie jest od takiego problemu wolne.

Wyobraźmy sobie na przykład, że chcesz się pozbyć nieruchomości. Po rozmowie z kilkoma agencjami wystawiasz dom na sprzedaż. Trzeba go trochę odmalować, trochę uporządkować ogródek – a potem tylko czekać na spływające oferty. W miarę jak się pojawiają, musisz zwykle zdecydować, czy je przyjąć czy też odrzucić. Jednak odrzucenie pociąga za sobą pewien koszt – kolejny tydzień czy miesiąc kredytu hipotecznego podczas czekania na następna ofertę bez gwarancji, że będzie lepsza.

Sprzedawanie domu jest podobne do gry z pełną informacją. Znamy obiektywną wartość pieniężną poszczególnych ofert, co mówi nie tylko, która jest lepsza, ale i o ile. Ponadto dysponujemy informacjami o ogólnym stanie rynku nieruchomości, co pozwala na przewidywanie ogólnej wysokości oczekiwanych ofert. (Są to warunki analogiczne do informacji o centylach z egzaminu maszynopisania w poprzednim przykładzie.) Różnica polega na tym, że naszym celem niekoniecznie jest zgarnięcie absolutnie najlepszej oferty – chcemy raczej zapewnić sobie najlepszy ostateczny wynik finansowy. Skoro czekanie ma swój koszt wyrażony pieniężnie, dobra oferta złożona dzisiaj przewyższa nieco lepszą złożoną za kilka miesięcy.

Dysponując tymi informacjami, nie musimy wstępnie się rozglądać, by ustalić wysokość progu. Możemy ją przyjąć i ignorować wszystkie oferty poniżej, a zaakceptować pierwszą, która wyjdzie ponad tę założoną. Oczywiście jeśli dysponujemy tylko ograniczonymi zasobami, które wyczerpią się, o ile nie dokonamy transakcji w określonym czasie, albo oczekujemy uzyskania tylko kilku ofert, a potem spadku zainteresowania, musimy obniżać standardy w miarę zbliżania się tych granic (nie bez powodu nabywcy poszukują „zmotywowanych” sprzedających). Jeśli jednak nic takiego nie przypiera nas do muru, możemy skupić się na kosztowo-efektywnościowej analizie gry w czekanie.

Poniżej omówimy jeden z najprostszych przykładów: gdy dobrze znamy zakres cenowy, w którym będą się pojawiać oferty, i gdy wszystkie oferty z tego zakresu są równie prawdopodobne. Jeżeli nie musimy martwić się tym, że strumień ofert (czy swoich oszczędności) wyschnie, możemy skupić się wyłącznie na tym, co można zyskać lub stracić przez czekanie na lepszą transakcję. Jeśli odrzucimy aktualną ofertę, to czy prawdopodobieństwo uzyskania lepszej pomnożone przez to, o ile spodziewamy się, że będzie większa, przewyższy koszt oczekiwania na nią? Obliczenia są tu bardzo klarowne, zwracając nam cenę stopu w funkcji kosztu czekania na ofertę.

Wynik matematyczny jest niezależny od tego, czy sprzedajemy wielomilionową rezydencję czy obdrapaną ruderę. Pozostaje wrażliwy jedynie na różnicę między najwyższą a najniższą ofertą, jaką możemy otrzymać. Odwołując się do konkretnych wielkości, przekonamy się, że algorytm ten oferuje istotne praktyczne wskazówki. Powiedzmy, że spodziewasz się ofert w przedziale od 400 do 500 tysięcy dolarów. Jeżeli koszty oczekiwania są pomijalnie małe, możemy być niemal nieskończenie wybredni. Jeżeli koszt uzyskania kolejnej oferty wynosi tylko 1 dolara, zmaksymalizujemy swój przychód, czekając na nabywcę gotowego zapłacić 499 552,79 i ani centa mniej. Jeżeli oczekiwanie kosztuje 2000 dolarów od oferty, powinniśmy poprzestać na równych 480 000. Na mało aktywnym rynku, gdzie koszt oczekiwania to 10 000 dolarów od oferty, powinniśmy brać wszystko powyżej 455 279. I w końcu jeżeli oczekiwanie kosztuje połowę lub więcej przedziału oczekiwanych ofert – czyli w tym przypadku 50 000 dolarów – wstrzymywanie się ze sprzedażą nie przynosi żadnej korzyści; zrobimy najlepiej, przyjmując pierwszą ofertę i załatwiając sprawę. Żebracy nie grymaszą.

Należy zauważyć, że wysokość progu zależy w tym zadaniu wyłącznie od kosztu czekania. Ponieważ prawdopodobieństwo, że kolejna oferta będzie dobra, nigdy się nie zmienia (podobnie jak koszt czekania na nią), nie ma powodu, by cena stopu spadała w miarę coraz dłuższego oczekiwania bez względu na to, czy dopisuje nam szczęście czy nie. Ustanawiamy ją raz, jeszcze przed otrzymaniem pierwszej oferty, i konsekwentnie się jej trzymamy.

Laura McLay z University of Wisconsin–Madison, specjalistka w dziedzinie optymalizacji, przypomina sobie, jak skorzystała ze znajomości teorii optymalnego momentu stopu, gdy sprzedawała własny dom. „Pierwsza otrzymana przez nas oferta była znakomita – wyjaśnia – ale pociągała za sobą spory koszt, bo nabywca chciał, żebyśmy wyprowadzili się miesiąc wcześniej, niż byliśmy na to przygotowani. Była też druga, bliska jej oferta (…) ale jakoś wyczekaliśmy aż do uzyskania tej właściwej.” Dla wielu sprzedawców odrzucenie dobrej oferty, a tym bardziej dwóch, wydaje się doświadczeniem nadto targającym nerwy, zwłaszcza jeżeli kolejne propozycje nie są szczególnie ciekawe. Ale McLay nie ugięła się, tylko zachowała zimną krew. „Byłoby mi naprawdę ciężko – przyznaje – gdybym nie wiedziała, że po mojej stronie opowiada się matematyka.”

Zasada ta stosuje się do każdej sytuacji, w której otrzymuje się ciąg ofert i płaci jakąś cenę za poszukiwanie kolejnej lub za czekanie na nią. W konsekwencji użyteczność tej zasady rozciąga się daleko poza kwestię sprzedaży nieruchomości. Na przykład ekonomiści stosowali ten algorytm do stworzenia modeli poszukiwania pracy, które zgrabnie wyjaśniały pozornie paradoksalny fakt współwystępowania ludzi chętnych do podjęcia pracy i wakujących miejsc.

Ten wariant problemu optymalnego stopowania ma i inną zaskakującą właściwość. Jak widzieliśmy, możliwość powrotu do pominiętej okazji odegrała kluczową rolę w miłosnych perypetiach Keplera. Jednak w sprzedaży nieruchomości oraz poszukiwaniu pracy, nawet jeżeli można ponownie rozważyć dawniejszą ofertę i nawet jeśli mamy gwarancję, że jest wciąż aktualna, mimo wszystko nigdy nie powinno się tego robić. Jeżeli nie przekraczała twojego progu wtedy, nie będzie powyżej niego i teraz. To, co zapłaciłeś za kontynuowanie poszukiwań, to koszt nieodwołalnie poniesiony. Nie idź na kompromis, nie wątp. I nie oglądaj się za siebie.

Gdzie zaparkować

Widzę, że trzema największymi problemami administracyjnymi na kampusie są seks dla studentów, sport dla absolwentów i miejsca parkingowe dla wykładowców.

Clark Kerr, rektor University of California w Berkeley, 1958–1967

Inną dziedziną, w której problemy optymalnego stopowania zajmują znaczące miejsce – i w której oglądanie się za siebie jest generalnie niewskazane – są samochody. Kierowcy pojawiają się już w najstarszych doniesieniach o problemie sekretarki, a wymóg ciągłego podążania do przodu sprawia, że niemal każda decyzja w trakcie jazdy ma charakter problemu stopowania: szukanie restauracji, szukanie toalety i największa zmora miast – szukanie miejsca parkingowego. A kto lepiej nadaje się do rozmowy o tajnikach parkowania od człowieka, którego Los Angeles Times opisał jako „rockową gwiazdę parkowania” – profesora urbanistyki w UCLA Donalda Shoupa? Wybraliśmy się do niego z Kalifornii Północnej, uspokoiwszy go, że zarezerwujemy sobie dostatecznie dużo czasu na nieprzewidziane korki na drodze. „Co do uwzględniania «nieprzewidywanych korków», proponowałbym uwzględnić po prostu przewidywane” – odparł Shoup. Zapewne najlepiej znany jest z książki The High Cost of Free Parking (Wysoki koszt darmowego parkowania). Człowiek ten zrobił wiele, by posunąć do przodu dyskusję i zwiększyć społeczną świadomość tego, co faktycznie dzieje się, gdy ktoś dojeżdża do miejsca przeznaczenia samochodem.

Robi się żal biednych kierowców. Idealne miejsce parkingowe, według modelu Shoupa, to takie, w którym zoptymalizowano równowagę między opłatą w parkomacie, czasem (i niewygodą) dojścia do celu piechotą, czasem przeznaczonym na znalezienie miejsca parkowania (zmiennym zależnie od lokalizacji, pory doby itd.) oraz zużytym w tym celu paliwem. Równanie zmienia się wraz z liczbą pasażerów w aucie, którzy mogą solidarnie podzielić opłatę między siebie, nie mogą jednak podzielić czasu poszukiwania czy dochodzenia pieszo do celu. Jednocześnie kierowca musi wziąć pod uwagę, że obszar, na którym jest najwięcej miejsc parkingowych, może być też obszarem największego zapotrzebowania na nie; w parkowaniu występuje komponent teorii gier, skoro starasz się przechytrzyć innych kierowców, starających się przechytrzyć ciebie.[4] Mimo to wiele wyzwań parkowania sprowadza się do jednej liczby: stopnia zapełnienia. Jest to odsetek wszystkich miejsc parkingowych, które są aktualnie zajęte. Jeśli stopień ten jest niski, łatwo znaleźć dla siebie miejsce. Jeśli jest wysoki, znalezienie go graniczy z cudem.

Shoup przekonuje, że koszmar parkowania jest w dużej mierze konsekwencją uchwalania przez władze miejskie przepisów skutkujących wyjątkowo wysokim stopniem zapełnienia. Jeżeli koszt parkowania jest w danej lokalizacji zbyt niski (albo – o zgrozo! – zerowy), stanowi to wyraźną zachętę do zostawiania tam auta zamiast postawienia go trochę dalej i dotarcia na miejsce piechotą. Zatem wszyscy starają się tam zaparkować i większości się to nie udaje. W rezultacie ludzie tracą czas i spalają niepotrzebnie benzynę, krążąc w poszukiwaniu wolnego miejsca.

Pomysł Shoupa polega na zainstalowaniu elektronicznych parkomatów zdolnych do dostosowywania ceny do wzrastającego zapotrzebowania (rozwiązanie to testuje się w centrum San Francisco). Podstawą przy ustalaniu wysokości opłat jest tu stopień zapełnienia, który zdaniem Shoupa powinien wynosić około 85% – zdecydowanie mniej niż blisko stuprocentowe zastawienie krawężników w większości dużych miast. Badacz zauważa, że gdy stopień zapełnienia podnosi się z 90% do 95%, mieści się tylko 5% więcej samochodów, ale czas poszukiwania wolnego miejsca podwaja się.

Kluczowy udział stopnia zapełnienia w strategii parkowania staje się jasny, gdy zdajemy sobie sprawę, że parkowanie jest problemem optymalnego momentu stopu. Kiedy kierujemy samochodem, ilekroć widzimy wolne miejsce, musimy podjąć decyzję, czy je zajmujemy, czy też jedziemy dalej, by szukać szczęścia nieco bliżej celu.

Załóżmy, że znajdujesz się na nieskończenie długiej ulicy, wolne miejsca są równomiernie rozłożone, a ty chcesz maksymalnie ograniczyć odległość, którą będziesz musiał przejść do celu piechotą. Rozwiązaniem jest wówczas reguła ogląd-pogląd. Optymalnie zatrzymujący się kierowca powinien pominąć wszystkie wolne miejsca oddalone bardziej niż na określony dystans od celu, a potem zająć pierwsze puste. Dystans, w którym przerzucamy się z „oglądu” na „działanie”, zależy od odsetka miejsc, które będą zapewne zajęte, czyli od stopnia zapełnienia. Poniższa tabela podaje odległości dla pewnych znamiennych wielkości procentowych.

Jeśli stopień zapełnienia na tej nieskończenie długiej ulicy wynosi 99% (czyli jest tylko 1% wolnych miejsc), powinieneś zajmować pierwszy wolny kawałek przestrzeni, na który trafisz w odległości prawie 70 miejsc parkingowych przed celem (blisko pół kilometra). Jeśli jednak zastosuje się rozwiązanie Shoupa i stopień zapełnienia spadnie do 85%, nie będziesz musiał na poważnie rozglądać się za wolnym miejscem, póki nie znajdziesz się w połowie odległości między przecznicami.

Większość z nas nie jeździ jednak po idealnie prostych i nieskończenie długich drogach. Dlatego, podobnie jak z innymi problemami optymalnego momentu stopu, uczeni rozważyli różne modyfikacje tego wyjściowego scenariusza. Na przykład przeanalizowali strategię optymalnego parkowania, gdy kierowca może zawracać; gdy liczba wolnych miejsc spada w miarę zbliżania się do celu; gdy rywalizujemy z innymi kierowcami zmierzającymi w to samo miejsce. Ale bez względu na konkretne parametry zadania zwiększenie liczby wolnych miejsc zawsze ułatwia życie. Jest w tym swoiste przesłanie dla władz lokalnych: parkowanie nie jest prostą sprawą dysponowania zasobami (miejscami) i maksymalizacji ich użycia (zapełnienia). Parkowanie jest również procesem – problemem optymalnego stopowania – który pochłania uwagę, czas i paliwo, generując dodatkowe zanieczyszczenie powietrza oraz tłok na jezdni. Właściwa polityka miejska powinna obejmować wszystkie te zagadnienia. I – wbrew intuicji – właśnie puste miejsca parkingowe w bardzo poszukiwanych lokalizacjach mogą świadczyć, że sprawy są pod kontrolą.

Zapytaliśmy Shoupa, czy prowadzone przez niego badania, pozwalają jemu samemu zoptymalizować docieranie zatłoczonymi ulicami Los Angeles do uniwersytetu UCLA. Czy czołowy na świecie ekspert parkowania ma jakąś tajną broń?

Okazuje się, że tak: „Jeżdżę rowerem” – odparł.

Kiedy rzucić pracę

W 1997 roku pismo Forbes uznało Borysa Berezowskiego, którego majątek sięgał trzech miliardów dolarów, za najbogatszego człowieka w Rosji. Zaledwie dziesięć lat wcześniej utrzymywał się z pensji matematyka w Rosyjskiej Akademii Nauk. Zbił kapitał, korzystając ze znajomości gospodarczych, które nawiązał w trakcie przygotowań do powołania spółki usprawniającej współpracę zagranicznych producentów samochodów z radzieckim wytwórcą AvtoVAZ. Spółka ta stała się działającym na wielką skalę sprzedawcą aut produkowanych przez AvtoVAZ na zasadzie systemu ratalnego, który korzystał z szalejącej inflacji rubla. Dzięki funduszom uzyskanym z tego przedsięwzięcia Berezowski stał się współwłaścicielem AvtoVAZ-u, a następnie telewizji ORT i w końcu kompanii petrochemicznej Sibnieft. Współtworząc nową klasę oligarchów, brał udział w polityce, wspierając reelekcję Borysa Jelcyna w 1996 roku oraz wybór jego sukcesora Władimira Putina w 1999 roku.

Wtedy jednak karta Berezowskiego się obróciła. Niedługo po wyborze Putina na urząd prezydenta Berezowski publicznie sprzeciwił się zaproponowanym zmianom konstytucyjnym, które zwiększały kompetencje głowy państwa. Wytrwale ponawiana przez niego publiczna krytyka Putina doprowadziła do ochłodzenia w ich relacjach. W październiku 2000 roku Putin, zapytany o wypowiedzi Berezowskiego, odparł: „Państwo dysponuje pałką, którą uderza się tylko raz, ale w głowę. Jeszcze jej nie użyliśmy (…) W dniu, w którym naprawdę się zdenerwujemy, nie będziemy się wahać”. Berezowski opuścił Rosję na stałe w następnym miesiącu, udając się na emigrację do Anglii, skąd dalej krytykował reżim Putina.

W jaki sposób zdecydował, że nadeszła pora wyjechać z Rosji? Czy jest jakiś matematyczny sposób na analizę znanej porady, by „odchodzić, gdy jest się na fali”? Niewykluczone, że sam Berezowski rozważał tę sprawę, gdyż zagadnienia, którymi przez lata zajmował się jako matematyk, dotyczyły właśnie teorii stopowania; jest autorem pierwszej (i na razie jedynej) książki w całości poświęconej problemowi sekretarki.

Kwestię odchodzenia, gdy jest się na fali, analizowano w różnych postaciach, ale zapewne najadekwatniejszy do przypadku Berezowskiego jest – z przeproszeniem rosyjskich oligarchów – problem włamywacza. W zadaniu tym włamywacz ma możliwość dokonania serii rabunków. Każdy rabunek wiąże się z pewnym łupem i za każdym razem istnieje szansa na zgarnięcie go bez jakichkolwiek konsekwencji. Jeśli jednak włamywacz zostanie przyłapany, idzie do więzienia i traci wszystko, co zgromadził. Jakiego algorytmu powinien się trzymać, by zmaksymalizować oczekiwany zysk?

Istnienie rozwiązania tego problemu jest złą wiadomością dla scenarzystów filmów rabunkowych; gdy szajka stara się skłonić starego wygę do porzucenia emerytury ten jeden ostatni raz, szczwany złodziej powinien tylko wykonać drobne działanie. Co więcej, wynik jest generalnie zbieżny z oczekiwaniami intuicyjnymi: liczba rabunków, których powinno się dokonać, jest w przybliżeniu równa prawdopodobieństwu powodzenia podzielonemu przez ryzyko wpadki. Jeśli jesteś wykwalifikowanym włamywaczem i masz 90-procentową szansę skutecznego wykonania skoku (oraz 10-procentowe ryzyko utracenia wszystkiego), idź na emeryturę po 90/10 = 9 włamach. Niezręczny amator, mający szansę 50/50? Za pierwszym razem nie masz nic do stracenia, ale nie kuś losu więcej niż raz.

Mimo biegłości Berezowskiego w optymalnym stopowaniu jego historia skończyła się ponuro. Zmarł w marcu 2013 roku; został znaleziony przez ochroniarza w zamkniętej łazience w swym domu w Berkshire, z węzłem zawiązanym wokół szyi. W oficjalnej opinii wydanej po sekcji zwłok stwierdzono, że popełnił samobójstwo przez powieszenie się po utracie większości fortuny w serii głośnych procesów sądowych ze swymi wrogami z Rosji. Być może powinien był zatrzymać się wcześniej, gromadząc, powiedzmy, kilkadziesiąt milionów dolarów i nie wkraczając na teren polityki. Ale to niestety nie było w jego stylu. Jeden ze znających go matematyków, Leonid Bogusławski, opowiadał anegdoty o nim z czasów, gdy obaj byli młodymi naukowcami. Podczas wyprawy na narty wodne nad podmoskiewskie jezioro zepsuła się motorówka, którą mieli wynająć. Oto jak David Hoffmann relacjonuje to zdarzenie w książce Oligarchowie:

Podczas gdy reszta towarzystwa udała się na plażę i rozpaliła ognisko, Bogusławski z Berezowskim poszli do doku, by spróbować naprawić motorówkę (…). Przez trzy godziny rozłożyli silnik na drobne części i złożyli z powrotem, ale wciąż nie działał. Stracili większość toczącej się zabawy, jednak Berezowski upierał się, że trzeba próbować. „Robiliśmy wszystko” – wspomina Bogusławski. Berezowski nie chciał się poddać.

Co ciekawe, niepoddawanie się – nigdy – też trafiło do piśmiennictwa na temat optymalnego momentu stopu. Może nie wynika to z licznych omówionych do tej pory wariantów, ale istnieją takie sekwencyjne zadania decyzyjne, dla których nie ma optymalnej zasady stopowania. Prostym przykładem jest gra w „trzykrotność albo nic”. Wyobraź sobie, że masz jednego dolara i możesz zagrać w następującą grę tyle razy, ile zechcesz: postawić całość pieniędzy i mieć 50-procentową szansę otrzymania potrójnej stawki oraz 50-procentowe ryzyko utraty całości środków. Jak wiele razy powinieneś grać? Mimo prostoty tego zadania nie ma dla niego reguły optymalnego stopowania, gdyż w każdej kolejnej turze gry twój średni zysk jest nieco większy. Wychodząc od 1 dolara, skończysz z 3 w połowie przypadków i z 0 w drugiej połowie, zatem średnio można liczyć na zakończenie tej rundy z 1,5 dolara w kieszeni. Jeśli poszczęściło ci się na początku, dwiema możliwościami z pułapu 3 dolarów są 9 dolarów i 0 dolarów – co daje średni zwrot 4,5 w drugiej turze. Z obliczeń wynika, że zawsze powinieneś grać dalej. Jeśli jednak zastosujesz się do tej strategii, w końcu wszystko stracisz. Od niektórych problemów lepiej trzymać się z daleka, niż je rozwiązywać.

Zawsze bądź gotów się zatrzymać

Spodziewam się przejść przez świat ten jeden raz. Dlatego wszelkie dobro, które mogę uczynić, czy serdeczność, którą mogę okazać, niechaj dzieje się teraz. Niechaj nie odkładam tego ani nie zaniedbuję, bo nie przejdę tą drogą powtórnie.

Stephen Grellet

Dobrze spędź popołudnie. Nie możesz go przesunąć na kiedy indziej.

Annie Dillard

Przyglądaliśmy się konkretnym przypadkom ludzi stających w życiu wobec problemu optymalnego momentu stopu i zdajmy sobie sprawę, że codziennie natykamy się na takie sytuacje w tej czy innej formie. Bez względu na to, czy chodzi o sekretarki, narzeczone i narzeczonych albo mieszkania, życie jest pełne stopów. Naturalnie nasuwa się więc pytanie, czy – za sprawą ewolucji, edukacji lub intuicji – stosujemy się do najlepszych strategii.

Na pierwszy rzut oka wydaje się, że nie. Około dziesięciu badań wskazało na ten sam rezultat: ludzie mają skłonność zatrzymywać się zbyt wcześnie, w ogóle nie poznając najlepszego kandydata. Aby lepiej zrozumieć sens tych ustaleń, rozmawialiśmy z Amnonem Rapoportem z University of California w Riverside, który od ponad czterdziestu lat prowadzi eksperymenty na temat optymalnego stopowania.

Badanie, które najwierniej odzwierciedlało klasyczny problem sekretarki, zostało przeprowadzone przez niego wraz z Darrylem Sealem w latach dziewięćdziesiątych. Uczestnicy wielokrotnie stawali przed problemem sekretarki, za każdym razem mając do dyspozycji 40 lub 80 kandydatek. Ogólna częstotliwość znajdowania najlepszej z możliwych aplikantek była całkiem dobra: 31%, więc niedaleko optymalnych 37%. Większość ludzi postępowała w sposób spójny z regułą ogląd-pogląd, jednak w ponad czterech piątych podejmowali decyzję szybciej, niż powinni.

Rapoport mówi, że ma to zawsze w pamięci, gdy rozwiązuje problemy optymalnego stopowania we własnym życiu. Podczas szukania mieszkań zwalcza w sobie pokusę, by szybko się zdecydować. „Wbrew temu, że z natury jestem bardzo niecierpliwy i chciałbym wziąć pierwsze nadarzające się mieszkanie, staram się powstrzymywać!”

Ta niecierpliwość wskazuje na kolejny aspekt, którego nie uwzględnia klasyczny problem sekretarki: rolę czasu. W końcu przez cały okres poszukiwania sekretarki odczuwa się jej brak. Co więcej, przeznacza się dzień na przeprowadzanie rozmów, zamiast zajmować się swoją podstawową pracą.

Ten koszt stanowi potencjalne wytłumaczenie, dlaczego ludzie zatrzymują się za wcześnie, rozwiązując problem sekretarki w laboratorium. Seale i Rapoport pokazali, że jeśli koszt rozmowy z każdą kandydatką wynosi na przykład 1% wartości znalezienia najlepszej sekretarki, to optymalna strategia jest ściśle zbieżna z tym, kiedy ludzie przerzucali się z „oglądu” na „pogląd” podczas eksperymentu.

Tajemnica polega jednak na tym, że w badaniu Sealego i Rapoporta nie było przecież kosztu poszukiwania. Dlaczego więc ludzie w laboratorium zachowywali się tak, jakby on istniał?

Bo dla ludzi zawsze występuje koszt czasowy. Nie wynika on ze sposobu zaprojektowania eksperymentu. Wynika z naszego życia.

„Endogenne” koszty poszukiwania, których zwykle nie wychwytują modele optymalnego stopowania, mogą więc stanowić wyjaśnienie, dlaczego podejmowanie decyzji przez ludzi z reguły odbiega od wskazań tych modeli. Jak ujmuje to badacz optymalnego momentu stopu Neil Bearden, „po szukaniu przez pewien czas ludzie zwykle czują się znudzeni. Znudzenie to nie jest irracjonalne, ale trudne do rygorystycznego wymodelowania”.

Nie sprawia to jednak, że problemy optymalnego stopowania tracą na znaczeniu. Przeciwnie, zyskują jeszcze większe, bo upływ czasu zmienia podejmowanie każdej decyzji w optymalne zatrzymywanie.

„Teoria optymalnego stopowania zajmuje się kwestią wyboru momentu na podjęcie działania” – tak rozpoczyna się szanowany podręcznik na ten temat i trudno o bardziej zwięzły opis kondycji ludzkiej. Decydujemy o właściwym momencie na zakup akcji i o momencie na ich sprzedaż; ale także o właściwym momencie na otwarcie butelki wina kupionego na specjalną okazję, o właściwym momencie na przerwanie komuś wypowiedzi, o właściwym momencie na pocałowanie go.

Z tego punktu widzenia najbardziej fundamentalne, a jednocześnie najbardziej wątpliwe założenie problemu sekretarki – ścisła seryjność, nieodwołalny marsz w jednym kierunku – ujawnia się jako natura samego czasu. W związku z tym jawna przesłanka problemu optymalnego stopowania jest ukrytą przesłanką tego, co znaczy żyć. To właśnie zmusza nas do decydowania na podstawie możliwości, których jeszcze nie poznaliśmy; zmusza nas do godzenia się z wysokim odsetkiem fiaska, nawet gdy działamy optymalnie. Żadna opcja nie pojawia się powtórnie. Możemy w życiu spotkać podobne, ale nigdy dokładnie tę samą. Wahanie – bezczynność – jest równie nieodwołalne jak czyn. W takiej relacji, w jakiej kierowca znajduje się na jednokierunkowej drodze w stosunku do przestrzeni, my znajdujemy się w stosunku do czasu: tylko raz przemierzamy tę drogę.

Intuicyjnie uznajemy, że racjonalne podejmowanie decyzji oznacza wyliczenie wszystkich dostępnych opcji, dokładne zważenie każdej z nich, a następnie wybór najlepszej. Ale w praktyce, gdy zegar – i serce – tyka, niewiele aspektów podejmowania decyzji (czy, ogólniej mówiąc, myślenia) jest tak ważnych jak to, kiedy się zatrzymać.

1. W całej książce stosujemy pogrubienie wyłącznie do wyróżniania nazw kolejnych algorytmów. ↩

2. Przyjmując tę strategię, mamy 33-procentowe ryzyko odrzucenia najlepszej kandydatki i 16-procentowe ryzyko niepoznania jej wcale. Tłumacząc dokładniej, istnieje dokładnie sześć możliwych uszeregowań trzech aplikantek: 1-2-3, 1-3-2, 2-1-3, 2-3-1, 3-1-2 i 3-2-1. Strategia przesłuchania jednej, a potem wybrania tej, która jako pierwsza ją przewyższy, odnosi powodzenie w trzech z tych sześciu przypadków (2-1-3, 2-3-1, 3-1-2), a zawodzi w trzech pozostałych – dwa razy przez zbyt wielką wybredność (1-2-3, 1-3-2) i raz przed zbyt małą (3-2-1). ↩

3. W zasadzie odrobinę mniej niż 37%. Mówiąc precyzyjnie, matematycznie optymalna pula kandydatów do przeprowadzenia wywiadu wynosi 1/e – to ta sama stała e (= 2,71828…), która pojawia się w obliczeniach procentu złożonego. Ale nie musisz wymagać od siebie znajomości e do dwunastego miejsca po przecinku; dowolna wielkość między 35% a 40% zapewni częstotliwość sukcesu bardzo bliską maksymalnej. Więcej szczegółów matematycznych znajdziesz w przypisach na końcu książki. ↩

4. Więcej o obliczeniowych pułapkach teorii gier piszemy w rozdziale 11. ↩

2 Eksploracja/eksploatacja

Najnowsze czy najlepsze?

Burczy ci w brzuchu. Czy lepiej, żebyś poszedł do dobrze znanej i lubianej włoskiej restauracyjki czy do świeżo otwartego lokalu z kuchnią tajską? Czy masz zabrać z sobą długoletniego przyjaciela czy nowego znajomego, którego chcesz lepiej poznać? Uf, to już może lepiej zostać w domu. Ugotujesz coś, co na pewno ci się uda, czy przejrzysz Internet w poszukiwaniu nowych inspiracji? Hm, a może po prostu zamówisz pizzę? Wybierzesz taką „jak zwykle” czy zdecydujesz się na coś wyjątkowego? Zanim pojawi się możliwość wzięcia pierwszego kęsa, jesteś już całkiem wyczerpany. Nagle nawet pomysł, by włączyć płytę, pooglądać film albo poczytać książkę – czyli w końcu co zrobić? – nie jawi się już relaksująco.

Codziennie musimy dokonywać wyborów między opcjami, które różnią się pewnym konkretnym wymiarem: próbować czegoś nowego czy trzymać się tego, co sprawdzone? Intuicyjnie rozumiemy, że w życiu konieczna jest zdrowa równowaga między nowinkami a tradycją, podejmowaniem ryzyka a rozkoszowaniem się tym, co znane i lubiane. Podobnie jednak jak w przypadku dylematu szukać/brać podczas polowania na mieszkanie, odpowiedzi wymaga pytanie, jaka powinna być proporcja starego i nowego.

W klasycznej książce z 1974 roku Zen i sztuka obsługi motocykla Robert Pirsig krytykuje zwrot „Co nowego?” jako zagajenie rozmowy, argumentując, że potraktowany dosłownie „skutkuje niekończącą się paradą banałów i mody, jutrzejszego śmiecia”. Za zdecydowanie lepsze uznaje alternatywne: „Co dobrego?”.

Jednak rzeczywistość nie jest aż tak prosta. Świadomość, że każda „dobra” twoim zdaniem piosenka czy restauracja zaczynała skromnie jako „nowa” dla ciebie, sugeruje, że wciąż mogą istnieć w świecie jakieś nieznane ci dobre rzeczy – a zatem to, co nowe, warte jest poświęcenia przynajmniej części uwagi.

Pokryte patyną aforyzmy dają wyraz temu napięciu, ale go nie usuwają. Make new friends, but keep the old / Those are silver, these are gold (dosł. nawiązuj nowe przyjaźnie i pielęgnuj stare; pierwsze są srebrem, drugie złotem) czy There is no life so rich and rare / But one more friend could enter there (dosł. nie ma tak bogatego i wyjątkowego życia, by nie mógł zmieścić się w nim jeszcze jeden przyjaciel) wydają się słuszne, a przynajmniej ich rytm jest bez zarzutu. Nie przekazują nam jednak żadnej użytecznej informacji o proporcji, powiedzmy, srebra do złota, która zapewni dobre życie.

Informatycy pracują nad uchwyceniem tej proporcji od ponad pięćdziesięciu lat. Nadali jej nawet nazwę: kompromis eksploracja/eksploatacja (explore/exploit tradeoff).

Eksploracja/eksploatacja

W języku codziennym słowa „eksploracja” i „eksploatacja” są obarczone przeciwstawnymi konotacjami, tymczasem w informatyce ich konkretniejsze znaczenie jest neutralne. Z grubsza eksploracja oznacza w niej pozyskiwanie danych, a eksploatacja – wykorzystanie posiadanych informacji w celu uzyskania znanego i pożądanego rezultatu.

Intuicja wyraźnie podpowiada, że nie da się żyć bez penetracji otoczenia. Ale warto dodać, że równie opłakane skutki może przynieść zaniechanie eksploatacji. Eksploatacja rozumiana w duchu informatycznym cechuje wiele z tego, co uznajemy za najlepsze chwile życia. Eksploatacją jest spotkanie całej rodziny podczas wakacji. Podobnie usadowienie się miłośnika kryminałów w fotelu z kubkiem gorącej kawy i elektryzującą lekturą; albo wykonywanie największych przebojów przez zespół rockowy dla tłumu wniebowziętych fanów; albo zdanie przez małżeństwo egzaminu z tańca na czas do „ich własnej melodii”.

Co więcej, eksploracja może być przekleństwem.

Tak na przykład w muzyce fajne jest to, że nieustannie mamy różne nowe rzeczy do słuchania. Albo, jeśli jesteś dziennikarzem muzycznym, w muzyce okropne jest to, że nieustannie mamy nowe rzeczy do słuchania. Bycie dziennikarzem muzycznym to 120 procent eksploracji, tak że do słuchania nie pozostaje już nic oprócz nowości. Wielbiciele muzyki mogą wyobrażać sobie, że taka praca to raj, ale kiedy trzeba bez przerwy poznawać nowe utwory, nie ma się możliwości nacieszyć owocami swojego znawstwa – to szczególny rodzaj piekła. Niewielu ludzi zna to doświadczenie tak dobrze jak Scott Plagenhoef, były redaktor naczelny Pitchforka. O życiu krytyka mówi on tak: „Podczas pracy starasz się złapać okazje do posłuchania czegoś, czego naprawdę chcesz”. Desperacka potrzeba, by choć przez chwilę nie brodzić w zalewie nieznanych piosenek wątpliwej jakości, a posłuchać czegoś, co uwielbiał, była w jego przypadku tak silna, że na swój iPod ładował same nowe utwory, by fizycznie uniemożliwić sobie porzucenie obowiązków zawodowych w chwilach, gdy tak bardzo, bardzo chciało mu się posłuchać Smithsów. Dziennikarze muzyczni to męczennicy, eksplorujący zasoby po to, by inni mogli je eksploatować.

W informatyce napięcie między eksploracją i eksploatacją przyjmuje postać scenariusza zwanego problemem wielorękiego bandyty. Zastanawiająca nazwa bierze się od kolokwialnego określenia maszyny wrzutowej do gry w kasynach – jednorękiego bandyty. Wyobraź sobie, że wchodzisz do kasyna pełnego różnych maszyn wrzutowych, z których każda ma własne prawdopodobieństwo wygranej. Szkopuł w tym, że oczywiście nie wiesz z góry, jakie jest to prawdopodobieństwo. Dopóki nie zaczniesz grać, nie masz pojęcia, które maszyny są najbardziej lukratywne („luźne”, jak nazywają to zapaleńcy), a które są tylko worami na twoje monety.

Naturalnie jesteś zainteresowany maksymalizacją swojego całościowego przychodu. Jasne jest też, że będzie to wymagać pewnej kombinacji pociągania za wajchę różnych maszyn, by je wypróbować (eksploracja), oraz faworyzowania tych najbardziej obiecujących (eksploatacja).

By zorientować się w niuansach problemu, wyobraź sobie, że masz przed sobą tylko dwie maszyny. Na jednej zagrałeś 15 razy; 9 razy otrzymałeś wypłatę, a 6 razy nie. Na drugiej zagrałeś tylko 2 razy; raz dostałeś wypłatę, raz nie. Która jest bardziej obiecująca?

Proste podzielenie wygranych przez liczbę prób daje „wartość oczekiwaną” maszyny i gdy stosujemy tę metodę, pierwsza zdecydowanie wychodzi na prowadzenie. Jej wynik 9–6 daje wartość oczekiwaną 60%, podczas gdy wynik drugiej maszyny (1–1) daje wartość oczekiwaną tylko 50%. Ale to nie wszystko. W końcu dwie próby to niezbyt wiele. Pozostaje poczucie, że tak naprawdę nie wiemy jeszcze, jak dobra może być ta druga.

Wybór restauracji czy płyty jest w zasadzie tożsamy z postanowieniem, którą dźwignię pociągnąć. Jednak zrozumienie proporcji eksploracja/eksploatacja nie tylko pozwala podejmować lepsze decyzje kulinarne i muzyczne, lecz także dostarcza fundamentalnych spostrzeżeń na temat tego, jak nasze cele powinny zmieniać się z wiekiem oraz dlaczego najbardziej racjonalnym działaniem nie zawsze jest dążenie do wyboru tego, co najlepsze. Okazuje się ponadto, że tkwi w samej istocie projektowania stron internetowych oraz prób klinicznych – zagadnień, których zwykle nie wymienia się razem w jednym zdaniu.

Ludzie mają skłonność do rozpatrywania decyzji w izolacji, do znajdowania za każdym razem wyniku z najwyższą wartością oczekiwaną. Tymczasem decyzje niemal nigdy nie występują w izolacji, a wartość oczekiwana to nie wszystko. Jeśli myślisz nie tylko o następnej decyzji, ale o wszystkich, które masz podjąć w przyszłości w sprawie tych samych opcji, kapitalnego znaczenia dla tego procesu nabiera proporcja eksploracji do eksploatacji. W ten sposób, jak pisze matematyk Peter Whittle, problem bandyty „ucieleśnia w zasadniczej formie konflikt widoczny we wszelkim działaniu człowieka”.

A zatem którą z dźwigni powinieneś pociągnąć? To podchwytliwe pytanie. Odpowiedź w pełni zależy od sprawy, której jeszcze wcale nie poruszyliśmy: jak długo planujesz zabawić w kasynie.

Chwytaj pozostający czas

Carpe diem – wzywał Robin Williams w pamiętnej scenie ze Stowarzyszenia Umarłych Poetów z 1989 roku. – Chwytajcie dzień, chłopcy. Sprawcie, by wasze życie było nadzwyczajne.

To ogromnie ważna rada. Jednocześnie jest w pewnym sensie niespójna. Łapanie dnia i łapanie życia to całkowicie różne zadania. Mamy powiedzenie: „Jedz, pij i raduj się, bo jutro umrzemy”, ale być może powinniśmy mieć też jego odwrotność: „Zacznij się uczyć nowego języka czy gry na instrumencie i porozmawiaj o czymś z nieznajomym, bo życie jest długie i kto wie, jakie radości mogą z tego wyniknąć w ciągu lat”. Gdy bilansujemy ulubione doświadczenia z nowymi, nic nie ma tak wielkiego znaczenia jak interwał, w którym planujemy się nimi cieszyć.

„Nową restaurację wypróbowuję raczej, gdy wprowadzam się do miasta, niż kiedy się z niego wynoszę” – wyjaśnia informatyk i bloger Chris Stucchio, weteran zmagań z kompromisami eksploracja/eksploatacja w życiu zawodowym i prywatnym. „Teraz chodzę głównie do restauracji, które znam i lubię, bo wiem, że niedługo rozstanę się z Nowym Jorkiem. Kiedy kilka lat temu przeprowadziłem się do Puny w Indiach, jadałem absolutnie wszędzie, o ile tylko nie miałem obaw, że się tam otruję. Gdy zaś opuszczałem to miasto, wracałem do ulubionych miejsc, zamiast wypróbowywać nowe (…) Nawet gdybym miał znaleźć nieco lepszy lokal, poszedłbym już do niego tylko jeden czy dwa razy, więc po co ryzykować?”

Trzeźwiącym aspektem nastawienia na nowości jest to, że wartość eksploracji, czyli znalezienia nowej preferencji, zawsze z czasem spada, w miarę jak kurczą się szanse na korzystanie z niej. Odkrycie urokliwej kafejki ostatniego dnia pobytu w jakimś miejscu nie daje ci szansy na powtórne jej odwiedzenie.

Z drugiej strony wartość eksploatacji zawsze rośnie z czasem. Najfajniejsza kawiarnia, którą znasz dzisiaj, jest z definicji przynajmniej tak fajna jak najfajniejsza znana ci miesiąc temu (a jeśli znalazłeś od tamtej pory ciekawszą, ta może być jeszcze ciekawsza). Zatem penetruj, gdy będziesz miał czas na skorzystanie z uzyskanej wiedzy, a eksploatuj, gdy jesteś gotów na zbieranie żniwa. Strategię determinuje czas, który masz do dyspozycji, nazywany dalej interwałem.

Co ciekawe, skoro strategia jest zdeterminowana przez interwał, z jej obserwacji można wnioskować o interwale. Weźmy na przykład Hollywood. Spośród dziesięciu najbardziej kasowych filmów z 1981 roku, tylko dwa były sequelami. W 1991 roku trzy. W 2001 roku pięć. A w 2011 roku sequelami było aż osiem najbardziej dochodowych filmów. Wspomniany rok był rekordowy pod tym względem. I zaraz w 2012 rekord został pobity. W grudniu 2012 roku Nick Allen z wyczuwalnym znużeniem wypatrywał kolejnego roku:

Widzowie dostaną szóstą porcję X-Menów plus Szybkich i wściekłych 6, Szklaną pułapkę 5, Straszny film 5 i Paranormal Activity 5. Będzie też Iron Man 3 i Kac Vegas 3 oraz dwójki Muppetów, Smurfów, GI Joe i Złego Mikołaja.

Z perspektywy producenta sequel jest filmem z gwarantowaną bazą fanów: to dojna krowa, pewniak, eksploatacja. A takie przeładowanie pewniakami sygnalizuje podejście krótkoterminowe, jak u Stucchia, gdy wyprowadzał się z miasta. Sequele mają większą szansę stać się hitami w danym roku, skąd będą jednak pochodzić ukochane franczyzy w przyszłości? Taki sequelowy wysyp jest nie tylko godny pożałowania (a z pewnością za taki mają go krytycy filmowi); jest też nieco rozpaczliwy. Wchodząc w fazę niemal całkowicie eksploatacyjną, branża filmowa wydaje się sygnalizować przekonanie, że dochodzi do kresu swojego interwału.

Przeczucie to potwierdza rzut oka na ekonomię Hollywoodu. W latach 2007–2011 zyski największych studiów filmowych stopniały o 40%, a sprzedaż biletów spadała przez siedem z ostatnich dziesięciu lat. Jak czytamy w The Economist, „wielkie studia, zepchnięte w narożnik wzrastających kosztów i spadających dochodów, zareagowały większą liczbą produkcji traktowanych jako potencjalne hity: zwykle sequeli, prequeli czy podobnych tworów, w których występują postacie rozpoznawalne z innych filmów”. Innymi słowy, pociągają za dźwignie najlepszych maszyn, póki nie zostaną wyrzucone z kasyna.

Wygrywasz-zostajesz

Znalezienie optymalnego algorytmu, który dokładnie mówiłby, jak rozgryźć problem wielorękiego bandyty, okazało się niezwykle trudne. Jak relacjonuje Peter Whittle, w trakcie drugiej wojny światowej wysiłki znalezienia rozwiązania „tak wysysały energię i osłabiały umysły alianckich analityków (…) że padła sugestia, aby problem ten zrzucić nad terenem Niemiec jako idealny instrument intelektualnego sabotażu”.

Pierwsze zbliżenie się do rozwiązania nastąpiło już po wojnie, gdy matematyk z Columbia University Herbert Robbins pokazał istnienie prostej strategii, która, choć niedoskonała, daje pewne mile brzmiące gwarancje.

Robbins rozważał sytuację, w której są dokładnie dwie maszyny wrzutowe, i zaproponował rozwiązanie zwane algorytmem wygrywasz-zostajesz, przegrywasz-zmieniasz (Win-Stay, Lose-Shift): wybierz losowo dźwignię i pociągaj ją tak długo, jak długo zyskujesz. Gdy po którymś pociągnięciu nie uzyskasz wypłaty, przejdź do drugiej maszyny. Choć ta prosta strategia jest daleka od pełnego rozwiązania, Robbins udowodnił w 1952 roku, że systematycznie sprawdza się lepiej niż przypadek.

W ślad za Robbinsem cała seria artykułów analizowała zasadę „trzymania się wygranej”. Intuicyjnie uznajemy, że skoro zdecydowałeś się pociągnąć daną dźwignię i właśnie otrzymałeś wypłatę, powinno to podnieść jej wartość oczekiwaną i tym bardziej skłonić do dalszego jej pociągania. Rzeczywiście trzymanie się wygranej okazuje się elementem optymalnej strategii bilansowania eksploracji z eksploatacją w bardzo różnych warunkach.

Inną sprawą jest jednak człon „przegrywasz-zmieniasz”. Zmiana dźwigni za każdym razem, gdy jej użycie kończy się brakiem nagrody, byłaby posunięciem dość przedwczesnym. Wyobraź sobie, że byłeś w danej restauracji sto razy i zawsze dostawałeś wspaniały obiad. Czy jeden zawód wystarczy, byś przekreślił lokal? Dobrych opcji nie powinno się karać zbyt surowo za to, że nie są doskonałe.

Co istotniejsze, w zasadzie „wygrywasz-zostajesz, przegrywasz-zmieniasz” nie uwzględnia się interwału, w którym dokonujemy optymalizacji. Jeśli twoja ulubiona restauracja ostatnim razem cię rozczarowała, algorytm ten zawsze mówi, że masz udać się do innego lokalu – nawet jeśli jest to ostatni dzień, który spędzasz w tym mieście.

Niemniej wstępne prace Robbinsa nad problemem wielorękiego bandyty zaowocowały przyrostem piśmiennictwa i w ciągu kolejnych lat naukowcy dokonali znacznego postępu. Richard Bellman, matematyk z RAND Corporation, znalazł ścisłe rozwiązanie problemu dla przypadków, gdy z góry wiemy, ile będziemy mieć wszystkich opcji i okazji. Podobnie jak w problemie sekretarki z pełną informacją, sztuczka Bellmana polegała na tym, by myśleć od końca – zacząć od wyobrażenia sobie ostatniego pociągnięcia dźwigni i rozważyć, którą maszynę do tego wybrać, znając wszystkie możliwe rezultaty poprzednich decyzji. Ustaliwszy to, przechodzisz do przedostatniej okazji, potem jeszcze wcześniejszej i tak dalej aż do początku.

Wskazania wynikające z metody Bellmana są niepodważalne, ale w przypadku wielu dostępnych opcji i długiego pobytu w kasynie metoda może wymagać zawrotnej – jeśli nie wręcz niewykonalnej – ilości pracy. Ponadto nawet jeżeli pozwala obliczyć wszystkie możliwe warianty przyszłości, nie zawsze przecież da się określić, ile będziemy mieć okazji (a nawet ile mamy opcji). Z tych powodów problem wielorękiego bandyty pozostawał w praktyce nierozwiązany. Cytując Whittle’a, „niebawem wszedł do klasyki i stał się synonimem niewykonalności”.

Indeks Gittinsa

W matematyce nierzadko bywa tak, że przechodzi się od szczegółu do ogółu. W latach siedemdziesiątych korporacja Unilever zwróciła się do młodego matematyka Johna Gittinsa z prośbą o pomoc w optymalizacji testowania leków. Niespodziewanie zaowocowało to odpowiedzią na zagadkę matematyczną, która od pokolenia czekała na rozwiązanie.

Gittins, dziś profesor statystyki na Oksfordzie, zastanawiał się nad pytaniem zadanym przez Unilever. W jaki sposób najszybciej określić, który z kilku branych pod uwagę związków chemicznych ma największą szansę na skuteczne działanie przeciw danej chorobie? Gittins postarał się sformułować problem w jak najogólniejszej postaci: wielorakie opcje do wykorzystania, inne prawdopodobieństwo nagrody w odniesieniu do każdej z nich oraz ograniczone zasoby sił (albo pieniędzy czy czasu) do alokacji pomiędzy nie. Było to więc inne wcielenie problemu wielorękiego bandyty.

Zarówno komercyjne koncerny farmaceutyczne, jak i opieka zdrowotna, której służą, nieustannie stają przed sprzecznymi wymogami bilansowania eksploracji z eksploatacją. Firmy chcą inwestować fundusze badawcze w odkrywanie nowych leków, ale jednocześnie zapewnić sobie bezpiecznie dochodowe linie przetestowanych już produktów. Lekarze chcą przepisywać najlepsze istniejące leki, tak by pacjenci otrzymywali optymalną pomoc, ale jednocześnie chcą motywować branżę do badań eksperymentalnych, które mogą zaowocować jeszcze skuteczniejszymi lekami.

Warto zauważyć, że w żadnym z tych przypadków określenie właściwego interwału nie jest proste. W pewnym sensie koncerny i lekarze są zainteresowani nieokreśloną przyszłością. Firmy chcą teoretycznie istnieć bez końca, a dzisiejszy przełom medyczny umożliwia niesienie pomocy nawet tym ludziom, którzy się jeszcze nie urodzili. Niemniej teraźniejszość ma większy priorytet: wyleczenie pacjenta dzisiaj traktuje się jako cenniejsze niż wyleczenie (innego) pacjenta w przyszłym tygodniu czy roku; niewątpliwie to samo stosuje się do zysków. Ekonomiści odwołują się do tej idei przedkładania teraźniejszości nad przyszłość pod nazwą dyskontowania.

W odróżnieniu od poprzednich uczonych Gittins podjął problem wielorękiego bandyty, wychodząc z tych założeń. Uznał, że celem jest maksymalne zwiększenie wygranej nie w ustalonym interwale czasowym, tylko w przyszłości nieskończenie długiej, lecz dyskontowanej.

Takie dyskontowanie nie jest nam obce w codziennym życiu. Jeżeli spędzasz w jakimś mieście dziesięciodniowy urlop, powinieneś dokonywać wyborów restauracji z myślą o ustalonym interwale. Jeżeli jednak mieszkasz w tym mieście na stałe, nie jest to równie sensowne. Zamiast tego można wyobrazić sobie spadek wartości nagrody wraz z wydłużaniem się czasu jej wypłaty w przyszłości: bardziej obchodzi cię dzisiejszy posiłek niż ten, który zjesz jutro, a jutrzejszy bardziej niż przyszłoroczny, przy czym wielkość tych różnic zależy od szczegółów „funkcji dyskontującej”. Gittins poczynił tu założenie, że wartość przypisywana wypłatom maleje geometrycznie, czyli każda wizyta w restauracji jest warta stałemu ułamkowi ostatniej. Jeśli na przykład uważasz, że istnieje 1-procentowe ryzyko, iż dowolnego dnia zostaniesz potrącony przez autobus, powinieneś wyceniać jutrzejszy obiad na 99% wartości dzisiejszego już tylko z tego powodu, że możesz go w ogóle nie doczekać.

Wychodząc z założenia o dyskoncie geometrycznym, Gittins analizował strategię, która jego zdaniem dawałaby „przynajmniej dobre przybliżenie”: oszacować indywidualną wartość każdej dźwigni wielorękiego bandyty rozpatrywaną z osobna. Zrobił to dzięki dość nieoczekiwanemu wyobrażeniu: łapówki.

W popularnym teleturnieju Deal or No Deal uczestnik wybiera jedną z dwudziestu sześciu aktówek, które zawierają nagrody o wartości od centa do miliona dolarów. W trakcie gry co pewien czas pojawia się tajemnicza postać zwana Bankierem, oferując uczestnikowi różne kwoty w zamian za nieotwarcie wybranej teczki. Od grającego zależy, kiedy, a dokładniej przy jakiej kwocie, będzie skłonny pójść na pewny układ zamiast zdawać się na ryzyko nieznanej nagrody z teczki.

Gittins (wiele lat przed pierwszym odcinkiem tego teleturnieju) zdał sobie sprawę, że tak właśnie przedstawia się problem wielorękiego bandyty. W odniesieniu do każdej maszyny wrzutowej, o której nie wiemy nic lub prawie nic, istnieje pewna gwarantowana wypłata taka, że zaoferowanie jej nam zamiast gry pozwoliłoby z czystym sumieniem nie pociągać za dźwignię. Liczba ta – którą Gittins nazwał indeksem alokacji dynamicznej, a obecnie znana jako indeks Gittinsa – wskazuje oczywistą strategię w kasynie: zawsze pociągaj za dźwignię z najwyższym indeksem.

Strategia indeksowa okazała się więcej niż dobrym przybliżeniem. W pełni rozwiązuje problem wielorękiego bandyty z geometrycznie dyskontowanymi wypłatami. Kompromis między eksploracją a eksploatacją sprowadza się do prostszego zadania maksymalizacji pojedynczej, skorelowanej z nimi wielkości. Gittins skromnie wyraża się o swoim dokonaniu. „To nie całkiem jest ostatnie twierdzenie Fermata”, mówi z uśmiechem – jednak twierdzenie to rozwiało wiele wątpliwości dotyczących dylematu eksploracja/eksploatacja.

Niemniej faktyczne obliczenie indeksu Gittinsa dla konkretnej maszyny na podstawie znajomości jej historii oraz zmiennej dyskontowej pozostaje stosunkowo skomplikowane. Kiedy jednak indeks ten jest znany dla określonego zbioru założeń, można go stosować do dowolnego problemu tego typu. Co najważniejsze, nie ma znaczenia, ile dźwigni jest do dyspozycji, gdyż indeks oblicza się dla każdej z nich osobno.

W tabeli na poprzedniej stronie podajemy wartości indeksu Gittinsa aż do dziewięciu sukcesów i porażek, zakładając, że wygrana z następnego pociągnięcia jest warta 90% wypłaty od razu. Z wartości tych można korzystać do rozwiązywania rozmaitych codziennych problemów typu wielorękiego bandyty. Tak na przykład przy tych założeniach powinno się przedłożyć maszynę z historią 1–1 (i wartością oczekiwaną 50%) nad maszynę z historią 9–6 (i wartością oczekiwaną 60%). Znajdując odpowiednie pozycje w tabeli, przekonujemy się, że słabiej poznana maszyna ma indeks 0,6346, podczas gdy ta używana częściej – tylko 0,6300. Problem rozwiązany: w tym przypadku kuś los i eksploruj.

W tabeli wartości indeksu Gittinsa można poczynić kilka innych ciekawych obserwacji. Po pierwsze, widać tu zasadę wygrywasz-zostajesz w działaniu: gdy w dowolnym rzędzie podążamy z lewej na prawo, wartości indeksu zawsze rosną. Jeśli więc dana dźwignia jest właściwą do pociągnięcia i pociągnięcie to daje wypłatę, to (przechodząc do następnej pozycji w prawo) tym bardziej sensowne jest ponowne jej pociągnięcie. Po drugie, widać, gdzie reguła przegrywasz-zmieniasz wpakowałaby cię w kłopoty. Uzyskanie dziewięciu początkowych wygranych, po których następuje jedna porażka, daje indeks 0,8695, wciąż wyższy od większości innych w tabeli – zatem prawdopodobnie powinieneś trzymać się tej dźwigni przynajmniej do następnego pociągnięcia.

Ale chyba najciekawszym fragmentem tabeli jest lewa górna komórka. Historia 0–0 (całkowicie nieznana dźwignia) ma wartość oczekiwaną 0,5000, a indeks Gittinsa 0,7029. Innymi słowy, coś, z czym nie masz żadnego doświadczenia, jest atrakcyjniejsze od maszyny, o której wiesz, że wypłaca nagrodę siedem razy na dziesięć! Gdy idziemy w dół po przekątnej, zauważamy, że historia 1–1 daje indeks 0,6346, historia 2–2 daje 0,6010 itd. Jeśli taka 50-procentowa skuteczność się utrzymuje, indeks zbiega się w końcu do 0,5000, a doświadczenie potwierdza, że jest to nieszczególna maszyna, która zabiera „premie” pobudzające do dalszej eksploracji. Jednak zbieżność ta postępuje stosunkowo powoli, a premia za eksplorację ma silne działanie. Zauważmy zresztą, że nawet porażka w pierwszej próbie (czyli historia 0–1) daje indeks Gittinsa powyżej 50%.

Spójrzmy jednak, jak proporcja eksploracji do eksploatacji zmienia się wraz ze zmianą dyskontowania przyszłości. Tabela na str. 59 zawiera dokładnie takie same informacje co poprzednia, ale przy założeniu, że wypłata następnym razem jest warta 99% (a nie 90%) tej otrzymywanej niezwłocznie. Gdy przyszłość ma wagę niemal taką jak teraźniejszość, wartość zrobienia przypadkowego odkrycia w porównaniu ze zdaniem się na pewniaka dodatkowo rośnie. W tym przypadku zupełnie niesprawdzona maszyna o historii 0–0 jest warta gwarantowanych 86,99% wypłaty!

Indeks Gittinsa dostarcza więc formalnego, rygorystycznego uzasadnienia dla preferowania tego, co nieznane, pod warunkiem że będziemy mieli okazję do wyzyskania owoców wiedzy zdobytej podczas eksploracji. Jest to zgodne z porzekadłem: „trawa jest zawsze zieleńsza po drugiej stronie płotu”, i matematyka tłumaczy nam, dlaczego tak jest: nieznane ma szansę być lepsze, nawet jeśli oczekujemy, że będzie takie samo, czy nawet jeśli ma równe prawdopodobieństwo bycia gorszym. Niesprawdzony nowicjusz w kadrze jest wart więcej (przynajmniej na początku sezonu) niż weteran o porównywalnych umiejętnościach właśnie dlatego, że mniej o nim wiemy. Eksploracja ma wartość sama w sobie, gdyż testowanie nowości zwiększa szansę na znalezienie tego, co najlepsze. Zatem branie pod uwagę przyszłości, zamiast skupiania się tylko na teraźniejszości, pcha nas ku nowościom.

Indeks Gittinsa oferuje w ten sposób zadziwiająco klarowne rozwiązanie problemu wielorękiego bandyty. Niekoniecznie jednak stanowi ostatnie słowo w rozwiązaniu samej zagadki czy pomaga poruszać się po wszystkich bilansach eksploracji/eksploatacji w codziennym życiu. Po pierwsze, indeks Gittinsa jest optymalny tylko pod warunkiem spełnienia wyraźnie podanych założeń. Opiera się na geometrycznym dyskoncie przyszłych nagród, czyli uznawaniu każdego kolejnego pociągnięcia dźwigni za warte stały ułamek poprzedniego, tymczasem liczne eksperymenty z zakresu ekonomii behawioralnej oraz psychologii sugerują, że ludzie tak nie robią. Strategia Gittinsa traci optymalność również wtedy, gdy mamy do czynienia z kosztem zmiany opcji (trawa u sąsiada może wyglądać na bardziej zieloną, ale niekoniecznie uzasadnia to przejście przez płot, a tym bardziej wzięcie na siebie spłaty drugiej hipoteki). Co może jeszcze ważniejsze, trudno jest obliczać indeks Gittinsa na bieżąco. Jeśli nosisz przy sobie tabele z jego wartościami, jesteś w stanie zoptymalizować wybory obiadowe, ale konieczny do tego czas i wysiłek mogą nie być tego warte („Czekajcie, mogę rozwiązać nasz spór. Ta restauracja podobała się 29 razy z 35, a tamta sprawdziła się 13 razy z 16, zatem indeksy Gittinsa wynoszą… Hej, gdzie wszyscy się podziali?”).

Zapraszamy do zakupu pełnej wersji książki