Alokacja przedmiotów w trybie okrężnym

Round robin to procedura sprawiedliwego przydzielania przedmiotów . Można jej użyć do rozdzielenia kilku niepodzielnych przedmiotów między kilka osób, tak że alokacja jest „prawie” wolna od zazdrości : każdy podmiot wierzy, że pakiet, który otrzymał, jest co najmniej tak dobry, jak pakiet dowolnego innego agenta, gdy co najwyżej jeden przedmiot zostanie usunięty z innego pakietu. W sporcie procedura okrężna nazywana jest draftem .

Ustawienie

Jest m obiektów do przydzielenia i n osób („agentów”) z równymi prawami do tych obiektów. Każda osoba ma inne preferencje co do obiektów. Preferencje agenta są określone przez wektor wartości - wartość dla każdego obiektu. Przyjmuje się, że wartość paczki dla agenta jest sumą wartości obiektów w wiązce (innymi słowy, wyceny agentów są addytywną funkcją zbioru na zbiorze obiektów).

Opis

Protokół przebiega w następujący sposób:

Ponumeruj ludzi dowolnie od 1 do ${\ displaystyle n}$ ;
Dopóki istnieją nieprzypisane obiekty:
- Niech każda osoba od 1 do ${\ displaystyle n}$ wybierze nieprzypisany obiekt.

Przyjmuje się, że każda osoba w swojej kolejce wybiera nieprzypisany obiekt o najwyższej wartości spośród pozostałych obiektów.

Wymóg addytywności

Protokół okrężny wymaga addytywności, ponieważ wymaga od każdego agenta wybrania swojego „najlepszego przedmiotu”, nie wiedząc, jakie inne przedmioty dostanie; addytywność wycen gwarantuje, że zawsze istnieje „najlepszy przedmiot” (przedmiot o najwyższej wartości). Innymi słowy, zakłada się, że przedmioty są dobrami niezależnymi . Wymóg addytywności można złagodzić do słabej addytywności .

Nieruchomości

Protokół okrężny jest bardzo prosty do wykonania: wymaga tylko m kroków. Każdy agent może $na$ z wyprzedzeniem, zmniejszając wartość ( zajmuje to agenta , wybrać obiekt w czasie ${\ Displaystyle O (1)}$ .

Ostateczna alokacja to EF1 - bez zazdrości do jednego obiektu. Oznacza $\$ każdej pary agentów $j$ $jeden$ obiekt zostanie usunięty z pakietu , to $}$ { zazdrość ${\ displaystyle j}$ .

Dowód: dla każdego agenta

ja

wybory dokonane przez agentów na podsekwencje: pierwsza podsekwencja zaczyna się od agenta 1 i kończy na agencie

\ displaystyle i-1}

; te ostatnie podsekwencje zaczynają się od

1

kończą na

{\ displaystyle i-1

} W ostatnich podsekwencjach agent

wybiera

, więc może wybrać swój najlepszy przedmiot, więc nie zazdrości żadnemu innemu agentowi. Agent

{\ displaystyle i}

może zazdrościć tylko jednemu z agentów

{\ Displaystyle 1, ..., i-1}

, a zazdrość pochodzi tylko z przedmiotu, który wybrali w pierwszej podsekwencji. Jeśli ten element zostanie usunięty, agent

.

zazdrości

Dodatkowo system okrężny gwarantuje, że każdy agent otrzyma taką samą liczbę przedmiotów ( m / n , jeśli m jest podzielne przez n ) lub prawie taką samą liczbę przedmiotów (jeśli m nie jest podzielne przez n ). Jest to zatem przydatne w sytuacjach z prostymi ograniczeniami kardynalności, takimi jak: przydzielanie studentom miejsc na kursach, w których każdy student musi otrzymać taką samą liczbę kursów.

Względy wydajności

Round-robin gwarantuje przybliżoną uczciwość, ale wynik może być nieefektywny. Jako prosty przykład załóżmy, że wyceny są następujące:

	z	y	X	w	w	u
Wartość Alicji:	12	10	8	7	4	1
Wartość George'a:	19	16	8	6	5	1

