Kierownikiem projektu jest dr hab. Marcin Anholcer, prof. UEP
Opis projektu:
Mając dane zbiór dóbr i zbiór uczestników mających określone preferencje względem tych dóbr, celem jest przydzielenie dóbr do uczestników w taki sposób, aby zostały spełnione pewne kryteria...
Opis projektu:
Mając dane zbiór dóbr i zbiór uczestników mających określone preferencje względem tych dóbr, celem jest przydzielenie dóbr do uczestników w taki sposób, aby zostały spełnione pewne kryteria sprawiedliwości. Przyjmujemy, że preferencje uczestników są określone za pomocą tzw. funkcji wartościujących, odpowiadających subiektywnej ocenie wartości dobra.
Można wziąć pod uwagę różne kryteria sprawiedliwości. Najczęściej stosowane to brak zazdrości (EF), proporcjonalność (PROP), równość (EQ) i optymalność w sensie Pareto (PO). EF oznacza, że po przydziale dóbr żaden uczestnik nie zazdrości innemu (tj. każdy jest przekonany, że jego własny pakiet dóbr jest co najmniej tak samo dobry jak pakiet kogokolwiek innego względem funkcji wartościującej).
W przypadku PROP każdy jest przekonany, że otrzymał przynajmniej proporcjonalną część wszystkich dóbr. EQ zakłada, że wszyscy są przekonani, iż otrzymali dokładnie taki sam udział (w odniesieniu do swojej funkcji wartościującej). PO oznacza, że nie ma innego przydziału, w którym każdy miałby nie gorzej niż w obecnym, a przynajmniej jeden uczestnik bezwzględnie lepiej.
Wszystkie wymienione kryteria są dobrze przeanalizowane, a spełniające je alokacje można znaleźć w przypadku dóbr nieskończenie podzielnych. Jednak w przypadku dóbr niepodzielnych niektóre z nich nie muszą istnieć. Z tego powodu rozważane są pewne relaksacje, w szczególności brak zazdrości względem dowolnego dobra (EFX), gdzie dla każdej pary agentów i, j oraz dla każdego dobra g, nawet jeśli agent i zazdrości agentowi j, zazdrość ta znika, jeśli j pozbędzie się g i sprawiedliwość względem podziału maksimin (MMS), gdzie każdy uczestnik otrzymuje co najmniej tyle samo (z punktu widzenia swojej funkcji wartościującej), ile wynosi maksimum ze wszystkich możliwych alokacji wartości najniżej wycenianego elementu alokacji. Chociaż MMS jest znaczącym osłabieniem PROP, nie musi istnieć, podczas gdy nie wiadomo, czy EFX zawsze istnieje, czy nie. Z tego powodu rozważane są również warianty aproksymacyjne obu kryteriów.
Niekompletność informacji występująca w realnym świecie skłoniła nas do rozważenia lokalnych wariantów problemu. Załóżmy, że rozważamy problem sprawiedliwego podziału w sieci społecznościowej (lub grafie wiedzy). Teraz każdy uczestnik porównuje otrzymany zbiór dóbr nie ze wszystkimi innymi agentami, a tylko z tymi widocznymi w sieci. W naturalny sposób zdefiniujemy lokalne wersje kryteriów sprawiedliwości i przeanalizujemy ich właściwości. W szczególności interesują nas dwie miary: lokalny brak zazdrości
względem dowolnego dobra (LEFX), odpowiednik EFX, oraz sprawiedliwość względem podziału maksimin (LMMS), odpowiednik MMS. Planujemy również przeanalizować aproksymacyjne wersje tych kryteriów sprawiedliwości.
Chcemy zidentyfikować struktury grafów wiedzy, które gwarantują istnienie lokalnie sprawiedliwego podziału. Ponieważ część dowodów będzie miała charakter konstruktywny, przedstawimy również kilka algorytmów sprawiedliwego podziału i przeanalizujemy ich właściwości. Na koniec chcemy zbadać relacje między sprawiedliwością lokalną i globalną. Łatwo zauważyć, że niektóre lokalnie sprawiedliwe alokacje mogą być niesprawiedliwe w skali globalnej. Naszym celem jest zbadanie, jak daleko lokalnie sprawiedliwa alokacja może być od globalnej sprawiedliwości i jak ta odległość jest związana ze strukturą grafu wiedzy. W przyszłości może to być podstawą modeli pozwalających wyjaśnić, w jaki sposób struktura powiązań społecznych może wpływać na poziom nierówności w społeczeństwie. Nasze wstępne badania pokazują, że w tym kontekście ważne są nie tylko oczywiste metryki grafu, takie jak średnica czy średni stopień, ale także niektóre inne parametry, takie jak liczba chromatyczna.
W naszej pracy będziemy wykorzystywać głównie metody matematyczne typowe dla ekonometrii, ekonomii matematycznej i badań operacyjnych, takie jak dedukcja, indukcja matematyczna i algebra macierzowa.
W przypadku dowodów niekonstruktywnych planujemy zastosować bardziej zaawansowane narzędzia: metodę probabilistyczną, algebrę wielomianów oraz twierdzenia o dualności, w tym KKT (po relaksacji warunku niepodzielności). Wyniki eksperymentów symulacyjnych będą analizowane przy użyciu standardowych metod statystycznych.