Uczciwe losowe przypisanie

Sprawiedliwe losowe przypisanie (zwane także probabilistycznym dopasowaniem jednostronnym ) jest rodzajem problemu sprawiedliwego podziału .

W problemie przypisania (zwanym także problemem alokacji domów lub jednostronnym dopasowywaniem ) jest m obiektów i muszą one być przydzielone między n agentów, tak aby każdy agent otrzymał co najwyżej jeden obiekt. Przykłady obejmują przydzielanie zadań pracownikom, pokojów współlokatorom, akademików studentom, przedziałów czasowych użytkownikom wspólnej maszyny i tak dalej.

Ogólnie rzecz biorąc, uczciwy przydział może być niemożliwy do osiągnięcia. Na przykład, jeśli Alicja i Batya wolą pokój wschodni od zachodniego, tylko jedno z nich go dostanie, a drugie będzie zazdrosne. W losowego przydziału sprawiedliwość osiąga się za pomocą loterii. Tak więc w powyższym prostym przykładzie Alicja i Batya rzucają uczciwą monetą, a zwycięzca otrzyma wschodni pokój.

Historia

Losowy przydział jest już wspomniany w Biblii : zastosowano loterię, aby przydzielić ziemie Kanaanu między plemiona Izraela (Liczb 26:55).

W Stanach Zjednoczonych loterie służyły do ​​przydzielania terenów publicznych osadnikom (np. Oklahoma w 1901 r.) oraz do przydzielania widm radiowych nadawcom (np. FCC 1981-1993). Loteria jest nadal używana do przyznawania zielonych kart .

Metody

Istnieje kilka sposobów rozszerzenia metody „rzutu monetą” na sytuacje, w których agentów jest więcej niż dwóch i mogą oni mieć różne relacje preferencji względem obiektów:

  • Losowy priorytet (RP, inaczej Random Serial Dictatorship lub RSD) to bardzo prosty mechanizm, który wymaga od agentów jedynie uporządkowania poszczególnych przedmiotów. Wybiera losową kolejność priorytetów przedmiotów i pozwala każdemu agentowi po kolei wybrać swój ulubiony pozostały przedmiot.
  • Probabilistic Serial (PS) to kolejny mechanizm, który działa tylko z porządkowym rankingiem przedmiotów. Agenci „zjadają” swoje ulubione pozostałe przedmioty ze stałą prędkością, a ułamek, który każdy agent zdołał zjeść, to jego/jej prawdopodobieństwo zdobycia tego przedmiotu.
  • Równowaga konkurencyjna wynikająca z równych dochodów (CEEI) to mechanizm rynkowy: każdy przedmiot jest postrzegany jako towar podzielny. Każdy agent otrzymuje równy budżet w walucie fiducjarnej, następnie agenci mogą handlować, aż do osiągnięcia równowagi cenowej . Jest to bardziej złożony mechanizm, który wymaga, aby agenci mieli pełne kardynalne funkcje użyteczności (lub alternatywnie ranking porządkowy w loteriach).

Nieruchomości

Efektywność

Jedną z pożądanych właściwości reguły losowego przydziału jest efektywność Pareto (PE). Istnieją trzy warianty PE:

  • Ex-post PE oznacza, że ​​po ustaleniu ostatecznej alokacji żadna inna alokacja nie jest lepsza dla jednego agenta i co najmniej tak dobra dla innych. Wszystkie trzy powyższe zasady (RP, PS i CEEI) są ex post PE.
  • Ex-ante PE jest silniejszą właściwością, istotną dla agentów o użyteczności kardynalnej. Oznacza to, że żadna inna loteria nie jest lepsza dla jednego agenta i co najmniej tak dobra dla innych. CEEI jest ex-ante PE, gdy agenci porównują loterie na podstawie ich oczekiwanej użyteczności.
  • Możliwy PE (lub sd-PE) jest właściwością pośrednią, odpowiednią dla agentów o użyteczności porządkowej . Oznacza to, że alokacja jest ex-ante PE dla niektórych funkcji wyceny zgodna z porządkowym rankingiem agentów. PS jest możliwe - PE, ale RP nie.

W przypadku PE implikacje są następujące: ex ante → sd(możliwe) → ex post .

Uczciwość