$)$ daje alokację z użytecznością (24,23 i opieką społeczną 47. Nie Pareto ponieważ jest zdominowany np. y alokacja z narzędziami ${\ Displaystyle (yxw, zvu)} .$

Alternatywnym algorytmem, który może osiągnąć wyższy dobrobyt społeczny, jest iterowany algorytm dopasowywania maksymalnej wagi . W każdej iteracji znajduje dopasowanie maksymalnej wagi na grafie dwudzielnym , w którym węzły są agentami i elementami, a wagi krawędzi są wartościami agentów dla elementów. W powyższym przykładzie pierwsze dopasowanie to ${\ Displaystyle (y, z)}$ , drugie to ${\ Displaystyle (w, x)}$ , a trzecie to ( w , x ) {\ Displaystyle (w, x)} ${\ Displaystyle (u, v)}$ . Całkowity przydział wynosi ${\ Displaystyle (ywu, zxv)}$ z narzędziami (18,32); dobrobyt społeczny (- suma użyteczności) wynosi 50, czyli jest wyższy niż w alokacji okrężnej.

Należy zauważyć, że nawet iterowane dopasowanie maksymalnej wagi nie gwarantuje wydajności Pareto, ponieważ powyższa alokacja jest zdominowana przez (xwv, zyu) z użytecznością (19,36).

Kolejka dla grup

Algorytm okrężny może być używany do sprawiedliwego przydzielania elementów między grupami . W tym ustawieniu wszyscy członkowie w każdej grupie korzystają z tego samego pakietu, ale różni członkowie w każdej grupie mogą mieć różne preferencje dotyczące przedmiotów. Rodzi to pytanie, w jaki sposób każda grupa powinna zdecydować, który element wybrać po kolei. Załóżmy, że celem każdej grupy jest maksymalizacja frakcji jej członków, którzy są „szczęśliwi”, to znaczy czują, że alokacja jest sprawiedliwa (zgodnie z ich osobistymi preferencjami). Załóżmy również, że agenci mają binarne wyceny addytywne, to znaczy, że każdy agent wycenia każdą pozycję na 1 („zaakceptuj”) lub 0 („odrzuć”). Następnie każda grupa może zdecydować, jakiego przedmiotu użyć ważone głosowanie zatwierdzające :

Każdemu członkowi grupy przypisywana jest waga. Ciężar członka j jest pewną funkcją w ( r _j , s _j ), gdzie:
- r _j to liczba pozostałych towarów, które j zatwierdza;
- s _j to liczba dóbr, które grupa j powinna jeszcze otrzymać, tak aby wybrane kryterium słuszności było spełnione dla j .
Każdemu pozostałemu elementowi przypisywana jest waga. Waga pozycji g jest sumą wag agentów, którzy zatwierdzają g : suma w ( r _j , s _j ) dla wszystkich j takich, że j ma wartość g przy 1.
Grupa wybiera przedmiot o największej wadze.

Wynikowy algorytm nazywa się RWAV (okrężny z ważonym głosowaniem zatwierdzającym). Funkcję wagi w ( r , s ) wyznacza się na podstawie funkcji pomocniczej B ( r , s ), określonej zależnością rekurencyjną:

${\ Displaystyle B (r, s): = 1 ~ ~ {\ tekst {jeśli}} ~ ~ s \ równoważnik 0;}$

${\ Displaystyle B (r, s): = 0 ~ ~ {\ tekst {jeśli}} ~ ~ 0 <s ~ {\ tekst {i}} ~ r <s;}$
${\ Displaystyle B (r, s): = \ min {\ bigg [}{\ Frac {1} {2}} [B (r-1, s) + B (r-1, s-1)], B(r-2,s-1){\bigg ]}~~{\text{inaczej}}}$ .

Intuicyjnie B( r , s ) agenta reprezentuje prawdopodobieństwo, że agent jest zadowolony z ostatecznej alokacji. Jeśli s ≤ 0, to z definicji prawdopodobieństwo to wynosi 1: agent nie potrzebuje więcej dóbr, aby być szczęśliwym. Jeśli 0< s i r < s , to prawdopodobieństwo wynosi 0: agent nie może być szczęśliwy, ponieważ potrzebuje więcej dóbr niż jest dostępnych. W przeciwnym razie B( r , s ) jest średnią między B( r -1, s ) - gdy druga grupa bierze dobro poszukiwane przez agenta, a B ( r -1, s-1 ) - gdy grupa agenta bierze towar poszukiwany przez agenta. Składnik B( r -2, s -1) reprezentuje sytuację, w której obie grupy biorą dobro poszukiwane przez agenta. Po obliczeniu B( r , s ) funkcja wagi w jest zdefiniowana w następujący sposób:

${\ Displaystyle w (r, s): = B (r, s) -B (r-1, s)}$

Używając tej funkcji wagi i uruchamiając RWAV z dwiema grupami, ułamek szczęśliwych członków w grupie 1 wynosi co najmniej B( r , s( r )), a ułamek szczęśliwych członków w grupie 2 wynosi co najmniej B ( r -1 , s( r )). Funkcja s ( r ) jest określona przez kryterium słuszności. Na przykład dla uczciwości 1-z-3 maximin-share, s ( r ) = podłoga ( r / 3). W poniższej tabeli przedstawiono niektóre wartości funkcji B , z wartościami B(r-1, floor(r/3)) pogrubionymi:


rs ↓ s →	0	1	2	3	4	5	6	7	8	9	10
-1		0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000
0	1	0,500	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000
1	1	0,750	0,375	0.000	0.000	0.000	0.000	0.000	0.000	0.000	0.000
2	1	0,875	0,625	0,313	0.000	0.000	0.000	0.000	0.000	0.000	0.000
3	1	0,938	0,781	0,547	0,273	0.000	0.000	0.000	0.000	0.000	0.000
4	1	0,969	0,875	0,711	0,492	0,246	0.000	0.000	0.000	0.000	0.000
5	1	0,984	0,930	0,820	0,656	0,451	0,226	0.000	0.000	0.000	0.000
6	1	0,992	0,961	0,891	0,773	0,612	0,419	0,209	0.000	0.000	0.000
7	1	0,996	0,979	0,935	0,854	0,733	0,576	0,393	0,196	0.000	0.000
8	1	0,998	0,988	0,961	0,908	0,820	0,698	0,546	0,371	0,185	0.000
9	1	0,999	0,994	0,978	0,943	0,882	0,790	0,668	0,519	0,352	0,176
10	1	1.000	0,997	0,987	0,965	0,923	0,857	0,762	0,641	0,497	0,336

Z tego można wywnioskować, że algorytm RWAV gwarantuje, że w obu grupach co najmniej 75% członków uważa, że przydział jest sprawiedliwy w 1 z 3 MMS-ów.

Rozszerzenia

1. Protokół okrężny gwarantuje EF1, gdy przedmioty są towarami (- wycenione pozytywnie przez wszystkich agentów) i kiedy są obowiązkami domowymi (- wycenione ujemnie przez wszystkich agentów). Jednak gdy występują zarówno towary, jak i obowiązki, nie gwarantuje to EF1. Adaptacja systemu okrężnego zwana podwójnym cyklem okrężnym gwarantuje EF1 nawet przy mieszance towarów i obowiązków.

2. Gdy agenci mają bardziej złożone ograniczenia liczności (tj. pozycje są podzielone na kategorie, a dla każdej kategorii pozycji istnieje górna granica liczby pozycji, które każdy agent otrzymuje z tej kategorii), okrężny może się nie powieść . Jednak połączenie działania okrężnego z procedurą wykresu zazdrości daje algorytm, który znajduje alokacje, które są zarówno EF1, jak i spełniają ograniczenia liczności.

Zobacz też

Round-robin to szczególny przypadek sekwencji kompletacji .

Protokoły okrężne są stosowane w innych obszarach oprócz sprawiedliwego przydziału pozycji. Na przykład zobacz planowanie w trybie okrężnym i turniej okrężny .