Machaj: Algorytm najlepszego wyboru nie tylko w małżeństwie

17 października 2012 Audio komentarze: 13

Autor: Mateusz Machaj
Wersja PDF

Posłuchaj komentarza w wersji audio (mp3, 5,62MB).

Zaczęło się od opracowanego w latach 60. XX w. algorytmu, który opisywał przykład nazywany „problemem stabilnego małżeństwa”. Nie chodziło o odpowiedź na odwieczne pytanie, jak żyć, lecz o dość prosty problem obliczeniowy, zademonstrowany na przykładzie małżeństw. Algorytm ten ma dla jego twórców wagę przyznanej właśnie nagrody Nobla.

A wygląda to tak: powiedzmy, że mamy w pomieszczeniu 10 mężczyzn i 10 kobiet. Załóżmy, że każde z nich może stworzyć własną osobistą listę preferencji pokazującą, kto według niego samego jest najbardziej atrakcyjny. Każdy mężczyzna może uszeregować subiektywnie atrakcyjność kobiet od najlepszej (pierwsza) do najmniej atrakcyjnej (dziesiąta). Każda kobieta jest w stanie uszeregować analogicznie, jak podobają się jej mężczyźni.

Algorytm Davida Gale’a i Lloyda Shapleya oferuje „rozwiązanie” tej sytuacji. Mianowicie otwieramy niekończącą się konkurencję. Mężczyźni w pierwszej rundzie oświadczają się tej kobiecie, która jest najwyżej w ich skali preferencji. W skrajnym przypadku wszystkie kobiety otrzymają propozycję i sprawa będzie od razu zamknięta. W drugim skrajnym jedna z nich otrzyma 10 propozycji. Pośrodku będą takie przypadki, że niektóre panie otrzymają kilka opcji, a inne pozostają bez propozycji. W każdym wariancie te, które propozycje otrzymają, udzielają odpowiedzi albo odmownej, albo „niech będzie, dopóki nie trafi się ktoś lepszy” (cóż za stereotypowe podejście do kobiet!).

Nadchodzi runda druga. Mężczyźni, którzy usłyszeli w zasadzie odpowiedź pozytywną, nie mają potrzeby w kolejnej rundzie szukać kogoś następnego, bo mają zarezerwowaną najlepszą — na razie — opcję z dostępnych. Ci, którzy nie otrzymali takiej odpowiedzi, w następnej rundzie wybierają opcję drugą z możliwych. I znowu część z nich otrzymuje odpowiedzi pozytywne, a część negatywne. Niektóre kobiety, które już wcześniej wyraziły zgodę warunkową, mogą otrzymać lepszą propozycję. Wtedy zrezygnują ze swojego poprzedniego wybranka, a ten zostanie uwolniony, by złożyć w następnej rundzie propozycję kobiecie, która jest na ich liście na niższym miejscu. I tak do skutku — osiągnięcia pewnej „równowagi”.

 

Aby dwoje chciało na raz

Jaki jest efekt końcowy tego wyścigu? Jak przedstawia to opisany przez Gale’a i Shapleya algorytm, efekt będzie „stabilny”. W końcu osiągniemy taki efekt równowagowy, że powstaną małżeństwa „stabilne”, to znaczy takie, w których nie będzie bodźca do rozpadu. Każdy mężczyzna będzie miał możliwie najlepszą dostępną kobietę.

Oczywiście niektórzy z nich woleliby być z inną, ale ta inna nie wolałaby być z nimi. Ta inna preferuje tego męża, na którego się zgodziła. Dlatego sytuacja jest „stabilna” — jest równowaga, ponieważ nie istnieje hipotetyczna para, którą woleliby stworzyć jakiś mężczyzna i jakaś kobieta. Dlatego mówimy o tym jako o „problemie stabilnego małżeństwa”.

Gdyby na przykład trzymać się zasady, że wybory są trwałe (i raz dobrana para musiałaby się trzymać razem), to efekt końcowy byłby zupełnie inny. Niektóre kobiety wybrałyby mężczyzn gorszych, choć za jakiś czas mogłyby dostać lepszą ofertę. W obawie jednak przed przegraniem w tej rozgrywce zaakceptowałyby wybór gorszy. Podobnie mężczyźni — mogliby oni celować w opcje mniej korzystne dla siebie, ponieważ obawialiby się, że w wypadku przegrania o najlepszą, wolne pozostałyby kobiety w ich oczach jeszcze mniej atrakcyjne.

 