Inną pożądaną właściwością jest brak zazdrości (EF). Ponownie, istnieją trzy warianty EF:

  • Ex post EF oznacza, że ​​po ustaleniu ostatecznej alokacji żaden agent nie preferuje alokacji innego agenta. Żadna reguła nie spełnia tej silnej właściwości; w rzeczywistości znalezienie alokacji niepodzielnych obiektów ex post może być niemożliwe.
  • Ex-ante EF jest słabszą właściwością, istotną dla agentów o użyteczności kardynalnej. Oznacza to, że żaden agent nie preferuje loterii innego agenta. CEEI to oczekiwane użyteczności ex ante EF wrt.
  • Niezbędny EF (lub sd-EF) to właściwość pośrednia, istotna dla agentów o użyteczności porządkowej . Oznacza to, że alokacja jest ex ante EF (patrz poniżej) dla wszystkich funkcji wyceny zgodnych z porządkowym rankingiem agentów. PS jest konieczne-EF, ale RP nie. RP jest słabo ex-ante sd-EF; jest to EF, gdy agenci porównują loterie według dominacji leksykograficznej (ld-EF).

Dla EF kierunek implikacji jest przeciwny do kierunku efektywności: ex-post → sd(niezbędne) → ex-ante .

Prawdomówność

Trzecią pożądaną właściwością jest prawdomówność (zwana także strategią). Ponownie mamy trzy warianty:

  • Prawdomówność ex ante, istotna dla agentów z kardynalną użytecznością, oznacza, że ​​żaden agent nie może wygrać lepszej loterii, zgłaszając fałszywe wyceny. Jest to silna właściwość, której nie spełnia żaden nietrywialny mechanizm.
  • Możliwa prawdomówność jest słabszą właściwością, istotną dla agentów o użyteczności porządkowej . Oznacza to, że agent nie może uzyskać stochastycznie dominującej loterii, zgłaszając fałszywy ranking. Ta słaba właściwość jest spełniona przez PS, gdy wszystkie rankingi są ścisłe i na osobę przypada co najwyżej jeden obiekt. W tym układzie jest to również zgodne z prawdą z dominacją leksykograficzną ( ld-truthful ). Nie jest usatysfakcjonowany, gdy rankingi są słabe.
  • Konieczna prawdomówność jest silniejszą właściwością, istotną dla agentów o użyteczności porządkowej . Oznacza to, że agent zgłaszający fałszywy ranking zawsze otrzymuje loterię zdominowaną stochastycznie. Tę mocną właściwość spełnia RP i można ją zgodnie z prawdą rozszerzyć także na ogólny przypadek, gdy przedmiotów jest więcej niż ludzi.

Poniższa tabela porównuje właściwości różnych reguł (kolumny RP i PS są oparte na ):

#przedmioty ≤ #agenci #przedmioty > #agenci
RP PS CEEI RP PS CEEI
Efektywność: PE ex post Możliwy PE ex-ante PE NIE możliwe PE ex-ante PE
Uczciwość : Słaby sd-EF;

ld-EF

 Niezbędny EF EF ex-ante Słaby sd-EF sd-EF EF
Prawdomówność: Koniecznie zgodny z prawdą Możliwe sd-prawdziwe; ld-truthful [ścisłe preferencje]

Brak [słabe preferencje]

NIE sd-prawdziwy* NIE NIE

Niemożliwe kombinacje

Niektóre kombinacje powyższych trzech właściwości nie mogą być jednocześnie spełnione przez żaden mechanizm:

  • W przypadku agentów o użyteczności kardynalnej Zhou udowadnia, że ​​żaden mechanizm nie spełnia kryteriów wydajności ex ante , prawdziwości ex ante i równego traktowania równych (= agenci o identycznych funkcjach użyteczności powinni uzyskać taką samą użyteczność).
  • agentom o ściśle określonych użytecznościach porządkowych, że żaden mechanizm nie spełnia możliwej skuteczności , koniecznej prawdomówności i równego traktowania równych .
  • W przypadku agentów o słabej użyteczności porządkowej Katta i Sethuraman dowodzą, że żaden mechanizm nie spełnia możliwej wydajności , możliwej prawdomówności i niezbędnej wolności od zazdrości .

Dekompozycja ułamkowej alokacji

Zarówno zasady PS, jak i CEEI obliczają macierz oczekiwanych przypisań, tj. krańcowe prawdopodobieństwa, z jakimi każdy agent otrzymuje każdy obiekt. Ponieważ jednak ostateczna alokacja musi być dopasowaniem, należy znaleźć rozkład tej macierzy na loterię dopasowań.

W klasycznym układzie, w którym m = n , można to zrobić za pomocą algorytmu Birkhoffa . Może rozłożyć dowolną n -na- n prawdopodobieństw agenta-obiektu na wypukłą kombinację macierzy permutacji O( n2 ) , z których każda reprezentuje dopasowanie . Jednak rozkład nie jest wyjątkowy, a niektóre rozkłady mogą być lepsze niż inne.

