Losowy przydział pozycji priorytetowych
Losowy priorytet (RP), zwany także losową dyktaturą szeregową (RSD), to procedura sprawiedliwego losowego przydziału - sprawiedliwego podziału niepodzielnych elementów między ludzi.
Załóżmy, muszą podzielić ) różne elementy. Ponieważ przedmioty są niepodzielne, niektórzy partnerzy z konieczności otrzymają mniej preferowane przedmioty (lub w ogóle nie otrzymają przedmiotów). RSD próbuje wprowadzić sprawiedliwość w tę sytuację w następujący sposób. Narysuj losową permutację agentów z rozkładu jednorodnego. Następnie pozwól im kolejno wybierać obiekt w tej kolejności (aby pierwszy agent w kolejności otrzymał pierwszy wybór i tak dalej).
Nieruchomości
RSD jest prawdziwym mechanizmem , gdy liczba przedmiotów jest co najwyżej liczbą agentów, ponieważ masz tylko jedną możliwość wybrania przedmiotu, a oczywiście dominującą strategią w tej okazji jest wybranie najlepszego dostępnego przedmiotu.
RSD jest ex-ante envy-free (EF), ponieważ każdy agent ma taką samą szansę na pojawienie się na każdej pozycji w zamówieniu. Oczywiście nie jest to ex post wolne od zazdrości, ponieważ agent, który jest ostatni w przypadkowej permutacji, może zazdrościć agentom, którzy pojawiają się wcześniej.
RSD zawsze daje wynik ex post efektywny w sensie Pareto (PE). Co więcej, w problemie przypisania każde deterministyczne przypisanie PE jest wynikiem SD dla pewnego uporządkowania agentów.
- ante PE, gdy agenci mają narzędzia Von Neumanna-Morgensterna nad losowymi alokacjami , tj. Efektywność Pareto jest silniejsza niż efektywność Pareto ex post). Załóżmy na przykład, że istnieją trzy agenty, trzy elementy, a narzędzia VNM to:
| Pozycja x | Pozycja y | Pozycja Z | |
|---|---|---|---|
| Alicja | 1 | 0,8 | 0 |
| Pion | 1 | 0,2 | 0 |
| Karol | 1 | 0,2 | 0 |
RSD daje każdemu agentowi 1/3 szansy na każdy obiekt (ponieważ ich preferencje względem pewnych obiektów są zbieżne) oraz profil oczekiwanego wektora użyteczności (0,6, 0,4, 0,4). Ale przypisanie pozycji y do Alicji na pewno i pozycji x, z losowo między Bobem a Karolem daje oczekiwany wektor użyteczności (0,8, 0,5, 0,5). Tak więc oryginalny wektor użyteczności nie jest efektywny w sensie Pareto .
Co więcej, gdy agenci mają porządkowe rankingi, RSD zawodzi nawet słabszą właściwość sd-efficiency .
Kiedy rankingi agentów nad obiektami są rysowane równomiernie losowo, prawdopodobieństwo, że alokacja podana przez RSD jest ex-ante PE, zbliża się do zera w miarę wzrostu liczby agentów.
Alternatywna reguła, reguła probabilistyczno-szeregowa , jest sd-efektywna (co implikuje ex-post PE) i sd-EF (co implikuje ex-ante EF), ale nie jest prawdziwa. Nie sposób korzystać z zalet obu mechanizmów:
- Przy kardynalnych addytywnych funkcjach użyteczności żaden mechanizm nie jest symetryczny, zgodny z prawdą i ex-ante PE.
- W przypadku funkcji użyteczności porządkowej żaden mechanizm nie jest efektywny pod względem SD, odporny na strategię i nie traktuje jednakowo równych.
Uogólnienia
Więcej przedmiotów niż agentów
Gdy obiektów jest więcej niż niektórzy agenci mogą otrzymać więcej niż jeden obiekt. Istnieje kilka sposobów rozszerzenia RSD na ten przypadek.
- Jednym ze sposobów jest zdefiniowanie przydziału dla każdego agenta (tak, aby suma przydziałów była równa liczbie obiektów) i umożliwienie każdemu agentowi po kolei pobierania elementów do jego limitu. Ta procedura pozostaje strategiczna , ale jest bardzo niesprawiedliwa.
- Innym sposobem jest pozwolenie każdemu agentowi na wybranie jednego przedmiotu, a następnie wykonanie kolejnej rundy, w której każdy agent wybierze jeden przedmiot, aż wszystkie przedmioty zostaną zabrane; prowadzi to do alokacji pozycji okrężnej . Ta procedura jest bardziej sprawiedliwa, ale nie jest uzasadniona strategią .
- Obie procedury są szczególnymi przypadkami sekwencji kompletacji .
Ogólne podejmowanie decyzji
RSD można zdefiniować dla bardziej ogólnego ustawienia, w którym grupa musi wybrać jedną alternatywę z zestawu alternatyw. W tym ustawieniu RSD działa w następujący sposób: najpierw losowo permutuj agentów. Zaczynając od zestawu wszystkich alternatyw, poproś każdego agenta w kolejności permutacji, aby wybrał swoją ulubioną alternatywę(e) spośród pozostałych alternatyw. Jeśli po uwzględnieniu preferencji wszystkich agentów pozostaje więcej niż jedna alternatywa, RSD losuje równomiernie te alternatywy. We wspomnianym wcześniej ustawieniu podziału pozycji alternatywy odpowiadają alokacji pozycji do agentów. Każdy agent ma w swoich preferencjach duże klasy równoważności, ponieważ jest obojętny między wszystkimi alokacjami, w których otrzymuje ten sam przedmiot.
W tym ogólnym ustawieniu, jeśli wszyscy agenci mają ścisłe preferencje co do alternatyw, RSD ogranicza się do wylosowania agenta i wybrania alternatywy, która najbardziej mu się podoba. Ta procedura jest znana jako losowa dyktatura (RD) i jest wyjątkową procedurą, która jest skuteczna i odporna na strategię , gdy preferencje są ścisłe. Jednak gdy agenci mogą mieć słabe preferencje, żadna procedura rozszerzająca RD (w tym RSD) nie spełnia zarówno wydajności, jak i odporności na strategię.
Zobacz też
- Strona dotycząca uczciwego losowego przydziału porównuje RSD z innymi procedurami rozwiązywania tego samego problemu, takimi jak reguła probabilistyczno-szeregowa .
- Strona o mechanizmie dyktatury opisuje, że RSD jest ogólną zasadą wyboru społecznego - niekoniecznie przydziału przedmiotów.