Praktyczna strona teoretycznego modelu

Przykład jest bardzo obrazowy, chociaż „problem stabilnego małżeństwa” oczywiście kompletnie nie stosuje się do związków małżeńskich z pewnych powodów, do których wrócimy poniżej. Na koniec wspomnimy także o ograniczeniach stosowania takich algorytmów. Najpierw jednak powiedzmy o ciekawych zastosowaniach praktycznych.

Za praktyczne ich zastosowanie odpowiada przede wszystkim drugi tegoroczny noblista — Alvin Roth (David Gale zmarł kilka lat temu). Wskazany powyżej algorytm nie jest przecież bardzo trudny. Stanowi łamigłówkę matematyczną, którą w zasadzie spodziewalibyśmy się już dawno mieć skrupulatnie opracowaną. A badania nad nią i jej bardziej skomplikowanymi wariantami trwają dopiero kilkadziesiąt lat.

Pierwszy praktyczny przykład to system rekrutacji do szkół, widoczny również na polskim podwórku. Kandydat do szkoły (obojętnie, czy średniej, czy wyższej) staje przed problemem, którą szkołę wybrać. Problem w tym, że jeśli wybierze najlepszą i się nie dostanie, to w kolejnej rundzie (skoro już miejsca będą zajęte) będzie musiał pójść do jednej z gorszych.

W ten sposób w szkole o średnim poziomie mogą znaleźć się najgorsi uczniowie, bo ci od nich lepsi próbowali aplikować do najlepszej szkoły i się nie dostali. Teraz będą musieli pójść do tych słabszych. Sprawa się rozwiązuje, jeśli zastosuje się powyższy algorytm. Miejsca w szkołach wystarczy potraktować jak „kobiety” z modelu, a kandydatów uznać za „mężczyzn” (feministki uspokajam, wśród tych „mężczyzn” z modelu są również prawdziwe kobiety). Kandydaci mogą uporządkować szkoły pod względem tego, która jest dla nich najlepsza, a które mniej ważne (jak atrakcyjność „kobiet” we wspomnianym modelu). Szkoły natomiast mają swoje kryteria, którzy kandydaci są ich zdaniem najlepsi (czyli odpowiedzi „póki co akceptuję”).

W efekcie zastosowania algorytmu można stworzyć „stabilne” rozwiązanie, czyli takie sparowanie miejsc w szkołach i uczniów, że nie istnieje rozwiązanie lepsze. To znaczy, że nie zdarzy się sytuacja po sparowaniu, w której jakiś student powie, że wolałby inną szkołę i jednocześnie ta szkoła by powiedziała, że wolałaby go przyjąć na miejsce innej osoby, która już wcześniej się zgłosiła. Jeśli przyjęlibyśmy zasadę, że kandydaci wybierają szkołę tylko raz (ich wybory są trwałe), to może się to skończyć sytuacją „niestabilną”. Istniałaby taka szkoła, do której wolałby trafić student i jednocześnie ta szkoła wolałaby, żeby on do niej trafił zamiast kogoś innego.

 

Pomoc w wyborze szkoły lub szpitala

Na bazie tego algorytmu zbudowano na przykład w USA system National Resident Matching Program (NRMP), który dotyczy absolwentów medycyny. Każdy z nich szuka szpitala, żeby zostać w nim „rezydentem”. Znowu przykład bardzo podobny do sytuacji z małżeństwami i szkołami. W pewnym momencie rozpoczynała się konkurencja o rezydentów i szkoły oferowały miejsca osobom na dwa lata przed stażem. Ci natomiast woleli opóźniać swoje decyzje, żeby mieć pewność, czy nie znajdą czegoś lepszego.

