Algorytmiczna sprawiedliwość: Trudny problem sprawiedliwego podziału
Międzynarodowy zespół badaczy udowodnił, że znalezienie sprawiedliwego podziału niedzielnych dóbr, wolnego od zazdrości, jest zadaniem o fundamentalnej trudności obliczeniowej, nawet gdy w grę wchodzą tylko dwie osoby.
Problem sprawiedliwego podziału jest stary jak ludzkość. Od podziału łupów po polowaniu, przez dziedziczenie majątku, aż po przydział obowiązków domowych – ludzie od zawsze szukali metody, która zadowoli wszystkich i nie pozostawi poczucia krzywdy. O ile w przypadku zasobów podzielnych, jak tort czy pole uprawne, istnieją eleganckie i stosunkowo proste rozwiązania, o tyle prawdziwe wyzwanie pojawia się przy podziale dóbr niepodzielnych: samochodu, domu, dzieł sztuki czy kolekcji monet. Nie da się ich przeciąć na pół bez utraty wartości. Informatycy i ekonomiści od lat zmagają się z tym zagadnieniem, próbując znaleźć algorytmiczne recepty na ludzką zazdrość. Celem jest osiągnięcie stanu, w którym nikt nie wolałby otrzymać zestawu przedmiotów przydzielonego komuś innemu. Ta prosta z pozoru definicja sprawiedliwości, znana jako "brak zazdrości" (envy-freeness), w świecie niedzielnych dóbr okazuje się matematyczną i obliczeniową łamigłówką.
Przez lata za praktyczny i osiągalny standard uważano tak zwany "brak zazdrości aż do jednego przedmiotu" (EF1). W tym scenariuszu dana osoba może zazdrościć drugiej, ale poczucie krzywdy zniknęłoby, gdyby z zestawu rywala usunąć jeden, najcenniejszy z jej perspektywy, przedmiot. Algorytmy pozwalające osiągnąć stan EF1 są znane i działają stosunkowo szybko, nawet dla wielu uczestników podziału. Jednak EF1 to kompromis. Znacznie bardziej pożądanym i silniejszym gwarantem sprawiedliwości jest "brak zazdrości aż do dowolnego przedmiotu" (EFX). Tutaj zazdrość musi zniknąć po usunięciu z cudzego zestawu dowolnego, nawet najmniej wartościowego przedmiotu. Gwarantuje to znacznie większą odporność na poczucie niesprawiedliwości. Mimo że matematycznie udowodniono, iż taki podział EFX zawsze jest możliwy, przez dekadę nikt nie potrafił odpowiedzieć na fundamentalne pytanie: czy istnieje wydajny algorytm, który potrafi go znaleźć?
Przełomu dokonał międzynarodowy zespół naukowców, w skład którego weszli Haris Aziz, Aris Filos-Ratsikas, Simon Mackenzie, Søren Kristoffer Stiil-Harving i Alexandros Voudouris. W swojej przełomowej pracy udowodnili, że problem znalezienia sprawiedliwego podziału EFX jest fundamentalnie trudny. Nawet w najprostszym, wydawałoby się, scenariuszu – z udziałem zaledwie dwóch osób – zadanie to należy do klasy złożoności obliczeniowej PPAD. Oznacza to, że jest skrajnie nieprawdopodobne, aby istniał prosty i szybki algorytm, który poradzi sobie z każdym przypadkiem podziału EFX. Dowód ten zakończył wieloletnie poszukiwania i stał się jednym z najważniejszych wyników w dziedzinie algorytmicznej teorii gier ostatniej dekady.
Czym jest klasa złożoności PPAD? W odróżnieniu od słynnej klasy NP, gdzie trudność polega na samym znalezieniu jakiegokolwiek rozwiązania, w problemach PPAD mamy gwarancję, że rozwiązanie istnieje. Trudność polega na jego odnalezieniu. Można to porównać do próby znalezienia wyjścia z ogromnego, skomplikowanego labiryntu, w którym każda ścieżka ostatecznie gdzieś prowadzi. Wiemy, że wyjście jest, ale błądzenie po omacku w poszukiwaniu właściwej drogi może zająć niewyobrażalnie dużo czasu. Problemy PPAD często dotyczą znajdowania punktów równowagi w złożonych systemach, takich jak równowaga Nasha w teorii gier. Kwalifikacja problemu podziału EFX do tej klasy jest sygnałem dla informatyków: zamiast szukać jednego, uniwersalnego i szybkiego algorytmu, należy skupić się na algorytmach przybliżonych lub takich, które działają wydajnie tylko w określonych, szczególnych warunkach.
Co ciekawe, badacze odkryli również istotny wyjątek od tej reguły. Okazuje się, że problem staje się obliczeniowo łatwy, jeśli obie osoby mają identyczne wartościowanie przedmiotów, czyli zgadzają się co do tego, ile warty jest każdy z dzielonych obiektów. W takiej sytuacji istnieje wydajny algorytm, który bez problemu znajduje podział EFX. Fundamentalna trudność nie leży więc w samym akcie dzielenia, ale w konieczności pogodzenia subiektywnych i często rozbieżnych preferencji uczestników. To właśnie różnice w postrzeganiu wartości generują obliczeniową złożoność, która uniemożliwia znalezienie prostego rozwiązania.
Odkrycie to ma doniosłe implikacje, wykraczające daleko poza mury akademickich ośrodków. W erze cyfrowej algorytmiczny podział zasobów staje się codziennością. Dotyczy to zarówno alokacji mocy obliczeniowej w chmurze, gdzie wiele firm walczy o dostęp do tych samych serwerów i procesorów, jak i podziału czasu antenowego dla reklam czy nawet ustalania grafików pracy w dużych korporacjach. Badania te stanowią swoiste "ograniczenie prędkości" dla projektantów systemów opartych na sztucznej inteligencji. Pokazują, że dążenie do absolutnej, gwarantowanej matematycznie sprawiedliwości może być zadaniem niepraktycznym z obliczeniowego punktu widzenia.
W praktyce firmy i instytucje projektujące takie systemy stają przed wyborem: mogą postawić na słabszą, ale obliczeniowo tanią gwarancję sprawiedliwości (jak EF1) albo zainwestować ogromne zasoby obliczeniowe w poszukiwanie idealnego podziału EFX, bez gwarancji znalezienia go w rozsądnym czasie. Wyniki badań zmuszają do refleksji nad tym, jakiego rodzaju sprawiedliwości oczekujemy od algorytmów i na jakie kompromisy jesteśmy gotowi. Co istotne, praca naukowców rozwiązała problem dla dwóch uczestników. Pytanie o złożoność obliczeniową dla trzech i więcej osób pozostaje otwarte, stanowiąc kolejne wielkie wyzwanie dla świata nauki. Tym samym, choć dokonano historycznego kroku, saga o algorytmicznym poszukiwaniu sprawiedliwości jest daleka od zakończenia.