Budish, Che, Kojima i Milgrom uogólniają algorytm Birkhoffa na dowolne m i n . Pozwalają również na dodawanie ograniczeń do przypisań, przy maksymalnym zbiorze warunków na zbiorze ograniczeń. Przedstawiają również metodę dekompozycji, która minimalizuje różnice w użyteczności doświadczanej przez agentów między różnymi dopasowaniami.

Demeulemeester, Goossens, Hermans i Leus przedstawiają algorytm dekompozycji w czasie wielomianowym, który maksymalizuje liczbę agentów otrzymujących obiekt w najgorszym przypadku. Ich algorytm gwarantuje, że liczba agentów w najgorszym przypadku równa się oczekiwanej liczbie agentów zaokrąglonej w dół, czyli najlepszej możliwej. Przedstawiają inny algorytm dekompozycji, który maksymalizuje liczbę przypisanych agentów w najgorszym przypadku, gwarantując jednocześnie, że wszystkie dopasowania w dekompozycji będą ex post PE; drugi algorytm może być użyty tylko do przypisań ułamkowych wyprowadzanych przez PS, ale nie do przypisań odpowiadających RP. W przypadku RP możliwe jest jedynie osiągnięcie 1/2-czynnikowego przybliżenia optymalnej najgorszej liczby przypisanych agentów. W przypadku ogólnych przydziałów ułamkowych maksymalizacja najgorszej liczby przydzielonych agentów podlegających PE ex post jest NP-trudna. Przedstawiają również generowania kolumn , które można wykorzystać do optymalizacji innych najgorszych kryteriów.

Porównanie empiryczne

Hosseini, Larson i Cohen porównują RP do PS w różnych ustawieniach. Pokazują, że:

  • Kiedy są co najwyżej 2 obiekty i co najwyżej 3 agentów, RP i PS zwracają ten sam przydział.
  • Kiedy są co najwyżej 2 obiekty, dla dowolnej liczby agentów, PS jest sd-prawdziwy, a RP jest wolny od zazdrości, aw większości przypadków PS dominuje RP, szczególnie przy 4 lub więcej agentach.
  • Gdy istnieją 3 lub więcej obiektów (i 3 lub więcej agentów), RP i PS mogą zwracać różne alokacje i żadna alokacja nie dominuje nad drugą. Załóżmy na przykład, że istnieją trzy obiekty a, b, c i trzej agenci z rankingami preferencji (1) a>c>b, (2) a>b>c, (3) b>a>c. Następnie agentowi (1) zarówno RP, jak i PS dają 1/2 a + 1/2 c; agentowi (2), RP daje 1/2 a + 1/6 b + 1/3 c, podczas gdy PS daje 1/2 a + 1/4 b + 1/4 c, co jest stochastycznie dominujące ; a agentowi (3), RP daje 5/6 b + 1/6 c, podczas gdy PS daje 3/4 b + 1/4 c, co jest zdominowane stochastycznie. Tak więc (1) jest obojętny, (2) ściśle preferuje PS i (3) ściśle preferuje RP.
  • Ułamek profili preferencji, dla których PS sd dominuje RP, jest duży, gdy liczba agentów i obiektów jest różna, ale zbliża się do 0, gdy liczby są równe. To samo dotyczy dominacji ld.
  • Gdy agenci są neutralni pod względem ryzyka , oczekiwany dobrobyt społeczny PS jest większy niż RP, ale różnica jest znacząca tylko wtedy, gdy n≠m . W przypadku RP frakcja zazdrosnych agentów jest bliska zeru, gdy n ≥ m. PS można manipulować, a zysk z manipulacji wzrasta, gdy m > n .
  • Kiedy agenci poszukują ryzyka , oczekiwany dobrobyt społeczny PS jest większy niż RP, a różnica szybko rośnie, gdy n≠m. Natomiast gdy n = m RP w większości przypadków osiąga wyższy dobrobyt społeczny. W przypadku RP frakcja zazdrosnych agentów jest bliska zeru, gdy n ≥ m, ale generuje zazdrość, gdy m>n. Zazdrość o RP maleje, gdy wzrasta skłonność do ryzyka. Zysk z manipulowania PS maleje, gdy agenci są bardziej skłonni do ryzyka.
  • Kiedy agenci mają awersję do ryzyka , różnica w dobrobycie społecznym między RP a PS zmniejsza się (choć nadal jest istotna statystycznie). Odsetek agentów zazdrosnych w RP wzrasta, ale zazdrość pozostaje poniżej 0,01, gdy n ≥ m . Manipulowalność PS spada do 1, gdy m / n .

Rozszerzenia

Tao i Cole badają istnienie losowych alokacji PE i EF, gdy użyteczności są nieliniowe (mogą mieć dopełnienia).

Yilmaz bada problem losowego przydziału, w którym agenci mają fundusze.

Zobacz też

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Fair_random_assignment&oldid=1131424049 ”