Obecnie stosowany algorytm pozwala stworzyć sytuację stabilną. Kandydaci mogą przedstawić swoją listę preferencji; od najlepszej dla nich placówki do najgorszej. A szkoły przedstawiają swoje kryteria wyboru. Algorytm generuje równowagowe rozwiązanie. Rezydent przy istniejącym wyborze trafia w najlepsze miejsce z możliwych. Nie istnieje taki szpital, w którym rezydent wolałby być i jednocześnie ten szpital wolałby go mieć u siebie zamiast kogoś innego. Jako ciekawostkę podam fakt, że sprawa NRMP trafiła przed sąd antytrustowy jako przykład zmowy.

Jak widać, algorytmy zajmujące się problemami „sparowania” wydają się bardzo istotne dla naszego życia. Jeszcze bardziej dobitnym przykładem może być sytuacja na rynku organów. W USA podobnie jak w większości krajów zakazany jest handel organami. Dopuszczalne jest jednak przekazanie komuś organu bez osiągania z tego bezpośrednich korzyści „majątkowych”; charytatywnie, na przykład koledze, żonie, córce (bez „motywacji” majątkowej, cokolwiek miałoby to znaczyć…) etc.

Okazuje się jednak, że dopuszczalny jest barter organowy. Przykładowo Karolina Kowalska z Białegostoku potrzebuje przeszczepu nerki, a jej mąż Krzysztof Kowalski nie może jej przekazać nerki ze względu na brak dostatecznej zgodności organów. Powiedzmy, że w podobnej sytuacji jest Natalia Nowak z Poznania, która potrzebuje przeszczepu, a organy jej męża Norberta Nowaka również nie wykazują zgodności. Załóżmy jednak, że taka zgodność występuje między organami Krzysztofa i Natalii oraz Karoliny i Norberta. Wzajemne oferowanie sobie organów — barter — jest w tej sytuacji dopuszczalne prawem.

Przykład jest dosyć prosty, bowiem dotyczy dwóch par, ale moglibyśmy go sobie bardziej skomplikować do trzech par, czterech, dziesięciu… Wtedy algorytm dopasowania osób staje się bardziej skomplikowany. I tutaj prace Rotha, inspirowane opracowaniami Gale’a i Shapleya okazują się bardzo korzystne (sam Roth bezpośrednio uczestniczył w praktycznych implementacjach tych opracowań). Kilka lat temu przeprowadzono operację, gdzie taki barter obejmował dziesięć przypadków. Wystarczyłoby, żeby jeden z dawców nie zgodził się na transplantację, a wszystkie operacje musiałyby zostać odwołane. Trudno o bardziej dobitny przykład tego, jak ważne mogą być badania na temat procesu „parowania” i dziedziny market design (projektowania rynku).

 

Życie bogatsze od modeli

Na koniec warto powiedzieć o tym, że powyższe zagadnienia mają w gruncie rzeczy zastosowanie do wąskich problemów (jakkolwiek ważnych). Jednocześnie trzeba zdawać sobie sprawę z ich ograniczeń. Wystarczy niektóre przypadki trochę bardziej skomplikować, a problemy są nierozwiązywalne. Na przykład wystarczy, że w przypadku małżeńskim dopuścimy możliwość powstawania par homoseksualnych. Wtedy rozwiązanie stabilne nie istnieje. W przypadku rezydentów i programu NRMP wystarczy, że dodamy pary małżeńskie i fakt, że pary lekarskie aplikują do szpitali i chciałyby razem znaleźć się w jednym miejscu. Wtedy już pojawiają się problemy kalkulacyjne.

Przypadek małżeństw jest tak naprawdę kuriozum, gdy pomyślimy o rzeczywistym życiu. W końcu nikt nie ustala swojej sztywnej hierarchii wyboru drugiej osoby. Na nasze decyzje ma wpływ to, co rzeczywiście robimy, a nie jakaś mapa psychologicznych preferencji. Jeśli podejmujemy decyzję o wyborze tej czy innej osoby, to później może to mieć wpływ na to, czy inna osoba nas będzie chciała. W dodatku do tego dochodzi prosty fakt zmienności naszych preferencji. A jeszcze ciekawsze jest to, że algorytm faworyzuje stronę aktywną — mężczyźni, będąc stroną wybierającą, trafiają najlepszą możliwą opcję. Jeśli odwrócimy zasadę i uznamy kobiety za stronę aktywną, to efekt końcowy będzie inny niż w wariancie poprzednim.

Tak, drogie panie, trzeba walczyć o swoje, bo inaczej najlepsze dostępne opcje uciekną — a tak na poważnie, to nie należy tego algorytmu przekładać w tym wypadku na dobór życiowego partnera.

Jeśli odrobinę skomplikujemy warunki wejściowe, to stajemy przed czymś, co specjaliści nazywają problemami „NP-trudnymi” i „NP-zupełnymi”, czyli takimi, których się w zasadzie nie da rozwiązać. Są zbyt złożone, aby dało się je rozwikłać w sensownym czasie. W istocie takimi problemami są na przykład decyzje gospodarcze, o tym „co, jak, kiedy i dla kogo” produkować.

Dlatego również projekty socjalistyczne centralnego planowania nie są w stanie stworzyć sensownej gospodarki, choć to temat na inną dyskusję. Nawet z punktu widzenia znajomości sytuacji i danych wyjściowych są to zbyt trudne problemy. A jeśli do tego dodamy rzeczywistą nieznajomość tych danych, a także ich nieprzewidywalną zmienność (niepewność życia gospodarczego), to sytuacja staje się jeszcze bardziej problematyczna.

Mimo to kwestia modelowania „parowania” ma, jak widać, bardzo szerokie zastosowania praktyczne i może być niezwykle przydatna. Warto jednak przy tym zdawać sobie sprawę z jej ograniczeń, bo jak mawiał Harry Callahan, „człowiek musi znać swoje ograniczenia”.

Tekst ukazał się także na portalu Obserwator finansowy.

Podobał Ci się artykuł?

Wesprzyj nas
Mateusz Machaj

O Autorze:

Mateusz Machaj

dr hab. Mateusz Machaj - Instytut Nauk Ekonomicznych Uniwersytetu Wrocławskiego, założyciel oraz główny ekonomista Instytutu Misesa.

Pozostałe wpisy autora:

13 Komentarze “Machaj: Algorytm najlepszego wyboru nie tylko w małżeństwie

  1. Czyż nie na podobnej zasadzie opiera się (a przynajmniej opierał, kiedy ja aplikowałem na studia) system naboru do szkół wyższych po reformie 1998r bodajże? Choć nie taki sformalizowany, jak opisany w artykule, raczej wynikający z posiadanych możliwości.

    W końcu pamiętam, że mając w ręku świadectwo maturalne, którego wyniki miały mi dać informację, do której szkoły mam szansę aplikować, wybrałem dwie, gdzie złożyłem dokumenty, oczywiście mając własną skalę preferencji w głowie. Po dostaniu się do dwóch szkół, zrezygnowałem z tej w mojej opinii gorszej uwalniając miejsce dla studentów, którzy się nie dostali nigdzie, na kolejne terminy naboru. Może przełożenia 1:1 nie ma, ale działało chyba podobnie.

    Przy czym wątpię, aby Pan Minister Handke i MEN swego czasu korzystali z ww. modelu;)

  2. A jeszcze co do ostatniego akapitu artykułu, to w zasadzie ujawnia się własnie, biorąc pod uwage mój przykład, ograniczenie dość istotne.

    W przykładzie z małżeństwami jakoś umyka element czasu…potrzebnego do rozpoznania, czy faktycznie to jest dobry wybór. W moim przypadku mogło się zdarzyć, że po załóżmy pół roku studiowania okazało się (zakładam, że zdobyłem jakoś wiedzę o tej drugiej uczelni), że lepiej byłoby wybrać drugą szkołę, ale koszt zmiany byłby może już zbyt wysoki (ograniczenia formalne, opóźnienie w realizacji programu), żebym zmiany chciał dokonać.

    Dlatego dodałbym aczasowość modelu jako negatyw, czyli że nie uwzględnia jakoś specjalnie czasu na realizację tych dopasowań, albo inaczej, nie dodaje (co autor artykułu zaznaczył), kosztów zmiany decyzji.

  3. Witam,

    a czy ta ,,sytuacja stabilna” czy inaczej ,,pewna równowaga” nie jest po prostu równowagą Nasha? Nash nie dostał Nobla, mimo że jego twierdzenie jest bardziej uniwersalne (o wiele szerszy zakres), bo to matematyk:)

    Pozdrawiam

  4. dostał, dostał – chodziło mi bardziej o podkreślenie różnego poziomu ,,uniwersalności” przy tej samej nagrodzie; źle to sformułowałem.

  5. @JM
    czas nie jest uwzględniony, bo to model równowagowy – wg niego w końcu musi być równowaga. A w praktyce może jej nigdy nie być, bo skala preferencji się zmienia (nigdy nie dojdzie do sytuacji idealnej, bo zawsze ktoś zmieni zdanie).

    W rekrutacji na uczelnie każdy może składać i zabierać papiery, uczelnie ogłaszają kolejne listy i nie ma modelowania – jest żywa oddolna organizacja 😉
    Oczywiście można użyć modelu, by „udowodnić”, że jest to dobry system (ale to będzie sofizmat, nie dowód – patrz uwaga o czasie). Za to do liceów rekrutacją zajmuje się komp na podstawie powyższego algorytmu (i tu już używa się modelu).

  6. A co do dokładnego modelowania rzeczywistości to problemem nie jest NP-zupełność, a chaotyczność układu.

    NP-zupełne to problemy, dla których nie ma (prawdopodobnie) szybkiego algorytmu.

    Chaotyczne układy mogą podlegać łatwym regułom, ale małe błędy danych na początku kończą się dużymi błędami na końcu, stąd model musiałby być nieskończenie dokładny, by mieć sens 😉

  7. „Jeśli odrobinę skomplikujemy warunki wejściowe, to stajemy przed czymś, co specjaliści nazywają problemami „NP-trudnymi” i „NP-zupełnymi”, czyli takimi, których się w zasadzie nie da rozwiązać. Są zbyt złożone, aby dało się je rozwikłać w sensownym czasie”

    Pierwsza kwestia – dla wielu problemów NP-zupełnych możemy znaleźć algorytmy aproksymacyjne działające w czasie wielomianowym. Rozwiązanie co prawda nie będzie optymalne, ale też może się od niego niewiele różnić.

    Drugie zagadnienie – jeśli centralny planista nie może łamać praw złożoności obliczeniowej, to nie widzę powodu by „rozproszony algorytm” wykonywany przez aktorów na wolnym rynku się w tym względzie różnił.

    Ba, jeśli pójdziemy dalej z matematyczno-technicznymi analogiami – każdy informatyk wie, że 2 procesory potrzebują ponad 2 razy więcej czasu niż jeden taki sam procesor na rozwiązanie tego samego problemu, a im więcej procesorów dokładamy tym mniejsza będzie korzyść.

    Miło tu dla odmiany poczytać o bardziej matematycznych zagadanieniach, zwłaszcza, że lubię grafy, ale z tym argumentem ze złożnoności niestety trochę Pan nie trafił.

  8. „każdy informatyk wie, że 2 procesory potrzebują ponad 2 razy więcej czasu niż jeden taki sam procesor na rozwiązanie tego samego problemu”
    No niekoniecznie, tak by było dla algorytmów sekwencyjnych, ogólniejsze jest prawo Adahla.

    Za to rozproszony planista może działać jak niedeterministyczna maszyna Turinga, więc problemy NP z definicji rozwiązywać w czasie wielomianowym 😉

    No ale jak już pisałem, tu nie chodzi o klasę złożoności, a o chaos w matematycznym sensie

  9. ad 9

    Dziękuję za odzew.

    Powiedziałbym tak: rynek nie ma wiele wspólnego z algorytmami.
    Co do 2 procesów działających na raz, to chodzi właśnie o to, że one nie rozwiązują tego samego problemu. Przy działalności rynkowej mamy kłótnie o to, jak problem rozwiązać. I też nie chodzi o to, kto lepszy algorytm stosuje, bo nie algorytmy konkurują.

    pozdrowienia

  10. „Za to rozproszony planista może działać jak niedeterministyczna maszyna Turinga, więc problemy NP z definicji rozwiązywać w czasie wielomianowym ;)”
    No spoko, ale chyba z przerwami na wykładniczy rozrost populacji. A to znowu nam ogranicza czas od dołu.

    Pomijając, że kompletnie pokręciłem wypowiedź z powodu późnej godziny – właśnie o implikacje prawa Amdahla mi chodziło.

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *

Nasi darczyńcy